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[];
int main()
{
ans[]=,ans[]=;
for(int i=;i<=;i++)
ans[i]=ans[i-]+*ans[i-]+;
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%d\n",ans[n]);
}
return ;
}
推推推
HDU - 2842Chinese Rings
题意一模一样，不同的是这题的数据量大，得把递推式用矩阵快速幂实现。
#include<cstdio>
#include<cstring>
#define ll long long
const ll mod=;
struct Node{
int r,c;
ll a[][];
Node(){
memset(a,,sizeof(a));
}
}A,T;
void init()
{
A.r=,A.c=;
memset(A.a,,sizeof(A.a));
A.a[][]=;A.a[][]=;A.a[][]=;
T.r=,T.c=;
memset(T.a,,sizeof(T.a));
T.a[][]=,T.a[][]=,T.a[][]=;
T.a[][]=T.a[][]=;
}
Node mul(Node n1,Node n2)
{
Node ans;
ans.r=n1.r,ans.c=n2.c;
for(int i=;i<n1.r;i++)
for(int j=;j<n2.c;j++)
for(int k=;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=;i<;i++)
ans.a[i][i]=;
while(b)
{
if(b&)
ans=mul(ans,n);
n=mul(n,n);
b>>=;
}
return ans;
}
int main()
{
int x;
while(scanf("%d",&x)&&x)
{
init();
T=pow(T,x-);
A=mul(T,A);
printf("%lld\n",A.a[][]);
}
return ;
}
再推再推
反思一下自己的状态，不能老熬夜了，身体是革命的本钱（主要是掉头发掉头发，我不想去主持非常勿扰）
最后夸一波源源，临危不乱，机智出题，（还有昭哥的nb面积对称法求和，不过臭男人不需要夸）。