ZOJ 3182 Nine Interlinks
题目大意：把一些带标号的环套到棍子上，标号为1的可以所以操作，标号i的根子在棍子上时，只有它标号比它小的换都不在棍子上，才能把标号为i+1的环，放在棍子上或者取下，问n个环全部放在棍子上需要的最少步骤？
一个简单的递推题，可是我硬生生想复杂了还把队友带偏了，真是惭愧，还好源源的一发强大的思路，简简单单就过了，源源太强了，tql,orz。我们以4个环全放上棍子为例，我们要先把第3个环放上，然后又把前两个环都取下，然后才能放上第4个环，再又把前两个环都上。听起来有点复杂，我们想一下如果4个都已全放上，要把他们取下呢，那就是先把前两个取下，然后才能取下第4个环，然后再把前2个放上，最后把前3个全取下，虽然中间细节可能不同，但全放上和全取下的操作步骤是一样的。我之前就陷入了，觉得放第i个时，前i-1个环不一定都要存在，然后推来推去把自己推晕了，其实要把i-2个取下，第i-3个就得在，最终就是全在。递推式就是ans[i]=ans[i-1]*2ans[i-2]+1,ans[i]就是前i个环全放上，或者全取下的步骤。
#include<cstdio> int ans[30]; int main() { ans[0]=0,ans[1]=1; for(int i=1;i<=30;i++) ans[i]=ans[i-1]+2*ans[i-2]+1; int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); printf("%d ",ans[n]); } return 0; }
HDU - 2842 Chinese Rings
题意一模一样，不同的是这题的数据量大，得把递推式用矩阵快速幂实现。
#include<cstdio> #include<cstring> #define ll long long const ll mod=200907; struct Node{ int r,c; ll a[5][5]; Node(){ memset(a,0,sizeof(a)); } }A,T; void init() { A.r=3,A.c=1; memset(A.a,0,sizeof(A.a)); A.a[0][0]=1;A.a[1][0]=0;A.a[2][0]=1; T.r=3,T.c=3; memset(T.a,0,sizeof(T.a)); T.a[0][0]=1,T.a[0][1]=2,T.a[0][2]=1; T.a[1][0]=T.a[2][2]=1; } Node mul(Node n1,Node n2) { Node ans; ans.r=n1.r,ans.c=n2.c; for(int i=0;i<n1.r;i++) for(int j=0;j<n2.c;j++) for(int k=0;k<n1.c;k++) ans.a[i][j]=(ans.a[i][j]+(n1.a[i][k]*n2.a[k][j])%mod)%mod; return ans; } Node pow(Node n,int b) { Node ans; ans.r=n.r,ans.c=n.c; for(int i=0;i<3;i++) ans.a[i][i]=1; while(b) { if(b&1) ans=mul(ans,n); n=mul(n,n); b>>=1; } return ans; } int main() { int x; while(scanf("%d",&x)&&x) { init(); T=pow(T,x-1); A=mul(T,A); printf("%lld ",A.a[0][0]); } return 0; }
反思一下自己的状态，不能老熬夜了，身体是革命的本钱（主要是掉头发掉头发，我不想去主持非常勿扰）
最后夸一波源源，临危不乱，机智出题，（还有昭哥的nb面积对称法求和，不过臭男人不需要夸）。