[关闭]
@KirinBill 2017-10-23T08:19:43.000000Z 字数 6548 阅读 605

2017.10.21 NOIP模拟赛

题解 套题

目录


最长不下降子序列

WbVKy.png
WbyJg.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 <cstring>
  31. using std::max;
  32. using std::min;
  33. using std::upper_bound;
  34. const int MAXN=350;
  35. int t,A,B,C,D,len,last,first;
  36. int a[MAXN*MAXN],pos[MAXN];
  37. long long n;
  38. inline void prod_seq(){
  39. a[1]=t;
  40. pos[t]=1;
  41. for(int i=2;;++i){
  42. t=(A*t*t%D+B*t%D+C)%D;
  43. if(pos[t]){
  44. first=pos[t];
  45. last=t;
  46. len=i-1;
  47. return;
  48. }
  49. pos[t]=i;
  50. a[i]=t;
  51. }
  52. }
  53. inline long long DP(){
  54. static int dp[MAXN*MAXN];
  55. int nocir=first-1;
  56. int cir=len-nocir;
  57. int pre=len;
  58. len+=cir*(cir-1)-nocir;
  59. long long now=nocir+len+(n-len-nocir)%len;
  60. if(now>n) now=n;
  61. for(int i=pre+1;i<=now;++i)
  62. a[i]=a[i-cir];
  63. long long rest= (n-len-nocir)/len>0 ? (n-len-nocir)/len:0;
  64. rest*=cir;
  65. memset(dp,0x7f,sizeof(dp));
  66. long long ret=0,tmp;
  67. for(int i=1;i<=now;++i){
  68. tmp=upper_bound(dp+1,dp+now+1,a[i])-dp;
  69. dp[tmp]=min(dp[tmp],a[i]);
  70. if(i>nocir) tmp+=rest;
  71. ret=max(ret,tmp);
  72. }
  73. return ret;
  74. }
  75. int main(){
  76. setIO("lis");
  77. read(n);
  78. read(t),read(A),read(B),read(C),read(D);
  79. prod_seq();
  80. write(DP());
  81. return 0;
  82. }

完全背包问题

Wb21X.png
WbJbG.png

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <bitset>
  4. #include <cstring>
  5. #include <queue>
  6. using std::sort;
  7. using std::min;
  8. using std::queue;
  9. const int MAXN=55;
  10. int n,l,c;
  11. long long w[MAXN];
  12. namespace solve1{
  13. const int MAXW=3000005;
  14. int dp[MAXW];
  15. inline void DP(){
  16. static queue<int> que;
  17. memset(dp,0x7f,sizeof(dp));
  18. dp[0]=0;
  19. que.push(0);
  20. int u,v;
  21. while(que.size()){
  22. u=que.front();
  23. que.pop();
  24. if(dp[u]>=c) continue;
  25. for(int i=1,d;i<=n;++i){
  26. v=u+w[i],d=dp[u]+1;
  27. if(dp[v]>d){
  28. dp[v]=d;
  29. que.push(v);
  30. }
  31. }
  32. }
  33. }
  34. inline bool jud(long long v){return v<=MAXW && dp[v]<=c;}
  35. }
  36. namespace solve2{
  37. const int MAXC=35,MAXW=20005;
  38. long long dp[MAXC][MAXW];
  39. struct node{
  40. int c;
  41. long long w;
  42. };
  43. inline void DP(){
  44. static bool inQ[MAXC][MAXW];
  45. static queue<node> que;
  46. memset(dp,0x7f,sizeof(dp));
  47. dp[0][0]=0;
  48. que.push((node){0,0});
  49. inQ[0][0]=true;
  50. node u,v;
  51. while(que.size()){
  52. u=que.front();
  53. que.pop();
  54. inQ[u.c][u.w%w[1]]=false;
  55. for(int i=1,d;i<=n;++i){
  56. v.w=u.w+w[i];
  57. v.c=u.c;
  58. if(w[i]>=l) ++v.c;
  59. if(v.c>c) continue;
  60. else if(dp[v.c][v.w%w[1]]>v.w){
  61. dp[v.c][v.w%w[1]]=v.w;
  62. if(!inQ[v.c][v.w%w[1]]){
  63. que.push(v);
  64. inQ[v.c][v.w%w[1]]=true;
  65. }
  66. }
  67. }
  68. }
  69. for(int i=1;i<=c;++i){
  70. for(int j=0;j<w[1];++j)
  71. dp[i][j]=min(dp[i][j],dp[i-1][j]);
  72. }
  73. }
  74. inline bool jud(long long v){return dp[c][v%w[1]]<=v;}
  75. }
  76. int main(){
  77. freopen("bag.in","r",stdin);
  78. freopen("bag.out","w",stdout);
  79. int m;
  80. scanf("%d%d",&n,&m);
  81. for(int i=1;i<=n;++i)
  82. scanf("%lld",&w[i]);
  83. scanf("%d%d",&l,&c);
  84. sort(w+1,w+n+1);
  85. bool (*jud)(long long);
  86. if(w[1]>=l){
  87. solve1::DP();
  88. jud=solve1::jud;
  89. }
  90. else{
  91. solve2::DP();
  92. jud=solve2::jud;
  93. }
  94. long long v;
  95. for(int i=1;i<=m;++i){
  96. scanf("%lld",&v);
  97. if(jud(v)) puts("Yes");
  98. else puts("No");
  99. }
  100. return 0;
  101. }

