Educational Codeforces Round 83

赛后看来这场还是挺简单的,还是太菜了

A
给正n边形和正m边形,问是否m上的所有点都在n的点上。
解 判断m%n即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    if(n%m==0){
        printf("YES\n");
    }else printf("NO\n");
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

B.
让你对数组进行排序,使得不存在\(a_i-i==a_j-j\)。
如果要相同,那么对于i>j必定有\(a_i>a_j\),那么反过来,把数组倒序排序即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
int a[105];
void work()
{
    int n,m;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    for(int i=n;i>=1;i--){
        printf("%d ",a[i]);
    }
    printf("\n");
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

C
给一个数组,每一步你可以对数组的任意一个值减去\(i^k\),或者不减,问是否能使得所有数都为0。
解 把每个数按照k进制求和(不进位),只有每一位都为0或者1时才可满足。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
ll a[35];
int b[105];
void work()
{
    int n;
    ll k;
    scanf("%d%lld",&n,&k);
    ll maxx=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        maxx=max(maxx,a[i]);
    }
    memset(b,0,sizeof(b));
    for(int i=1;i<=n;i++){
        for(ll j=1,t=0;j<=a[i];j=j*k,t++){
            if((a[i]/j)%k==1){
                b[t]++;
            }else{
                if((a[i]/j)%k>=2){
                    printf("NO\n");
                    return;
                }
            }
        }
    }
    for(int i=0;i<=100;i++){
        //printf("%d ",b[i]);
        if(b[i]>=2){
            printf("NO\n");return;
        }
    }
    printf("YES\n");
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

D.
要求从1到m中选n个数,满足数组为前面严格递增,后面严格递减,并且有且只有一个数出现了2次(其他数为1次)。
因为有一个数出现了2次,那么就是从m中选n-1个数,即\(C_m^{n-1}\),然后对于第n个数,可以为这n-1个数中除了最大的那个以外(为最大时不可能满足先递增后递减)的所有数(n-2),再是以最大的那个数为中心,剩下的n-1个数中因为有2个相同的数,这俩必定在最大的数的左右两侧,那么就是对剩下的n-3个数分到到左侧或者右侧,即\(2^{n-3}\),注意n=2时,n-3为-1。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int p=998244353;
ll qpow(ll a,ll n)
{
    ll res=1;
    while(n){
        if(n&1)res=res*a%p;
        a=a*a%p;
        n>>=1;
    }
    return res;
}
ll a[200005];
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    if(n==2){
        printf("0\n");return;
    }
    a[1]=1;
    for(int i=2;i<=m;i++){
        a[i]=a[i-1]*i%p;
    }
    printf("%lld\n",a[m]*qpow(a[n-1],p-2)%p*qpow(a[m-n+1],p-2)%p*qpow(2,n-3)%p*(n-2)%p);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

E
你可以将数组相邻2个相同的数合并为一个加一后的数,问最少可以剩下几个数
区间dp,dp[i][j]代表i到j合并的最优情况,然后在求dp[i][j]时,枚举分割点k,判断dp[i][k]+dp[k+1][j],还有没有分割点的情况暴力判断。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int p=998244353;
int a[505];
int dp[505][505];
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n-i+1;j++){
            int l=j;
            int r=i+j-1;
            stack<int>s;
            for(int k=l;k<=r;k++){
                int tmp=a[k];
                while(!s.empty()&&s.top()==tmp){
                    s.pop();
                    tmp++;
                }
                s.push(tmp);
            }
            dp[l][r]=s.size();
            for(int k=l;k<r;k++){
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
            }
        }
    }
    printf("%d\n",dp[1][n]);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

补一个n^2做法(syh的代码)
update:前面贴的是n^3的,现在改成n^2了

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#define pb push_back
using namespace std;
const int maxn=510;
int n,a[maxn],cnt,dp[maxn],sta[maxn],top;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=0;i<=n;i++) dp[i]=1e9;
	dp[0]=0;
	for (int i=0;i<n;i++)
	{
		top=0;
		for (int j=i+1;j<=n;j++)
		{
			int v=a[j];
			while (top && sta[top]==v) {top--; v++;}
			sta[++top]=v;
			if (top==1) dp[j]=min(dp[j],dp[i]+1);
		}
	}
	printf("%d\n",dp[n]);
return 0; 
}

 

