ZOJ Monthly, November 2014

zimpha posted @ Sun, 30 Nov 2014 17:14:33 +0800 in ZOJ , 1730 readers

ZOJ Monthly, November 2014
A	Alkanes	8.33% (3/36)
B	Permutation	0.00% (0/14)
C	Tilt Cylinder	4.58% (5/109)
D	Kill Mosquitos	0.00% (0/159)
E	Comet and Tracker	5.88% (1/17)
F	Nuclear Reactor	0.00% (0/0)
G	Circulation pipe	7.50% (3/40)
H	Miner	10.14% (7/69)
I	Infusion Altar	25.24% (127/503)
J	Poker Face	25.24% (131/519)

这周忙着给一些奇怪的比赛出题，然后又要赶作业。。。真的好忙，今天先把简要的题解写一下，让ZOJ那边的过题数变得好看些。

Problem A Alkanes

题目给出了一些简单烷烃的命名规则, 然后给你一些烷烃, 要求命名.

数据规模：主链长度小于15, 支链长度小于15, 可能的主链个数不超过15个

只要按照题目给的规则搞就好了，然后Input里面有句话：

You can assume all the test cases can be solved by the rules in the statement.

你可以理解为支链都是直的，然后就可以直接命名了。暴力搞出所有的命名，根据规则取个最优。

#include <bits/stdc++.h>
using namespace std;

string carbon(int n) {
    if (n == 1) return "meth";
    else if (n == 2) return "eth";
    else if (n == 3) return "prop";
    else if (n == 4) return "but";
    else if (n == 5) return "pent";
    else if (n == 6) return "hex";
    else if (n == 7) return "hept";
    else if (n == 8) return "oct";
    else if (n == 9) return "non";
    else if (n == 10) return "dec";
    else if (n == 11) return "undec";
    else if (n == 12) return "dodec";
    else if (n == 13) return "tridec";
    else if (n == 14) return "tetradec";
    else if (n == 15) return "pentadec";
    return "";
}

string prefix(int n) {
    if (n == 1) return "";
    else if (n == 2) return "di";
    else if (n == 3) return "tri";
    else if (n == 4) return "tetra";
    else if (n == 5) return "penta";
    else if (n == 6) return "hexa";
    else if (n == 7) return "hepta";
    else if (n == 8) return "octa";
    else if (n == 9) return "nona";
    else if (n == 10) return "deca";
    else if (n == 11) return "undeca";
    else if (n == 12) return "dodeca";
    else if (n == 13) return "trideca";
    else if (n == 14) return "tetradeca";
    else if (n == 15) return "pentadeca";
    return "";
}

//0: ane, 1 : yl
string suffix(int n) {
    if (n == 0) return "ane";
    else if (n == 1) return "yl";
    return "";
}

const int MAXN = 1000;

vector<int> G[MAXN];
vector<int> chain;
bool vis[MAXN];
int N, M, length, deg[MAXN];
int st, ed, now;

void dfs(int u, int f, int l) {
    if (l > length) {
        st = now, ed = u;
        length = l;
    }
    for (auto v : G[u]) {
        if (v == f) continue;
        dfs(v, u, l + 1);
    }
}

void getchain() {
    for (int i = 1; i <= N; ++ i) {
        deg[i] = G[i].size();
        vis[i] = false;
    }
    queue<int> Q;
    for (int i = 1; i <= N; ++ i) {
        if (deg[i] == 1 && i != st && i != ed) {
            Q.push(i); deg[i] = 0;
        }
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); vis[u] = true;
        for (auto v : G[u]) {
            if (deg[v] == 0) continue;
            -- deg[v];
            if (deg[v] == 1) deg[v] = 0, Q.push(v);
        }
    }
    chain.clear(); Q.push(st);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); chain.push_back(u); vis[u] = true;
        for (auto v : G[u]) {
            if (!vis[v]) Q.push(v);
        }
    }
    /*for (auto x : chain) {
        printf("%d ", x);
    }
    puts("");*/
}

int gao(int u) {
    vis[u] = 1;
    int ret = 1;
    for (auto v : G[u]) {
        if (vis[v]) continue;
        ret += gao(v);
    }
    return ret;
}

string number(int &sum) {
    int order[] = {4, 10, 12, 2, 7, 6, 1, 9, 8, 5, 15, 3, 14, 13, 11};
    vector<int> subchain[20];
    sum = 0; memset(vis, 0, sizeof(vis));
    for (int i = 0; i < 20; ++ i) subchain[i].clear();
    for (auto x : chain) vis[x] = 1;
    for (int i = 0; i < (int)chain.size(); ++ i) {
        int u = chain[i];
        for (auto v : G[u]) {
            if (vis[v]) continue;
            subchain[gao(v)].push_back(i + 1);
            sum += i + 1;
        }
    }
    string ret = "";
    bool first = true;
    for (int i = 0; i < 15; ++ i) {
        int n = order[i];
        if (subchain[n].size()) {
            sort(subchain[n].begin(), subchain[n].end());
            char buf[100]; buf[0] = '\0';
            for (int j = 0; j < (int)subchain[n].size(); ++ j) {
                int len = strlen(buf);
                if (j) sprintf(buf + len, ",%d", subchain[n][j]);
                else sprintf(buf + len, "%d", subchain[n][j]);
            }
            if (!first) ret += "-";
            else first = false;
            ret += (string)buf + "-" + prefix(subchain[n].size()) + carbon(n) + suffix(1);
        }
    }
    ret += carbon(chain.size()) + suffix(0);
    return ret;
}

