[关闭]
@Junlier 2018-11-07T12:22:32.000000Z 字数 1438 阅读 1301

[FJOI2007]轮状病毒 题解(dp(找规律)+高精度)

题解
阅读体验:https://zybuluo.com/Junlier/note/1335733

没什么好说的,直接把规律找出来,有两种规律(据说还有多种dp),再套个高精度


就直接写个高精+低精和高精×低精和高精-高精就行了


为奇数时,
为偶数时,
这个需要高精+高精,高精×高精,高精-低精。。。

反正这就是个暴力题啦,只要找得到规律(我反正将近半个小时找到第二个规律,但是上网看题解写了第一种的)

  1. #include<bits/stdc++.h>
  2. #define il inline
  3. #define rg register
  4. #define ldb double
  5. #define lst long long
  6. #define rgt register int
  7. #define N 150
  8. using namespace std;
  9. const int Inf=1e9;
  10. il int MAX(rgt x,rgt y){return x>y?x:y;}
  11. il int MIN(rgt x,rgt y){return x<y?x:y;}
  12. il int read()
  13. {
  14. int s=0,m=0;char ch=getchar();
  15. while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
  16. while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  17. return m?-s:s;
  18. }
  19. int n;
  20. struct PLUS
  21. {
  22. int S[150],len;
  23. il void Print()
  24. {
  25. for(rgt i=len;i>=1;--i)
  26. printf("%d",S[i]);puts("");
  27. }
  28. }dp[N],blank;
  29. PLUS operator+(PLUS A,int x)
  30. {
  31. A.S[1]+=x;rgt nw=1;
  32. while(A.S[nw]>=10)
  33. ++A.S[nw+1],A.S[nw]%=10,++nw;
  34. if(A.S[A.len+1])++A.len;
  35. return A;
  36. }
  37. PLUS operator*(PLUS A,int x)
  38. {
  39. rg PLUS mid=blank;
  40. mid.len=A.len;
  41. for(rgt i=1;i<=A.len;++i)
  42. {
  43. mid.S[i]+=A.S[i]*x;
  44. mid.S[i+1]+=mid.S[i]/10;
  45. mid.S[i]%=10;
  46. }
  47. while(mid.S[mid.len+1])
  48. {
  49. ++mid.len;
  50. mid.S[mid.len+1]+=mid.S[mid.len]/10;
  51. mid.S[mid.len]%=10;
  52. }return mid;
  53. }
  54. PLUS operator-(PLUS A,PLUS B)
  55. {
  56. for(rgt i=1;i<=A.len;++i)
  57. {
  58. A.S[i]-=B.S[i];
  59. if(A.S[i]<0)
  60. --A.S[i+1],A.S[i]+=10;
  61. }return A;
  62. }
  63. int main()
  64. {
  65. n=read();
  66. dp[1].S[1]=1,dp[1].len=1;
  67. dp[2].S[1]=5,dp[2].len=1;
  68. for(rgt i=3;i<=n;++i)
  69. dp[i]=((dp[i-1]*3)-dp[i-2])+2;
  70. dp[n].Print();
  71. return 0;
  72. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注