首页 > 代码库 > Codeforces Round #269 (Div. 2)

Codeforces Round #269 (Div. 2)

a.就是先找出四个一样的,然后看剩下两个的关系。

#include <cstdio>#include <cstring>using namespace std;int main(){    int a[10];    int vis[20];    int i;    memset(vis,0,sizeof(vis));    for(i=1;i<=6;i++)    {        scanf("%d",&a[i]);        vis[a[i]]+=1;    }    int flag=0;    for(i=1;i<=18;i++)        if(vis[i]>=4) {vis[i]-=4;flag=1;}    if(flag==0) {printf("Alien\n");return 0;}    for(i=1;i<=18;i++)        if(vis[i]==2) {printf("Elephant\n");return 0;}    printf("Bear\n");    return 0;}

b.看有没有一个数重复出现至少三次或者两个数各重复出现至少两次

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int n;struct node{    int x,id;}e[2100];int cmp(node a,node b){    return a.x<b.x;}int main(){    int i;    scanf("%d",&n);    for(i=0;i<n;i++)    {        scanf("%d",&e[i].x);        e[i].id=i+1;    }    sort(e,e+n,cmp);    int a=-1,b=-1;    int num1=1;    for(i=1;i<n;i++)    {        if(e[i].x==e[i-1].x)        {            if(a==-1) a=i-1;            else if(b==-1&&e[i].x!=e[a].x) b=i-1;            if(e[i].x==e[a].x) num1++;        }        if(b!=-1) break;    }    if(num1>2)    {        printf("YES\n");        for(i=0;i<n;i++)        {            if(i!=a) printf("%d ",e[i].id);            else {printf("%d %d %d ",e[i].id,e[i+1].id,e[i+2].id);i+=2;}        }        printf("\n");        for(i=0;i<n;i++)        {            if(i!=a) printf("%d ",e[i].id);            else {printf("%d %d %d ",e[i+1].id,e[i].id,e[i+2].id);i+=2;}        }        printf("\n");        for(i=0;i<n;i++)        {            if(i!=a) printf("%d ",e[i].id);            else {printf("%d %d %d ",e[i+2].id,e[i+1].id,e[i].id);i+=2;}        }        printf("\n");    }    else if(a!=-1&&b!=-1)    {        printf("YES\n");        for(i=0;i<n;i++)        {            if(i!=a) printf("%d ",e[i].id);            else {printf("%d %d ",e[i].id,e[i+1].id);i++;}        }        printf("\n");        for(i=0;i<n;i++)        {            if(i!=a) printf("%d ",e[i].id);            else {printf("%d %d ",e[i+1].id,e[i].id);i++;}        }        printf("\n");        for(i=0;i<n;i++)        {            if(i!=b) printf("%d ",e[i].id);            else {printf("%d %d ",e[i+1].id,e[i].id);i++;}        }        printf("\n");    }    else printf("NO\n");    return 0;}

c. 题意是给出n个扑克牌,问能搭出多少种不同高度的房子。假设某层有x个屋子,那么该层一共消耗扑克牌3*x-1。所以说给出n个扑克牌,假如能搭出高为h的房子,那么(n+h)一定是3的倍数。其次再看看以最省的方式搭需要多少扑克牌,假如不够就break。

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;ll n;int main(){    scanf("%I64d", &n);    ll xx=2;    ll ans=0;    for(int i=1;;i++)    {        if(xx>n) break;        if((n-xx)%3==0) ans++;        xx=xx+i*3+2;    }    printf("%I64d\n", ans);    return 0;}

d.给定s串和t串,看s中出现过几次t串,这里的出现是只要差值一定就行,即s1=t1+a,s2=t2+a....sn=tn+a。将上述式子相减消去a会发现匹配的充要条件是相邻数的差值完全匹配,所以先预处理出两个数组的相邻差值数组s1,t1,对着两个数组kmp即可。

#include <cstdio>#include <cstring>using namespace std;const long long  inf = 1200000000;#define maxn 201000int a[maxn],b[maxn];int f[maxn];int n,m;int ans;void get(int *p,int *f){    f[0]=0;f[1]=0;    for(int i=1;i<m;i++)    {        int j=f[i];        while(j&&p[i]!=p[j]) j=f[j];        f[i+1]=p[i]==p[j]?j+1:0;    }}void find(int *t,int *p,int *f){    get(p,f);    int j=0;    for(int i=0;i<n;i++)    {        while(j&&p[j]!=t[i]) j=f[j];        if(p[j]==t[i]) j++;        if(j==m-1) ans++;    }}int main(){    int i,j;    scanf("%d%d",&n,&m);    for(i=0;i<n;i++) scanf("%d",&a[i]);    for(i=0;i<m;i++) scanf("%d",&b[i]);    if(m==1) {printf("%d\n",n);return 0;}    for(i=0;i<n-1;i++) a[i]=a[i+1]-a[i];    for(i=0;i<m-1;i++) b[i]=b[i+1]-b[i];    find(a,b,f);    //for(i=0;i<m-1;i++) printf("%d ",b[i]);    n--;m--;    printf("%d\n",ans);    return 0;    return 0;}

 

Codeforces Round #269 (Div. 2)