首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。