【WC2019】远古计算机

Author Avatar
mrsrz 10月 23, 2019

提交答案题。

题目大意：

给你 n 台计算机，每台计算机可以维护两个变量。给出了一些操作语句。

每台计算机能独立地从标准输入中输入数据，把数据输出到标准输出上。

有一些计算机之间有数据线连接（双向），一台计算机可以输出东西到数据线中或从数据线中输入数据。被输入的数据立即消失。每个数据线同时只能有一个数据。

然后要你完成一些任务，要求计算机的运行周期尽可能少。

具体操作及要求见原题。

题解：

UOJ 放这道题了就来补一下博客

Point 1：

让你把输入的东西按顺序原样输出来。由于题目说“一台远古计算机如果执行完了最后一条指令，将会重新从第一条指令开始执行”，所以只需要三行：

  1. node 1
  2. read 0 a
  3. write a 0

Point 2：

要你输出斐波那契数。

两个变量怎么维护啊QAQ

我们可以考虑打表。

每句都用判断语句的话，周期就会过多。

由于答案是一个周期检查一遍的，所以我们可以运用jmp操作，根据输入的值直接跳转到相应行即可。

  1. node 1
  2. read 0 b
  3. add b 4
  4. jmp b
  5. write 0 0
  6. write 1 0
  7. write 1 0
  8. write 2 0
  9. write 3 0
  10. write 5 0
  11. write 8 0
  12. write 13 0
  13. write 21 0
  14. write 34 0
  15. write 55 0
  16. write 89 0
  17. write 144 0
  18. write 233 0
  19. write 377 0
  20. write 610 0
  21. write 987 0
  22. write 159 0
  23. write 2584 0
  24. write 4181 0
  25. write 6765 0
  26. write 10946 0
  27. write 17711 0
  28. write 28657 0
  29. write 46368 0
  30. write 75025 0
  31. write 121393 0
  32. write 196418 0
  33. write 317811 0
  34. write 514229 0
  35. write 832040 0
  36. write 1346269 0
  37. write 2178309 0
  38. write 3524578 0
  39. write 5702887 0
  40. write 9227465 0
  41. write 14930352 0
  42. write 24157817 0
  43. write 39088169 0
  44. write 63245986 0
  45. write 102334155 0
  46. write 165580141 0
  47. write 267914296 0
  48. write 433494437 0
  49. write 701408733 0

Point 3：

把1号计算机的输入里的东西按顺序输出到 n 号计算机的输出中。

显然，找一条最短路，每次把一个数据往后传一格即可。由于起点、终点相同，并行传递显然不能使答案变优。

Code：

  1. #include<cstdio>
  2. #include<vector>
  3. #include<queue>
  4. int pre[23333],vis[23333],n,m,nxt[23333];
  5. std::vector<int>G[23333];
  6. std::queue<int>q;
  7. int main(){
  8.     freopen("oldcomputer3.in","r",stdin);
  9.     freopen("oldcomputer3.out","w",stdout);
  10.     scanf("%*d%d%d",&n,&m);
  11.     while(m--){
  12.         int u,v;
  13.         scanf("%d%d",&u,&v);
  14.         G[u].push_back(v),G[v].push_back(u);
  15.     }
  16.     for(q.push(vis[1]=1);!q.empty();){
  17.         int u=q.front();q.pop();
  18.         for(int to:G[u])
  19.         if(!vis[to]){
  20.             vis[to]=1;
  21.             pre[to]=u;
  22.             q.push(to);
  23.         }
  24.     }
  25.     for(int i=n;i!=1;i=pre[i])nxt[pre[i]]=i;
  26.     printf("node 1\nread 0 a\nwrite a %d\n",nxt[1]);
  27.     for(int i=2;i<n;++i)if(nxt[i])
  28.     printf("node %d\nread %d b\nwrite b %d\n",i,pre[i],nxt[i]);
  29.     printf("node %d\nread %d a\nwrite a 0\n",n,pre[n]);
  30.     return 0;
  31. }

Point 4：

前 50 个计算机每个读入一个数，把每个数按任意顺序随意输出到 51∼100 号的任意一台计算机中。

这里就需要并行传递数据来优化效率了。

但如果两条路径交汇在同一个点，需要一个一个传递。

考虑建分层图跑费用流。

对每层的每个点拆成入点和出点。

从源点向 1∼50 号的第一层的入点连容量为1，费用为0的边。

从 51∼100 号的每一层向汇点连容量为1，费用为层数的边，表示从这里输出需要这么多周期，且这样的输出只可能出现一次。

从每个点的入点向出点连容量为1，费用为0的边，表示能够向下一周期输出一个数据。

从每个点每层的入点向其下一层的入点连容量为inf，费用为0的边，表示等待一个周期。