最近公共祖先

WadB8.png
Wbkej.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;
  32. int n;
  33. class segT{
  34. private:
  35. struct node{int ls,rs,l,r,max;}d[MAXN<<2];
  36. int new_nd(){
  37. static int cnt=1;
  38. return ++cnt;
  39. }
  40. void push_d(int u){
  41. int ls=d[u].ls,rs=d[u].rs;
  42. int &tag=d[u].max;
  43. d[ls].max=max(d[ls].max,tag);
  44. d[rs].max=max(d[rs].max,tag);
  45. }
  46. void mdf(int u,int lp,int rp,int x){
  47. if(lp<=d[u].l && d[u].r<=rp){
  48. d[u].max=max(d[u].max,x);
  49. return;
  50. }
  51. push_d(u);
  52. int mid=d[u].l+d[u].r>>1;
  53. if(lp<=mid) mdf(d[u].ls,lp,rp,x);
  54. if(rp>mid) mdf(d[u].rs,lp,rp,x);
  55. }
  56. int qry(int u,int pos){
  57. if(d[u].l==d[u].r) return d[u].max;
  58. push_d(u);
  59. int mid=d[u].l+d[u].r>>1;
  60. if(pos<=mid) return qry(d[u].ls,pos);
  61. else return qry(d[u].rs,pos);
  62. }
  63. void build(int u,int l,int r){
  64. d[u].max=-1;
  65. d[u].l=l,d[u].r=r;
  66. if(l==r) return;
  67. int mid=l+r>>1;
  68. d[u].ls=new_nd();
  69. build(d[u].ls,l,mid);
  70. d[u].rs=new_nd();
  71. build(d[u].rs,mid+1,r);
  72. }
  73. public:
  74. void build(){build(1,1,n);}
  75. void mdf(int lp,int rp,int x){
  76. if(lp>rp) return;
  77. mdf(1,lp,rp,x);
  78. }
  79. int qry(int pos){return qry(1,pos);}
  80. };
  81. class TP{
  82. private:
  83. struct node{
  84. int w,he,fa,top,id,sz,hson,lpos;
  85. bool blk,mdf;
  86. }d[MAXN];
  87. struct line{int to,nex;}ed[MAXN<<1];
  88. segT T;
  89. void addE(int u,int v){
  90. static int cnt;
  91. ed[++cnt]=(line){v,d[u].he};
  92. d[u].he=cnt;
  93. }
  94. void DFS(int u,int fa){
  95. d[u].sz=1;
  96. for(int i=d[u].he,v,&hson=d[u].hson;i;i=ed[i].nex){
  97. v=ed[i].to;
  98. if(v!=fa){
  99. d[v].fa=u;
  100. DFS(v,u);
  101. d[u].sz+=d[v].sz;
  102. if(d[v].sz>d[hson].sz) hson=v;
  103. }
  104. }
  105. }
  106. void link(int u,int fa){
  107. static int cnt;
  108. d[u].id=++cnt;
  109. d[u].top= d[fa].hson==u ? d[fa].top:u;
  110. int hson=d[u].hson;
  111. if(hson) link(hson,u);
  112. for(int i=d[u].he,v;i;i=ed[i].nex){
  113. v=ed[i].to;
  114. if(v!=fa && v!=hson) link(v,u);
  115. }
  116. d[u].lpos=cnt;
  117. }
  118. public:
  119. void init(){
  120. for(int i=1;i<=n;++i)
  121. read(d[i].w);
  122. for(int i=1,u,v;i<n;++i){
  123. read(u),read(v);
  124. addE(u,v),addE(v,u);
  125. }
  126. }
  127. void build(){
  128. DFS(1,0);
  129. link(1,0);
  130. T.build();
  131. }
  132. void mdf(int u){
  133. if(d[u].blk) return;
  134. T.mdf(d[u].id,d[u].lpos,d[u].w);
  135. d[u].blk=true;
  136. int fa;
  137. while(d[u].fa){
  138. fa=d[u].fa;
  139. T.mdf(d[fa].id,d[u].id-1,d[fa].w);
  140. T.mdf(d[u].lpos+1,d[fa].lpos,d[fa].w);
  141. if(d[fa].mdf) break;
  142. d[fa].mdf=true;
  143. u=fa;
  144. }
  145. }
  146. int qry(int u){return T.qry(d[u].id);}
  147. }T;
  148. int main(){
  149. setIO("lca");
  150. int m;
  151. read(n),read(m);
  152. T.init();
  153. T.build();
  154. char cmd[10];
  155. for(int i=1,v;i<=m;++i){
  156. scanf("%s%d",cmd,&v);
  157. if(cmd[0]=='Q') write(T.qry(v),'\n');
  158. else T.mdf(v);
  159. }
  160. return 0;
  161. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注