int main() {
    while (scanf("%d%d", &N, &M) == 2) {
        for (int i = 1; i <= N; ++ i) G[i].clear();
        for (int i = 1; i <= M; ++ i) {
            int x, y; scanf("%d%d", &x, &y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        length = 0;
        for (now = 1; now <= N; ++ now) {
            dfs(now, 0, 1);
        }
        getchain();
        int sl, sr;
        string left = number(sl);
        reverse(chain.begin(), chain.end());
        string right = number(sr);
        if (sl < sr) printf("%s\n", left.c_str());
        else printf("%s\n", right.c_str());
    }
    return 0;
}

Problem B Permutation

给你两个数组\(\{A_1,A_2,\dots,A_N\}\)和\(\{B_1,B_2,\dots,B_N\}\)，问有多少个1到\(N\)排列\(\sigma\)满足：\(\forall i \in [1, N], A_{\sigma_i} = \sigma_{B_i}\)

数据规模：\(1 \le N \le 5 \times 10^4, 1 \le A_i, B_i \le N\)

如果你成功过掉了NEERC 2013 C Cactus Automorphisms，那么这题对于你来说应该很简单。首先我们可以将数组\(A, B\)变成两个图（\(i\)到\(A_i\)连一条有向边），问题转化成问这两个图是否同构，如果同构输出自同构映射方案数目。

这个图是由若干个有向环+外向树组成的，然后可以把问题转化成为三部分。

树的同构
一个有向环的同构
若干个有向环的同构

这三个部分分别拿出来都是很经典的问题，然后具体怎么做就不说了。算同构方案数目也很简单，自己对着程序yy吧，不懂可以在comment里问。

#include <bits/stdc++.h>
using namespace std;

struct Node;
typedef vector<Node> VI;
typedef long long LL;

const int MAXN = 50000 + 10;
const int MOD = 1e9 + 7;

struct Node {
	int idx, value;
	Node() {};
	Node(int i, int v) : idx(i), value(v) {}
	bool operator < (const Node &rhs) const {
		return value < rhs.value;
	}
    bool operator == (const Node &rhs) const {
        return value == rhs.value;
    }
    bool operator != (const Node &rhs) const {
        return value != rhs.value;
    }
};

struct VectorCmp {
	bool operator () (const VI &A, const VI &B) {
		if (A.size() == B.size()) return A < B;
		else return A.size() < B.size();
	}
};

map<VI, int, VectorCmp> TreeCache;
int A[MAXN], deg[MAXN], total, N;
int P[MAXN], fact[MAXN];

int getTreeID(const VI &Tree) {
	if (TreeCache.find(Tree) == TreeCache.end()) {
		TreeCache[Tree] = total ++;
	}
	return TreeCache[Tree];
}

void minexpr(VI &circle) {
    int n = circle.size(), i = 0, j = 1, k;
    while (1) {
        Node vi, vj;
        for (k = 0; k < n; ++ k) {
            vi = circle[(i + k) % n];
            vj = circle[(j + k) % n];
            if (vi != vj) break;
        }
        if (k == n) break;
        if (vj < vi) {
            i += k + 1;
            if (i == j) ++ i;
        }
        else {
            j += k + 1;
            if (i == j) ++ j;
        }
    }
    int idx = min(i, j);
    rotate(circle.begin(), circle.begin() + idx, circle.end());
}

VI text(MAXN * 2, Node());
int fail[MAXN * 2];

int match(const VI &pat) {
    int n = pat.size(), m = 2 * n - 1;
    for (int i = 0; i < n; ++ i) {
        text[i] = text[i + n] = pat[i];
    }
    fail[0] = -1;
    for (int i = 1, j; i < n; ++ i) {
        j = fail[i - 1];
        while (j >= 0 && pat[j + 1] != pat[i]) j = fail[j];
        fail[i] = (pat[j + 1] == pat[i]) ? ++ j : j;
    }
    int ret = 0;
    for (int i = 0, j = -1; i < m; ++ i) {
        while (j >= 0 && pat[j + 1] != text[i]) j = fail[j];
        if (pat[j + 1] == text[i]) ++ j;
        if (j + 1 == n) ++ ret, j = fail[j];
    }
    return ret;
}

struct OCTOPUS {
	bool inCircle[MAXN];
	int Hash[MAXN];
	vector<VI> circles;
	vector<int> G[MAXN];
	void build();
	void rebuild();
	void getCircle();
	void GraphHash();
	int TreeHash(int u);
	void getChain(int u, VI &V);
} GA, GB;

void OCTOPUS::build() {
	for (int i = 1; i <= N; ++ i) G[i].clear(), deg[i] = 0;
	for (int i = 1; i <= N; ++ i) G[i].push_back(A[i]), ++ deg[A[i]];
}

void OCTOPUS::rebuild() {
	for (int i = 1; i <= N; ++ i) G[i].clear();
	for (int i = 1; i <= N; ++ i) 
		if (!inCircle[i]) G[A[i]].push_back(i);
}

void OCTOPUS::getChain(int u, VI &V) {
	V.push_back(Node(u, 0)); -- deg[u];
	for (auto v : G[u]) {
		if (deg[v] == 0) continue;
		getChain(v, V);
	}
}

void OCTOPUS::getCircle() {
	queue<int> Q;
	for (int i = 1; i <= N; ++ i) {
		inCircle[i] = true;
		if (deg[i] == 0) Q.push(i);
	}
	while (!Q.empty()) {
		int u = Q.front(); Q.pop(); inCircle[u] = false;
		for (auto v : G[u]) {
			-- deg[v];
			if (deg[v] == 0) Q.push(v);
		}
	}
	circles.clear();
	for (int i = 1; i <= N; ++ i) {
		if (deg[i] != 0) {
			VI V; V.clear();
			getChain(i, V);
			circles.push_back(V);
		}
	}
}

int OCTOPUS::TreeHash(int u) {
	VI son; son.clear();
	for (auto v : G[u]) son.push_back(Node(v, TreeHash(v)));
	sort(son.begin(), son.end());
	return Hash[u] = getTreeID(son);
}

void OCTOPUS::GraphHash() {
	for (int i = 1; i <= N; ++ i) Hash[i] = -1;
	for (int i = 1; i <= N; ++ i) {
		if (inCircle[i]) Hash[i] = TreeHash(i);
	}
	for (int i = 1; i <= N; ++ i) assert(Hash[i] != -1);
	for (int i = 0; i < (int)circles.size(); ++ i) {
        for (int j = 0; j < (int)circles[i].size(); ++ j) {
            circles[i][j].value = Hash[circles[i][j].idx];
        }
        minexpr(circles[i]);
	}
    sort(circles.begin(), circles.end());
}

void init(OCTOPUS &G) {
	for (int i = 1; i <= N; ++ i) {
        scanf("%d", A + i);
        assert(1 <= A[i] && A[i] <= N);
    }
	G.build(); G.getCircle(); 
	G.rebuild(); G.GraphHash();
}

int dfs(int uA, int uB) {
	P[uB] = uA;
	VI sonA, sonB;
	sonA.clear(); sonB.clear();
	for (auto vA : GA.G[uA]) sonA.push_back(Node(vA, GA.Hash[vA]));
	for (auto vB : GB.G[uB]) sonB.push_back(Node(vB, GB.Hash[vB]));
    sort(sonA.begin(), sonA.end());
    sort(sonB.begin(), sonB.end());
	assert(sonA.size() == sonB.size());
    int ret = 1, n = sonA.size();
	for (int i = 0; i < n; ++ i) {
		ret = (LL)ret * dfs(sonA[i].idx, sonB[i].idx) % MOD;
        assert(ret >= 0);
	}
    for (int i = 0, j; i < n; i = j) {
        for (j = i; j < n && sonA[i] == sonA[j]; ++ j) {}
        ret = (LL)ret * fact[j - i] % MOD;
        assert(ret >= 0);
    }
    return ret;
}

int solve(OCTOPUS &GA, OCTOPUS &GB) {
    int ret = 1;
    vector<VI> &CA = GA.circles, &CB = GB.circles;
    if (CA != CB) return -1;
    for (int i = 0; i < (int)CA.size(); ++ i) {
        VI &ta = CA[i], &tb = CB[i];
        ret = (LL)ret * match(ta) % MOD;
        assert(ret >= 0);
        for (int j = 0; j < (int)ta.size(); ++ j) {
            ret = (LL)ret * dfs(ta[j].idx, tb[j].idx) % MOD;
            assert(ret >= 0);
        }
    }
    for (int i = 0, j; i < (int)CA.size(); i = j) {
        for (j = i; j < (int)CA.size() && CA[i] == CA[j]; ++ j) {}
        ret = (LL)ret * fact[j - i] % MOD;
        assert(ret >= 0);
    }
	return ret;
}

int main() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; ++ i) fact[i] = (LL)i * fact[i - 1] % MOD;
	while (scanf("%d", &N) == 1) {
        assert(1 <= N && N <= 50000);
		total = 0; TreeCache.clear();
		init(GA);
        init(GB);
        int ret = solve(GA, GB);
		if (ret != -1) {
            printf("FOUND %d\n", ret);
            assert(ret >= 0);
			for (int i = 1; i <= N; ++ i) {
				printf("%d%c", P[i], " \n"[i == N]);
			}
		}
		else puts("IMPOSSIBLE");
	}
	return 0;
}

