牛客练习赛95 A~E

A：Duplicate Strings

给你一个字符串，有两个操作：把这个复制复制若干次接在后面，或者输出一个字符在这个串中的出现次数。

思路

可以一开始直接记录每个字符的出现次数，然后每操作一遍每个的出现次数就乘上 $x + 1$ （ $x$ 是复制的次数）然后询问就可以直接输出了。

代码

#include<cstdio>
#define ll long long
#define mo 1000000007

using namespace std;

int n, q, x;
ll num[26], t;
char c;

int main() {
	scanf("%d %d", &n, &q);
	
	t = 1;
	c = getchar(); while (c < 'a' || c > 'z') c = getchar();
	while (c >= 'a' && c <= 'z') {
		num[c - 'a']++; c = getchar();
	}
	
	for (int i = 1; i <= q; i++) {
		scanf("%d", &x);
		if (x == 1) {
			scanf("%d", &x);
			t = t * (x + 1) % mo;
		}
		else {
			c = getchar(); while (c < 'a' || c > 'z') c = getchar();
			printf("%lld\n", num[c - 'a'] * t % mo);
		}
	}
	
	return 0;
}

B：Non-interger Area

给你一个平面上若干个点，然后问你有多少个三角形的面积不是整数。

思路

考虑用叉积。

然后你发现它就跟每个点的奇偶有关。然后你分类讨论一下，算一算每个的种数即可。（其实可以不用像我这样算，这样太麻烦了，直接在每次输入的时候算它跟别人的贡献即可）

代码

#include<cstdio>
#define ll long long

using namespace std;

int n;
ll x, y, kd[2][2], ans;
bool in[2][2][2][2][2][2];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld %lld", &x, &y);
		kd[x & 1][y & 1]++;
	}
	
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++) {
			for (int ii = 0; ii < 2; ii++) {
				for (int jj = 0; jj < 2; jj++) {
					for (int iii = 0; iii < 2; iii++)
						for (int jjj = 0; jjj < 2; jjj++) {
							if (in[i][j][ii][jj][iii][jjj]) continue;
							in[i][j][ii][jj][iii][jjj] = in[i][j][iii][jjj][ii][jj] = 1; 
							in[ii][jj][iii][jjj][i][j] = in[ii][jj][i][j][iii][jjj] = 1;
							in[iii][jjj][ii][jj][i][j] = in[iii][jjj][i][j][ii][jj] = 1;
							ll num = kd[i][j] * kd[ii][jj] * kd[iii][jjj];
							if (i * 2 + j == ii * 2 + jj && i * 2 + j == iii * 2 + jjj) {num = kd[i][j] * (kd[i][j] - 1) * (kd[i][j] - 2) / 6; if (kd[i][j] < 3) continue;}
								else if (i * 2 + j == ii * 2 + jj) {num = kd[i][j] * (kd[i][j] - 1) / 2 * kd[iii][jjj]; if (kd[i][j] < 2) continue;}
									else if (i * 2 + j == iii * 2 + jjj) {num = kd[i][j] * (kd[i][j] - 1) / 2 * kd[ii][jj]; if (kd[i][j] < 2) continue;}
										else if (ii * 2 + jj == iii * 2 + jjj) {num = kd[ii][jj] * (kd[ii][jj] - 1) / 2 * kd[i][j]; if (kd[ii][jj] < 2) continue;}
							if (((ii - i) * (jjj - j) - (iii - i) * (jj - j)) & 1) ans += num;
						}
				}
			}
		}
	printf("%lld", ans);
	
	return 0;
}

C：Division

给您一个数列，每次你可以选一个长度大于一个给出大小的区间的数把它们都除以 $2$ ，然后问你最少要多少次操作把所有数变成 $1$ 。

思路

首先不难看出我们可以直接算出每个数能除且要除多少次。然后就变成一个数列你每次可以选一个长度大于一个给出大小的区间集体减一问你最少要减多少次才能变成 $0$ 。

考虑一路扫过去，要增加左端点的就增加（比上一个要减的多了），要放右端点匹配的就跟最早放的匹配（这样贪心肯定没问题）（这种就是比上一个要减的少了）。

代码

#include<queue>
#include<cstdio>
#define ll long long

using namespace std;

int T, n, k, a[10001];
queue <int> q;
ll x, ans, an[500001][2], l;

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d", &n, &k);
		for (int i = 1; i <= n; i++) {
			scanf("%lld", &x);
			a[i] = 0;
			while (x > 1) {
				x >>= 1; a[i]++;
			}
		}
		
		bool no = 0;
		while (!q.empty()) q.pop(); ans = 0; l = 1;
		for (int i = 1; i <= a[1]; i++) q.push(1), an[++ans][0] = 1;
		for (int i = 2; i <= n; i++) {
			if (a[i] > a[i - 1]) {
				for (int j = 1; j <= a[i] - a[i - 1]; j++) q.push(i), an[++ans][0] = i;
			}
			if (a[i] < a[i - 1]) {
				for (int j = 1; j <= a[i - 1] - a[i]; j++) {
					int now = q.front(); q.pop();
					if ((i - 1) - now + 1 < k) {
						no = 1; break;
					}
					an[l++][1] = i - 1;
				}
				if (no) break;
			}
		}
		if (!no) {
			while (!q.empty()) {
				int now = q.front(); q.pop();
				if (n - now + 1 < k) {
					no = 1; break;
				}
				an[l++][1] = n;
			}
		}
		
		if (no) printf("-1\n");
			else {
				printf("%lld\n", ans);
				for (int i = 1; i <= ans; i++) printf("%lld %lld\n", an[i][0], an[i][1]);
			}
	}
	
	return 0;
}

