[关闭]
@KirinBill 2017-09-19T09:34:47.000000Z 字数 5498 阅读 538

2017.9.14 NOIP模拟赛

题解 套题

目录


Bookstore

rWvaX.png
rWSBe.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. x=0;
  13. int pm=1; char c;
  14. do{c=getchar();}while(!isdigit(c) && c!='-');
  15. c=='-' ? pm=-1:x=c^'0';
  16. while(c=getchar(),isdigit(c))
  17. x=x*10+(c^'0');
  18. x*=pm;
  19. }
  20. template<typename type>
  21. void write(type x,char c=0){
  22. if(x<0) putchar('-'),x=-x;
  23. if(x>9) write(x/10);
  24. putchar(x%10|'0');
  25. if(c) putchar(c);
  26. }
  27. #include <algorithm>
  28. using std::sort;
  29. const int MAXN=1e5+5;
  30. int n,lim;
  31. int c[MAXN];
  32. long long ans;
  33. inline bool cmp(int a,int b){
  34. return a>b;
  35. }
  36. int main(){
  37. setIO("bookstore");
  38. read(n);
  39. for(int i=1;i<=n;++i)
  40. read(c[i]);
  41. sort(c+1,c+n+1,cmp);
  42. lim=n/3*3;
  43. for(int i=1;i<=lim;i+=3)
  44. ans+=c[i]+c[i+1];
  45. for(int i=lim+1;i<=n;++i)
  46. ans+=c[i];
  47. write(ans);
  48. return 0;
  49. }

Table

rWb9c.png
rW728.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. x=0;
  13. int pm=1; char c;
  14. do{c=getchar();}while(!isdigit(c) && c!='-');
  15. c=='-' ? pm=-1:x=c^'0';
  16. while(c=getchar(),isdigit(c))
  17. x=x*10+(c^'0');
  18. x*=pm;
  19. }
  20. template<typename type>
  21. void write(type x,char c=0){
  22. if(x<0) putchar('-'),x=-x;
  23. if(x>9) write(x/10);
  24. putchar(x%10|'0');
  25. if(c) putchar(c);
  26. }
  27. #include <cstring>
  28. const int MAXN=2005,P=1e9;
  29. int n,m;
  30. int tab[MAXN][MAXN],dp[MAXN][MAXN];
  31. inline void pre_tab(){
  32. for(int i=0;i<MAXN;++i)
  33. tab[0][i]=1;
  34. for(int i=1;i<MAXN;++i){
  35. tab[i][0]=tab[i-1][0];
  36. for(int j=1;j<MAXN;++j)
  37. tab[i][j]=(tab[i-1][j]+tab[i][j-1])%P;
  38. }
  39. for(int i=1;i<MAXN;++i){
  40. for(int j=MAXN-1;j;--j)
  41. tab[i][j]=(tab[i][j]-tab[i][j-1]+P)%P;
  42. }
  43. }
  44. inline int DP(){
  45. memset(dp,0,sizeof(dp));
  46. dp[1][0]=tab[m][0];
  47. for(int i=1;i<=m;++i)
  48. dp[1][i]=(tab[m][i]+dp[1][i-1])%P;
  49. for(int i=2;i<=n;++i){
  50. dp[i][0]=(long long)dp[i-1][0]*tab[m][0]%P;
  51. for(int j=1;j<=m;++j)
  52. dp[i][j]=((long long)dp[i-1][j]*tab[m][j]%P+dp[i][j-1])%P;
  53. }
  54. return dp[n][m];
  55. }
  56. int main(){
  57. setIO("table");
  58. pre_tab();
  59. int T;
  60. read(T);
  61. while(T--){
  62. read(n),read(m);
  63. write(DP(),'\n');
  64. }
  65. return 0;
  66. }

Board

rWh1g.png
rW08N.png
rW3EG.png

思路

