[关闭]
@KirinBill 2017-10-09T07:12:19.000000Z 字数 7478 阅读 1042

2017.10.8 NOIP模拟赛

题解 套题

目录


逗你玩

Ahxig.png
AhSoW.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 <queue>
  30. #include <cstring>
  31. using std::queue;
  32. const int MAXN=5,all=(1<<9)-1;
  33. int dirx[]={0,1,0,-1,0},diry[]={0,0,1,0,-1};
  34. int G[MAXN][MAXN],id[MAXN][MAXN],his[MAXN][MAXN][1<<9][200];
  35. struct state{
  36. int x,y,rest,tm,vis;
  37. state(){x=y=rest=tm=vis=0;}
  38. };
  39. inline bool inG(state &u){
  40. return 1<=u.x && u.x<=3 && 1<=u.y && u.y<=3;
  41. }
  42. inline bool jud(state &u){
  43. if(u.tm<his[u.x][u.y][u.vis][u.rest]){
  44. his[u.x][u.y][u.vis][u.rest]=u.tm;
  45. return true;
  46. }
  47. else return false;
  48. }
  49. inline int BFS(){
  50. static queue<state> que;
  51. memset(his,0x7f,sizeof(his));
  52. state u,v;
  53. u.x=1,u.y=1;
  54. u.rest=G[1][1];
  55. u.tm=1;
  56. u.vis=1;
  57. que.push(u);
  58. while(que.size()){
  59. u=que.front();
  60. que.pop();
  61. if(u.rest<0) break;
  62. for(int i=0;i<5;++i){
  63. v.x=u.x+dirx[i],v.y=u.y+diry[i];
  64. v.rest=u.rest+G[v.x][v.y];
  65. v.tm=u.tm+1;
  66. if(!inG(v) || v.rest<0) continue;
  67. v.vis=u.vis;
  68. v.vis|=id[v.x][v.y];
  69. if(jud(v)){
  70. if(v.vis==all) return v.tm;
  71. que.push(v);
  72. }
  73. }
  74. }
  75. return -1;
  76. }
  77. int main(){
  78. #ifdef DEBUG
  79. setIO("a");
  80. #endif
  81. for(int i=1,cnt=0;i<=3;++i){
  82. for(int j=1;j<=3;++j){
  83. read(G[i][j]);
  84. id[i][j]=1<<cnt++;
  85. }
  86. }
  87. write(BFS());
  88. return 0;
  89. }

简单题

Ah00L.png
Ahpri.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 <queue>
  30. #include <algorithm>
  31. #include <cstring>
  32. using std::queue;
  33. using std::max;
  34. const int MAXN=505,MAXM=3005;
  35. int n,m,s1,t1,s2,t2,l1,l2;
  36. int he[MAXN],dis[MAXN][MAXN];
  37. struct line{int to,nex;}ed[MAXM<<1];
  38. inline void addE(int u,int v){
  39. static int cnt=0;
  40. ed[++cnt]=(line){v,he[u]};
  41. he[u]=cnt;
  42. }
  43. inline void BFS(int s){
  44. static queue<int> que;
  45. memset(dis[s],-1,sizeof(dis[s]));
  46. int *d=dis[s];
  47. d[s]=0;
  48. que.push(s);
  49. int u;
  50. while(que.size()){
  51. u=que.front();
  52. que.pop();
  53. for(int i=he[u],v;i;i=ed[i].nex){
  54. v=ed[i].to;
  55. if(d[v]==-1){
  56. d[v]=d[u]+1;
  57. que.push(v);
  58. }
  59. }
  60. }
  61. }
  62. inline void cal_dis(){
  63. for(int i=1;i<=n;++i) BFS(i);
  64. }
  65. inline int solve(){
  66. if(dis[s1][t1]>l1 || dis[s2][t2]>l2 || dis[s1][t1]==-1 || dis[s2][t2]==-1)
  67. return -1;
  68. int ret=m-dis[s1][t1]-dis[s2][t2];
  69. for(int i=1;i<=n;++i){
  70. for(int j=1;j<=n;++j){
  71. if(dis[s1][i]==-1 || dis[i][j]==-1 || dis[j][t1]==-1 || dis[s2][i]==-1 || dis[j][t2]==-1)
  72. continue;
  73. if(dis[s1][i]+dis[i][j]+dis[j][t1]<=l1 && dis[s2][i]+dis[i][j]+dis[j][t2]<=l2)
  74. ret=max(ret,m-dis[s1][i]-dis[s2][i]-dis[i][j]-dis[j][t1]-dis[j][t2]);
  75. }
  76. for(int j=1;j<=n;++j){
  77. if(dis[s1][j]==-1 || dis[i][j]==-1 || dis[i][t1]==-1 || dis[s2][i]==-1 || dis[j][t2]==-1)
  78. continue;
  79. if(dis[s1][j]+dis[j][i]+dis[i][t1]<=l1 && dis[s2][i]+dis[i][j]+dis[j][t2]<=l2)
  80. ret=max(ret,m-dis[s1][j]-dis[s2][i]-dis[i][j]-dis[i][t1]-dis[j][t2]);
  81. }
  82. }
  83. return ret;
  84. }
  85. int main(){
  86. #ifdef DEBUG
  87. setIO("b");
  88. #endif
  89. read(n),read(m);
  90. read(s1),read(t1),read(l1);
  91. read(s2),read(t2),read(l2);
  92. for(int i=1,u,v;i<=m;++i){
  93. read(u),read(v);
  94. addE(u,v),addE(v,u);
  95. }
  96. cal_dis();
  97. write(solve());
  98. return 0;
  99. }

