2019 ICPC Asia Xuzhou Regional

Contest Info
Solutions

Contest Info

Solved	A	B	C	D	E	F	G	H	I	J	K	L	M
8/13	O	-	O	-	O	O	-	O	-	O	-	O	O

O 在比赛中通过
Ø 赛后通过
! 尝试了但是失败了
- 没有尝试

Solutions

A. Cat

题意：

每次询问给出\(L, R, S\)，要求找一个最长的连续区间\(l, r\)，满足\(l \oplus (l + 1) \oplus, \cdots, \oplus r <= S\)。

思路：

考虑\(4k \oplus (4k + 1) \oplus (4k + 2) \oplus (4k +3) = 0\)

那么我们枚举一下头，枚举一下尾，暴力判断一下即可。

代码：

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF = 0x3f3f3f3f3f3f3f3f;

ll L, R, S;

ll gao(ll l, ll r) {

	if (l > r) return INF;

	ll res = 0;

	if (r - l + 1 <= 10) {

		for (ll i = l; i <= r; ++i) {

			res ^= i;

		}

	} else {

		ll ql = l, qr = r;

		while (ql % 4 != 0) {

			res ^= ql;

			ql++;

		}

		while (qr % 4 != 3) {

			res ^= qr;

			qr--;

		}

	}

	return res;

}

int main() {

	int T;

	scanf("%d", &T);

	while (T--) {

		scanf("%lld %lld %lld", &L, &R, &S);

		ll res = -1;

		for (int i = 0; i <= 4; ++i) {

			for (int j = 0; j <= 4; ++j) {

				ll tmp = gao(L + i, R - j);

				if (tmp <= S) res = max(res, (R - j) - (L + i) + 1);

			}

		}

		printf("%lld\n", res);

	}

	return 0;

}

B. Cats line up

题意：

给出\(n\)个数，问有多少个排列使得任意相邻两个数的差距小于等于\(K(1 \leq K \leq 3)\)

C. < 3 numbers

题意：

令\(x\)为区间\([L, R]\)内素数个数，每次询问给出\([L, R]\)，判断下式是否成立：

\[\begin{eqnarray*}
\frac{x}{R - L + 1} < \frac{1}{3}
\end{eqnarray*}
\]

思路：

考虑素数密度，大区间直接'Yes'

小区间暴力判断

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int L, R, pri[N], check[N];

void sieve() {

	memset(check, 0, sizeof check);

	for (int i = 2; i < N; ++i) {

		if (!check[i]) {

			pri[++*pri] = i;

		}

		for (int j = 1; j <= *pri; ++j) {

			if (1ll * i * pri[j] >= N) break;

			check[i * pri[j]] = 1;

			if (i % pri[j] == 0) break;

		}

	}

}

bool prime(int x) {

	if (x < N) return !check[x];

	for (int i = 2; 1ll * i * i <= x; ++i) {

		if (x % i == 0)

			return false;

	}

	return true;

}

bool ok(int l, int r) {

	int tot = r - l + 1;

	int p = 0;

	for (int i = l; i <= r; ++i) {

		if (prime(i)) {

			++p;

		}

	}

	return p * 3 < tot;

}

int main() {

	sieve();

	int _T; scanf("%d", &_T);

	while (_T--) {

		scanf("%d%d", &L, &R);

		if (R - L + 1 > 60) {

			puts("Yes");

		} else {

			puts(ok(L, R) ? "Yes" : "No");

		}

	}

	return 0;

}

E. Multiply

题意：

给出\(n\)个数\(a_i\)，令\(Z = a_1! \times a_2! \times \cdots \times a_n!\)

现在给出\(X, Y\)，令\(b_i = Z \times X^i\)，它想要一个最大的\(i\)，使得\(b_i \;|\; Y!\)

思路：

考虑分解\(X\)得到它的所有素因子及幂次。

然后找出其每个因子在\(\frac{Y!}{Z}\)中还剩多少个。

然后贪心拼\(X\)就可以了

代码：

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)

void err() { cout << "\033[39;0m" << endl; }

template<class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << " "; err(args...); }