代码

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <cmath>
  5. #define ls (u<<1)
  6. #define rs (ls|1)
  7. using std::swap;
  8. using std::min;
  9. using std::abs;
  10. const int MAXN=1e5+5;
  11. int ns,nt;
  12. char cmd[MAXN],s[MAXN],t[MAXN];
  13. class segT{
  14. private:
  15. int n;
  16. struct node{int sum,tag;}d[MAXN<<2];
  17. void upd(int u){
  18. d[u].sum=d[ls].sum+d[rs].sum;
  19. }
  20. void push_d(int u,int l,int r){
  21. if(l==r || !d[u].tag) return;
  22. int mid=l+r>>1;
  23. d[ls].sum=(mid-l+1)*(d[u].tag-1);
  24. d[ls].tag=d[u].tag;
  25. d[rs].sum=(r-mid)*(d[u].tag-1);
  26. d[rs].tag=d[u].tag;
  27. d[u].tag=0;
  28. }
  29. void mdf(int u,int lp,int rp,int l,int r,int k){
  30. if(l<=lp && rp<=r){
  31. d[u].sum=(rp-lp+1)*(k-1);
  32. d[u].tag=k;
  33. return;
  34. }
  35. push_d(u,lp,rp);
  36. int mid=lp+rp>>1;
  37. if(l<=mid) mdf(ls,lp,mid,l,r,k);
  38. if(r>mid) mdf(rs,mid+1,rp,l,r,k);
  39. upd(u);
  40. }
  41. int qry(int u,int lp,int rp,int r,int k){
  42. if(lp>r) return 0;
  43. if(lp==rp) return d[u].sum==k ? lp:0;
  44. if(k==1 && d[u].sum==0) return 0;
  45. else if(k==0 && d[u].sum==rp-lp+1) return 0;
  46. push_d(u,lp,rp);
  47. int mid=lp+rp>>1;
  48. int ret=qry(rs,mid+1,rp,r,k);
  49. if(ret==0) ret=qry(ls,lp,mid,r,k);
  50. return ret;
  51. }
  52. void prt(int u,int lp,int rp,int r,char c[]){
  53. if(lp>r) return;
  54. if(lp==rp){
  55. c[lp]=d[u].sum|'0';
  56. return;
  57. }
  58. push_d(u,lp,rp);
  59. int mid=lp+rp>>1;
  60. prt(ls,lp,mid,r,c);
  61. prt(rs,mid+1,rp,r,c);
  62. }
  63. public:
  64. void sgl_mdf(int pos,int k){mdf(1,1,n,pos,pos,k+1);}
  65. void rge_mdf(int l,int r,int k){
  66. if(l>r) return;
  67. mdf(1,1,n,l,r,k+1);
  68. }
  69. int qry(int r,int k){return qry(1,1,n,r,k);}
  70. void init(int sz){
  71. memset(d,0,sizeof(d));
  72. n=sz;
  73. sgl_mdf(1,1);
  74. }
  75. void out(int r,char c[]){prt(1,1,n,r,c);}
  76. }T;
  77. inline int find(char c[]){
  78. int lastbit=1,lim=strlen(cmd+1)+1;
  79. T.init(lim);
  80. for(int i=1,lowbit;i<=lim;++i){
  81. switch(cmd[i]){
  82. case '1': ++lastbit;
  83. T.sgl_mdf(lastbit,0);
  84. break;
  85. case '2': ++lastbit;
  86. T.sgl_mdf(lastbit,1);
  87. break;
  88. case 'U': --lastbit;
  89. break;
  90. case 'L': lowbit=T.qry(lastbit,1);
  91. T.sgl_mdf(lowbit,0);
  92. T.rge_mdf(lowbit+1,lastbit,1);
  93. break;
  94. case 'R': lowbit=T.qry(lastbit,0);
  95. T.sgl_mdf(lowbit,1);
  96. T.rge_mdf(lowbit+1,lastbit,0);
  97. break;
  98. }
  99. }
  100. T.out(lastbit,c);
  101. return lastbit;
  102. }
  103. inline int cal_dis(){
  104. int n=min(ns,nt);
  105. int lim=n-1<<1,disy=abs(nt-ns)+lim,ret=disy;
  106. bool apart=false;
  107. for(int i=2,disx=0;i<=n;++i){
  108. disy-=2;
  109. if(apart){
  110. disx=disx<<1|1;
  111. if(s[i]=='1') --disx;
  112. if(t[i]=='0') --disx;
  113. }
  114. else if(s[i]!=t[i]){
  115. apart=true;
  116. ++disx;
  117. if(s[i]=='1') swap(s,t);
  118. }
  119. if(disx>ret) break;
  120. ret=min(ret,disx+disy);
  121. }
  122. return ret;
  123. }
  124. int main(){
  125. freopen("board.in","r",stdin);
  126. freopen("board.out","w",stdout);
  127. scanf("%s",cmd+1);
  128. ns=find(s);
  129. scanf("%s",cmd+1);
  130. nt=find(t);
  131. printf("%d",cal_dis());
  132. return 0;
  133. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注