采矿

AhBcw.png
AhTWX.png
AhFNR.png
AhPz8.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. #include <climits>
  31. #include <algorithm>
  32. using std::max;
  33. using std::sort;
  34. const int MAXN=20005,MAXM=55;
  35. int n,m,A,B,Q;
  36. int data[MAXN][MAXM],id[MAXN],subt[MAXM],edge[MAXM];
  37. class segT{
  38. #define ls (u<<1)
  39. #define rs (ls|1)
  40. private:
  41. struct node{int subt[MAXM],edge[MAXM];}d[MAXN<<2];
  42. void upd(int u){
  43. for(int i=1;i<=m;++i){
  44. d[u].subt[i]=d[u].edge[i]=max(d[ls].edge[i],d[rs].edge[i]);
  45. for(int j=0;j<=i;++j)
  46. d[u].subt[i]=max(d[u].subt[i],d[ls].subt[j]+d[rs].subt[i-j]);
  47. }
  48. }
  49. void build(int u,int l,int r){
  50. if(l==r){
  51. for(int i=1;i<=m;++i)
  52. d[u].subt[i]=d[u].edge[i]=data[id[l]][i];
  53. return;
  54. }
  55. int mid=l+r>>1;
  56. build(ls,l,mid),build(rs,mid+1,r);
  57. upd(u);
  58. }
  59. void mdf(int u,int l,int r,int pos){
  60. if(l==r){
  61. for(int i=1;i<=m;++i)
  62. d[u].subt[i]=d[u].edge[i]=data[id[l]][i];
  63. return;
  64. }
  65. int mid=l+r>>1;
  66. if(pos<=mid) mdf(ls,l,mid,pos);
  67. else mdf(rs,mid+1,r,pos);
  68. upd(u);
  69. }
  70. void qry_subt(int u,int l,int r,int lp,int rp){
  71. if(lp<=l && r<=rp){
  72. for(int i=m;i;--i){
  73. for(int j=0;j<i;++j)
  74. subt[i]=max(subt[i],subt[j]+d[u].subt[i-j]);
  75. }
  76. return;
  77. }
  78. int mid=l+r>>1;
  79. if(lp<=mid) qry_subt(ls,l,mid,lp,rp);
  80. if(rp>mid) qry_subt(rs,mid+1,r,lp,rp);
  81. }
  82. void qry_edge(int u,int l,int r,int lp,int rp){
  83. if(lp<=l && r<=rp){
  84. for(int i=1;i<=m;++i)
  85. edge[i]=max(edge[i],d[u].edge[i]);
  86. return;
  87. }
  88. int mid=l+r>>1;
  89. if(lp<=mid) qry_edge(ls,l,mid,lp,rp);
  90. if(rp>mid) qry_edge(rs,mid+1,r,lp,rp);
  91. }
  92. public:
  93. void build(){build(1,1,n);}
  94. void qry_subt(int l,int r){qry_subt(1,1,n,l,r);}
  95. void qry_edge(int l,int r){qry_edge(1,1,n,l,r);}
  96. void mdf(int pos){mdf(1,1,n,pos);}
  97. #undef ls
  98. #undef rs
  99. };
  100. class TP{
  101. private:
  102. struct node{int he,hson,top,lpos,sz,fa,id;}d[MAXN];
  103. struct line{int to,nex;}ed[MAXN];
  104. segT T;
  105. void addE(int u,int v){
  106. static int cnt=0;
  107. ed[++cnt]=(line){v,d[u].he};
  108. d[u].he=cnt;
  109. }
  110. void DFS(int u){
  111. int fa=d[u].fa;
  112. d[u].sz=1;
  113. for(int i=d[u].he,v,&hson=d[u].hson;i;i=ed[i].nex){
  114. v=ed[i].to;
  115. DFS(v);
  116. if(d[v].sz>d[hson].sz) hson=v;
  117. d[u].sz+=d[v].sz;
  118. }
  119. }
  120. void link(int u){
  121. static int cnt=0;
  122. d[u].id=++cnt;
  123. id[cnt]=u;
  124. int fa=d[u].fa;
  125. d[u].top= d[fa].hson==u ? d[fa].top:u;
  126. int hson=d[u].hson;
  127. if(hson) link(hson);
  128. for(int i=d[u].he,v;i;i=ed[i].nex){
  129. v=ed[i].to;
  130. if(v!=hson) link(v);
  131. }
  132. d[u].lpos=cnt;
  133. }
  134. public:
  135. void init(){
  136. for(int i=2;i<=n;++i){
  137. read(d[i].fa);
  138. addE(d[i].fa,i);
  139. }
  140. }
  141. void build(){
  142. DFS(1);
  143. link(1);
  144. T.build();
  145. }
  146. void mdf(int u){T.mdf(d[u].id);}
  147. int qry(int u,int v){
  148. memset(subt,0,sizeof(subt));
  149. memset(edge,0,sizeof(edge));
  150. T.qry_subt(d[u].id,d[u].lpos);
  151. if(u!=v){
  152. u=d[u].fa;
  153. while(d[u].top!=d[v].top){
  154. T.qry_edge(d[d[u].top].id,d[u].id);
  155. u=d[d[u].top].fa;
  156. }
  157. T.qry_edge(d[v].id,d[u].id);
  158. }
  159. int ret=0;
  160. for(int i=0;i<=m;++i)
  161. ret=max(ret,subt[i]+edge[m-i]);
  162. return ret;
  163. }
  164. }T;
  165. inline int getint(){
  166. static const int X=1<<16,Y=INT_MAX;
  167. A=((A^B)+B/X+B*X)&Y;
  168. B=((A^B)+A/X+A*X)&Y;
  169. return (A^B)%Q;
  170. }
  171. inline void prod_data(int a[]){
  172. for(int i=1;i<=m;++i)
  173. a[i]=getint();
  174. sort(a+1,a+m+1);
  175. }
  176. int main(){
  177. #ifdef DEBUG
  178. setIO("c");
  179. #endif
  180. read(n),read(m);
  181. read(A),read(B),read(Q);
  182. T.init();
  183. for(int i=1;i<=n;++i)
  184. prod_data(data[i]);
  185. T.build();
  186. int C;
  187. read(C);
  188. for(int i=1,type,p,u,v;i<=C;++i){
  189. read(type);
  190. if(type==0){
  191. read(p);
  192. prod_data(data[p]);
  193. T.mdf(p);
  194. }
  195. else{
  196. read(u),read(v);
  197. write(T.qry(u,v),'\n');
  198. }
  199. }
  200. return 0;
  201. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注