Problem C Tilt Cylinder

给出一个倾斜的圆柱，告诉你水平面的高度，问里面有多少水？

数据规模：\(1 \le R, H, h \le 100, 1 \le \alpha \le 90\)，数据保证合法

翻开数学手册，里面就有公式，然后分类讨论下就好了。

貌似直接simpson也可以过。

还有直接推出积分式子的做法，我数学差，不会。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef double ldb;
const ldb eps = 1e-8;
const ldb PI = acos(-1.0);

int sgn(ldb x) {
	if (fabs(x) <= eps) return 0;
	else if (x > 0) return 1;
	else return -1;
}

ldb calc(ldb r, ldb l, ldb theta) {
    ldb h = l / sin(theta);
    ldb b = l / cos(theta);
    ldb d = sqrt(2.0 * r * b - b * b);
    ldb a = asin(d / r);
    if (b > r) a = PI - a;
    return h * r * r * r / b * (sin(a) - sin(a) * sin(a) * sin(a) / 3 - a * cos(a));
}

int main() {
	ldb R, H, h, a;
	while (scanf("%lf%lf%lf%lf", &R, &H, &h, &a) == 4) {
		ldb total = PI * R * R * H, ret = 0;
		a = a / 180.0 * PI;
		if (sgn(a - 90) == 0) {
			ret = PI * R * R * h;
			printf("%.10f\n", ret);
			continue;
		}
		if (sgn(a) == 0) {
            ldb alpha = acos(fabs(R - h) / R);
            if (h > R) alpha = PI - alpha;
			ldb area = 0.5 * R * R * (alpha * 2 - sin(alpha * 2));
			ret = area * H;
			printf("%.10f\n", ret);
			continue;
		}
		ldb h1 = 2.0 * R * cos(a);
		ldb h2 = H * sin(a);
        ldb h3 = (2.0 * R / tan(a) + H) * sin(a);
        if (sgn(h1 - h2) <= 0) { // h1 <= h2
		    if (sgn(h - h1) <= 0) {
                ret = calc(R, h, a);
		    }
		    else if (sgn(h - h2) <= 0) {
                ldb l1 = h / sin(a);
                ldb d = l1 * tan(a);
                ldb l2 = (d - 2 * R) / d * l1;
                ret = PI * R * R * 0.5 * (l1 + l2);
            }
            else {
                ret = total - calc(R, h3 - h, a);
            }
            printf("%.10f\n", ret);
        }
        else {
            if (sgn(h - h2) <= 0) {
                ret = calc(R, h, a);
            }
            else if (sgn(h - h1) <= 0) {
                ret = calc(R, h, a) - calc(R, h - h2, a);
            }
            else {
                ret = total - calc(R, h3 - h, a);
            }
            printf("%.10f\n", ret);
        }
	}
	return 0;
}

