[关闭]
@KirinBill 2017-10-26T09:27:50.000000Z 字数 5586 阅读 1058

2017.10.26 NOIP模拟赛

题解 套题

目录


string

q8w4J.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 <cstring>
  30. const int MAXN=100005;
  31. int n;
  32. char s[MAXN];
  33. class segT{
  34. private:
  35. struct data{
  36. int tag;
  37. int c[26];
  38. void clear(){
  39. tag=0;
  40. memset(c,0,sizeof(c));
  41. }
  42. data(){clear();}
  43. int& operator [](int i){return c[i];}
  44. void operator ()(int cnt,data &that){
  45. clear();
  46. tag=that.tag;
  47. //1 up,-1 dwn
  48. for(int i= tag>0 ? 0:25;0<=i && i<26;i+=tag){
  49. if(that[i]>=cnt){
  50. c[i]=cnt;
  51. that[i]-=cnt;
  52. return;
  53. }
  54. else{
  55. c[i]=that[i];
  56. cnt-=that[i];
  57. that[i]=0;
  58. }
  59. }
  60. }
  61. data operator +(const data &that)const{
  62. data ret;
  63. for(int i=0;i<26;++i)
  64. ret[i]=c[i]+that.c[i];
  65. return ret;
  66. }
  67. data& operator +=(const data &that){
  68. *this=*this+that;
  69. return *this;
  70. }
  71. };
  72. struct node{
  73. int l,r,ls,rs;
  74. data c;
  75. int len(){return r-l+1;}
  76. }d[MAXN<<2];
  77. int new_nd(){
  78. static int cnt=1;
  79. return ++cnt;
  80. }
  81. void upd(int u){
  82. d[u].c=d[d[u].ls].c+d[d[u].rs].c;
  83. }
  84. void push_d(int u){
  85. if(!d[u].c.tag) return;
  86. int ls=d[u].ls,rs=d[u].rs;
  87. data tmp=d[u].c;
  88. d[ls].c(d[ls].len(),tmp);
  89. d[rs].c(d[rs].len(),tmp);
  90. d[u].c.tag=0;
  91. }
  92. data qry(int u,int lp,int rp){
  93. if(lp<=d[u].l && d[u].r<=rp)
  94. return d[u].c;
  95. push_d(u);
  96. int mid=d[u].l+d[u].r>>1;
  97. data ret;
  98. if(lp<=mid) ret=qry(d[u].ls,lp,rp);
  99. if(rp>mid) ret+=qry(d[u].rs,lp,rp);
  100. return ret;
  101. }
  102. void mdf(int u,int lp,int rp,data &sum){
  103. if(lp<=d[u].l && d[u].r<=rp){
  104. d[u].c(d[u].len(),sum);
  105. return;
  106. }
  107. push_d(u);
  108. int mid=d[u].l+d[u].r>>1;
  109. if(lp<=mid) mdf(d[u].ls,lp,rp,sum);
  110. if(rp>mid) mdf(d[u].rs,lp,rp,sum);
  111. upd(u);
  112. }
  113. void prt(int u){
  114. if(d[u].l==d[u].r){
  115. for(int i=0;i<26;++i){
  116. if(d[u].c[i]){
  117. s[d[u].l]=i+'a';
  118. return;
  119. }
  120. }
  121. }
  122. push_d(u);
  123. int mid=d[u].l+d[u].r>>1;
  124. prt(d[u].ls),prt(d[u].rs);
  125. }
  126. void build(int u,int l,int r){
  127. d[u].l=l,d[u].r=r;
  128. if(l==r){
  129. d[u].c[s[l]-'a']=1;
  130. return;
  131. }
  132. int mid=l+r>>1;
  133. d[u].ls=new_nd();
  134. build(d[u].ls,l,mid);
  135. d[u].rs=new_nd();
  136. build(d[u].rs,mid+1,r);
  137. upd(u);
  138. }
  139. public:
  140. void build(){build(1,1,n);}
  141. void sort(int lp,int rp,int type){
  142. type= type ? 1:-1;
  143. data sum=qry(1,lp,rp);
  144. sum.tag=type;
  145. mdf(1,lp,rp,sum);
  146. }
  147. void prt(){prt(1);}
  148. }T;
  149. int main(){
  150. setIO("string");
  151. int m;
  152. read(n),read(m);
  153. scanf("%s",s+1);
  154. T.build();
  155. for(int i=1,l,r,type;i<=m;++i){
  156. read(l),read(r),read(type);
  157. T.sort(l,r,type);
  158. }
  159. T.prt();
  160. printf("%s",s+1);
  161. return 0;
  162. }

