Streaming#5模拟赛

Posted on | In
Words count in article: 2,124 | Reading time ≈ 11

Streaming#5 题解报告

T1.珠

题目大意 : 给你一个长度为\(n\)的数字环, 你可顺时针或者逆时针选择一个子序列, 满足子序列的以\(2\)开头, 后面的数字都是\(3\), 求最长子序列

题解 : 我们考虑对于每一个数字为\(2\)的位置向左边和右边二分一个位置, 使得这个位置到数字\(2\)中间全是\(3\), 所以我们必须得先处理处两个数组\(preL, preR\), 表示从一个为\(3\)的位置向左向右全部都是\(3\)的结束位置, 这样就可以二分了, 特别的如果你向右边二分出的位置为这个序列的末尾, 那你必须从这个序列的开头再次二分一个位置, 因为这个是一个环, 头尾可以相接

复杂度为\(O(nlogn)\)

代码 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 2e5 + 5;
const int inf = 1e9 + 5;

int posR[maxn], posL[maxn], ans, L, R, n;

char s[maxn];

inline int binaryR(int l, int r, int i){
	int mid = (l + r) / 2, ans = l - 1;
	while(l <= r){
		mid = (l + r) / 2;
		if(posR[mid] == i)l = mid + 1, ans = mid;
		else r = mid - 1;
	} return ans;
}

inline int binaryL(int l, int r, int i){
	int mid = (l + r) / 2, ans = r + 1;
	while(l <= r){
		mid = (l + r) / 2;
		if(posL[mid] == i)r = mid - 1, ans = mid;
		else l = mid + 1;
	} return ans;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("beads.in", "r", stdin);
	freopen("beads.out", "w", stdout);
#endif
	scanf("%s", s + 1); n = strlen(s + 1);
	for(register int i = 1; i <= n; i++)
		if(s[i] == '3')posR[i] = (s[i - 1] == s[i]) ? posR[i - 1] : i;
		else posR[i] = inf;
	for(register int i = n; i >= 1; i--)
		if(s[i] == '3')posL[i] = (s[i + 1] == s[i]) ? posL[i + 1] : i;
		else posL[i] = -inf;
	for(register int i = 1; i <= n; i++){
		if(s[i] != '2')continue;
		R = binaryR(i + 1, n, i + 1), L = binaryR(1, i - 1, 1);
		ans = max(ans, R - i + 1 + L * (R == n));
		R = binaryL(i + 1, n, n), L = binaryL(1, i - 1, i - 1);
		ans = max(ans, i - L + 1 + (n - R + 1) * (L == 1));
	}
	if(ans == 0)puts("TvT");
	else {
		putchar('2');
		for(register int i = 1; i < ans; i++)putchar('3');
	}
	return 0;
}
/*
323

333

2332323333

33332233233
*/

T2.免农

题目大意 : 一开始你有两个免子, 下一个时刻, 你的免子会变成当前时刻的两倍, 然后我们会将这些免子分为若干组, \(k\)个为一组, 特别的如果存在一组, 这一组里只有一个免子, 那么这个免子就会死去, 求\(n\)时刻时免子的个数对\(p\)取余的结果

题解 :

  • 考虑如果\(k\)为偶数的话, 是不会存在单个免子为一组的, 所以最后的答案就是\(2^{n + 1} \% p\)
  • 如果\(k\)为奇数的话, 当\(2^{q} \% k == 1\)的话那么在\(q\)时刻之后, 就不会有免子再会落单了, 并且可以证明在\(k\)个时刻以内, 一定存在一个时刻\(t\), 使得\(2^t \% k == 1\), 所以直接模拟就好了

复杂度\(O(min(k, n))\)

代码 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e5 + 5;

LL n, k, p, now, ans;

