[关闭]
@KirinBill 2017-10-31T23:27:35.000000Z 字数 4795 阅读 954

2017.10.28 NOIP模拟赛

题解 套题

目录


神炎皇

7eRcM.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  4. using std::string;
  5. inline void setIO(string file){
  6. string in=file+".in",out=file+".out";
  7. freopen(in.c_str(),"r",stdin);
  8. freopen(out.c_str(),"w",stdout);
  9. }
  10. template<typename type>
  11. inline void read(type &x){
  12. int pm=1; char c;
  13. do{
  14. c=getchar();
  15. if(c=='-') pm=-1;
  16. }while(!isdigit(c));
  17. x=c^'0';
  18. while(c=getchar(),isdigit(c))
  19. x=x*10+(c^'0');
  20. x*=pm;
  21. }
  22. template<typename type>
  23. void write(type x,char c=0){
  24. if(x<0) putchar('-'),x=-x;
  25. if(x>9) write(x/10);
  26. putchar(x%10|'0');
  27. if(c) putchar(c);
  28. }
  29. #include <cmath>
  30. using std::sqrt;
  31. const int MAXN=1e7+5;
  32. int phi[MAXN];
  33. inline void Euler_phi(int n){
  34. static int prm[MAXN];
  35. static bool notP[MAXN];
  36. notP[1]=true,phi[1]=1;
  37. for(int i=2;i<=n;++i){
  38. if(!notP[i]){
  39. prm[++prm[0]]=i;
  40. phi[i]=i-1;
  41. }
  42. for(int j=1,tmp;j<=prm[0] && i*prm[j]<=n;++j){
  43. tmp=i*prm[j];
  44. notP[tmp]=true;
  45. if(i%prm[j]==0){
  46. phi[tmp]=phi[i]*prm[j];
  47. break;
  48. }
  49. else phi[tmp]=phi[i]*phi[prm[j]];
  50. }
  51. }
  52. }
  53. inline unsigned long long cal(long long n){
  54. int sqrt_n=sqrt(n);
  55. Euler_phi(sqrt_n);
  56. unsigned long long ret=0;
  57. for(int i=2;i<=sqrt_n;++i)
  58. ret+=(unsigned long long)phi[i]*(n/i/i);
  59. return ret;
  60. }
  61. int main(){
  62. #ifdef DEBUG
  63. setIO("a");
  64. #endif
  65. long long n;
  66. read(n);
  67. write(cal(n));
  68. return 0;
  69. }

降雷皇