Problem D Kill Mosquitos

平面上有\(n\)只红蚊子和\(m\)只黑蚊子。然后你可以制作一个圆形的拍子，用这个拍子来打蚊子。问在只用一次拍子的情况下，如何才能在不打死一个红蚊子的条件下打死最多的黑蚊子。

数据规模：\(0 \le n, m \le 200, 0 \le |x_i|, |y_i| \le 1000\)

~~这道题目貌似卡精度，貌似要用分数类才可以过~~。请自觉无视左边的话。

我们可以枚举两个黑蚊子的位置\(A\)和\(B\)，假设这两个黑蚊子一定在拍子的边缘。然后我们只需要另一个量就可以确定这个拍子。注意到，圆心必定在\(AB\)的中垂线上，然后我们可以通过假设有一只红蚊子在拍子上，确定出圆心在中垂线上的可行位置。

确定出可行区间之后，我们就可以确定哪些黑蚊子可能被打到（考虑某个某个黑蚊子和AB所确定的圆的圆心在AB中垂线上的位置）。之后类似扫描线的方法就可以确定每个可行拍子所能最多打到的蚊子数目（由于黑蚊子最多有\(m\)个，那么可行的拍子总共最多有\(m\)个）。

#include<bits/stdc++.h>
using namespace std;
using namespace rel_ops;
typedef long long ll;
const ll one=0x7fffffffffffffffll;
struct pt{
	int x,y;
	void read(){scanf("%d%d",&x,&y);}
	bool operator==(const pt&r)const{return x==r.x && y==r.y;}
	bool operator<(const pt&r)const{return x<r.x || x==r.x && y<r.y;}
	const pt operator-(const pt&r)const {return {x-r.x,y-r.y};}
	int cross(const pt&r)const {return x*r.y-y*r.x;}
	int dot(const pt&r)const {return x*r.x+y*r.y;}
	int len2()const {return x*x+y*y;}
};
struct frac{
	ll n,d;
	bool operator==(const frac& r)const{return cmp(n,d,r.n,r.d)==0;}
	bool operator<(const frac&r)const{return cmp(n,d,r.n,r.d)==-1;}
	bool operator<=(const frac&r)const{return cmp(n,d,r.n,r.d)<=0;}
	static int cmp(ll n1,ll d1,ll n2,ll d2){
		if(!(n1 && n2))return n1==n2?0:n1<n2?-1:1;
		if(n1>0 ^ n2 >0)return n1<0?-1:1;
		if(n1<0) return rc(d1,-n1,d2,-n2);
		return rc(d2,n2,d1,n1);
	}
	static int rc(ll n1,ll d1,ll n2,ll d2){
		ll k1=n1/d1,k2=n2/d2;
		if(k1!=k2)return k1<k2?-1:1;
		ll r1=n1%d1,r2=n2%d2;
		if(r1&&r2) return rc(d2,r2,d1,r1);
		if(r1 && !r2)return 1;
		if(r2 && !r1)return -1;
		return 0;
	}
};

int main(){
	for(int n,m;scanf("%d%d",&n,&m)==2;) {
		vector<pt> red(n),black(m);
		set<pt> pos;
		for(int i=0;i<n;++i)red[i].read();
		for(int i=0;i<m;++i){
			black[i].read();
			pos.insert(black[i]);
		}
		for(pt p:red)pos.erase(p);
		int ans=0;
		for(pt p:pos)ans=max(ans,(int)count(black.begin(),black.end(),p));
		for(pt a:pos)for(pt b:pos)if(a<b){
			int tmp=0;
			bool ok=true;
			frac L{-1,1},R{1,1}; // (L, R) without a red 
			for(pt c:red){
				pt u=a-c,v=b-c;
				int cross=u.cross(v),dot=u.dot(v);
				if(cross==0){
					if(dot>0)continue;
					ok=false;break;
				}
				frac now{(ll)dot*abs(dot), (ll)u.len2()*v.len2()};
				if(cross>0)R=min(R,now);
				else{now.n*=-1;L=max(L,now);}
			}
			if(!ok || R<=L )continue;
			vector<frac> ge,le;
			for(pt c:black){
				pt u=a-c,v=b-c;
				int cross=u.cross(v),dot=u.dot(v);
				if(cross==0){
					if(dot<=0)++tmp;
					continue;
				}
				frac now{(ll)dot*abs(dot), (ll)u.len2()*v.len2()};
				if(cross>0) {
					if(now>=R)continue;
					ge.push_back(now);
				}else{
					now.n*=-1;
					if(now<=L)continue;
					le.push_back(now);
				}
			}
			if(ans>= tmp+ge.size()+le.size())continue;
			sort(ge.begin(),ge.end());
			sort(le.begin(),le.end());
			tmp+=le.size();
			ans=max(ans,tmp);
			for(int i=0,j=0;i<ge.size();++i){
				for(;j<le.size() && le[j]<ge[i];++j);
				ans=max(ans,tmp-j+i+1);
			}
		}
		printf("%d\n",ans);
	}
}

