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

2017.10.8 NOIP模拟赛

题解 套题

目录

逗你玩

Ahxig.png
AhSoW.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  5. using std::string;
  7. inline void setIO(string file){
  8.     string in=file+".in",out=file+".out";
  9.     freopen(in.c_str(),"r",stdin);
  10.     freopen(out.c_str(),"w",stdout);
  11. }
  13. template<typename type>
  14. inline void read(type &x){
  15.     int pm=1; char c;
  16.     do{
  17.         c=getchar();
  18.         if(c=='-') pm=-1;
  19.     }while(!isdigit(c));
  20.     x=c^'0';
  21.     while(c=getchar(),isdigit(c))
  22.         x=x*10+(c^'0');
  23.     x*=pm;
  24. }
  26. template<typename type>
  27. void write(type x,char c=0){
  28.     if(x<0) putchar('-'),x=-x;
  29.     if(x>9) write(x/10);
  30.     putchar(x%10|'0');
  31.     if(c) putchar(c);
  32. }
  34. #include <queue>
  35. #include <cstring>
  37. using std::queue;
  39. const int MAXN=5,all=(1<<9)-1;
  40. int dirx[]={0,1,0,-1,0},diry[]={0,0,1,0,-1};
  41. int G[MAXN][MAXN],id[MAXN][MAXN],his[MAXN][MAXN][1<<9][200];
  43. struct state{
  44.     int x,y,rest,tm,vis;
  45.     state(){x=y=rest=tm=vis=0;}
  46. };
  48. inline bool inG(state &u){
  49.     return 1<=u.x && u.x<=3 && 1<=u.y && u.y<=3;
  50. }
  52. inline bool jud(state &u){
  53.     if(u.tm<his[u.x][u.y][u.vis][u.rest]){
  54.         his[u.x][u.y][u.vis][u.rest]=u.tm;
  55.         return true;
  56.     }
  57.     else return false;
  58. }
  60. inline int BFS(){
  61.     static queue<state> que;
  62.     memset(his,0x7f,sizeof(his));
  63.     state u,v;
  64.     u.x=1,u.y=1;
  65.     u.rest=G[1][1];
  66.     u.tm=1;
  67.     u.vis=1;
  68.     que.push(u);
  69.     while(que.size()){
  70.         u=que.front();
  71.         que.pop();
  72.         if(u.rest<0) break;
  73.         for(int i=0;i<5;++i){
  74.             v.x=u.x+dirx[i],v.y=u.y+diry[i];
  75.             v.rest=u.rest+G[v.x][v.y];
  76.             v.tm=u.tm+1;
  77.             if(!inG(v) || v.rest<0) continue;
  78.             v.vis=u.vis;
  79.             v.vis|=id[v.x][v.y];
  80.             if(jud(v)){
  81.                 if(v.vis==all) return v.tm;
  82.                 que.push(v);
  83.             }
  84.         }
  85.     }
  86.     return -1;
  87. }
  89. int main(){
  90. #ifdef DEBUG
  91.     setIO("a");
  92. #endif
  93.     for(int i=1,cnt=0;i<=3;++i){
  94.         for(int j=1;j<=3;++j){
  95.             read(G[i][j]);
  96.             id[i][j]=1<<cnt++;
  97.         }
  98.     }
  99.     write(BFS());
  100.     return 0;
  101. }

简单题

Ah00L.png
Ahpri.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  5. using std::string;
  7. inline void setIO(string file){
  8.     string in=file+".in",out=file+".out";
  9.     freopen(in.c_str(),"r",stdin);
  10.     freopen(out.c_str(),"w",stdout);
  11. }
  13. template<typename type>
  14. inline void read(type &x){
  15.     int pm=1; char c;
  16.     do{
  17.         c=getchar();
  18.         if(c=='-') pm=-1;
  19.     }while(!isdigit(c));
  20.     x=c^'0';
  21.     while(c=getchar(),isdigit(c))
  22.         x=x*10+(c^'0');
  23.     x*=pm;
  24. }
  26. template<typename type>
  27. void write(type x,char c=0){
  28.     if(x<0) putchar('-'),x=-x;
  29.     if(x>9) write(x/10);
  30.     putchar(x%10|'0');
  31.     if(c) putchar(c);
  32. }
  34. #include <queue>
  35. #include <algorithm>
  36. #include <cstring>
  38. using std::queue;
  39. using std::max;
  41. const int MAXN=505,MAXM=3005;
  42. int n,m,s1,t1,s2,t2,l1,l2;
  43. int he[MAXN],dis[MAXN][MAXN];
  45. struct line{int to,nex;}ed[MAXM<<1];
  47. inline void addE(int u,int v){
  48.     static int cnt=0;
  49.     ed[++cnt]=(line){v,he[u]};
  50.     he[u]=cnt;
  51. }
  53. inline void BFS(int s){
  54.     static queue<int> que;
  55.     memset(dis[s],-1,sizeof(dis[s]));
  56.     int *d=dis[s];
  57.     d[s]=0;
  58.     que.push(s);
  59.     int u;
  60.     while(que.size()){
  61.         u=que.front();
  62.         que.pop();
  63.         for(int i=he[u],v;i;i=ed[i].nex){
  64.             v=ed[i].to;
  65.             if(d[v]==-1){
  66.                 d[v]=d[u]+1;
  67.                 que.push(v);
  68.             }
  69.         }
  70.     }
  71. }
  73. inline void cal_dis(){
  74.     for(int i=1;i<=n;++i) BFS(i);
  75. }
  77. inline int solve(){
  78.     if(dis[s1][t1]>l1 || dis[s2][t2]>l2 || dis[s1][t1]==-1 || dis[s2][t2]==-1)
  79.         return -1;
  80.     int ret=m-dis[s1][t1]-dis[s2][t2];
  81.     for(int i=1;i<=n;++i){
  82.         for(int j=1;j<=n;++j){
  83.             if(dis[s1][i]==-1 || dis[i][j]==-1 || dis[j][t1]==-1 || dis[s2][i]==-1 || dis[j][t2]==-1)
  84.                 continue;
  85.             if(dis[s1][i]+dis[i][j]+dis[j][t1]<=l1 && dis[s2][i]+dis[i][j]+dis[j][t2]<=l2)
  86.                 ret=max(ret,m-dis[s1][i]-dis[s2][i]-dis[i][j]-dis[j][t1]-dis[j][t2]);
  87.         }
  88.         for(int j=1;j<=n;++j){
  89.             if(dis[s1][j]==-1 || dis[i][j]==-1 || dis[i][t1]==-1 || dis[s2][i]==-1 || dis[j][t2]==-1)
  90.                 continue;
  91.             if(dis[s1][j]+dis[j][i]+dis[i][t1]<=l1 && dis[s2][i]+dis[i][j]+dis[j][t2]<=l2)
  92.                 ret=max(ret,m-dis[s1][j]-dis[s2][i]-dis[i][j]-dis[i][t1]-dis[j][t2]);
  94.         }
  95.     }
  96.     return ret;
  97. }
  99. int main(){
  100. #ifdef DEBUG
  101.     setIO("b");
  102. #endif
  103.     read(n),read(m);
  104.     read(s1),read(t1),read(l1);
  105.     read(s2),read(t2),read(l2);
  106.     for(int i=1,u,v;i<=m;++i){
  107.         read(u),read(v);
  108.         addE(u,v),addE(v,u);
  109.     }
  110.     cal_dis();
  111.     write(solve());
  112.     return 0;
  113. }

采矿

AhBcw.png
AhTWX.png
AhFNR.png
AhPz8.png

思路

代码

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