第一题:Dice Tower
题意:给你n个骰子,一个叠在一个上面,连接位置的两个面是两个不同的数字,问只告诉你最上面一个骰子的顶面和所有骰子面向你的两个面的数字,能否确定所有骰子每个面是什么数字?
题解:
代码:
#include<cstdio> #include<cstring> using namespace std; int main() { int n,x,num; bool flag=false; scanf("%d%d",&n,&x); for(int i=0;i<2*n;++i) { scanf("%d",&num); if(num==x||num==7-x) flag=true; } if(flag) puts("NO"); else puts("YES"); return 0; }
第二题:Well-known Numbers
题意:
题解:
代码:
#include<cstdio> #include<cstring> #define LL long long using namespace std; LL fib[1005]= {0,1},num[1005]; int main() { int s,k; int idx=0,i,j; scanf("%d%d",&s,&k); for(i=2; fib[i-1]<s; ++i) for(j=i-1; j>=0&&j>=i-k; --j) fib[i]+=fib[j]; for(; i>0&&s>0; --i) if (fib[i]<=s) { s-=fib[i]; num[idx++]=fib[i]; } printf("%d\n",idx); for(int l=0; l<idx; ++l) printf("%d ",num[l]); return 0; }
第三题:Barcode
题意:
题解:
代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int num[1005]= {0},dp[1005][2]; int main() { int n,m,x,y; scanf("%d%d%d%d",&n,&m,&x,&y); for(int i=0; i<n; ++i) { getchar(); for(int j=0; j<m; ++j) { if(getchar()=='#') num[j+1]++; } } for(int i=1; i<m; ++i) num[i+1]+=num[i]; for(int i=1; i<=m; ++i) dp[i][0]=dp[i][1]=9999999; dp[0][0]=dp[0][1]=0; for(int i=0; i<m; ++i) for(int j=x; j<=y&&i+j<=m; ++j) { dp[i+j][0]=min(dp[i+j][0],dp[i][1]+(num[i+j]-num[i])); dp[i+j][1]=min(dp[i+j][1],dp[i][0]+j*n-(num[i+j]-num[i])); } printf("%d\n",min(dp[m][0],dp[m][1])); return 0; }