Problem E Comet and Tracker

给出两组点的轨迹，问\(t\)秒之后点的位置。

就是一个解常微分方程的题目，首先我们需要列出微分方程。

然后分类讨论，运用大学课本里面的知识，花点时间解个方程就好了。

#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-8, PI = M_PI;

int sgn(double x) {
    if (fabs(x) < eps) return 0;
    else if (x > 0) return 1;
    else return -1;
}

double f1(double K, double a, double b, double t) {
    return a + (b - a) * exp(-K * t);
}

double f2(double K, double a, double b, double c, double t) {
    return a * t + b - a / K + (c + a / K - b) * exp(-K * t);
}

double fix(double x) {
    x = fmod(x, PI * 2);
    if (x > PI) x -= PI * 2;
    if (x < -PI) x += PI;
    return x;
}

int main() {
    double A, B, K, x10, y10, x20, y20, t;
    while (scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &A, &B, &K, &x10, &y10, &x20, &y20, &t) == 8) {
        if (sgn(A) == 0 && sgn(B) == 0) {
            printf("%.10f %.10f %.10f %.10f\n", x10, y10, f1(K, x10, x20, t), f1(K, y10, y20, t));
        }
        else if (sgn(A) == 0) {
            printf("%.10f %.10f %.10f %.10f\n", x10, y10 + B * x10 * t, f1(K, x10, x20, t), f2(K, B * x10, y10, y20, t));
        }
        else if (sgn(B) == 0) {
            printf("%.10f %.10f %.10f %.10f\n", x10 - A * y10 * t, y10, f2(K, -A * y10, x10, x20, t), f1(K, y10, y20, t));
        }
        else {
            double w = sqrt(A * B), coswt = cos(fix(w * t)), sinwt = sin(fix(w * t));
            double d = K * K + A * B;
            auto f3 = [&](double a, double b, double c) {
                double tmp = K * a - w * b;
                return (tmp * coswt + (w * a + K * b) * sinwt) / d + (c - tmp / d) * exp(-K * t);
            };
            printf("%.10f %.10f %.10f %.10f\n", x10 * coswt - A * y10 / w * sinwt,
                y10 * coswt + B *x10 / w * sinwt,
                f3(x10 * K, -A * y10 / w * K, x20),
                f3(y10 * K, B * x10 / w * K, y20));
        }
    }
    return 0;
}

Problem F Nuclear Reactor

有一个MC里面的核电反应仓，现在给出其摆放方案，求铀棒反应的tick数。规则貌似与MC里面略有不同，然后请仔细研究题意。

对于每个tick，按顺序执行以下步骤：

铀棒反应（自己+四个相邻格子铀棒数*热量）

对于每个铀棒的热量，按最近距离的倒数为权重全部分配给散热器和均热器（如果没有，那么反应仓爆炸）

均热器在瞬间将其以及与其相邻的均热器和冷却器热量平均（整个联通块平均）冷却器散热（需要统计其四周升级元件数量）

（在每个步骤，如果元件热量超过Q，这个元件及其上面热量会消失）

数据规模：\(1 \le N, M \le 20, 1 \le T \le 100000\)

这题我显然不会做，这里就写个当初出题人的题解吧，看不懂不要来找我。顺带一提，这道题目的样例貌似有问题，答案应该是3444.

对于每个tick依次模拟, 通过对每个U棒, 计算其发热量, BFS将其与可以到达的各个均热器和散热器距离求出, 把热量分配过去（在这之后判下是否超过\(Q\)）. 复杂度\(O(N^2M^2)\).

对于每个还没在连通块的均热器, 求出其联通块, 然后将热量平均（因为最多的也不超过\(Q\), 这里不会爆）. 复杂度\(O(NM)\).

