【AtCoder】AtCoder Regular Contest 099 题解

92 阅读 0 评论 61 点赞

我是靠谱客的博主唠叨大地，最近开发中收集的这篇文章主要介绍【AtCoder】AtCoder Regular Contest 099 题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【比赛链接】

点击打开链接

【题解链接】

点击打开链接

【C】Minimization

【思路要点】

显然我们每次操作的区间内都会包含1。
因此(Ans=1+lceilfrac{N-K}{K-1}rceil)。
时间复杂度(O(1))。

【代码】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, k;
int main() {
	read(n), read(k);
	int ans = 1;
	n -= k;
	ans += n / (k - 1);
	n %= (k - 1);
	if (n != 0) ans++;
	writeln(ans);
	return 0;
}

【D】Snuke Numbers

【思路要点】

打表发现所有数位都是9的数都是Snuke Number。
考虑求出值域内最大的Snuke Number（显然为(10^{15}-1)），并依次求出恰小于当前Snuke Number的Snuke Number。
也就是说，对于当前数(X)，我们需要找到最大的(Y)使得(X>Y,frac{Y}{S(Y)}≤frac{X}{S(X)})。
我们发现在不退位的情况下使得(X)的两个数位减少是不优的，我们可以只减少较高的那个数位。
因此，我们可以从低到高枚举每个数位，将其的1~9倍分别减在(X)上，并检查是否满足(X>Y,frac{Y}{S(Y)}≤frac{X}{S(X)})，若满足，则替换(X)成为新的Snuke Number。
时间复杂度(O(CntLogV))，其中(Cnt)为值域内Snuke Number的个数，为792。

【代码】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int cnt;
long long ans[MAXN];
int s(long long x) {
	int ans = 0;
	while (x != 0) {
		ans += x % 10;
		x /= 10;
	}
	return ans;
}
int main() {
	long long now = 1e15; now--;
	ans[cnt = 1] = now;
	while (now) {
		bool found = false;
		int bits = s(now);
		for (long long base = 1; !found; base *= 10) {
			for (int j = 1; j <= 9; j++) {
				long long tmp = now - base * j;
				if (tmp * bits <= now * s(tmp)) {
					found = true;
					now = tmp;
					break;
				}
			}
		}
		ans[++cnt] = now;
	}
	cnt--;
	sort(ans + 1, ans + cnt + 1);
	int T; read(T);
	for (int i = 1; i <= T; i++)
		writeln(ans[i]);
	return 0;
}

【E】Independence

【思路要点】

若两个点之间没有边，那么它们显然不能够被分在同一组。
因此若原图的反图不是二分图，问题无解。
否则，记原图反图的每一个联通块中二分图两部分的点数分别为(x_i)、(y_i)。我们希望交换一些(x_i)、(y_i)使得(sum x_i)最接近(frac{N}{2})。
简单背包即可，时间复杂度(O(N^2))。

【代码】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 705;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, m, cnt[2], tot, x[MAXN], y[MAXN];
bool vis[MAXN], col[MAXN], a[MAXN][MAXN], dp[MAXN][MAXN];
void dfs(int pos) {
	vis[pos] = true;
	cnt[col[pos]]++;
	for (int i = 1; i <= n; i++)
		if (a[pos][i] == false) {
			if (!vis[i]) {
				col[i] = !col[pos];
				dfs(i);
			} else if (col[i] == col[pos] && i != pos) {
				printf("-1n");
				exit(0);
			}
		}
}
int main() {
	read(n), read(m);
	for (int i = 1; i <= m; i++) {
		int x, y; read(x), read(y);
		a[x][y] = a[y][x] = true;
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			cnt[0] = cnt[1] = false;
			dfs(i);
			tot++;
			x[tot] = cnt[0];
			y[tot] = cnt[1];
		}
	}
	dp[0][0] = true;
	for (int i = 1; i <= tot; i++)
	for (int j = 0; j <= n; j++)
		if (dp[i - 1][j]) {
			dp[i][j + x[i]] = true;
			dp[i][j + y[i]] = true;
		}
	int ans = n * n;
	for (int i = 0; i <= n; i++)
		if (dp[tot][i]) chkmin(ans, i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);
	writeln(ans);
	return 0;
}

【F】Eating Symbols Hard

【思路要点】