inline LL read(){
	char ch = getchar(); LL u = 0, f = 1;
	while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
	while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline LL ksm(LL x, LL k){
	LL cnt = 1;
	while(k){
		if(k & 1)cnt = cnt * x % p;
		x = x * x % p; k >>= 1;
	} return cnt;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("rabit.in", "r", stdin);
	freopen("rabit.out", "w", stdout);
#endif
	n = read(); k = read(); p = read();
	now = 2 % k; ans = 2;
	if(!(k & 1)){cout << ans * ksm(2, n) % p; return 0;}
	while(now != 1 && n > 0){
		now = 2 * now % k;
		ans = 2 * ans % p;
		n--;
	} if(now == 1)ans--;
	cout << (ans + p) % p * ksm(2, n) % p;
	return 0;
}
/*
6 7 10086

*/

T3.高维网络

题目大意 : 现在有一个\(d\)维空间, 起始坐标为\(A(0, 0, ...., 0)\), 结束坐标为\(B(a_1, a_2, ...., a_d)\), 现在有\(p\)个坐标上设有障碍, 并且每一步只能在某一个维度上走一步, 也就是说只能这样转移 : \[ (0, 0, ...., 0) -> (1, 0, ...., 0) or (0, 0,...., 0) -> (0, 1, ...., 0) \] 求从起点走到终点不经过障碍有多少种方案, 输出方案数对\(P\)取余后的结果

题解 :

我们先考虑没有障碍的情况, 从\(x(s_1, s_2, ...., s_d)\)移动到\(y(t_1, t_2, ...., t_d)\)有多少种方案, 首先我们设数组\(tmp_i = t_i - s_i\), 其后缀和为\(S\), 那么我们一定会走\(\sum_{i = 1}^{d}tmp_i\)步, 前\(tmp_1\)步我们可以任意分配就有\(C_{S_1}^{tmp_1}\)种方案, 然后我们依次分配步数就可以知道方案数为 : \[ Paths(x, y) = \prod_{i = 1} ^ {i \leq d} C_{S_i}^{tmp_i} \] 然后如果直接容斥的话复杂度为\(O(2^p \cdot d \cdot logP)\), 实测可以获得\(80\)分的好成绩

我们现在再考虑\(dp\), \(f[i]\)表示从起点到第\(i\)个障碍点并且不经过任何障碍点的方案数, 不难得出转移方程为 : \[ f[i] = Paths(A, i) - \sum_{i \ne j} f[j] * Paths(j, i) \] \(PS\) :

  • 注意\(Paths(x, y)\)有方向性, 表示从\(x\)转移到\(y\)可以经过任意障碍的方案数
  • 并且这个\(dp\) 的转移顺序必需是从最靠近起点\(A\)的障碍点开始转移, 不然会有问题

\(Update\) : 我们来考虑一下这个\(dp\)的正确性, 我们可能会想这样\(dp\)会不会减掉一些重复的路径, 比如说有三个点\(i, j, k\), \(i\)可以到达\(j\), \(j\)可以到达\(k\), 在转移的时候我们会将 \[ f[i] * Paths(i, k) \& \& f[j] * Paths(j, k) \] 都减掉, 这样会不会有问题呢?

实际上是不会的, 我们注意到\(f[i]\)的定义是指从\(A\)到\(i\)号障碍点不经过任何其他障碍的路径方案数, 所以\(f[j]\)中的方案数是不包括\(f[i] * Paths(i, j)\)的, 所以这样\(dp\)的正确性是有保障的, 最终复杂度为\(O(p ^ 2 \cdot d \cdot logP)\)这样的复杂度是正确的

代码 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e7 + 5;
const int inf = 1e9 + 5;
const int P = 1e9 + 7;
const int zero = 0;

int a[105], d, p, fac[maxn], s[105], pos[505][105], tmp[105], ans, sum, Q[505];
int f[505];

inline int read(){
	char ch = getchar(); int u = 0, f = 1;
	while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
	while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline int ksm(int x, int k){
	int cnt = 1;
	while(k){
		if(k & 1)cnt = 1ll * cnt * x % P;
		x = 1ll * x * x % P; k >>= 1;
	} return cnt % P;
}

inline int calc(int *S, int *T){
	int ans = 1;
	for(register int i = 1; i <= d; i++){
		tmp[i] = abs(T[i] - S[i]);
		if(S[i] > T[i])return zero;
	}
	for(register int i = d; i >= 1; i--)
		s[i] = s[i + 1] + tmp[i];
	for(register int i = 1; i <= d; i++){
		int C = 1;
		C = 1ll * C * ksm(fac[s[i] - tmp[i]], P - 2) % P;
		C = 1ll * C * ksm(fac[tmp[i]], P - 2) % P * fac[s[i]] % P;
		ans = 1ll * ans * C % P;
	} return ans % P;
}

inline bool cmp(int x, int y){
	for(register int i = 1; i <= d; i++)
		if(pos[x][i] != pos[y][i]) return pos[x][i] < pos[y][i];
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("cube.in", "r", stdin);
	freopen("cube.out", "w", stdout);
#endif
	d = read(); p = read(); fac[1] = 1; fac[0] = 1;
	for(register int i = 1; i <= d; i++)
		sum += (a[i] = read());
	for(register int i = 2; i <= sum; i++)
		fac[i] = 1ll * fac[i - 1] * i % P;
	for(register int i = 1; i <= p; i++)
		for(register int j = 1; j <= d; j++)
			pos[i][j] = read();
	for(register int i = 1; i <= p; i++)Q[i] = i;
	sort(Q + 1, Q + 1 + p, cmp);
	ans = calc(pos[0], a);
	//cout << "ans = " << ans << endl;
	/*for(register int i = 1; i <= p; i++){
		cout << Q[i] << " : ";
		for(register int j = 1; j <= d; j++)
			cout << pos[Q[i]][j] << " ";
		cout << endl;
	}*/
	for(register int i = 1; i <= p; i++){
		f[Q[i]] = calc(pos[0], pos[Q[i]]);
		for(register int j = 1; j <= p; j++)
			if(Q[i] != Q[j])
				f[Q[i]] = (f[Q[i]] - 1ll * f[Q[j]] * calc(pos[Q[j]], pos[Q[i]]) % P + P) % P;
		//cout << "f[" << Q[i] << "] = " << f[Q[i]] << endl;
	}
	for(register int i = 1; i <= p; i++)
		ans = (ans - 1ll * f[i] * calc(pos[i], a) % P + P) % P;
	cout << ans;
	return 0;
}
/*
2 1
2 1
1 0

2 1
2 1
2 0

*/

Summary

  • 推容斥式子时不要想当然, 想清楚再打

水水水

咕咕咕