const int N = 2e5 + 10, INF = 0x3f3f3f3f;

int n; ll x, y, a[N], f[N];

mt19937 rd(time(0));

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

//ll mul(ll a, ll b, ll p) {

//	return (a * b - (ll)(a / (long double)p * b + 1e-3) * p + p) % p;

//}

ll mul(ll a, ll b, ll p) {

	return (__int128)a * b % p;

}

ll qpow(ll base, ll n, ll p) {

	ll res = 1;

	base %= p;

	while (n) {

		if (n & 1) {

			res = mul(res, base, p);

		}

		base = mul(base, base, p);

		n >>= 1;

	}

	return res;

}

struct Mill {

	ll n, fac[22000][2], bk[22000]; int tot;

	const int C = 2307;

	const int S = 8;

	bool check(ll a, ll n) {

		ll m = n - 1, x, y = 0;

		int j = 0;

		while (!(m & 1)) {

			m >>= 1;

			++j;

		}

		x = qpow(a, m, n);

		for (int i = 1; i <= j; x = y, ++i) {

			y = mul(x, x, n);

			if (y == 1 && x != 1 && x != n - 1) {

				return 1;

			}

		}

		return y != 1;

	}

	bool miller_rabin(ll n) {

		if (n < 2) {

			return 0;

		} else if (n == 2) {

			return 1;

		} else if (!(n & 1)) {

			return 0;

		}

		for (int i = 0; i < S; ++i) {

			if (check(rd() % (n - 1) + 1, n)) {

				return 0;

			}

		}

		return 1;

	}

	ll pollard_rho(ll n, int c) {

		ll i = 1, k = 2, x = rd() % n, y = x, d;

		while (1) {

			++i; x = (mul(x, x, n) + c) % n;

			d = gcd(y - x, n);

			if (d > 1 && d < n) {

				return d;

			}

			if (y == x) {

				return n;

			}

			if (i == k) {

				y = x;

				k <<= 1;

			}

		}

	}

	void findfac(ll n, int c) {

		if (n == 1) {

			return;

		}

		if (miller_rabin(n)) {

			bk[++*bk] = n;

			return;

		}

		ll m = n;

		while (m == n) {

			m = pollard_rho(n, c--);

		}

		findfac(m, c);

		findfac(n / m, c);

	}

	void gao(ll _n) {

		n = _n; *bk = 0;

		findfac(n, C);

		sort(bk + 1, bk + 1 + *bk);

		fac[1][0] = bk[1];

		fac[1][1] = 1;

		tot = 1;

		for (int i = 2; i <= *bk; ++i) {

			if (bk[i] == bk[i - 1]) {

				++fac[tot][1];

			} else {

				++tot;

				fac[tot][0] = bk[i];

				fac[tot][1] = 1;

			}

		}

	}

}mill;

int main() {

	int _T; cin >> _T;

	while (_T--) {

		scanf("%d%lld%lld", &n, &x, &y);

		for (int i = 1; i <= n; ++i) scanf("%lld", a + i);

		mill.gao(x);

		int tot = mill.tot;

		for (int i = 1; i <= tot; ++i) f[i] = 0;

		ll res = 8e18;

		for (int i = 1; i <= tot; ++i) {

//			dbg(mill.fac[i][0], mill.fac[i][1]);

			ll now = 1;

			for (int j = 1; now <= y / mill.fac[i][0]; ++j) {

				now *= mill.fac[i][0];

				f[i] += (y / now);

				for (int o = 1; o <= n; ++o) {

					f[i] -= (a[o] / now);

				}

			}

			res = min(1ll * res, f[i] / mill.fac[i][1]);

		}

		printf("%lld\n", res);

	}

	return 0;

}

F. The Answer to the Ultimate Question of Life, The Universe, and Everything.

题意：

每次询问给出\(x(0 \leq x \leq 200)\)，需要找出\(a, b, c(|a|, |b|, |c| \leq 5000)\)满足\(a^3 + b^3 + c^3 = x\)

思路：

\(x\)只有201个，可以暴力打表。

打表的时候可以枚举两维，第三维直接算。

