2017 ACM/ICPC Asia Regional Shenyang Online

happy happy happy

预处理+暴力。

Aki

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 105, B = 44;
int a[N];
LL ans; bool found = 0;
vector<LL> pre[N][N];
void dfs(int l, int r, LL res = 0) {
	if (r - l + 1 <= B) {
		auto it = upper_bound(pre[l][r].begin(), pre[l][r].end(), -res);
		if (it != pre[l][r].end()) {
			res += *it;
			if (!found || ans > res) {
				found = 1;
				ans = res;
			}
		}
		return;
	}
	LL c = max(a[l], a[r]);
	if (a[l] == max(a[l], a[r])) l ++; else r --;
	dfs(l + 1, r, res + c - a[l]);
	dfs(l, r - 1, res + c - a[r]);
}
bool debug = 0;
int main() {
	int n;
	while (scanf("%d", &n) == 1) {
		if (debug) n = 90;
		for (int i = 1; i <= n; ++ i) if (debug) a[i] = rand() % (int) 1e9 + 1; else scanf("%d", &a[i]);
		for (int i = 1; i <= n; ++ i) {
			pre[i][i - 1].clear();
			pre[i][i - 1].push_back(0);
		}
		for (int len = 2; len <= min(B, n); ++ len) {
			for (int i = 1; i + len - 1 <= n; ++ i) {
				int l = i, r = i + len - 1;
				LL c = max(a[l], a[r]);
				if (a[l] == c) l ++; else r --;
				auto L = pre[l + 1][r];
				auto R = pre[l][r - 1];
				for (LL &x : L) x += c - a[l];
				for (LL &x : R) x += c - a[r];
				auto &M = pre[i][i + len - 1];
				M.resize(L.size() + R.size());
				merge(L.begin(), L.end(), R.begin(), R.end(), M.begin());
				M.erase(unique(M.begin(), M.end()), M.end());
			}
			for (int i = 1; i + len - 2 - 1 <= n; ++ i) {
				vector<LL> emp;
				pre[i][i + len - 2 - 1].swap(emp);
			}
		}
		//puts("-------");
		found = 0;
		dfs(1, n, 0);
		if (found)
		printf("%lld\n", ans);
		else puts("The child will be unhappy...");
		if (debug) break;
	}
}

mustedge mustedge mustedge

Aki

并查集+树链剖分。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int f[N];
int fat(int x) {
	if (f[x] == x) return x;
	return f[x] = fat(f[x]);
}
vector<int> G[N];
#define fors(i) for (auto i : G[x]) if (i != p)
typedef int ai [N];
int cnt; ai s, h, top, pa, dfn, tree;
int size(int x, int p) {
	s[x] = 1;
	fors (i) s[x] += size(i, x);
	return s[x];
}
void add(int x, int c) {
	while (x <= cnt) {
		tree[x] += c;
		x += x & -x;
	}
}
int query(int x) {
	int res = 0;
	while (x) {
		res += tree[x];
		x -= x & -x;
	}
	return res;
}
void dfs(int x, int p, int t) {
	pa[x] = p, top[x] = t, h[x] = h[p] + 1, dfn[x] = ++ cnt;
	tree[cnt] = 0;
	int y = 0;
	fors (i) if (s[y] < s[i]) y = i;
	if (y) dfs(y, x, t);
	fors (i) if (i != y) dfs(i, x, i);
}
void build() {
	size(1, 0);
	cnt = 0;
	dfs(1, 0, 1);
}
int path(int x, int y, int &w) {
	int res = 0;
	while (top[x] != top[y]) {
		if (h[top[x]] >= h[top[y]]) {
			res += query(dfn[x]) - query(dfn[top[x]] - 1);
			x = pa[top[x]];
		}
		else swap(x, y);
	}
	if (dfn[x] < dfn[y]) {
		res += query(dfn[y]) - query(dfn[x]);
		w = x;
	}
	else {
		res += query(dfn[x]) - query(dfn[y]);
		w = y;
	}
	return res;
}
void addedge(int u, int v) {
	while (fat(u) != fat(v)) {
		u = fat(u), v = fat(v);
		if (h[u] >= h[v]) {
			add(dfn[u], 1);
			f[u] = pa[u];
		}
		else swap(u, v);
	}
}
int getint() {
	char c;
	while ((c = getchar()) < '0' || c > '9');
	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9') {
		res = res * 10 + c - '0';
	}
	return res;
}
int main() {
	int T = getint(), zzz = 0;
	while (T --) {
		int n = getint(), m = getint();
		for (int i = 1; i <= n; ++ i) {
			f[i] = i;
			G[i].clear();
		}
		vector<pair<int, int>> nt;
		for (int i = 0; i < m; ++ i) {
			int u, v;
			u = getint(), v = getint();
			if (fat(u) != fat(v)) {
				G[u].push_back(v);
				G[v].push_back(u);
				f[fat(u)] = fat(v);
			}
			else {
				nt.push_back({u, v});
			}
		}
		build();
		for (int i = 1; i <= n; ++ i) f[i] = i;
		for (auto e : nt) {
			addedge(e.first, e.second);
		}
		int q;
		q = getint();
		printf("Case #%d:\n", ++ zzz);
		while (q --) {
			int type = getint(), u = getint(), v = getint();
			if (type == 1) {
				addedge(u, v);
			}
			else {
				int w;
				int res = path(u, v, w);
				printf("%d\n", h[u] + h[v] - 2 * h[w] - res);
			}
		}
	}
}

