Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!) 题解

Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!)

Kuroni and the Gifts

由于 $a,b$ 分别互不相同，因此想让 $a+b$ 互不相同，对 $a,b$ 分别排序即可。

const int N = 107;
int n, a[N], b[N];

inline void solve() {
	rd(n), rda(a, n), rda(b, n);
	sort(a + 1, a + n + 1);
	sort(b + 1, b + n + 1);
	for (int i = 1; i <= n; i++)
		print(a[i], " \n"[i==n]);
	for (int i = 1; i <= n; i++)
		print(b[i], " \n"[i==n]);
}

int main() {
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

Kuroni and Simple Strings

要求最终不能再存在 () 这样的子串，因此只能是若干个 ) 后接若干个 (。

因此我们要找到一个位置，这个位置左边的 ( 全部被删掉，右边的 ) 全部被删掉。

由于只能删掉同等数量的 ( 和 )，而这个位置一定存在，因此答案要么为 $0$ ，要么为 $1$ 。

const int N = 1e3 + 7;
int n, a[N], b[N];
char s[N];

int main() {
	rds(s, n);
	vi ans;
	for (int i = 1; i <= n; i++)
		a[i] = a[i-1] + (s[i] == '(');
	for (int i = n; i; i--)
		b[i] = b[i+1] + (s[i] == ')');
	for (int i = 0; i <= n; i++)
		if (a[i] == b[i+1]) {
			for (int j = 1; j <= i; j++)
				if (s[j] == '(') ans.pb(j);
			for (int j = i + 1; j <= n; j++)
				if (s[j] == ')') ans.pb(j);
			if (!ans.size()) {
				print(0);
				return 0;
			}
			print(1);
			print(ans.size());
			for (int x : ans) print(x, ' ');
			return 0;
		}
	return 0;
}

Kuroni and Impossible Calculation

这个绝对值看起来不太好搞，那么我们排序一下，就一定是后面减前面了。

依次考虑每个数与前面的数对答案的贡献，但我们显然不能 $\mathcal O(n^2)$ 枚举。

注意到这个模数非常小，因此我们对前面的数开一个桶，记录每个余数的个数。

那么我们只需要 $\mathcal O(nm)$ 就可以求出每个可能的差的数量，最后快速幂一下就能求出答案了。

什么，你问 $\mathcal O(nm)$ 不是 $2 \times 10^8$ 吗，怎么能过？

你要相信 CF 神机一秒跑十亿不成问题。

const int N = 2e5 + 7, M = 1e3 + 7;
int n, a[N], c[M];
ll f[M];
modint ans = 1;

int main() {
	rd(n), rd(P), rda(a, n);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		a[i] %= P;
		for (int j = 0; j < P; j++)
			f[(a[i]-j+P)%P] += c[j];
		c[a[i]]++;
	}
	for (int i = 0; i < P; i++) ans *= (modint)i ^ f[i];
	print(ans);
	return 0;
}

Kuroni and the Celebration

每次询问两个点的 LCA，最多询问 $\lfloor \frac{n}{2} \rfloor$ 次确定根。

很傻的一道交互题。

注意到如果一个叶子和另一个点的 LCA 就是这个叶子，那么这个叶子一定为根；如果不是，则这个叶子一定不是根。

那么我们每次询问两个叶子的 LCA 即可，如果是其中某一个点，则那个点就是根；否则删掉两个点，注意可能产生新的叶子。

最坏情况下，每次询问会删掉两个叶子，那么 $\lfloor \frac{n}{2} \rfloor$ 次后最多只剩下一个点，这个点显然就是根了。

const int N = 1e3 + 7;
int n, d[N], v[N];
vi e[N];

int main() {
	ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 1, x, y; i < n; i++)
		cin >> x >> y, e[x].pb(y), e[y].pb(x), d[x]++, d[y]++;
	queue<int> q;
	for (int i = 1; i <= n; i++)
		if (d[i] == 1) q.push(i);
	for (int i = 1; i <= n / 2; i++) {
		int x = q.front();
		q.pop();
		int y = q.front();
		q.pop();
		cout << "? " << x << " " << y << endl;
		fflush(stdout);
		int z;
		cin >> z;
		if (z == x || z == y) {
			cout << "! " << z << endl;
			return 0;
		}
		for (int z : e[x])
			if (!v[z] && (--d[z] == 1)) q.push(z);
		for (int z : e[y])
			if (!v[z] && (--d[z] == 1)) q.push(z);
		v[x] = v[y] = 1;
	}
	for (int i = 1; i <= n; i++)
		if (!v[i]) cout << "! " << i << endl;
	return 0;
}