7eFoT.png
7eXr7.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  4. using std::string;
  5. inline void setIO(string file){
  6. string in=file+".in",out=file+".out";
  7. freopen(in.c_str(),"r",stdin);
  8. freopen(out.c_str(),"w",stdout);
  9. }
  10. template<typename type>
  11. inline void read(type &x){
  12. int pm=1; char c;
  13. do{
  14. c=getchar();
  15. if(c=='-') pm=-1;
  16. }while(!isdigit(c));
  17. x=c^'0';
  18. while(c=getchar(),isdigit(c))
  19. x=x*10+(c^'0');
  20. x*=pm;
  21. }
  22. template<typename type>
  23. void write(type x,char c=0){
  24. if(x<0) putchar('-'),x=-x;
  25. if(x>9) write(x/10);
  26. putchar(x%10|'0');
  27. if(c) putchar(c);
  28. }
  29. #include <algorithm>
  30. using std::max;
  31. const int MAXN=100005,P=123456789;
  32. int n,maxr;
  33. int r[MAXN];
  34. struct query{
  35. int sz;
  36. long long sum;
  37. query(int sz=0,long long sum=0):sz(sz),sum(sum){}
  38. };
  39. class val_segT{
  40. #define ls (u<<1)
  41. #define rs (ls|1)
  42. private:
  43. typedef query node;
  44. node d[MAXN<<2];
  45. void upd(int u){
  46. if(d[ls].sz>d[rs].sz) d[u]=d[ls];
  47. else if(d[rs].sz>d[ls].sz) d[u]=d[rs];
  48. else d[u]=node(d[ls].sz,(d[ls].sum+d[rs].sum)%P);
  49. }
  50. void ist(int u,int l,int r,int pos,query &val){
  51. if(l==r){
  52. if(d[u].sz<val.sz) d[u]=val;
  53. else if(d[u].sz==val.sz)
  54. d[u].sum=(d[u].sum+val.sum)%P;
  55. return;
  56. }
  57. int mid=l+r>>1;
  58. if(pos<=mid) ist(ls,l,mid,pos,val);
  59. else ist(rs,mid+1,r,pos,val);
  60. upd(u);
  61. }
  62. query qry(int u,int l,int r,int lp,int rp){
  63. if(lp<=l && r<=rp) return d[u];
  64. int mid=l+r>>1;
  65. query ret,tmp;
  66. if(lp<=mid) ret=qry(ls,l,mid,lp,rp);
  67. if(rp>mid){
  68. tmp=qry(rs,mid+1,r,lp,rp);
  69. if(tmp.sz>ret.sz) ret=tmp;
  70. else if(tmp.sz==ret.sz) ret.sum=(ret.sum+tmp.sum)%P;
  71. }
  72. return ret;
  73. }
  74. public:
  75. void ist(int pos,query &val){ist(1,1,maxr,pos,val);}
  76. query qry(int rp){
  77. if(rp<=0) return query(0,0);
  78. return qry(1,1,maxr,1,rp);
  79. }
  80. #undef ls
  81. #undef rs
  82. }T;
  83. inline query DP(){
  84. query ret,tmp;
  85. for(int i=1;i<=n;++i){
  86. tmp=T.qry(r[i]-1);
  87. if(tmp.sz==0) tmp.sum=1;
  88. ++tmp.sz;
  89. if(ret.sz<tmp.sz) ret=tmp;
  90. else if(ret.sz==tmp.sz) ret.sum=(ret.sum+tmp.sum)%P;
  91. T.ist(r[i],tmp);
  92. }
  93. return ret;
  94. }
  95. int main(){
  96. #ifdef DEBUG
  97. setIO("b");
  98. #endif
  99. int type;
  100. read(n),read(type);
  101. for(int i=1;i<=n;++i){
  102. read(r[i]);
  103. maxr=max(maxr,r[i]);
  104. }
  105. query ans=DP();
  106. write(ans.sz,'\n');
  107. if(type) write(ans.sum);
  108. return 0;
  109. }

幻魔皇

7eBS6.png

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. using std::max;
  4. const int MAXN=5005,P=123456789;
  5. int n;
  6. long long ans[MAXN<<1];
  7. long long wht[MAXN],blk[MAXN];
  8. long long sumw[MAXN],sumb[MAXN];
  9. inline void pre_cal(){
  10. wht[1]=1,wht[2]=0,wht[3]=1;
  11. for(int i=4;i<=n;++i)
  12. wht[i]=(wht[i-1]+wht[i-2])%P;
  13. blk[1]=0,blk[2]=1;
  14. for(int i=3;i<=n;++i)
  15. blk[i]=(blk[i-1]+blk[i-2])%P;
  16. for(int i=1;i<=n;++i){
  17. sumw[i]=(sumw[i-1]+wht[i])%P;
  18. sumb[i]=(sumb[i-1]+blk[i])%P;
  19. }
  20. }
  21. inline void solve(){
  22. for(int i=1;i<=n;++i)
  23. ans[i]=sumw[n-i]*wht[i+1]%P;
  24. for(int i=1;i<=n;++i){
  25. for(int j=1;j<=n;++j)
  26. ans[i+j]=(ans[i+j]+sumb[n-max(i,j)]*wht[i]%P*blk[j]%P)%P;
  27. }
  28. }
  29. int main(){
  30. scanf("%d",&n);
  31. pre_cal();
  32. solve();
  33. for(int i=1,lim=n<<1;i<=lim;++i)
  34. printf("%d ",ans[i]);
  35. return 0;
  36. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注