上面复杂度\(O(N^2M^2T\), 明显TLE. 其实如果没有元件消失的话, 每个tick每个元件从铀棒吸收到的热量是不会变的, 只要预先求出即可. 因为最多\(NM\)个元件, 最多只需要计算\(NM\)次, 预处理一下. 然后在有元件消失的时候再更新即可. 复杂度\(O(NMT + N^3M^3)\).

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 21, SIZE = MAXN * MAXN;
typedef pair<int, int> PII;
vector<PII> li;
PII qu[SIZE];
char d[MAXN][MAXN];
double h[MAXN][MAXN], su[MAXN][MAXN], sum;
int sv[MAXN][MAXN], dis[MAXN][MAXN];
int n, m, T, Q, qul;
bool flag;

void expand(int x, int y, int d, int &r) {
    if (dis[x][y] <= d) return;
    dis[x][y] = d; qu[++ r] = PII(x, y);
}

void bfs(int x, int y) {
    dis[x][y] = 0; qu[0] = PII(x, y);
    int l = 0, r = 0;
    for (; l <= r; ++ l) {
        int x = qu[l].first;
        int y = qu[l].second;
        if (d[x][y] == 'C' || d[x][y] == 'I') {
            li.push_back(qu[l]);
            continue;
        }
        int dd = dis[x][y] + 1;
        if (x) expand(x - 1, y, dd, r);
        if (y) expand(x, y - 1, dd, r);
        if (x < n) expand(x + 1, y, dd, r);
        if (y < m) expand(x, y + 1, dd, r);
    }
    qul = r;
}

void dfs(int x, int y, bool p) {
    if (dis[x][y] == 0) return;
    dis[x][y] = 0;
    sum += h[x][y]; li.push_back(PII(x, y));
    if (p) {
        if (x && d[x - 1][y] == 'C') dfs(x - 1, y, 0);
        if (y && d[x][y - 1] == 'C') dfs(x, y - 1, 0);
        if (x < n && d[x + 1][y] == 'C') dfs(x + 1, y, 0);
        if (y < m && d[x][y + 1] == 'C') dfs(x, y + 1, 0);
    }
    if (x && d[x - 1][y] == 'I') dfs(x - 1, y, 1);
    if (y && d[x][y - 1] == 'I') dfs(x, y - 1, 1);
    if (x < n && d[x + 1][y] == 'I') dfs(x + 1, y, 1);
    if (y < m && d[x][y + 1] == 'I') dfs(x, y + 1, 1);
}

bool gao() {
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < m; ++ j) {
            su[i][j] = sv[i][j] = 0;
            dis[i][j] = 1e9;
        }
    }
    for (int i = 0; i < n; ++ i) {
        for(int j = 0; j < m; ++ j) {
            if (d[i][j] == 'U') {
                li.clear();
                bfs(i,j); sum = 0;
                for (auto &x : li) sum += 1.0/(dis[x.first][x.second]);
                if (li.empty()) return false;
                int cnt = 1;
                cnt += (i && d[i - 1][j] == 'U') + (i < n && d[i + 1][j] == 'U');
                cnt += (j && d[i][j - 1] == 'U') + (j < m && d[i][j + 1] == 'U');
                sum = cnt * 24.0 / sum;
                for (auto &x : li) {
                    su[x.first][x.second] += sum / dis[x.first][x.second];
                }
                for (int k = 0; k <= qul; ++ k) dis[qu[k].first][qu[k].second] = 1e9;
            }
            else if (d[i][j] == 'C') {
                sv[i][j] = 8;
                sv[i][j] += 2 * ((i && d[i - 1][j] == 'X') + (i < n && d[i + 1][j] == 'X'));
                sv[i][j] += 2 * ((j && d[i][j - 1] == 'X') + (j < m && d[i][j + 1] == 'X'));
            }
        }
    }
    return true;                        
}

int main() {
    while (scanf("%d%d%d%d", &n, &m, &T, &Q) == 4) {
        flag = true;
        for (int i = 0; i < n; ++ i) {
            scanf("%s", d[i]);
            for (int j = 0; j < m; ++ j) {
                if (d[i][j] == 'U') flag = false;
            }
        }
        int ret = 0;
        if (flag) T = 0;
        memset(h, 0, sizeof(h));
        for (; ret < T; ++ ret) {
            if (!flag) flag = gao();
            if (!flag) break;
            for (int i = 0; i < n; ++ i) for (int j = 0; j < m; ++ j) {
                h[i][j] += su[i][j];
                if (h[i][j] > Q) {
                    d[i][j] = '.';
                    flag = false;
                    su[i][j] = h[i][j] = 0;
                }
                dis[i][j] = 1;
            }
            for (int i = 0; i < n; ++ i) for (int j = 0; j < m; ++ j) {
                if ((d[i][j] == 'C' || d[i][j] == 'I') && dis[i][j]) {
                    li.clear(); sum = 0;
                    if (d[i][j] == 'C') dfs(i, j, 0);
                    else if (d[i][j] == 'I') dfs(i, j, 1);
                    sum /= li.size();
                    for (auto &x : li) h[x.first][x.second] = sum;
                }
            }
            for (int i = 0; i < n; ++ i) {
                for (int j = 0;j < m; ++ j) {
                    h[i][j] -= sv[i][j];
                    if (h[i][j] < 0) h[i][j] = 0;
                }
            }
        }
        printf("%d\n", min(ret + 1, T));
    }
    return 0;
}

Problem G Circulation pipe

有一根长度为L的管道，由\(L\)个单位管道构成。每隔\(K\) tick，会有一个物品被输入到第0个单位管道，物品在管道内会以每tick一个单位长度的速度被传输。当物品被传输到管道末端的时候，方向会反转。当某tick，某单位管道内物品数超过\(C\)的时候，管道会爆炸。问管道在哪个tick会爆炸。

数据规模：\(1 \le L, K, C \le 10^4\)

又是一道MC的题目。。。。

很容易想到，管道爆炸的时候，这个管道里必定有第一个被传入的物品。因为之后的所有物品都在重复第一个行为。

记\(Len = 2(L-1), D = \gcd(L, K), G = \frac{Len}{D}\). 我们可以将物品分成\(G\)个等价的类，同一个类里的物品在每一个时刻的位置和运动方向都是相同的。而且每个类的物品数只会相差1。相邻类之间的相对距离为\(D\)。

所以当每个类的物品数量等于\(\frac{C}{2}\)的时候，管道会处于一个临界状态。记第一个物品所在类为\(G_1\)，第二个为\(G_2\)，依次类推。若\(C\)为偶数，当\(G_1\)回到pipe 0时，恰好又传进了一个物品，此时\(G_1\text{物品数}=\frac{C}{2}+1\)，所以一旦\(G_1\)跟某个回来的类叠起来的时候，管道就会爆掉。

\(D\)为类间相对距离. 若\(D\)为偶数，\(G_1\)会跟最先碰到的往回走的类\(G_1^\prime\)相遇。若D为奇数，\(G_1\)会跟第二碰到的往回走的类\(G_2^\prime\)相遇，会和\(G_1^\prime\)擦肩而过……