cube cube cube

异形魔方。没看视屏转动结构完全搞错了。

Aki

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> permutation;
vector<vector<permutation>> all = {
	{{19, 54, 68}, {28, 30, 31, 35, 36, 14, 15, 11, 12, 10, 45, 44, 43, 42,41}, {5, 1, 9}, {2, 4, 7}, {3, 8, 6}},
	{{28, 63, 41}, {1, 3, 4, 8, 9, 23, 24, 20, 21, 19, 54, 53, 52, 51, 50}, {14, 10, 18}, {11, 13, 16}, {12, 17, 15}},
	{{1, 72, 50}, {10, 12, 13, 17, 18, 32, 33, 29, 30, 28, 63, 62, 61, 60, 59}, {23, 19, 27}, {21, 26, 24}, {22, 25, 20}},
	{{45, 59, 10}, {19, 21, 22, 26, 27, 5, 6, 2, 3, 1, 72, 71, 70, 69, 68}, {32, 28, 36}, {34, 29, 31}, {33, 30, 35}},
	{{55, 36, 14}, {9, 8, 7, 6, 5, 46, 48, 49, 53, 54, 68, 69, 65, 66, 64}, {45, 41, 37}, {44, 42, 39}, {43, 38, 40}},
	{{64, 9, 23}, {18, 17, 16, 15, 14, 55, 57, 58, 62, 63, 41, 42, 38, 39, 37}, {54, 50, 46}, {53, 51, 48}, {52, 47, 49}},
	{{32, 37, 18}, {50, 51, 47, 48, 46, 27, 26, 25, 24, 23, 64, 66, 67, 71, 72}, {55, 63, 59}, {57, 62, 60}, {58, 61, 56}},
	{{5, 46, 27}, {36, 35, 34, 33, 32, 37, 39, 40, 44, 45, 59, 60, 56, 57, 55}, {68, 64, 72}, {65, 67, 70}, {66, 71, 69}},
	{{40, 39, 38, 49, 53, 52, 29, 33, 34, 70, 69, 65, 16, 17, 13, 20, 21, 22}},
	{{43, 42, 38, 49, 48, 47, 29, 30, 31, 2, 6, 7, 58, 62, 61, 25, 26, 22}},
	{{2, 3, 4, 11, 15, 16, 67, 71, 70, 34, 35, 31, 52, 51, 47, 58, 57, 56}},
	{{11, 12, 13, 20, 24, 25, 40, 44, 43, 7, 8, 4, 61, 60, 59, 67, 66, 65}},
};
typedef vector<int> cube;
cube rot(cube x, permutation p) {
	for (int &x : p) x --;
	assert(p.size() % 3 == 0);
	int len = (int) p.size() / 3;
	vector<int> c;
	for (int i = 0; i < len; ++ i) c.push_back(x[p[i]]);
	for (int i = 0; i < 2; ++ i) {
		for (int j = 0; j < len; ++ j) {
			x[p[i * len + j]] = x[p[i * len + j + len]];
		}
	}
	for (int i = 0; i < len; ++ i) x[p[2 * len + i]] = c[i];
	return x;
}
bool check(const cube &x) {
	for (int i = 0; i < 8; ++ i) {
		for (int j = 0; j < 9; ++ j) if (x[i * 9 + j] != x[i * 9]) return 0;
	}
	return 1;
}
bool dfs(cube x, int step) {
	if (check(x)) return 1;
	if (step == 3) return 0;
	for (auto &pers : all) {
		for (int r = 0; r < 2; ++ r) {
			cube y = x;
			for (auto p : pers) {
				if (r) reverse(p.begin(), p.end());
				y = rot(y, p);
			}
			if (dfs(y, step + 1)) return 1;
		}
	}
	return 0;
}
int main() {
	int T;
	scanf("%d", &T);
	while (T --) {
		cube x;
		for (int i = 0; i < 72; ++ i) {
			int a;
			scanf("%d", &a);
			x.push_back(a);
		}
		bool res = dfs(x, 0);
		puts(res ? "YES" : "NO");
	}
}