对每条数据线，为了防止同时输入或同时输出的问题，可以把数据线也拆成入点和出点，然后再连边即可。

跑满流，然后输出方案即可。

这里输出方案需要注意，必须按照层数从小到大的顺序输出，否则会因为先后顺序的问题增加周期。

周期要卡到7。

Code：

  1. #include<cstdio>
  2. #include<queue>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<vector>
  6. #include<cassert>
  7. const int inf=0x3f3f3f3f;
  8. struct edge{
  9.     int to,nxt,cap,cost;
  10. }e[4319744];
  11. int head[120000],cnt=1,n,m,T,t0t=45002;
  12. inline void addedge(int u,int v,int flow,int cost){
  13.     e[++cnt]=(edge){v,head[u],flow,cost};head[u]=cnt;
  14.     e[++cnt]=(edge){u,head[v],0,-cost};head[v]=cnt;
  15. }
  16. std::queue<int>q;
  17. std::vector<int>read[42005],write[42005],h[7];
  18. bool spfa(int&flow,int&cost){
  19.     static int a[120000],d[120000],pre_e[120000],vis[120000];
  20.     memset(a,0x3f,sizeof a);
  21.     memset(d,0x3f,sizeof a);
  22.     memset(vis,0,sizeof a);
  23.     memset(pre_e,0,sizeof a);
  24.     *d=0;
  25.     for(q.push(0);!q.empty();){
  26.         int u=q.front();q.pop();
  27.         vis[u]=0;
  28.         for(int i=head[u];i;i=e[i].nxt)
  29.         if(e[i].cap&&d[e[i].to]>d[u]+e[i].cost){
  30.             d[e[i].to]=d[u]+e[i].cost;
  31.             a[e[i].to]=std::min(a[u],e[i].cap);
  32.             pre_e[e[i].to]=i;
  33.             if(!vis[e[i].to])vis[e[i].to]=1,q.push(e[i].to);
  34.         }
  35.     }
  36.     if(d[T]==0x3f3f3f3f)return 0;
  37.     flow+=a[T];cost=std::max(cost,d[T]);
  38.     for(int i=T;i;i=e[pre_e[i]^1].to){
  39.         e[pre_e[i]].cap-=a[T];
  40.         e[pre_e[i]^1].cap+=a[T];
  41.     }
  42.     return 1;
  43. }
  44. int main(){
  45.     freopen("oldcomputer4.in","r",stdin);
  46.     freopen("oldcomputer4.out","w",stdout);
  47.     scanf("%*d%d%d",&n,&m);
  48.     T=119999;
  49.     for(int i=1;i<=n;++i)
  50.     for(int j=0;j<6;++j)addedge(i+n*j,i+n*j+20000,1,0);
  51.     for(int i=1;i<=n;++i)
  52.     for(int j=0;j<6;++j)addedge(i+n*j,i+n*j+n,inf,0);
  53.     for(int i=51;i<=100;++i)
  54.     for(int j=0;j<6;++j)addedge(i+n*j+20000,T,1,j+1);
  55.     while(m--){
  56.         int u,v;
  57.         scanf("%d%d",&u,&v);
  58.         for(int j=0;j<6;++j){
  59.             h[j].push_back(++t0t);
  60.             addedge(u+n*j+20000,t0t,1,0);
  61.             addedge(v+n*j+20000,t0t,1,0);
  62.             addedge(t0t,t0t+1,1,0);
  63.             ++t0t;
  64.             addedge(t0t,v+n*j+n,1,0);
  65.             addedge(t0t,u+n*j+n,1,0);
  66.         }
  67.     }
  68.     int flow=0,cost=0;
  69.     for(int i=1;i<=50;++i)addedge(0,i,1,0);
  70.     while(spfa(flow,cost));
  71.     for(int i=1;i<=50;++i)read[i].push_back(0);
  72.     for(int i=0;i<6;++i)
  73.     for(int t:h[i]){
  74.         int lft=0,rgt=0;
  75.         for(int i=head[t];i;i=e[i].nxt)
  76.         if(e[i].cap&&e[i].to<45003)lft=(e[i].to-20001)%n+1;
  77.         for(int i=head[t+1];i;i=e[i].nxt)
  78.         if(!e[i].cap&&e[i].to<45003)rgt=(e[i].to-1)%n+1;
  79.         if(lft!=rgt)write[lft].push_back(rgt),read[rgt].push_back(lft);
  80.     }
  81.     for(int i=1;i<=n;++i)
  82.     for(int j=0;j<6;++j){
  83.         for(int k=head[i+j*n+20000];k;k=e[k].nxt)
  84.         if(e[k].to==T&&!e[k].cap){
  85.             write[i].push_back(0);
  86.         }
  87.     }
  88.     for(int i=1;i<=n;++i){
  89.         assert(read[i].size()==write[i].size());
  90.         if(read[i].size()){
  91.             printf("node %d\n",i);
  92.             for(int x=0;x<read[i].size();++x)
  93.             printf("read %d a\nwrite a %d\n",read[i][x],write[i][x]);
  94.         }
  95.     }
  96.     return 0;
  97. }

