第二届ACM山东省赛




A: Nim+Bash 博弈

Nim博弈可以看做只考虑取二进制化后的数的位数上的1,结合Bash就变成了从几堆中取相应的1

答案是 统计二进制位数,如果全部取模(3+1)等于0,则是必败态

#include<bits/stdc++.h>
using namespace std;
const int maxn=11000;

int a[maxn],N,T,K,max_tot;

int main(){
    scanf("%d",&T);
    while(T--){
        memset(a,0,sizeof(a));
        max_tot=0;
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%d",&K);
            int tot=0;
            while(K){
                if(K&1) a[tot++]++;
                else tot++;
                K>>=1;
            }
            max_tot=max(max_tot,tot);
        }
        //printf("max: %d\n",max_tot);
        bool flag=true;
        for(int i=0;i<max_tot;++i){
            if(a[i]%4){
                flag=false;
                break;
            }
        }
        printf(flag?"No\n":"Yes\n");
    }
    return 0;
}

B:排序模拟

#include<bits/stdc++.h>
using namespace std;

struct team{
    char name[40];
    bool all_girls;
    int solved;
    int pe;
    int id;

    bool operator<(const team& A) const{
        if(solved==A.solved){
            return pe>A.pe;
        }else return solved<A.solved;
    }
};

struct Name{
    char name[40];
    int id;
    bool operator<(const Name& A) const{
        return id<A.id;
    }
};

int T,kase=1;
int N,M;
char str[1000];
priority_queue<team> pt;
vector<Name> ans;

void init(){
    while(!pt.empty()) pt.pop();
    ans.clear();
}

team get_team(int id){
    char name[40];
    bool all_girls;
    int solved;
    int pe;
    team t;

    sscanf(str,"%s %d %d %d",name,&all_girls,&solved,&pe);
    strcpy(t.name,name);
    t.all_girls=all_girls;
    t.solved=solved;
    t.pe=pe;
    t.id=id;
    return t;
}

Name new_me(char str[40],int ind){
    Name me;
    strcpy(me.name,str);
    me.id=ind;
    return me;
}

void can(){
    bool has_girl=false;
    while(!pt.empty()){
        team a=pt.top();pt.pop();
        if(a.solved<=0) break;
        if(a.all_girls) has_girl=true;
        ans.push_back(new_me(a.name,a.id));
        M--;
        if(M==0)break;
    }
    if(M==0){
        if(!has_girl){
            while(!pt.empty()){
                team a=pt.top();pt.pop();
                if(a.solved<=0) break;
                if(a.all_girls){
                    ans.push_back(new_me(a.name,a.id));
                    break;
                }
            }
        }
    }
}

void cant(){
    while(!pt.empty()){
        team a=pt.top();pt.pop();
        ans.push_back(new_me(a.name,a.id));
    }
}

void print(){
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();++i){
        printf("%s\n",ans[i].name);
    }
    puts("");
}

int main(){
    scanf("%d",&T);
    while(T--){
        init();
        scanf("%d%d\n",&N,&M);
        int low=0;
        for(int i=0;i<N;++i){
            gets(str);
            team a=get_team(i);
            if(a.solved>=1) low++;
            pt.push(a);
        }
        printf("Case %d:\n",kase++);
        if(low>=M) can();
        else cant();
        print();
    }
    return 0;
}

C:水

#include<bits/stdc++.h>
using namespace std;
const int maxn=200;
char str[maxn];
int T;

int main(){
    scanf("%d",&T);
    while(T--){
        bool is=true;
        gets(str);
        int len=strlen(str);
        if(isalpha(str[0]) || str[0]=='_'){
            for(int i=1;i<len;++i){
                if(!(isalpha(str[i]) || isdigit(str[i]) || str[i]=='_')){
                    printf("No\n");
                    is=false;
                    break;
                }
            }
        }else{
            printf("No\n");
            is=false;
        }
        if(is) printf("Yes\n");
    }

    return 0;
}


D: 求组合数模,可以大数,可以打表

///1000*1000的数据直接打表就好
#include <iostream>
#include <string.h>
using namespace std;
const int mod=10000003;
const int N=1002;
int c[N][N];

void init()//递推打表
{
    memset(c,0,sizeof(c));
    c[0][0]=c[1][0]=c[1][1]=1;
    for(int i=2;i<N;i++)
    {
        c[i][i]=c[i][0]=1;
        for(int j=0;j<i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;//不会越界
        }
    }
}
int main()
{
    init();
    int k;cin>>k;
    int a,b;
    while(k--)
    {
        cin>>a>>b;
        cout<<c[a][b]<<endl;//直接输出
    }
}

E:快速幂模+数组模拟trie

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e6+7;

int mp[11][11][11];
char res[11][11][11];
char str[maxn];

ll mod_pow(ull x,ull n,int mod){
    ull res=1;
    while(n>0){
        if(n&1) res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}

void f(int id,int n){
    int ans=mod_pow(id,n,997);
    //cout<<ans<<endl;
    int cnt=0;
    int dt[3]={0,0,0};
    while(ans){
        dt[cnt++]=ans%10;
        ans/=10;
    }
    mp[dt[2]][dt[1]][dt[0]]++;
    res[dt[2]][dt[1]][dt[0]]=(char)id;
}

void init(int n){
    memset(mp,0,sizeof(mp));
    ///处理数字
    for(int i=0;i<10;++i)
        f('0'+i,n);
    ///处理lowalpha
    for(int i=0;i<27;++i)
        f('a'+i,n);
    ///处理upperalpha
    for(int i=0;i<27;++i)
        f('A'+i,n);
}

int main(){
    int T,K;
    scanf("%d",&T);
    while(T--){
        scanf("%d\n%s",&K,str);
        init(K);
        int len=strlen(str);
        if(len%3){
            printf("No Solution\n");
            continue;
        }
        bool flag=true;
        string ans;
        for(int i=0;i<len;i+=3){
            int x=str[i]-'0',y=str[i+1]-'0',z=str[i+2]-'0';
            //cout<<x<<y<<z<<mp[x][y][z]<<endl;
            if(mp[x][y][z]>1 || mp[x][y][z]==0){
                flag=false;
                break;
            }
            ans+=res[x][y][z];
        }
        if(flag) cout<<ans<<endl;
        else cout<<"No Solution"<<endl;
    }

    return 0;
}

I: 区间DP

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=1010;
typedef long long LL;
LL dp[maxn];
LL sum[maxn],num;
int T,N,M;


int main(){
    scanf("%d",&T);
    while(T--){
        sum[0]=0ll;
        dp[0]=0ll;
        scanf("%d%d",&N,&M);
        for(int i=1;i<=N;++i){
            scanf("%lld",&num);
            sum[i]=sum[i-1]+num;
            dp[i]=sum[i]*sum[i];
        }

        for(int i=2;i<=M;++i){
            ///枚举区间,j为i划分倒推的一维
            for(int j=N-M+i;j>=i;--j){
                for(int k=1;k<j;++k){
                    dp[j]=min(dp[j],dp[k]+(sum[j]-sum[k])*(sum[j]-sum[k]));
                }
            }
        }
        printf("%lld\n",dp[N]);
    }
    return 0;
}