NOIP2022模拟赛 8

, ,

T1

因为 $f(a)=f(b)=f(c)$ ，所以 $a,b,c$ 三个数模三同余。

所以 $n$ 一定是三的倍数才有解。

对于三的倍数，直接除以三。

否则输出无解。

code:

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
#include<bits/stdc++.h>
#define maxn 20005
#define ll long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}
int a[maxn],n;
inline void READ(void) {
	char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') a[++n]=ch-'0',ch=getchar();
}
int ans[maxn];
signed main(void){
//	freopen("1.in","r",stdin);
	READ();
	int i,j,tot=0;
	for (i=1;i<=n;i++) tot+=a[i];
	if (n==1&&a[1]==0) return puts("0 0 0"),0;
	if (tot%3) return puts("-1"),0;
	for (i=1;i<=n;i++) {
		ans[i]+=a[i]/3;
		a[i+1]+=a[i]%3*10;
	}
	tot=1;
	if (ans[1]==0) tot=2;
	for (j=1;j<=3;j++,putchar(' ')) for (i=tot;i<=n;i++) printf("%d",ans[i]);
	return 0;
}

注意特判 $0$

T2

同 bzoj1939。

考虑区间 dp。令 $f[i][j][c]$ 表示在区间 $[l,r]$ 中，左边加入 $c$ 个同 $a_l$ 颜色一样的球后，还需要多少代价。$f[i][j][k-1]$ 代表了加入 $\ge k-1$ 个球，因为加入更多的球没有意义了。

把 $i$ 用 $k-1$ 个球消掉，就是：
$$
f[i][j][k-1]=f[i+1][j][0]
$$
根据定义，显然有：
$$
f[i][j][c]=f[i][j][c+1]+1\
f[i][j][c]=\min(f[i][j][c],f[i][j][c-1])
$$
考虑两个区间合起来的情况。令 $i<l\le j$ 且满足 $a_i=a_l$。

那么 $f[i][j][c]$ 的代价相当于 $f[i+1][l-1][0]+f[l][j][c+1]$，$i$ 相当于在 $l$ 左边加了个球。

那么转移：
$$
f[i][j][c]=\min(f[i+1][l-1][0]+f[l][j][c+1])
$$
代码就很好写了：

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
#include<bits/stdc++.h>
#define maxn
#define ll long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}
int f[105][105][5];
int a[105],n,k;
signed main(void){
	freopen("1.in","r",stdin);
	int i,j,l,c;
	memset(f,0x3f,sizeof(f));
	read(n);read(k);
	for (i=1;i<=n;i++) {
		read(a[i]);
		f[i][i][k-1]=0;
		for (j=k-2;j>=0;j--) f[i][i][j]=f[i][i][j+1]+1;
	}
	for (i=n;i>=1;i--) 
	    for (j=i;j<=n;j++) {
	        f[i][j][k-1]=min(f[i][j][k-1],f[i+1][j][0]);
	        for (c=k-2;c>=0;c--) {
	        	f[i][j][c]=min(f[i][j][c],f[i][j][c+1]+1);
	        	for (l=i+1;l<=j;l++) 
	        		if (a[l]==a[i]) {
	        			if (l==i+1) f[i][j][c]=min(f[i][j][c],f[l][j][c+1]);
 	        			else f[i][j][c]=min(f[i][j][c],f[i+1][l-1][0]+f[l][j][c+1]);
					}
			}
			for (c=1;c<k;c++) f[i][j][c]=min(f[i][j][c],f[i][j][c-1]);
		}
/*	for (i=1;i<=n;i++)
	    for (j=i;j<=n;j++){
	    	printf("[ %d , %d ] : ",i,j);
	    	for (c=0;c<k;c++) printf("%d ",f[i][j][c]);put();
		}*/
	printf("%d\n",f[1][n][0]);
	return 0;
}

T3

EJOI2017

贪心，能选就选。正确性反证易得。判断相等用 hash。最好用双模。

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
#include<bits/stdc++.h>
#define maxn 1000005
#define int long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}
const int mod=998244353,p=29;
inline int power(int x,int y) {
	int ans=1;
	while (y) {
		if (y&1) ans=ans*x%mod;
		x=x*x%mod;y>>=1;
	}
	return ans;
}
namespace BL{
	string s;
	int has[maxn],isuf[maxn],suf[maxn],w[27];
	inline int Ha(int l,int r) {
		return (has[r]-has[l-1]+mod)*isuf[l]%mod;
	}
	inline void main(void) {
		int i,j;
		cin>>s;int n=s.size();s='_'+s;
		suf[0]=isuf[0]=1;suf[1]=p;isuf[1]=power(p,mod-2);
		for (i=1;i<=26;i++) w[i]=i;
		random_shuffle(w+1,w+1+26);//防hack
		for (i=2;i<=n;i++) suf[i]=suf[i-1]*p%mod,isuf[i]=isuf[i-1]*isuf[1]%mod;
		for (i=1;i<=n;i++) has[i]=(has[i-1]+(w[s[i]-'a'+1])*suf[i])%mod;
		int m=n/2;
		int las=1,tot=0;
	    for (i=1;i<=m;i++) if (Ha(las,i)==Ha(n-i+1,n-las+1)) tot+=2,las=i+1;
		if (las!=(n+1)/2+1) tot++;  
	    printf("%lld\n",tot);
	}
}
signed main(void){
	freopen("1.in","r",stdin);
	int T,n;
	srand(time(0));
	read(T);
	while (T--) BL::main();
	return 0;
}