matrix

q8gAt.png

思路

代码

  1. #include <cstdio>
  2. const int MAXN=3005,P=998244353;
  3. int n,m;
  4. int l[MAXN],r[MAXN],prel[MAXN],prer[MAXN];
  5. inline int DP(){
  6. static int dp[MAXN][MAXN];
  7. dp[0][0]=1;
  8. for(int i=1;i<=m;++i){
  9. dp[i][0]=dp[i-1][0];
  10. for(int j=1;j<=i && prer[i]>=j-1;++j)
  11. dp[i][j]=(dp[i-1][j]+(long long)dp[i-1][j-1]*(prer[i]-(j-1))%P)%P;
  12. for(int j=prel[i-1];j<prel[i];++j){
  13. for(int k=0;k+j<=i;++k)
  14. dp[i][k]=(long long)dp[i][k]*(i-j-k)%P;
  15. }
  16. }
  17. return dp[m][n];
  18. }
  19. int main(){
  20. freopen("matrix.in","r",stdin);
  21. freopen("matrix.out","w",stdout);
  22. scanf("%d%d",&n,&m);
  23. for(int i=1;i<=n;++i){
  24. scanf("%d%d",&l[i],&r[i]);
  25. ++prel[l[i]],++prer[r[i]];
  26. }
  27. for(int i=1;i<=m;++i){
  28. prel[i]+=prel[i-1];
  29. prer[i]+=prer[i-1];
  30. }
  31. printf("%d",DP());
  32. return 0;
  33. }

big

q8kBF.png
q8VwM.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. #include <functional>
  31. using std::sort;
  32. using std::greater;
  33. const int MAXM=100005,MAXN=30;
  34. int n,m;
  35. int a[MAXM],xor_suf[MAXM],ans[MAXM];
  36. class Trie{
  37. private:
  38. int c[MAXM*MAXN][2];
  39. int new_nd(){
  40. static int cnt;
  41. return ++cnt;
  42. }
  43. void trans(int u,int step,int num){
  44. if(step<0){
  45. ans[++ans[0]]=num;
  46. return;
  47. }
  48. if(!c[u][0] && c[u][1])
  49. trans(c[u][1],step-1,num|1<<step);
  50. else if(!c[u][1] && c[u][0])
  51. trans(c[u][0],step-1,num|1<<step);
  52. else if(c[u][0] && c[u][1]){
  53. trans(c[u][0],step-1,num);
  54. trans(c[u][1],step-1,num);
  55. }
  56. }
  57. public:
  58. void ist(int x){
  59. for(int u=0,i=n-1;i>=0;--i){
  60. if(!c[u][(bool)(x&1<<i)])
  61. c[u][(bool)(x&1<<i)]=new_nd();
  62. u=c[u][(bool)(x&1<<i)];
  63. }
  64. }
  65. void trans(){trans(0,n-1,0);}
  66. }T;
  67. int main(){
  68. setIO("big");
  69. read(n),read(m);
  70. for(int i=1;i<=m;++i)
  71. read(a[i]);
  72. for(int i=m;i;--i)
  73. xor_suf[i]=a[i]^xor_suf[i+1];
  74. for(int i=0,xor_pre=0;i<=m;++i){
  75. xor_pre^=a[i];
  76. T.ist((xor_pre<<1>>n)+(xor_pre<<1)&(1<<n)-1^xor_suf[i+1]);
  77. }
  78. T.trans();
  79. sort(ans+1,ans+ans[0]+1,greater<int>());
  80. write(ans[1],'\n');
  81. int cnt=0;
  82. for(int i=1;ans[i]==ans[1] && i<=ans[0];++i)
  83. ++cnt;
  84. write(cnt);
  85. return 0;
  86. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注