记临界状态下第一个被传入物品的类为\(K_1\)，第二个为\(K_2\)…… 若\(C\)为奇数，当\(K_1\)变成\(\frac{C}{2}+1\)个物品后一直往前走直到折返时，在其碰到正在前进的\(K_2\)或\(K_3\)的瞬间，某管道内物品就会超过\(C\), 然后就会爆炸。若\(K\)为偶数，则\(K_1\)会和\(K_2\)相遇。若\(K\)为奇数，则\(K_1\)会和\(K_3\)相遇。

还有一些特殊情况：\(L=1\)，\(G=1 \text{ or } 2\)。特判一下即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL solve(LL N, LL K, LL C){
    LL L = N + N - 2;
    LL G = L / __gcd(L, K);
    if (!L) return C * K;
    if (G == 1 || G == 2 && (__gcd(L, K) & 1)) return C * G * K;
    LL T_base = (C & 1) ? (C-1) / 2 * G * K : C / 2 * G * K;
    LL T_run, Dis;

    if (C & 1) {
        if (K & 1) T_base += K * 2, Dis = K * 2 % L;
        else T_base += K, Dis = K % L;
        if (Dis == 0) T_run = 0;
        else if (Dis < N) T_run = N - 1 - Dis + Dis / 2;
        else T_run = (N + N - 2 - Dis) / 2;
    }
    else {
        Dis = __gcd(L, K);
        if (Dis & 1) Dis = Dis * 2;
        T_run = Dis / 2;
    }
    return T_base + T_run;
}

int main() {
    LL N, K, C;
    while (cin >> N >> K >> C) {
        cout << solve(N, K, C) << endl;        
    }
    return 0;
}

Problem H Miner

有个二维网格图，大小为\(n \times n\)，给出这个正方形内的初始情况，包括每个格子里面是石头还是矿物，石头会有一个挖掉需要的代价。求挖到所有矿物的最少所需要代价。

数据规模：\(1 \le n \le 9, n \text{ is odd}\)

把矿物和人都当做一个特殊点，这道题目就变成了斯坦纳树，直接套模板就好了。

#include<bits/stdc++.h>
using namespace std;

const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
char aa[10][10];
bool ore[100];
int pp[100],w[100],n;
int f[8192][100];
vector<int> e[100];

int id(int x,int y){return x*n+y;}

int ff(int x){
	return x==pp[x]?x:pp[x]=ff(pp[x]);
}

void cmin(int&x,int y){if(x>y)x=y;}
int ore_id[100];

int d[81][81];
int main(){
	int T;
	for(scanf("%d",&T);T--;){
		scanf("%d",&n);
		for(int i=0;i<n;++i)scanf(" %s",aa[i]);
		aa[n>>1][n>>1]='@';
		for(int i=0;i<n*n;++i){
			pp[i]=i;
			e[i].clear();
		}
		fill(ore,ore+n*n,false);
		for(int i=0;i<n;++i)
		for(int j=0;j<n;++j)
			if(aa[i][j]!='X'){
				int uid = id(i,j);
				if(aa[i][j]=='@'){
					ore[uid]=1;
					w[uid]=0;
				}
				if(isdigit(aa[i][j]))
					w[uid]=aa[i][j]-'0';
				for(int k=0;k<4;++k){
					int x=i+dx[k],y=j+dy[k];
					if(x<0 || y<0 || x>=n || y>=n ||
						aa[x][y]=='X')continue;
					e[uid].push_back(id(x,y));
				}
			}else {
				w[id(i,j)]=99999;
			}
		for(int u=0;u<n*n;++u)
			for(int v:e[u])
			if(w[u]==0 && w[v]==0)
				pp[ff(u)]=ff(v);
		for(int u=0;u<n*n;++u)
		if(ore[u])ore[ff(u)]=1;
		set<int> s[81];
		for(int u=0;u<n*n;++u)
			for(int v:e[u])
				s[ff(u)].insert(ff(v));
		int cnt=0,n2=n*n;
		for(int u=0;u<n*n;++u)
		if(ff(u)==u && ore[u])
			ore_id[u]=cnt++;
#define fa(i) for(int i=0;i<n2;++i)if(ff(i)==i)
		fa(i)fill(d[i],d[i]+n2,99999);
		fa(i)d[i][i]=w[i];
		fa(u)for(int v:s[u])d[u][v]=w[u]+w[v];
		fa(k)fa(i)fa(j)
			d[i][j]=min(d[i][j],d[i][k]+d[k][j]-w[k]);
		int h=1<<cnt;
		for(int z=0;z<h;++z)
			fill(f[z],f[z]+n2,99999);
		fa(i)if(ore[i])fa(j)
			f[1<<ore_id[i]][j]=d[i][j];
		for(int z=1;z<h;++z){
			if(__builtin_popcount(z)==1)continue;
			fa(k)for(int y=(z-1)&z;y;y=y-1&z)
				cmin(f[z][k],f[y][k]+f[z^y][k]-w[k]);
			fa(i)fa(j)
				cmin(f[z][i],f[z][j]+d[j][i]-w[j]);
		}
		int ans=*min_element(f[h-1],f[h-1]+n2);
		if(ans>10000)ans=-1;
		printf("%d\n",ans);
	}
}

Problem I Infusion Altar

给出一个\(n \times n\)的区域，正中间是注魔台。要求求把这个区域变成有4条对称轴的时候，最少需要做多少次方块的变换。正方形总共就4条对称轴，竖直，水平，2个斜对角。

数据规模：\(1 \le n \le 99, n \text{ is odd}\)

暴力搞搞就好了。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100 + 10;
char G[MAXN][MAXN];
int N;