D：gcd

给你 n 个区间，然后每个区间可以选一个整数出来，然后对答案的贡献是它们的 gcd 的约数个数。然后问你所有情况的贡献和。

思路

我们考虑可以直接这样看一组情况的贡献：找有多少个数都能整除选出的数。

那我们对于每个这些数，如果它要贡献，那它会存在的方案数就是每个区间中满足的数的乘起来。那每个区间有多少个数呢？可以用整除和前缀和： $\left\lfloor \dfrac{r}{x}\right\rfloor-\left\lfloor \dfrac{l-1}{x}\right\rfloor$

那要怎么加速这个过程？显然可以整合分块。（就每个除都整除分块一下搞）

然后我们可以用类似差分的方法来维护。然后发现如果乘了 $0$ 会有问题，所以我们可以单独维护每个是否为 $0$ ，打个标记什么的，到时直接用。

代码

#include<cstdio>
#include<vector>
#define ll long long 
#define mo 998244353

using namespace std;

int n, l, r;
ll ans, c[300001], answer;
ll inv[300001], b[300001];

int main() {
	inv[0] = inv[1] = 1;
	for (int i = 2; i <= 300000; i++)
		inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i = 0; i <= 300000; i++) c[i] = 1;
	
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &l, &r);
		int x = l - 1, y = r;
		for (int L = 1, R; L <= y; L = R + 1) {
			R = y / (y / L);
			if (L <= x) R = min(R, x / (x / L));
			ll val = y / L - x / L;
			if (val) c[L] = c[L] * val % mo, c[R + 1] = c[R + 1] * inv[val] % mo;
				else b[L]++, b[R + 1]--;
		}
		b[r + 1]++; 
	}
	
	for (int i = 1; i <= 300000; i++) c[i] = c[i] * c[i - 1] % mo;
	for (int i = 1; i <= 300000; i++) {
		b[i] += b[i - 1]; if (b[i]) c[i] = 0;
		answer = (answer + c[i]) % mo;
	}
	
	printf("%lld", answer);
	
	return 0;
}

E：Painting Fences

给你一个序列，然后一开始所有位置都可以填 $1\sim m$ 的数。然后一个序列的分数是它有多少个最长相同数字段。然后有若干次操作：约束一个位置不能填某个数，或者取消某个约束。然后一开始和每次操作后问你期望序列分数是多少。

思路

我们可以发现我们可以假设一开始的分数是 $1$ ，然后如果某两个之间颜色不同，那分数就加一。或者一开始的分数是 $n - 1$ ，然后如果某两个颜色相同，分数就减一。

那我们可以维护相邻两个颜色相同的贡献。具体来讲，我们可以通过维护它们两个共有的颜色 $b o t h$ ，以及它们两个分别有的颜色 $c x, c y$ ，算出它们的相同期望是 $\dfrac{both}{cx*cy}$ 。

然后每次修改就先减去之间的修改完再加回去即可。然后记得维护这个 $b o t h$ 和 $c$ 。

代码

#include<map>
#include<cstdio>
#define ll long long
#define mo 998244353

using namespace std;

ll n, m, q, can[300001], both[300001], ans;
ll op, x, y, rx[300001], ry[300001];
map <ll, ll> no[300001];

ll ksm(ll x, ll y) {
	ll re = 1;
	while (y) {
		if (y & 1) re = re * x % mo;
		x = x * x % mo; y >>= 1;
	} 
	return re;
}

ll inv(ll x) {
	return ksm(x, mo - 2);
}

int main() {
	scanf("%lld %lld %lld", &n, &m, &q);
	for (int i = 1; i <= n; i++) {
		can[i] = m;
		if (i != n) both[i] = m;
	}
	
	ans = ((n - 1) * (m - 1) % mo * inv(m) + 1) % mo;
	printf("%lld\n", ans);
	for (int qq = 1; qq <= q; qq++) {
		scanf("%lld", &op);
		if (op == 1) {
			scanf("%lld %lld", &x, &y);
			rx[qq] = x; ry[qq] = y;
			if (x > 1) ans = (ans - (1 - both[x - 1] * inv(can[x - 1] * can[x] % mo) % mo) + mo) % mo;
			if (x < n) ans = (ans - (1 - both[x] * inv(can[x] * can[x + 1] % mo) % mo) + mo) % mo;
			if (x > 1 && !no[x - 1][y]) both[x - 1]--;
			if (x < n && !no[x + 1][y]) both[x]--;
			no[x][y] = 1; can[x]--;
			if (x > 1) ans = (ans + (1 - both[x - 1] * inv(can[x - 1] * can[x] % mo) % mo) + mo) % mo;
			if (x < n) ans = (ans + (1 - both[x] * inv(can[x] * can[x + 1] % mo) % mo) + mo) % mo;
		}
		else {
			scanf("%lld", &x);
			y = ry[x]; x = rx[x];
			if (x > 1) ans = (ans - (1 - both[x - 1] * inv(can[x - 1] * can[x] % mo) % mo) + mo) % mo;
			if (x < n) ans = (ans - (1 - both[x] * inv(can[x] * can[x + 1] % mo) % mo) + mo) % mo;
			if (x > 1 && !no[x - 1][y]) both[x - 1]++;
			if (x < n && !no[x + 1][y]) both[x]++;
			no[x][y] = 0; can[x]++;
			if (x > 1) ans = (ans + (1 - both[x - 1] * inv(can[x - 1] * can[x] % mo) % mo) + mo) % mo;
			if (x < n) ans = (ans + (1 - both[x] * inv(can[x] * can[x + 1] % mo) % mo) + mo) % mo;
		}
		printf("%lld\n", ans);
	}
	
	return 0;
}