KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200）题解_ringo's favorite numbers 2题解

KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200）

A - Century

简单的除以$200$向上取整

B - 200th ABC-200

翻译成程序，$while$模拟即可

C - Ringo’s Favorite Numbers 2

差为$200$倍数，则两个数同余$200$，按照模完后的余数分类单独计算即可$C_{r_i}^2$

#include <cstdio>
#define maxn 200005
#define int long long
int n;
int A[maxn], r[205];

signed main() {
	scanf( "%lld", &n );
	for( int i = 1;i <= n;i ++ )
		scanf( "%lld", &A[i] ), r[A[i] % 200] ++;
	int ans = 0;
	for( int i = 0;i < 200;i ++ )
		ans += ( r[i] * ( r[i] - 1 ) / 2 );
	printf( "%lld\n", ans );
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

D - Happy Birthday! 2

设$d{p}_{i,j}:$前$i$个数中选某些数的和模$200$余数为$j$（$i$必选）的方案数

直接大力转移，顺便用维克托儿记录下转移路径，方案数一旦等于$2$即代表有解

因为$DP$定义限制，两个序列的最后一个一定是一样的，这可能导致无法记录下最后一位不一样的方案

所以在原序列后面加一个$0$，这样保证了两个数列的最后一位一定会是一样的

#include <cstdio>
#include <vector>
using namespace std;
#define int long long
#define maxn 205
vector < pair < int, int > > G[maxn][maxn];
int n;
int A[maxn], ans1[maxn], ans2[maxn];
int f[maxn][maxn];

void print( int *ans, int &cnt, int p, int r ) {
	if( ! G[p][r].size() ) return;
	ans[++ cnt] = p;
	print( ans, cnt, G[p][r][0].first, G[p][r][0].second );
}

signed main() {
	scanf( "%lld", &n );
	for( int i = 1;i <= n;i ++ )
		scanf( "%lld", &A[i] );
	A[++ n] = 0;
	f[0][0] = 1;
	int pos, r; bool flag = 1;
	for( int i = 1;i <= n && flag;i ++ )
		for( int j = 0;j < i && flag;j ++ )
			for( int k = 0;k <= 200 && flag;k ++ )
				if( f[j][k] ) {
					f[i][( k + A[i] ) % 200] += f[j][k];
					G[i][( k + A[i] ) % 200].push_back( make_pair( j, k ) );
					if( f[i][( k + A[i] ) % 200] == 2 ) {
						pos = i, r = ( k + A[i] ) % 200;
						flag = 0;
						break;
					}
				}
	if( ! flag ) {
		printf( "Yes\n" );
		int cnt1 = 0, cnt2 = 0, t = 0;
		ans1[++ cnt1] = ans2[++ cnt2] = pos;
		print( ans1, cnt1, G[pos][r][0].first, G[pos][r][0].second );
		print( ans2, cnt2, G[pos][r][1].first, G[pos][r][1].second );
		if( pos == n ) t = 1;
		printf( "%lld", cnt1 - t );
		for( int i = cnt1;i > t;i -- )
			printf( " %lld", ans1[i] );
		printf( "\n%lld", cnt2 - t );
		for( int i = cnt2;i > t;i -- )
			printf( " %lld", ans2[i] );
	}
	else
		printf( "No\n" );
	return 0;
}
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

E - Patisserie ABC 2

设$d{p}_{i,j}$表示选到第$i$个数和为$j$的方案数量

发现状态转移$d{p}_{i,j}\to d{p}_{i+1,j+1},d{p}_{i+1,j+2}...d{p}_{i+1,j+n}$是连续段转移，用差分即可

接着线性即可扫出总和，然后枚举美丽度，计算出味道的取值范围，进而确定味道，自然而然就确定了欢迎度

#include <cstdio>
#include <iostream>
using namespace std;
#define int long long
int dp[4][3000005];
int n, k;

signed main() {
	scanf( "%lld %lld", &n, &k );
	dp[0][0] = 1;
	for( int i = 0;i < 3;i ++ ) {
		for( int j = 0;j <= i * n;j ++ ) {
			dp[i + 1][j + 1] += dp[i][j];
			dp[i + 1][j + n + 1] -= dp[i][j];
		}
		for( int j = 1;j <= ( i + 1 ) * n;j ++ )
			dp[i + 1][j] += dp[i + 1][j - 1];
	}
	int sum;
	for( int i = 3;i <= 3 * n;i ++ )
		if( dp[3][i] >= k ) {
			sum = i;
			break;
		}
		else
			k -= dp[3][i];
	for( int beauty = 1;beauty <= n;beauty ++ ) {
		int minn = max( 1ll, sum - beauty - n );
		int maxx = min( n, sum - beauty - 1 );
		if( minn > maxx ) continue;
		if( k > maxx - minn + 1 ) k -= ( maxx - minn + 1 );
		else {
			int taste = minn + k - 1;
			return ! printf( "%lld %lld %lld\n", beauty, taste, sum - beauty - taste );
		}
	}
	return 0;
}
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

F - Minflip Summation

对于每种可能串$T$，设 S = { i ∣ T i ≠ T i + 1 } , i ∈ [ 0 , l e n ) S=\{i|T_i≠T_{i+1}\},i∈[0,len) S={i∣Ti​​=Ti+1​},i∈[0,len)，举个栗子T=010110，S={0,1,2,4}

改写每次对一段l,r进行操作
{ l ≠ 1 α ( l − 1 ) r ≠ l e n − 1 α ( r )

$$\begin{cases} l≠1&&\alpha(l-1)\\ r≠len-1&&\alpha(r)\\ \end{cases}$$ \\ {l​=1r​=len−1​​α(l−1)α(r)​
$\alpha (i):$如果$T_i\ne T_{i+1}$，把$i$从$S$中删掉，否则加入其中

最后答案形态则是$S=\varnothing$

不难发现，每次最多会从$S$中删去两个数，所以最后的答案为$\lceil \frac{tot}{2}\rceil$($tot=|S|$)

接下来考虑统计所有情况串中相邻两个字符不同的数量

$cnt=2^{kq}\times (k\times {\sum }_{i=0}^{len-1}f(i,i+1)+(k-1)\times f_{len,0})$
f i , j = { 1 2 ( T i = ? ) ∣ ( T j = ? ) 1 ( T i ≠ T j ) 0 ( T i = T j ) f_{i,j}=

$$\begin{cases} \frac{1}{2}&&&(T_i=?)|(T_{j}=?)\\ 1&&&(T_i≠T_j)\\ 0&&&(T_i=T_j) \end{cases}$$ fi,j​=⎩⎪⎨⎪⎧​21​10​​​(Ti​=?)∣(Tj​=?)(Ti​​=Tj​)(Ti​=Tj​)​

简单讨论一下

• $T_i=T_j=0/1$，那么对于$2^{kq}$种情况的字符串$i$都不可能被算进$S$，贡献$0$
• $T_i=0/1,T_j=1/0,T_i\ne T_j$，同理对于$2^{kq}$种情况的字符串$i$都会被算进$S$，贡献$1$
• 只有一个是$?$，那么只有$\frac{1}{2}$的概率贡献$1$，与另一个确定的字符不一样
• 两个都是$?$，一共有$4$种情况，两种相同（都是$1$，都是$0$），概率同样是$\frac{1}{2}$

重复$K$次原串，那么除了首尾少一次，其余都要$\times k$

但是这里仍然存在有一点小问题。

10100有三对相邻字符不一样，101001有四对相邻字符不一样，但是都需要花费$2$次操作

我们本意是想上取整，但是在模意义下非常难搞

事实上，对于一个有奇数对相邻字符不一样的串，重复多次后，理想与实际操作之间是恒定的

举个例子，101100，三对不一样，花费$2$，实际算的是$1$，重复一遍101100101100，七对不一样，花费$4$，实际算的是$3$……

归纳一下，也就是说对于奇数对的串答案总是少了$1$

加上这奇数对串的个数即为正确结果

不难发现，奇数对串的个数恰恰为首尾字符不相等的个数，$2^{kq}\times f(T_0,T_{len-1})$

所以最后的答案是$cnt=2^{kq}\times k\times {\sum }_{i=0}^{len-1}f(i,(i+1)\%len))$

#include <cstdio>
#include <cstring>
#define int long long
#define mod 1000000007
#define maxn 100005
char s[maxn];
int k, inv, ans;

int qkpow( int x, int y ) {
	int ans = 1;
	while( y ) {
		if( y & 1 ) ans = ans * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return ans;
}

int f( char x, char y ) {
	if( x == '?' || y == '?' ) return inv;
	else if( x != y ) return 1;
	else return 0;
}

signed main() {
	scanf( "%s %lld", s, &k );
	int len = strlen( s );
	if( len * k == 1 ) return ! printf( "0\n" );
	int tot = 0;
	inv = qkpow( 2, mod - 2 );
	for( int i = 0;i < len;i ++ )
		tot += ( s[i] == '?' );
	int t = qkpow( 2, k * tot ) * k % mod;
	for( int i = 0;i < len;i ++ )
		ans = ( ans + t * f( s[i], s[( i + 1 ) % len] ) % mod ) % mod;
	ans = ans * inv % mod;
	printf( "%lld\n", ans );
	return 0;
}
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