Point 5：

把 1∼10 号计算机中的输入按顺序输出到 100∼91 号计算机中。

仔细观察，发现这是一张 10×10 的网格图。第一行是 1∼10 ，最后一行是 91∼100 。

先把每个格子的编号处理出来。

然后考虑构造方案。

首先一个答案的下界为 20 ，因为左上角的数要传到右下角。

然后，答案不可能取到 20 ，考虑 2 号计算机的位置，发现不可能。

我们可以构造一个 21 的方案：

  1. 把第 i 个计算机的数移动到 (i,i) 。
  2. 把第 i 个计算机的数移动到 (11−i,i) 。
  3. 往下移动到相应的位置。

通过并行，加上IO，总共21次。

Code：

  1. #include<cstdio>
  2. #include<vector>
  3. #include<queue>
  4. #include<cstring>
  5. #include<cassert>
  6. int pre[233],vis[233],n,m;
  7. std::vector<int>G[233],read[233],write[233];
  8. std::queue<int>q;
  9. int down[233],up[233],left[233],right[233],dis[233];
  10. int a[233][233];
  11. int main(){
  12.     freopen("oldcomputer5.in","r",stdin);
  13.     freopen("oldcomputer5.out","w",stdout);
  14.     scanf("%*d%d%d",&n,&m);
  15.     while(m--){
  16.         int u,v;
  17.         scanf("%d%d",&u,&v);
  18.         G[u].push_back(v),G[v].push_back(u);
  19.     }
  20.     for(int i=1;i<=10;++i){
  21.         memset(vis,0,sizeof vis);
  22.         memset(dis,0,sizeof dis);
  23.         vis[i]=1;
  24.         for(q.push(i);!q.empty();){
  25.             int u=q.front();q.pop();
  26.             for(int to:G[u])
  27.             if(!vis[to]){
  28.                 dis[to]=dis[u]+1;
  29.                 vis[to]=1;
  30.                 pre[to]=u;
  31.                 q.push(to);
  32.             }
  33.         }
  34.         for(int s=90+i;s!=i;s=pre[s])
  35.         down[pre[s]]=s,up[s]=pre[s];
  36.     }
  37.     for(int i=1;i<=10;++i)
  38.     for(int j=i;j;j=down[j])
  39.     for(int u:G[j])if(u!=down[j]&&u!=up[j]&&u!=left[j])right[j]=u,left[u]=j;
  40.     for(int i=1;i<=10;++i){
  41.         a[1][i]=i;
  42.         for(int j=2,nw=i;j<=10;++j){
  43.             nw=down[nw];
  44.             a[j][i]=nw;
  45.         }
  46.     }
  47.     for(int i=1;i<=10;++i)
  48.     read[i].push_back(0);
  49.     for(int i=2;i<=10;++i){
  50.         for(int j=i;j<=10;++j)
  51.         write[a[i-1][j]].push_back(a[i][j]),
  52.         read[a[i][j]].push_back(a[i-1][j]);
  53.     }
  54.     for(int i=1;i<=5;++i){
  55.         for(int j=i;j<11-i;++j)
  56.         write[a[i][j]].push_back(a[i][j+1]),
  57.         read[a[i][j+1]].push_back(a[i][j]);
  58.     }
  59.     for(int i=6;i<=10;++i){
  60.         for(int j=i;j>11-i;--j)
  61.         write[a[i][j]].push_back(a[i][j-1]),
  62.         read[a[i][j-1]].push_back(a[i][j]);
  63.     }
  64.     for(int i=2;i<=10;++i){
  65.         for(int j=11-i;j<10;++j)
  66.         write[a[j][i]].push_back(a[j+1][i]),
  67.         read[a[j+1][i]].push_back(a[j][i]);
  68.     }
  69.     for(int i=1;i<=10;++i)write[a[10][i]].push_back(0);
  70.     for(int i=1;i<=n;++i)
  71.     if(read[i].size()){
  72.         assert(read[i].size()==write[i].size());
  73.         printf("node %d\n",i);
  74.         for(int j=0;j<read[i].size();++j)
  75.         printf("read %d a\nwrite a %d\n",read[i][j],write[i][j]);
  76.     }
  77.     return 0;
  78. }

Gitalking ...

Powered by Hexo
Theme - Material