CUC-Spring-Traning-Contest题解
Primo Pan
  2022-05-18 19:01:54 2022-05-18 19:01    

D - Yet Another Palindrome Partitioning

【题目大意】

给你一坨字符串，现在你可以分割它，问你最少分割成多少个子串可以使每个子串重新排列后能成为一个回文串。

【题解】

观察一下回文串的性质，长度为偶数的回文串中所有字母的出现次数必定是偶数，而长度为奇数的回文串是在长度为偶数的回文串的基础上加一个出现次数为奇数的字母。

所以我们用一个26位的二进制数表示读入到当前这个位置的字母时每个字母出现的次数的奇偶性，如果当前这个状态某字母出现次数是奇数则该位为奇数。然后我们枚举出现次数为奇数的那个字母，如果当前状态的该位和这个字母的奇偶性不一样那么就可以转移了。 

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
#include <bits/stdc++.h>
using namespace std;
#define maxn 200010
const int maxm=1<<26;
#define INF 0x3f3f3f3f
int dp[maxm];
char s[maxn];
int idx(char x)
{
	int ans=x-'a';
	return 1<<ans;
}
int main()
{
	memset(dp,INF,sizeof(dp));
	cin>>s;
	int n=strlen(s);
	dp[0]=0;
	int now=idx(s[0]);
	dp[now]=1;
	for (int i=1;i<n;i++)
	{
		now^=idx(s[i]);
		for (int j=0;j<=25;j++)
		{
			if (now^(1<<j)!=now) dp[now]=min(dp[now],dp[now^(1<<j)]+1);
		}
	}
	if (now==0) dp[now]=1;
	printf("%d\n",dp[now]);
	return 0;
}

E - Martian Strings

【题目大意】

给你一个文本串T,对于每个询问串问你是不是可以将T拆成两个连续子串拼成每个询问串.

【题解】

z algorithm可以线性地搞出来一个字符串的每个后缀和它自身的最长公共前缀.

我们把每个询问串s搞成s的形式跑一遍再把和倒过来搞一个T’再跑一遍z algorithm,然后在第一个T的z数组里跑对于每个能匹配一部分的点看它在T’中对应的点的前面是否能拼成这个串..(非常抽象..看代码…)

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
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
#define maxm 1005
#define ll long long
ll ans=0;
char S[maxn],S2[maxn],s[maxn+maxm],t[maxn+maxm];
char t1[maxm],t2[maxm];
int z1[maxn+maxm],z2[maxn+maxm];
inline void getz(int *z,int sz)
{
		z[0]=sz;
		int j=1,k;
		for (int i=1;i<sz;i=k)
		{
			if (j<i) j=i;
			while (s[j-i]==s[j] && j<sz) j++;
			z[i]=j-i;
			k=i+1;
			while (k+z[k-i]<j) k++;
		}

}
int main()
{
	cin>>S;
	int N=strlen(S);
	for (int j=0,cnt=N-1;cnt>=0;j++,cnt--) S2[j]=S[cnt];
	int T;
	cin>>T;
	while (T--)
	{
		memset(z1,0,sizeof(z1));memset(z2,0,sizeof(z2));
		cin>>t1;
		int M=strlen(t1);
		if (M<2 || M>N) continue;
		for (int j=0,cnt=M-1;cnt>=0;j++,cnt--) t2[j]=t1[cnt];
		for (int i=0;i<M;i++) s[i]=t1[i];
		s[M]='$';
		for (int i=M+1,j=0;j<N;j++,i++) s[i]=S[j];
		getz(z1,N+M+1);
		for (int i=0;i<M;i++) s[i]=t2[i];
		s[M]='$';
		for (int i=M+1,j=0;j<N;j++,i++) s[i]=S2[j];
		getz(z2,N+M+1);
		for (int i=1;i<=N;i++) z1[i]=z1[i+M];
		for (int i=1;i<=N;i++) z2[i]=z2[i+M];
		z2[0]=0;
		for (int i=1;i<=N;i++) z2[i]=max(z2[i],z2[i-1]);
		for (int i=1;i<=N;i++){
			if (z1[i]!=0) {int pos=z1[i]+i-1+(M-z1[i]);
				pos=N-pos+1;
				if (pos<1 || pos>N) continue;
				if (z2[pos]+z1[i]>=M) {ans++;break;}
	}}}
	cout<<ans<<endl;
}

F - Promising String (hard version)

题目大意

给你一个长度为n，只包含+-符号的字符串。连续两个-可以合并成一个+。问你该字符串中有多少子串满足，经过一些合并（或没有合并）后子串中+-号数量相等。

题解

上结论： 子串中-的个数比+多，且差值是3的倍数，则记一次贡献。

首先根据狄利克雷原理（抽屉原理），如果-的个数比+多于2个即一定有两个-相连。并且进行一次操作后，+-号的差异度会+3。那么就可以进行很多次操作将差异度变为0。

这题有小数据，那么对于小数据，O(n^2)的暴力为（假设一开始差异度为n）。 

1
2
3
4
5
6
7
8
9
cur=n;
for (int i=0;i<n;i++)
{
    cur+=(s[i]=='+')?1:-1;
    dp[i]=cur;
    for (int j=0;j<i;j++)
        if (s[j]>s[i] && (s[j]-s[i])%3==0)
            ans++;//[j,i]为合理区间
}

考虑优化这个的暴力，如果把cur模3 ，那么当前右端点的贡献就是左侧所有比它大的%3剩余系的值。看到很多人写了一个log级的数据结构，但观察到差异度最大值为2n-1，不是很大，所以直接可以开个表记录一下，O(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
inline void solve()
{
	int n;
	cin>>n;
	string s;
	cin>>s;
	int lim=2*n+1;
	int lst=n;
	vector<int> f (3,0);
	vector<int> cnt (lim,0);
	f[lst%3]++;
	cnt[lst]++;
	ll ans=0;
	for (int i=0;i<n;i++)
	{
		int cur=lst;
		if (s[i]=='+')
		{
			f[cur%3]-=cnt[cur];//比cur小的不能用了
			cur++;
			ans+=f[cur%3];
			f[cur%3]++;
			cnt[cur]++;
		}
		else{
			cur--;
			f[cur%3]+=cnt[cur];//小于等于cur的都能用
			ans+=f[cur%3];
			f[cur%3]++;
			cnt[cur]++;
		}
		lst=cur;
	}
	cout<<ans<<endl;
}

G - Jumping on Walls

暴力DFS即可…

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
#include<stdio.h>  
#include<string.h>  
#include<math.h>  
#include<stdlib.h>  
#include<queue>  
#include<vector>  
#include <bits/stdc++.h>  
using namespace std;  
const int maxn=1e5+100;  
int n,m,water;  
char a[2][maxn];  
int v[2][maxn];  
int dfs(int pos,int j){  
    if(j>n) return 1;  
    if(a[pos][j]=='X'||j<water||v[pos][j]) return 0;  
    v[pos][j]=1;  
    water++;  
    int f=dfs(pos,j-1)||dfs(1-pos,j+m)||dfs(pos,j+1);  
    water--;  
    return f;  
}  
int main(){  
  
    scanf("%d %d",&n,&m);  
        water=1;  
        scanf("%s %s",a[0]+1,a[1]+1);  
        if(dfs(0,1)) printf("YES\n");  
        else printf("NO\n");  
    return 0;  
}