Kuroni and the Score Distribution

要求构造一个长度为 $n$ 的单调上升序列 $a$ ，使得恰好有 $m$ 个三元组 $(i,j,k)(i < j < k)$ 满足 $a_i + a_j = a_k$ 。

很傻的一道构造题。

先 $1,2,3,4,5,\dots$ 的填，产生的三元组个数为 $0,0,1,1,2,\dots$ 。

一直填到第一次个数 $\ge m$ 的位置，假设多了 $k$ 个。

注意到在这个位置上的数每增加 $2$ ，个数会减 $1$ ，因此这个位置上的数加上 $2k$ 即可。

后面的不应该再存在满足条件的三元组了，那么填一定间隔下最大的几个数就够了。

如果填完 $n$ 个数，三元组的数量依旧 $< m$ ，则说明无解，因为这个填数的方法最大化了三元组的数量。

const int N = 5e3 + 7;
int n, m, a[N];

int main() {
	rd(n), rd(m);
	int t = 0;
	for (int i = 0; i < n; i++) {
		a[i] = i + 1;
		t += i >> 1;
		if (t >= m) {
			a[i] += (t - m) << 1;
			for (int j = n - 1, k = 1e9; j > i; j--, k -= i + 2)
				a[j] = k;
			for (int j = 0; j < n; j++)
				print(a[j], " \n"[j==n]);
			return 0;
		}
	}
	print(-1);
	return 0;
}

Kuroni and the Punishment

首先可以知道答案一定 $\le n$ ，这个界还可以再紧一点，一定 $\le$ 奇数的个数，设为 $t$ 。

考虑找到所有最终可能的 $\gcd$ ，随便找一个数 $x$ ，由于最多 $+t/-t$ ，因此这个 $x$ 最终只能在 $[a_i-t, a_i+t]$ 这个范围内，因此 $\gcd$ 也只能在这个范围内的数的质因数中。

我们对这个范围做区间筛，即可找到所有的质因数。具体而言，设这个区间为 $[l,r]$ ，则可能的 $\gcd$ （即所有质因数）包括：

$2 \sim \sqrt r$ 内的所有质数，称为小质数。
对于 $x \in [l,r]$ ， $x$ 超过 $\sqrt r$ 的质因数，而这个质因数最多只有一个，称为大质数。

把这些可能的 $\gcd$ 全部暴力 check，check 的时候剪枝就行了。

看起来复杂度不太对，但是实际上长得很像答案的 $\gcd$ 最多只有 $12$ 个，其中 $10$ 个是小质数， $2$ 个是相邻的大质数。

const int N = 2e5 + 7;
const ll M = 2e6;
int n;
bool v[M|1];
ll a[N];
vector<ll> p, q;

int main() {
	for (ll i = 2; i <= M; i++) {
		if (v[i]) continue;
		p.pb(i);
		for (ll j = i * i; j <= M; j += i) v[j] = 1;
	}
	q = p;
	rd(n), rda(a, n);
	sort(a + 1, a + n + 1);
	ll d = a[1];
	for (int i = 2; i <= n; i++) d = __gcd(d, a[i]);
	if (d != 1) return print(0), 0;
	ll t = 0;
	for (int i = 1; i <= n; i++) t += a[i] & 1;
	ll l = max(M + 1, a[n] - t), r = a[n] + t;
	map<ll, ll> w;
	for (ll i = l; i <= r; i++) w[i] = i; 
	for (ll x : p) 
		for (ll i = l / x * x; i <= r; i += x)
			if (i >= l) while (!(w[i] % x)) w[i] /= x;
	for (ll i = l; i <= r; i++)
		if (w[i] > M) q.pb(w[i]);
	for (ll x : q) {
		if (x == 2) continue;
		ll o = 0;
		for (int i = 1; i <= n; i++) {
			o += min(a[i] < x ? x : a[i] % x, x - a[i] % x);
			if (o >= t) break;
		}
		t = min(t, o);
	}
	print(t);
	return 0;
}

Kuroni and Antihype

题目太神仙了，先咕咕咕着。

Kuroni the Private Tutor