Codeforces Round #269 (Div. 2)

赛后当练习做的，估摸着真实参加的话也只能出前两题，姿势水平还有待提高

 

A，要注意的trick有5个棒棒都相同的情况和6个棒棒都相同的情况，代码写的很乱

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int mark[10];
int main(){
    int num[10],i,j,k,n,m;
    while(cin>>num[0]){
        memset(mark,0,sizeof(mark));
        mark[num[0]]++;
        for(i=1;i<6;i++){
            cin>>num[i];
            mark[num[i]]++;
        }
        bool flag1=0,flag2=0;
        for(i=1;i<=9;i++){
            if(mark[i]>=4){
                flag1=1;
                if(mark[i]==6){
                    flag2=1;
                }
            }
            if(mark[i]==2){
                flag2=1;
            }
        }
        if(!flag1){
            cout<<"Alien\n";
        }else{
            if(flag2){
                cout<<"Elephant\n";
            }else{
                cout<<"Bear\n";
            }
        }
    }
    return 0;
}

 

B，对所有难度排序之后，查看有没有 两个相同的难度*2 或者是 三个相同的难度*1，不满足则输出no，满足的话再分情况讨论。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
class num{
public:
    int a,b;}seq[2006];
int cmp(const void *a,const void *b){
    num *aa=(num*)a;
    num *bb=(num*)b;
     return(((aa->a)>(bb->a))?1:-1);
}
int rright[2006];
int main(){
    int i,j,k,n,res;
    while(cin>>n){
        res=0;
        for(i=0;i<n;i++){
            cin>>seq[i].a;
            seq[i].b=i+1;
        }
        qsort(seq,n,sizeof(seq[0]),cmp);
        memset(rright,0,sizeof(rright));
        for(i=n-2;i>=0;i--){
            if(seq[i].a==seq[i+1].a){
                rright[i]=rright[i+1]+1;
            }
        }
        bool flag3=0;
        res=0;
        int loc[2003];
        int l3;
        for(i=0;i<n;i++){
            if(rright[i]>=2){
                l3=i;
                flag3=1;
                break;
            }
            if(rright[i]==1){
                loc[res]=i;
                res++;
            }
        }
        if(!flag3&&res<2){
            cout<<"NO"<<endl;
        }else{
            cout<<"YES"<<endl;
            for(i=0;i<n-1;i++){
                cout<<seq[i].b<<" ";
            }cout<<seq[n-1].b<<endl;
            if(flag3){
                for(i=0;i<l3;i++){
                    cout<<seq[i].b<<" ";
                }
                cout<<seq[l3+1].b<<" "<<seq[l3].b<<" "<<seq[l3+2].b;
                for(i=l3+3;i<n;i++){
                    cout<<" "<<seq[i].b;
                }cout<<endl;
                for(i=0;i<l3;i++){
                    cout<<seq[i].b<<" ";
                }
                cout<<seq[l3+2].b<<" "<<seq[l3].b<<" "<<seq[l3+1].b;
                for(i=l3+3;i<n;i++){
                    cout<<" "<<seq[i].b;
                }cout<<endl;
            }
            else{
                for(i=0;i<loc[0];i++){
                    cout<<seq[i].b<<" ";
                }cout<<seq[loc[0]+1].b<<" "<<seq[loc[0]].b;
                for(i=loc[0]+2;i<n;i++){
                    cout<<" "<<seq[i].b;
                }cout<<endl;
                for(i=0;i<loc[1];i++){
                    cout<<seq[i].b<<" ";
                }cout<<seq[loc[1]+1].b<<" "<<seq[loc[1]].b;
                for(i=loc[1]+2;i<n;i++){
                    cout<<" "<<seq[i].b;
                }cout<<endl;
            }
        }
    }
    return 0;
}

 C，很容易发现每层的卡片数n都满足（n+1）%3==0；然后数学推导出如果n个卡片存在k层则有

3*a1-1+3*a2-1+3*a3-1+  +3*ak-1=n

===>3*(a1+a2+a3+  +ak)=n+k

===>a1+a2+a3+  +ak=(n+k)/3

所以有n+k必须被3整除

(n+k)/3必须大于等于f(k)=1+2+3+  +k

因为这里f(k)增长很快，所以枚举很快就会跳出

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

int main(){
    long long n,k,i,j,res;
    while(cin>>n){
        res=0;
        for(k=1;k<n;k++){
            if((n+k)%3!=0)continue;
            if((n+k)/3<(k*(k+1)/2))break;
            res++;
        }
        cout<<res<<endl;
    }
    return 0;
}

 

D最没技术含量的一题，做差+kmp模板就过了

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=200050;
const int mMax=200005;
int text[mMax],pat[nMax];
int lent,lenp,next[nMax];

void get_next(){
    int i,j=-1;
    next[0]=-1;
    for(i=1;i<=lenp;i++){     //pat[j]是不是可以理解为i的前一个字符的next值所指想的字符
        while(j>-1&&pat[j+1]!=pat[i])j=next[j];
        if(pat[j+1]==pat[i])j++;
        next[i]=j;
    }
}

int KMP(){
    int ans=0,i=0,j=-1;
    get_next();
    for(i=0;i<lent;i++){
        while(j!=-1&&pat[j+1]!=text[i]){
            j=next[j];
        }
        if(pat[j+1]==text[i])j=j+1;
        if(j==lenp-1)ans++;  //找到一个匹配
    }
    return ans;
}

int main(){
    int i,j,k;
    while(scanf("%d%d",&lent,&lenp)!=EOF){
        for(i=0;i<lent;i++){
            scanf("%d",&text[i]);
        }
        for(i=0;i<lenp;i++){
            scanf("%d",&pat[i]);
        }
        lent--,lenp--;
        if(lenp==0){
            cout<<lent+1<<endl;
            continue;
        }
        if(lent==0){
            cout<<"ssss"<<endl;
            continue;
        }
        for(i=0;i<lent;i++){
            text[i]=text[i+1]-text[i];
        }
        for(i=0;i<lenp;i++){
            pat[i]=pat[i+1]-pat[i];
        }
        cout<<KMP()<<endl;
    }
    return 0;
}