考虑对一个方案进行哈希：令一个方案的哈希值为(Hash(S)=sum_{i=-infty}^{+infty}A_iX^i Mod M)，其中(X)为一个随机数，(M)为一个大质数。该哈希函数有以下性质：
1、(Hash(+S)=Hash(S)+1)
2、(Hash(-S)=Hash(S)-1)
3、(Hash(>S)=Hash(S)*X)
4、(Hash(<S)=Hash(S)*X^{-1})
定义函数(pls(Hash(S)))为在(S)前添加一个(+)后得到的字符串的哈希值。
显然有(pls(Hash(S))=Hash(S)+1)，也即(Hash(S)=pls(Hash(S))-1)。
定义(pls^{-1}(Hash(S)))为在(S)前删除一个(+)后得到的字符串的哈希值，称为上述函数的逆函数，有(pls^{-1}(Hash(S))=Hash(S)-1)。
类似的，我们可以对剩余的三个操作也定义以上函数。
令(f_{r,l}(x))表示用(S_r)到(S_l)的字符对应的函数依次操作(x)得到的结果。
令(f^{-1}_{r,l}(x))表示用(S_r)到(S_l)的字符对应的逆函数依次操作(x)得到的结果。
令(c=f_{n,1}(0))，我们希望统计(f_{j,i}(0)=c)的((i,j)(i≤j))的数量。
(f_{j,i}(0)=cLeftrightarrow f^{-1}_{i,N}(f_{j,i}(0))=f^{-1}_{i,N}(c)Leftrightarrow f^{-1}_{j+1,N}(0)=f^{-1}_{i,N}(c))
对于所有(i)，分别计算(a_i=f^{-1}_{i,N}(c),b_i=f^{-1}_{i+1,N}(0))，然后统计(a_i=b_j(i≤j))的((i,j))数量即可。
注意到所有函数和逆函数均为一次函数，因此它们嵌套起来同样是一次函数，维护一次函数即可计算(a_i)和(b_i)。
取(Cnt)个不同的(X)，减小哈希冲突的概率。
时间复杂度(O(NLogN*Cnt))，取(Cnt=6)。

【代码】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 250005;
const int P = 1e9 + 7;
const int val[6] = {18, 40, 23, 2333333, 58, 720};
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
struct Hash {int val[6]; };
struct info {Hash k, b; };
bool operator < (Hash a, Hash b) {
	for (int i = 0; i <= 5; i++)
		if (a.val[i] != b.val[i]) return a.val[i] < b.val[i];
	return false;
}
map <Hash, int> mp;
char s[MAXN];
int inv[6];
Hash unit() {
	Hash ans;
	memset(ans.val, 0, sizeof(ans.val));
	return ans;
}
info unitinfo() {
	info ans;
	for (int i = 0; i <= 5; i++) {
		ans.b.val[i] = 0;
		ans.k.val[i] = 1;
	}
	return ans;
}
Hash operator * (Hash x, info a) {
	Hash ans;
	for (int i = 0; i <= 5; i++)
		ans.val[i] = (1ll * a.k.val[i] * x.val[i] + a.b.val[i]) % P;
	return ans;
}
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
void pls(Hash &tmp) {
	for (int i = 0; i <= 5; i++)
		tmp.val[i] = (tmp.val[i] + 1) % P;
}
void mns(Hash &tmp) {
	for (int i = 0; i <= 5; i++)
		tmp.val[i] = (tmp.val[i] + P - 1) % P;
}
void rit(Hash &tmp) {
	for (int i = 0; i <= 5; i++)
		tmp.val[i] = (1ll * tmp.val[i] * val[i]) % P;
}
void lft(Hash &tmp) {
	for (int i = 0; i <= 5; i++)
		tmp.val[i] = (1ll * tmp.val[i] * inv[i]) % P;
}
void pls(info &tmp) {
	for (int i = 0; i <= 5; i++)
		tmp.b.val[i] = (tmp.b.val[i] + tmp.k.val[i]) % P;
}
void mns(info &tmp) {
	for (int i = 0; i <= 5; i++)
		tmp.b.val[i] = (tmp.b.val[i] + P - tmp.k.val[i]) % P;
}
void rit(info &tmp) {
	for (int i = 0; i <= 5; i++)
		tmp.k.val[i] = (1ll * tmp.k.val[i] * val[i]) % P;
}
void lft(info &tmp) {
	for (int i = 0; i <= 5; i++)
		tmp.k.val[i] = (1ll * tmp.k.val[i] * inv[i]) % P;
}
int main() {
	for (int i = 0; i <= 5; i++)
		inv[i] = power(val[i], P - 2);
	int n; read(n);
	scanf("n%s", s + 1);
	Hash now = unit();
	for (int i = n; i >= 1; i--) {
		if (s[i] == '+') pls(now);
		if (s[i] == '-') mns(now);
		if (s[i] == '>') rit(now);
		if (s[i] == '<') lft(now);
	}
	Hash tmp = unit(); mp[tmp]++;
	info Now = unitinfo(), Tmp = unitinfo();
	long long ans = 0;
	for (int i = n; i >= 1; i--) {
		if (s[i] == '-') pls(Now), pls(Tmp);
		if (s[i] == '+') mns(Now), mns(Tmp);
		if (s[i] == '<') rit(Now), rit(Tmp);
		if (s[i] == '>') lft(Now), lft(Tmp);
		ans += mp[now * Now];
		mp[tmp * Tmp]++;
	}
	writeln(ans);
	return 0;
}