triangulation triangulation triangulation

平方枚举最大三角形,剩下来的是个带面积限制的平方dp。

常数优化: 1. dp区域中的最大三角形面积比全局最大三角形面积小直接用卡特兰数算 2. dp对称性,只需要for前一半 3. 加8次再取模

Aki

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 405;
typedef long double DB;
const long double pi = acos(-1.);
const DB eps = 1e-14;
DB SA[N], SB[N], part[N];
int dp[N], C[2 * N][N];
int calc(int n, int MOD) {
	int res = 0;
	for (int i = 0; i <= 2 * n; ++ i) {
		C[i][0] = 1 % MOD;
		for (int j = 1; j <= min(n, i); ++ j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
	}
	for (int i = 0; i <= n; ++ i) SA[i] = i * sin(2 * pi / n);
	for (int i = 0; i <= n; ++ i) SB[i] = sin(i * 2 * pi / n);
	for (int i = 0; i <= n; ++ i) {
		if (i * 2 > n) {
			part[i] = n * sin(2 * pi / n) - part[n - i];
		}
		else {
			part[i] = i * sin(2 * pi / n) - sin(i * 2 * pi / n);
		}
	}
	//for (int i = 0; i <= n; i += 10) printf("part[%d]=%.20f\n", i, (double) part[i]);
	for (int a = 1; a < n; ++ a) {
		for (int b = 1; a + b < n; ++ b) {
			int c = n - a - b;
			long long bei = n;
			if (a == b && b == c) {
				bei = n / 3;
			}
			else if (a == c || b == c) continue;
			if (a != b && a != min(min(a, b), c)) continue;
			DB A = part[n] - part[a] - part[b] - part[c];
			dp[1] = 1 % MOD;
			for (int i = 2; i <= max(max(a, b), c); ++ i) {
				if (part[i] - part[i / 2] - part[i - i / 2] + eps < A) {
					dp[i] = (C[2 * (i - 1)][i - 1] + MOD - C[2 * (i - 1)][i - 2]) % MOD;
					continue;
				}
				unsigned long long tmp = 0;
				for (int j = 1; j < i / 2; ++ j) {
					DB a = part[i] - part[j] - part[i - j];
					if (a + eps < A) {
						tmp += 2LL * dp[j] * dp[i - j];
						if (j % 7 == 0) tmp %= MOD;
					}
				}
				int j = i / 2;
				if (i - j == j) {
					DB a = part[i] - part[j] - part[i - j];
					if (a + eps < A) {
						tmp += 1LL * dp[j] * dp[i - j];
					}
				}
				dp[i] = tmp % MOD;
			}
			(res += bei * dp[a] % MOD * dp[b] % MOD * dp[c] % MOD) %= MOD;
		}
	}
	//printf("calc %d %d = %d\n", n, MOD, res % MOD);
	return res % MOD;
}
int main() {
	int T;
	scanf("%d", &T);
	while (T --) {
		int n, m1, m2;
		scanf("%d%d%d", &n, &m1, &m2);
		long long ans = 1LL * calc(n, m1) * calc(n, m2);
		printf("%lld\n", ans);
	}
}