int gao1(int x, int y) {
    vector<char> v; 
    v.push_back(G[x][y]);
    v.push_back(G[y][x]);
    v.push_back(G[x][N - y - 1]);
    v.push_back(G[y][N - x - 1]);
    
    v.push_back(G[N - y - 1][x]);
    v.push_back(G[N - x - 1][y]);
    v.push_back(G[N - y - 1][N - x - 1]);
    v.push_back(G[N - x - 1][N - y - 1]);
    
    int mx = 0;
    for (int i = 0; i < 8; ++ i) {
        int cnt = 0;
        for (int j = 0; j < 8; ++ j) {
            if (v[i] == v[j]) cnt ++;
        }
        mx = max(mx, cnt);
    }
    return 8 - mx;
}

int gao2(int x, int y) {
    vector<char> v; 
    v.push_back(G[x][y]);
    v.push_back(G[y][x]);
    v.push_back(G[N - x - 1][y]);
    v.push_back(G[y][N - x - 1]);

    int mx = 0;
    for (int i = 0; i < 4; ++ i) {
        int cnt = 0;
        for (int j = 0; j < 4; ++ j) {
            if (v[i] == v[j]) cnt ++;
        }
        mx = max(mx, cnt);
    }
    return 4 - mx;
}

int gao3(int x, int y) {
    vector<char> v; 
    v.push_back(G[x][y]);
    v.push_back(G[N - x - 1][y]);
    v.push_back(G[x][N - y - 1]);
    v.push_back(G[N - x - 1][N - y - 1]);

    int mx = 0;
    for (int i = 0; i < 4; ++ i) {
        int cnt = 0;
        for (int j = 0; j < 4; ++ j) {
            if (v[i] == v[j]) cnt ++;
        }
        mx = max(mx, cnt);
    }
    return 4 - mx;
}

int main() {
    int T; scanf("%d", &T);
    while (T --) {
        scanf("%d", &N);
        for (int i = 0; i < N; ++ i) scanf("%s", G[i]);
        int ret = 0;
        for (int i = 0; i < N / 2; ++ i) {
            for (int j = i + 1; j < N / 2; ++ j) {
                //printf("%d %d %d\n", i, j, gao1(i, j));
                ret += gao1(i, j);
            }
            //printf("%d %d %d\n", i, N / 2, gao2(i, N / 2));
            ret += gao2(i, N / 2);
            ret += gao3(i, i);
        }
        printf("%d\n", ret);
    }
    return 0;
}

Problem J Poker Face

给出几个样例，要你找规律。然后根据找到的规律做题。

规律很简单就找到了。。。不说了。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2000;

char face[MAXN][MAXN];
int N;

void turn(int len) {
    char tmp[MAXN];
    for (int i = 0; i < len / 2; ++ i) {
        for (int j = 0; j < len; ++ j) tmp[j] = face[i][j];
        for (int j = 0; j < len; ++ j) face[i][j] = face[len - i - 1][j];
        for (int j = 0; j < len; ++ j) face[len - i - 1][j] = tmp[j];
        /*strcpy(tmp, face[i]);
        strcpy(face[i], face[len - i - 1]);
        strcpy(face[len - i - 1], tmp);
        */
    }
}

void move(int len) {
    char tmp[MAXN];
    for (int i = 0; i < len; ++ i) {
        for (int j = 0; j < len; ++ j) tmp[j] = face[i][j];
        for (int j = 0; j < len * 2; ++ j) face[i][j] = ' ';
        for (int j = 0; j < len; ++ j) face[i][j + len / 2] = tmp[j];
    }
}

void draw(int len) {
    for (int i = 0; i < len; ++ i) {
        for (int j = 0; j < len * 2; ++ j) face[i + len][j] = ' ';
        face[i][0] = '*';
        face[i][len * 2 - 1] = '*';
        face[i + len][0] = '*';
        face[i + len][len * 2 - 1] = '*';
    }
    for (int i = 0; i < len * 2; ++ i) face[0][i] = '*';
    for (int i = 0; i < len * 2; ++ i) face[len * 2 - 1][i] = '*';
    // 
    for (int j = 0; j < len / 2; ++ j) {
        face[len + len / 4 - 1][j + len / 4] = '*';
        face[len + len / 4 + len / 2 - 1][j + len / 4] = '*';
        face[len + len / 4 - 1][j + len / 4 + len] = '*';
        face[len + len / 4 + len / 2 - 1][j + len / 4 + len] = '*';
    }
    for (int i = 0; i < len / 2; ++ i) {
        face[i + len / 4 + len][len / 4] = '*';
        face[i + len / 4 + len][len / 4 + len / 2 - 1] = '*';
        face[i + len / 4 + len][len / 4 + len] = '*';
        face[i + len / 4 + len][len / 4 + len + len / 2 - 1] = '*';
    }
}

int main() {
    while (scanf("%d", &N) == 1 && N >= 8) {
        strcpy(face[7], "********");
        strcpy(face[6], "***  ***");
        strcpy(face[5], "***  ***");
        strcpy(face[4], "***  ***");
        strcpy(face[3], "* **** *");
        strcpy(face[2], "* *  * *");
        strcpy(face[1], "* *  * *");
        strcpy(face[0], "********");
        for (int i = 8; i < N; i *= 2) {
            turn(i);
            move(i);
            draw(i);
        }
        for (int i = N - 1; i >= 0; -- i) {
            for (int j = 0; j < N; ++ j) {
                putchar(face[i][j]);
            }
            puts("");
        }
        puts("");
    }
    return 0;
}

月赛题就这样，完坑了，下周准备把ONTAK 2014搞定。