NOIP1998题解报告
T1 进制位
题目大意:自己看吧
首先让我们来看两个引理:
- 如果有解,则进制一定为
- 如果有解,则字母一定表示 至 的数
证明如下:
因为有 个不同的数,所以最少 进制。
假设为 进制,那么一定有一个数没有出现,假设为 。
若 或 ,有 (进制下) ,矛盾。
,有 ,矛盾。
其它 进制的情况同理,所以一定是 进制,结论 得证。
结论 成立 ,则结论 显然。
有了以上两个结论,这道题就好做多了。
数据范围才为 ,直接枚举每种全排列,对每一种进行判断是否满足加法表就行了。
#include<cstdio> #include<iostream> #include<cstring> #include<vector> #include<algorithm> using namespace std; int n,a[9],c[366666][9],tot,num[233],vis[233]; char cnm[9]; char ch[9][9][233]; inline int my_pow(int a,int b) { int cnm=1; for(;b;b>>=1) { if(b&1) cnm=cnm*a; a=a*a; } return cnm; } inline bool calc(int jz,int a,int b) { int A=num[(int)cnm[a]],B=num[(int)cnm[b]],C=0; int siz=ch[a+1][b+1][0]; for(int i=1;i<=siz;++i) C+=num[(int)ch[a+1][b+1][i]]*my_pow(jz,siz-i); if(A+B<jz) { if(A+B==C) return true; return false; } else { int temp=A+B; B=temp%jz,A=temp/jz; B+=A*jz; if(B==C) return true; return false; } } inline void dfs(int k) { if(k==n-1) { ++tot; for(int i=0;i<n-1;++i) c[tot][i]=a[i]; return; } for(int i=0;i<n-1;++i) { if(!vis[i]) { vis[i]=1; a[k]=i,dfs(k+1); vis[i]=0; } } } int main() { scanf("%d",&n); getchar();//小心换行 for(int i=0;i<n;++i) { for(int j=0;j<n;++j) { scanf("%s",ch[i][j]+1); ch[i][j][0]=strlen(ch[i][j]+1); } } for(int i=1;i<n;++i) cnm[i-1]=ch[0][i][1]; dfs(0); for(int i=1;i<=tot;++i) { int sum=0; for(int j=0;j<n-1;++j) num[(int)cnm[j]]=c[i][j]; for(int j=0;j<n-1;++j) { for(int k=0;k<n-1;++k) { if(calc(n-1,j,k)) ++sum; } } if(sum==(n-1)*(n-1)) { for(int j=0;j<n-1;++j) printf("%c=%d ",cnm[j],c[i][j]); puts(""); printf("%d\n",n-1);return 0; } } puts("ERROR!"); return 0; }
T2 拼数
题目大意:给你个正整数,让你把它们重新排列,使得排列后形成的数最大。
水题,直接切掉
#include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<iostream> using namespace std; int n; string s[23]; inline bool cmp(string a,string b) {return a+b>b+a;} int main() { scanf("%d",&n); for(int i=1;i<=n;++i) cin>>s[i]; sort(s+1,s+n+1,cmp); for(int i=1;i<=n;++i) cout<<s[i]; return 0; }
T3 车站
题目大意:给你列车每一站上下车人数的规律以及终点人数,求第站人数。
水的不能再水的题,直接上代码……
#include<cstdio> using namespace std; int f[23],n,m,a,x; int main() { scanf("%d%d%d%d",&a,&n,&m,&x); f[1]=1,f[2]=1; for(int i=3;i<=n;++i) f[i]=f[i-1]+f[i-2]; if(x==1 || x==2) printf("%d",a); else if(x==3) printf("%d",2*a); else { int y=(m-a*(f[n-3]+1))/(f[n-2]-1); printf("%d",y*(f[x-1]-1)+a*(f[x-2]+1)); } return 0; }