很简单的一场（似乎），因为是练习所以只花了两个小时，做出来5题，一样先放上来等以后填坑Σ(?д?;)
题意简述：有一个密码锁，每次对密码锁每个轮盘进行操作，问最终状态。
很简单的模拟。。。
时间复杂度 O(nm)，n是密码锁大小，m是操作次数。
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; int stat[110]; char buf[110]; int main(){ int l=0; while(scanf("%s",buf)!=EOF){ if(l==0) l=strlen(buf); for(int i=0;i<l;i++){ stat[i]=(stat[i]+buf[i]-‘0‘)%10; } } for(int i=0;i<l;i++) printf("%d",stat[i]); printf("\n"); return 0; }
题意简述：给一段文本，将其全部转大写后放入矩阵然后进行移动操作以加密文本，输出加密结果。
有点复杂的模拟，这些操作我是递归实现的，注意判断什么时候终止就行。我是嫌麻烦才递归，一般用循环更好
时间复杂度 O(mn^2)，m 是操作次数，n 是矩阵大小。
#include <cstdio> #include <algorithm> #include <cstring> #include <cctype> using namespace std; typedef long long ll; char buf[10010],head[110]; int n; char &arr(int i,int j){ return buf[(i-1)*n+j-1]; } void shake(int i,int j){ if(j%2==1){ char c=arr(i%n+1,j); if(i==2) arr(i,j)=c; else { shake((i+n-2)%n+1,j); arr(i,j)=c; } } else { char c=arr((i+n-2)%n+1,j); if(i==n) arr(i,j)=c; else { shake(i%n+1,j); arr(i,j)=c; } } } void rattle(int i,int j){ if(i%2==0){ char c=arr(i,j%n+1); if(j==2) arr(i,j)=c; else { rattle(i,(j+n-2)%n+1); arr(i,j)=c; } } else { char c=arr(i,(j+n-2)%n+1); if(j==n) arr(i,j)=c; else { rattle(i,j%n+1); arr(i,j)=c; } } } void rotate(int i,int j,int di,int dj,int t){ if(t==-1){ t=i%2; if(t==1){ di=0; dj=1; } else { di=1; dj=0; } rotate(i+di,j+dj,di,dj,t); return; } char c=arr(i-di,j-dj); if(i==j&&i<=n/2&&t!=-1){ arr(i,j)=c; return; } if(i==j||i+j==n+1){ if(t==0){ int ddi=di; di=-dj; dj=ddi; } else { int ddi=di; di=dj; dj=-ddi; } } rotate(i+di,j+dj,di,dj,t); arr(i,j)=c; } int main(){ while(scanf("%s",head)!=EOF){ getchar(); scanf("%[^\n]",buf); n=(head[0]-‘0‘)*10+head[1]-‘0‘; if(n==0) n=100; char ch=‘A‘; for(int i=strlen(buf)-1;i>=0;i--){ if(islower(buf[i])) buf[i]-=32; } for(int i=strlen(buf);i<n*n;i++){ buf[i]=ch; ch+=1; if(ch==‘Z‘+1) ch=‘A‘; } buf[n*n]=‘\0‘; int l=strlen(head); for(int i=2;i<l;i++){ if(head[i]==‘S‘) for(int i=1;i<=n;i++) shake(1,i); else if(head[i]==‘R‘) for(int i=1;i<=n;i++) rattle(i,1); else for(int i=1;i<=n/2;i++) rotate(i,i,0,0,-1); } printf("%s\n",buf); } }
题意简述：给出两个数，按给出的方案将数字简化表示，如 1234-1256 表示为 1234-56，4321-4411 表示为 4321-11。
可以发现压缩后第二个数永远是压缩前第二个数的后几位，因此从小到大试出取几位可以得到正确结果即可。如果你想的话还可以写个二分，反正我没写
时间复杂度 O(mlog b)，m 是测试数据组数，b 是第二个数。
#include <cstdio> #include <algorithm> #include <cstring> #include <cctype> using namespace std; typedef long long ll; char fmt[]="%lld-%000lld\n"; int main(){ ll a,b; while(scanf("%lld-%lld",&a,&b)!=EOF){ ll d=0,n=1,r=-1; while(b!=r){ d+=1; n*=10; if(b%n<=a%n){ r=a/n*n+n+b%n; } else { r=a/n*n+b%n; } } fmt[7]=‘0‘+d/10; fmt[8]=‘0‘+d%10; printf(fmt,a,b%n); } return 0; }
题意简述：在一个 10*10 的矩阵上有一些木桩，有若干长度小于 10 的木板，木板的两端必须放在木桩上，且不允许斜放。问是否有方案能从 (1,1) 到达 (10,10) 。
如果在 (x,y) 有一个长度为 l 的木板，那么能达到的点就只有 (x+l,y), (x-l,y), (x,y+l), (x,y-l). 这样我们就可以判断这些地方有没有木桩，然后dfs。
时间复杂度理论上可达 O(m!), m 是木板的数量，但这题这样就已经能过了（
#include <cstdio> #include <algorithm> #include <cstring> #include <cctype> using namespace std; typedef long long ll; char M[20][20]; bool vis[20][20]; int plk[50],n; char msg[50][100],mc; bool proc(int i,int j,int p,int d); bool dfs(int i,int j,int d){ if(i==9&&j==9) { mc=d; return true; } for(int p=0;p<n;p++){ int pl=plk[p]; if(pl==0) continue; plk[p]=0; if(proc(i+pl,j,p,d)) return true; if(proc(i-pl,j,p,d)) return true; if(proc(i,j+pl,p,d)) return true; if(proc(i,j-pl,p,d)) return true; plk[p]=pl; } return false; } bool proc(int i,int j,int p,int d){ if(!(i>=0&&i<10&&j>=0&&j<10&&M[i][j]==‘*‘&&!vis[i][j])) return false; vis[i][j]=true; bool r=dfs(i,j,d+1); if(r) sprintf(msg[d],"place plank %d to stump (%d,%d)",p+1,i+1,j+1); vis[i][j]=false; return r; } int main(){ for(int i=0;i<10;i++){ scanf("%s",M[i]); } bool rt=false; vis[0][0]=true; while(scanf("%d",&n)!=EOF){ if(rt) printf("\n"); rt=true; for(int i=0;i<n;i++){ scanf("%d",&plk[i]); } if(dfs(0,0,0)){ for(int i=0;i<mc;i++){ printf("%s\n",msg[i]); } } else { printf("no solution possible\n"); } } return 0; }
题意简述：问长度为 n，逆序对数量为 k 的 1-n 的排列有多少个。
这大概是这场唯一不是暴力求解的题吧（
令 dp[i][j] 表示长度为 i ，逆序对数量为 j 的排列的个数。
那么考虑如何转移。以 m 结尾的，长度为 i ，有 j 个逆序对的排列的数量等于长度为 i-1 ，有 j-(i-m) 个逆序对的数量。这是因为m和前面的数总是会形成 i-m 个逆序对。
例如之前的序列为 2 1 3，那么如果长度为 4 的序列以2结尾时，转移后的新序列为 3 1 4 2，2 和前面的 3 和 4 形成两个新的逆序对。
不太明白的可以看看我的AC代码是如何转移的。
时间复杂度 O(n^2*k+m)，n=18，k=200（就是询问的n和k的上界），m 是测试数据的组数。
#include <cstdio> #include <algorithm> #include <cstring> #include <cctype> using namespace std; typedef long long ll; ll dp[20][210]; int main(){ dp[1][0]=1; for(int i=2;i<=18;i++){ for(int j=0;j<=200;j++){ for(int k=1;k<=i;k++){ if(j-(i-k)>=0) dp[i][j]+=dp[i-1][j-(i-k)]; } } } int a,b; while(scanf("%d%d",&a,&b)!=EOF&&a!=0){ printf("%lld\n",dp[a][b]); } return 0; }
2003 Rocky Mountain Regional 题解 (5/8)
原文：https://www.cnblogs.com/whatss7/p/13540336.html
