BZOJ|BZOJ 1002 轮状病毒 BZOJ|数论

1002: [FJOI2007]轮状病毒 Time Limit: 1 Sec Memory Limit: 162 MB
[ Submit][ Status] Description 给定n(N<=100)，编程计算有多少个不同的n轮状病毒。

文章图片

Input 第一行有1个正整数n。
Output 将编程计算出的不同的n轮状病毒数输出
Sample Input 3 Sample Output 16

第一眼看上去，n<=100
不错打表于是就写了一个暴力搜索
可是说好的暴力出奇迹呢？
跑了半天就跑到了18
我就呵呵呵了
恩！
开始找规律！我就笑笑不说话
【BZOJ|BZOJ 1002 轮状病毒】好了！我不会告诉你
a[n]=a[n-1]*3-a[n-2]+2;
//反正我是没搞出来的
好了先看看，暴力出奇迹

文章图片

暴力代码

#include #include #include using namespace std; const int maxn=200; struct node { int l,r; }map[maxn]; int f[maxn],N,n,i,ans; bool flag[maxn]; int find(int x) { if (x==f[x]) return x; return f[x]=find(f[x]); }void search(int k,int sta) { if (k==n+1) { ans++; return; } int temp[maxn]; for (int i=sta+1; i<=N; i++) if (!flag[i]) { int t1=find(map[i].l); int t2=find(map[i].r); if (t1==t2) continue; for (int j=0; j<=n; j++) temp[j]=f[j]; flag[i]=true; f[t1]=t2; search(k+1,i); for (int j=0; j<=n; j++) f[j]=temp[j]; flag[i]=false; } } int main() { for(n=1; n<=100; n++) { for(i=1; i%d\n",n,ans); ans=0; } return 0; }

AC代码

#include #include #include using namespace std; //a[n] = 3 * a[n-1] - a[n-2] + 2 const int base=10000; struct bign { int len,c[10000],sign; bign() { memset(c,0,sizeof(c)); len=1; sign=0; } void zero() { while(len>1&&c[len]==0)len--; } void writein(char *s) { int l=strlen(s),k=1; for(int i=l-1; i>=0; i--) { c[len]+=(s[i]-'0')*k; k*=10; if(k==base) { k=1; len++; } } zero(); } void read() { char s[10000]; scanf("%s",s); writein(s); } bign operator = (int b) { char s[10000]; sprintf(s,"%d",b); writein(s); return *this; } void print()//输出 { if(sign)printf("-"); printf("%d",c[len]); for(int i=len-1; i>=1; i--) printf("%04d",c[i]); //printf("\n"); } bool operator < (const bign &b)const { if(len!=b.len)return len=1; i--) if(c[i]!=b.c[i])return c[i]>n; for(int i=3; i<=n; i++) { a[i]=a[i-1]*3-a[i-2]+2; } a[n].print(); return 0; }