打表代码：

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll ok(ll need) {

	ll l = -5000, r = 5000, res = -12345678;

	while (r - l >= 0) {

		ll mid = (l + r) >> 1;

		ll tmp = mid * mid * mid;

		if (tmp == need) {

			return mid;

		}

		if (tmp > need) {

			r = mid - 1;

		} else {

			l = mid + 1;

		}

	}

	return res;

}

bool gao(int x) {

	int limit = 5000;

	for (ll a = -limit; a <= limit; ++a) {

		for (ll b = -limit; b <= limit; ++b) {

			ll need = 1ll * x - a * a * a - b * b * b;

			ll c = ok(need);

			if (abs(c) <= 5000) {

				cout << a << " " << b << " " << c << endl;

				return true;

			}

		}

	}

	return false;

}

int main() {

	int cnt = 0;

	int Y = -12345678;

	for (int i = 0; i <= 200; ++i) {

		if (!gao(i)) {

			cout << Y << " " << Y << " " << Y << endl;

		}

	}

	cout << cnt << " " << cnt << " " << cnt << endl;

	return 0;

}

H. Yuuki and a problem

题意：

给出一个序列\(a_i\)，支持两个操作：

将\(a_x\)改成\(y\)
询问最小的不能被\(a_l \cdots a_r\)里面的数表示出来的正整数

思路：

考虑没有修改操作怎么做：

主席树权值\(i\)表示\(i\)这个数的和.

然后考虑每次递增上去，假设已经能够表示出\([1, x]\)范围的数，那么我们可以将\([1, x + 1]\)范围内还未加入的数加进去。

这个可以在主席树上查。

并且这个加入次数跟斐波那契列类似，不会很多。

那么有修改，就敲个动态主席树

注意不要把vector当参数传下去，空间要给够

代码：

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)

void err() { cout << "\033[39;0m" << endl; }

template<class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << " "; err(args...); }

const int N = 2e5 + 10;

int n, m, q, a[N], L[510][510], R[510][510], cl, cr;

inline int lowbit(int x) { return x & -x; }

struct SEG {

	struct node {

		int ls, rs;

		ll sum;

		void init() { ls = rs = sum = 0; }

	}t[N * 80];

	int rt[N], tot;

	ll res;

	int newnode() {

		++tot;

		t[tot].init();

		return tot;

	}

	void init() { memset(rt, 0, sizeof rt); tot = 0; }

	void update(int &rt, int l, int r, int pos, int v) {

		if (!rt) rt = newnode();

		t[rt].sum += v;

		if (l == r) return;

		int mid = (l + r) >> 1;

		if (pos <= mid) update(t[rt].ls, l, mid, pos, v);

		else update(t[rt].rs, mid + 1, r, pos, v);

	}

	void update(int x, int pos, int v) {

		for (; x <= n; x += lowbit(x)) {

			update(rt[x], 1, m, pos, v);

		}

	}

	void query(int dep, int l, int r, int ql, int qr) {

	    if (ql > qr) return;

		if (l >= ql && r <= qr) {

			for (int i = 1; i <= cl; ++i) res -= t[L[dep][i]].sum;

			for (int i = 1; i <= cr; ++i) res += t[R[dep][i]].sum;

			return;

		}

		int mid = (l + r) >> 1;

		if (ql <= mid) {

			for (int i = 1; i <= cl; ++i) L[dep + 1][i] = t[L[dep][i]].ls;

			for (int i = 1; i <= cr; ++i) R[dep + 1][i] = t[R[dep][i]].ls;

			query(dep + 1, l, mid, ql, qr);

		}

		if (qr > mid) {

			for (int i = 1; i <= cl; ++i) L[dep + 1][i] = t[L[dep][i]].rs;

			for (int i = 1; i <= cr; ++i) R[dep + 1][i] = t[R[dep][i]].rs;

			query(dep + 1, mid + 1, r, ql, qr);

		}

	}

}seg;