F
有2个国家轮流行动,要对n个地方进行攻打,最后一个进行攻打的人获胜,有3种方式x,y,z,可以分别使地方的兵力减少x,y,z,x在任意情况下都可以使用,如果上一次这个地方受到的攻打为y,那么这次就不能用y,同理z,问第一次攻打有多少种方法使得第一个国家获胜。
解 因为x,y,z都很小,所以可以暴力求一下sg函数,然后暴力寻找循环节,sg[j][k][i]中 i代表当前还剩下多少兵,j代表下一次能否使用y,k代表下一次能否使用z。因为在接近0的情况下 循环节会出现一点点特例,存在max(0,i-x),max(0,i-y),max(0,i-z),所以判断循环节时要在比较大的地方去判断,测试结果是16开始不行,32开始可以。
然后利用循环节求出所有a[i]的sg值(同样求sg值时也要在一个比较大的地方),然后异或(如果不懂这个异或的话,百度一下NIM游戏),然后枚举每一个a[i],将这个a[i]的的sg值异或回去,然后将这个a[i]所可以受到的3种攻击得到的结果分别和前面的异或和 异或一下,为0就是ans++(当前是第二个人行动,sg为0为必败态,即第一个人获胜,sg不为0为必胜态,即第二个人获胜)

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
int sg[2][2][300005],v[4];
ll a[300005];
int repeat;
int maxx=32;
int cal(ll x,int j,int k)
{
	if(x<maxx){
		return sg[j][k][x];
	}else{
		return sg[j][k][(x-maxx)%repeat+maxx];
	}
}
void work()
{
    int n,x,y,z;
    scanf("%d%d%d%d",&n,&x,&y,&z);
    for(int i=1;i<=maxx*3;i++){
    	for(int j=0;j<=1;j++){
    		for(int k=0;k<=1;k++){
    			for(int l=0;l<=3;l++){
    				v[l]=0;
    			}
    			v[sg[1][1][max(0,i-x)]]=1;
    			if(j)v[sg[0][1][max(0,i-y)]]=1;
    			if(k)v[sg[1][0][max(0,i-z)]]=1;
    			for(int l=0;l<=3;l++){
    				if(v[l]==0){
    					sg[j][k][i]=l;break;
    				}
    			}
    		}
    	}
    }
    for(repeat=1;repeat<=maxx;repeat++){
    	bool f=1;
    	for(int i=0;i<=maxx-1;i++){
    		for(int j=0;j<=1;j++){
    			for(int k=0;k<=1;k++){
    				if(sg[j][k][i+maxx]!=sg[j][k][i+maxx+repeat]){
    					f=0;
    					break;
    				}
    			}
    			if(!f)break;
    		}
    		if(!f)break;
    	}
    	if(f){
    		break;
    	}
    }
    int sum=0,ans=0;
    for(int i=1;i<=n;i++){
    	scanf("%lld",&a[i]);
    	sum^=cal(a[i],1,1);
    }
    for(int i=1;i<=n;i++){
    	int tmp=sum^cal(a[i],1,1);
    	if(tmp==cal(max(0ll,a[i]-x),1,1))ans++;
    	if(tmp==cal(max(0ll,a[i]-y),0,1))ans++;
    	if(tmp==cal(max(0ll,a[i]-z),1,0))ans++;
    }
    printf("%d\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

 

G
给一棵字典树,然后给q个询问,要键入树上从0到q[i]的字符串链,然后可以有2种操作,一种是键入下一个字母,另一种是自动补全,考虑所有以当前子串为前缀的询问字符串,按照字典树顺序排列,对于第i个字符串需要i秒进行补全,问每个字符串最少需要多少时间。
考虑离线dfs dp,首先建好字典树,然后在每个询问的字符串的终点对一个记录自动补全时间的s[i]+1,然后在dfs时将s[i]进行回溯增加,那么当前的s[x]就是代表如果要进行下一次自动补全,要先花多少时间,用a[x],b[x]记录两种操作的答案即可。
对于自动补全可以理解为有一个输入法软件,但其中的词库只有询问的所有字符串,然后这些字符串按照字典序排序,选第一个要1秒,选第二个要2秒。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int inf=0x3f3f3f;
int a[1000005],b[1000005],s[1000005],qy[1000005],tr[26][1000005];
//a代表优先键入字母 和答案的最优,b代表优先补全,s代表选中那个字符串要多少秒(自动补全时)
void dfs(int x){
	b[x]=min(a[x],b[x]);
	if(s[x])a[x]=min(a[x],b[x]+1);
	for(int i=0;i<26;i++){
		if(tr[i][x]){
			a[tr[i][x]]=min(a[tr[i][x]],a[x]+1);
			b[tr[i][x]]=min(b[tr[i][x]],b[x]+s[x]);//此时的s[x]代表如果要进行自动补全,需要先花多少时间,即有多少个字符串在他前面
			dfs(tr[i][x]);
			s[x]+=s[tr[i][x]];
		}
	}
}
void work()
{
    int n;
    scanf("%d",&n);
    char c[15];
    for(int i=1;i<=n;i++){
    	int x;
    	scanf("%d%s",&x,c);
    	tr[c[0]-'a'][x]=i;//记录字典树
    }
    int q;
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
    	scanf("%d",&qy[i]);
    	s[qy[i]]++;//记录字符串
    }
    memset(a,inf,sizeof(a));
    memset(b,inf,sizeof(b));
    a[0]=b[0]=0;
    dfs(0);
    for(int i=1;i<=q;i++){
    	printf("%d ",a[qy[i]]);
    }
    printf("\n");
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

 

“Educational Codeforces Round 83”的一个回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注