int main() {

	m = 2e5;

	while (scanf("%d%d", &n, &q) != EOF) {

		for (int i = 1; i <= n; ++i) scanf("%d", a + i);

		seg.init();

		for (int i = 1; i <= n; ++i) {

			seg.update(i, a[i], a[i]);

		}

		int op, x, y;

		for (int i = 1; i <= q; ++i) {

			scanf("%d%d%d", &op, &x, &y);

			if (op == 1) {

				seg.update(x, a[x], -a[x]);

				a[x] = y;

				seg.update(x, a[x], a[x]);

			} else {

				--x;

				cl = cr = 0;

				for (int j = x; j; j -= lowbit(j)) {

					L[0][++cl] = seg.rt[j];

				}

				for (int j = y; j; j -= lowbit(j)) {

					R[0][++cr] = seg.rt[j];

				}

				ll l = -1, r = 0;

				while (1) {

					seg.res = 0;

					seg.query(0, 1, m, min(1ll * m + 1, l + 2), min(1ll * m, r + 1));

					ll tot = seg.res;

				//	dbg(i, tot, l + 2, r + 1);

					if (tot == 0) break;

					l = r;

					r += tot;

				}

				printf("%lld\n", r + 1);

			}

		}

	}

	return 0;

}

J. Loli, Yen-Jen, and a graph problem

题意：

给出一个完全图，要将这张图分成\(n - 1\)条路径，第\(i\)条路径的长度为\(i\)，并且一条边只能存在于一条路径中。

代码：

#include <bits/stdc++.h>

using namespace std;

#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)

void err() { cout << "\033[39;0m" << endl; }

template<class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << " "; err(args...); }

const int N = 1e3 + 10;

int n;

int e[N][N];

int Max[N];

int now;

vector<vector<int> > vec;

void fix(int x, int y) {

	e[x][y] = e[y][x] = 1;

}

int find(int x) {

	while (e[Max[x]][x]) {

		++Max[x];

	}

	return Max[x];

}

void insert(int x) {

	vec[now].push_back(x);

	if ((int)vec[now].size() == now + 1) {

		now--;

		if (now % 2 == 0) vec[now].push_back(x);

	}

}

void gao(int x, int y) {

	insert(x);

	int ny = y + 1;

	if (ny > n) return ;

	insert(ny);

	gao(x + 1, ny);

}

int main() {

	while (scanf("%d", &n) != EOF) {

		for (int i = 1; i <= n; ++i) {

			for (int j = 1; j <= n; ++j) {

				e[i][j] = (i == j ? 1 : 0);

			}

			Max[i] = 1;

		}

		vec.clear();

		vec.resize(n + 1);

		if (n & 1) {

			for (int cas = n - 1; cas >= 1; --cas) {

				vec[cas].push_back(n);

				int sze = 1;

				while (sze <= cas) {

					int nxt = find(vec[cas].end()[-1]);

					fix(vec[cas].end()[-1], nxt);

					vec[cas].push_back(nxt);

					sze++;

				}

			}

			for (int i = 1; i < n; ++i) {

				for (int j = 0, sze = vec[i].size(); j < sze; ++j) {

					printf("%d%c", vec[i][j], " \n"[j == sze - 1]);

				}

			}

		} else {

			now = n - 1;

		//	insert(2);

		//	gao(1, 2);

			for (int i = 2; i <= n; i += 2) {

				insert(i);

				gao(1, i);

			}

			for (int i = 1; i < n; ++i) {

				for (int j = 0, sze = vec[i].size(); j < sze; ++j) {

					printf("%d%c", vec[i][j], " \n"[j == sze - 1]);

				}

			}

		}

	}

	return 0;

}

K. K-rectangle

题意：

给出\(n\)个点\((x_i, y_i)(x_i < x_{i + 1}, 0 < y_i)\)

现在你要找若干个矩形覆盖这些点，矩形的底边必须在\(x\)轴上，矩形之间不能有面积交，矩形的花费是\(h(w + k)\)，\(h\)为高，\(w\)为宽，\(k\)为给定参数。

求最小花费。

L. Loli, Yen-Jen, and a cool problem

题意：

给出一个Trie，每次询问给出一个\(x_i, L_i\)，问有多少个结点为起点向上跳\(L - 1\)步连成的长度为\(L\)的字符串和以\(x_i\)为起点连成的字符串相同

这里的字符在点上，不在边上

思路：

多加一个根节点，就能将点上的字符转化成边上的字符

然后Trie上建SAM，每次查找倍增跳深度最深的合法祖先，它的cnt就是答案

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10, ALP = 26, M = 20;

int n, q, trie_pos[N]; char s[N];

struct SAM {

	struct node {

		int maxlen, cnt, fa, nx[ALP];

		void init() { maxlen = cnt = fa = 0; memset(nx, 0, sizeof nx); }

	}t[N << 1];

	int tot, c[N << 1], rk[N << 1], fa[N << 1][M];

	vector <vector<int>> G;

	int newnode() {

		++tot;

		t[tot].init();

		return tot;

	}

	void init() {

		tot = 0;

		newnode();

	}

	int extend(int id, int lst, int cnt) {

		int cur = newnode(), p;

		t[cur].cnt = cnt;

		t[cur].maxlen = t[lst].maxlen + 1;

		for (p = lst; p && !t[p].nx[id]; p = t[p].fa) t[p].nx[id] = cur;

		if (!p) {

			t[cur].fa = 1;

		} else {

			int q = t[p].nx[id];

			if (t[q].maxlen == t[p].maxlen + 1) {

				t[cur].fa = q;

			} else {

				int clone = newnode();

				t[clone] = t[q];

				t[clone].cnt = 0;

				t[clone].maxlen = t[p].maxlen + 1;

				for (; p && t[p].nx[id] == q; p = t[p].fa) t[p].nx[id] = clone;

				t[cur].fa = t[q].fa = clone;

			}

		}

		return cur;

	}

	void dfs(int u) {

		for (int i = 1; i < M; ++i)

			fa[u][i] = fa[fa[u][i - 1]][i - 1];

		for (auto &v : G[u]) {

			fa[v][0] = u;

			dfs(v);

			t[u].cnt += t[v].cnt;

		}

	}

	void build() {

		memset(c, 0, sizeof c);

		for (int i = 1; i <= tot; ++i) c[t[i].maxlen]++;

		for (int i = 1; i <= tot; ++i) c[i] += c[i - 1];

//		for (int i = 1; i <= tot; ++i) rk[c[t[i].maxlen]--] = i;

//		for (int i = tot; i; --i) t[t[rk[i]].fa].cnt += t[rk[i]].cnt;

		G.clear(); G.resize(tot + 1);

		for (int i = 1; i <= tot; ++i) {

			if (t[i].fa) {

				G[t[i].fa].push_back(i);

			}

		}

		fa[1][0] = 0;

		dfs(1);

	}

	int query(int x, int len) {

		for (int i = M - 1; i >= 0; --i) {

			if (t[fa[x][i]].maxlen >= len) {

				x = fa[x][i];

			}

		}

		return t[x].cnt;

	}

}sam;

vector <vector<int>> G;

struct Trie {

	struct node {

		int nx[ALP], cnt, sam_pos;

		void init() { memset(nx, 0, sizeof nx); cnt = 0; sam_pos = 0; }

	}t[N];

	int rt, tot;

	int newnode() {

		++tot;

		t[tot].init();

		return tot;

	}

	void init() { tot = 0; rt = newnode(); }

	int add(int p, int ch) {

		if (!t[p].nx[ch]) {

			t[p].nx[ch] = newnode();

		}

		int now = t[p].nx[ch];

		++t[now].cnt;

		return now;

	}

	void dfs(int u) {

		for (auto &v : G[u]) {

			trie_pos[v] = add(trie_pos[u], s[v] - 'A');

			dfs(v);

		}

	}

	void bfs() {

		queue <int> q;

		q.push(1);

		t[1].sam_pos = 1;

		while (!q.empty()) {

			int u = q.front(); q.pop();

			for (int i = 0; i < ALP; ++i) {

				if (!t[u].nx[i]) continue;

				int now = t[u].nx[i];

				t[now].sam_pos = sam.extend(i, t[u].sam_pos, t[now].cnt);

				q.push(now);

			}

		}

	}

}trie;

int main() {

	while (scanf("%d%d", &n, &q) != EOF) {

		G.clear(); G.resize(n + 1);

		scanf("%s", s + 1);

		trie.init();

		trie_pos[0] = 1;

		trie_pos[1] = trie.add(trie_pos[0], s[1] - 'A');

	    for (int u = 2, v; u <= n; ++u) {

			scanf("%d", &v);

			G[v].push_back(u);

		}

		trie.dfs(1);

		sam.init(); trie.bfs(); sam.build();

		int x, len;

		while (q--) {

			scanf("%d%d", &x, &len);

			printf("%d\n", sam.query(trie.t[trie_pos[x]].sam_pos, len));

		}

	}

	return 0;

}

M. Kill the tree

题意：

给出一棵有根树，根节点为\(1\)，定义\(d(u, v)\)为\(u\)到\(v\)简单路径的长度，\(c(w) = \sum_{v \in T} d(w, v)\)，定义结点\(w\)为一棵树\(T\)的'critical point'，当且仅当\(c(w) \leq min_{u \in T} c(u)\)

现在要对于每个\(i \in [1, n]\)，要找出以\(i\)为根节点的子树中的'critical point'

思路：

猜想'critical point'就是重心。

问题转化成找重心。

我们考虑假设\(x\)的子树中的所有重心都找出来了：

那么\(x\)子树的重心不可能在它的轻儿子的子树中，因为选\(x\)本身肯定更优
并且\(x\)的重心不可能在它重儿子重心的子树中。
只可能在其重儿子的重心到\(x\)的路径上

暴力判断一下即可，每个点只会被判断一次。

但是这里要求输出所有可能的点，考虑重心最多只有两个，并且是连着的，那么我们找到深度最大的一个，另一个如果存在的话，那么就是它父亲，判一下即可。

代码：

#include <bits/stdc++.h>

using namespace std;

#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)

void err() { cout << "\033[39;0m" << endl; }

template<class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << " "; err(args...); }

const int N = 2e5 + 10;

int n;

vector<vector<int> >G;

int sze[N], fa[N], son[N], res[N];

void dfs(int u, int pre = 0) {

	sze[u] = 1;

	fa[u] = pre;

	for (auto &v : G[u]) {

		if (v == pre) continue;

		dfs(v, u);

		sze[u] += sze[v];

		if (son[u] == -1 || sze[son[u]] < sze[v]) {

			son[u] = v;

		}

	}

	if (son[u] == -1) son[u] = u;

}

void gao(int u) {

	if (sze[u] == 1) {

		res[u] = u;

		return ;

	}

	for (auto &v : G[u]) {

		if (v == fa[u]) continue;

		gao(v);

	}

	int now = res[son[u]];

	while (now != u) {

		int tmp = max(sze[u] - sze[now], sze[son[now]]);

		if (tmp <= sze[u] / 2) {

			break;

		}

		now = fa[now];

	}

//	assert(max(sze[u] - sze[now], sze[son[now]]) <= sze[u] / 2);

	res[u] = now;

}

int main() {

	while (scanf("%d", &n) != EOF) {

		memset(son, -1, sizeof son);

		G.clear();

		G.resize(n + 1);

		for (int i = 1, u, v; i < n; ++i) {

			scanf("%d %d", &u, &v);

			G[u].push_back(v);

			G[v].push_back(u);

		}

		dfs(1);

		gao(1);

		for (int i = 1; i <= n; ++i) {

			vector <int> vec;

			int x = res[i], y = -1;

			vec.push_back(x);

			if (x != i) {

				y = fa[x];

				if (max(sze[i] - sze[y], sze[son[y]]) <= sze[i] / 2) {

					vec.push_back(y);

				}

			}

			if (vec.size() > 1 && vec[0] > vec[1]) swap(vec[0], vec[1]);

			for (int j = 0, sze = vec.size(); j < sze; ++j)

				printf("%d%c", vec[j], " \n"[j == sze - 1]);

		}

	}

	return 0;

}

巴特西