【WC2019】远古计算机

Author Avatar
mrsrz 10月 23, 2019

提交答案题。

题目大意：

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

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

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

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

具体操作及要求见原题。

题解：

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

Point 1：

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

node 1
read 0 a
write a 0

Point 2：

要你输出斐波那契数。

两个变量怎么维护啊QAQ

我们可以考虑打表。

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

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

node 1
read 0 b
add b 4
jmp b
write 0 0
write 1 0
write 1 0
write 2 0
write 3 0
write 5 0
write 8 0
write 13 0
write 21 0
write 34 0
write 55 0
write 89 0
write 144 0
write 233 0
write 377 0
write 610 0
write 987 0
write 159 0
write 2584 0
write 4181 0
write 6765 0
write 10946 0
write 17711 0
write 28657 0
write 46368 0
write 75025 0
write 121393 0
write 196418 0
write 317811 0
write 514229 0
write 832040 0
write 1346269 0
write 2178309 0
write 3524578 0
write 5702887 0
write 9227465 0
write 14930352 0
write 24157817 0
write 39088169 0
write 63245986 0
write 102334155 0
write 165580141 0
write 267914296 0
write 433494437 0
write 701408733 0

Point 3：

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

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

Code：

#include<cstdio>
#include<vector>
#include<queue>
int pre[23333],vis[23333],n,m,nxt[23333];
std::vector<int>G[23333];
std::queue<int>q;
int main(){
    freopen("oldcomputer3.in","r",stdin);
    freopen("oldcomputer3.out","w",stdout);
    scanf("%*d%d%d",&n,&m);
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v),G[v].push_back(u);
    }
    for(q.push(vis[1]=1);!q.empty();){
        int u=q.front();q.pop();
        for(int to:G[u])
        if(!vis[to]){
            vis[to]=1;
            pre[to]=u;
            q.push(to);
        }
    }
    for(int i=n;i!=1;i=pre[i])nxt[pre[i]]=i;
    printf("node 1\nread 0 a\nwrite a %d\n",nxt[1]);
    for(int i=2;i<n;++i)if(nxt[i])
    printf("node %d\nread %d b\nwrite b %d\n",i,pre[i],nxt[i]);
    printf("node %d\nread %d a\nwrite a 0\n",n,pre[n]);
    return 0;
}

Point 4：

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

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

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

考虑建分层图跑费用流。

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

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

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

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

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

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

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

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

周期要卡到7。

Code：

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cassert>
const int inf=0x3f3f3f3f;
struct edge{
    int to,nxt,cap,cost;
}e[4319744];
int head[120000],cnt=1,n,m,T,t0t=45002;
inline void addedge(int u,int v,int flow,int cost){
    e[++cnt]=(edge){v,head[u],flow,cost};head[u]=cnt;
    e[++cnt]=(edge){u,head[v],0,-cost};head[v]=cnt;
}
std::queue<int>q;
std::vector<int>read[42005],write[42005],h[7];
bool spfa(int&flow,int&cost){
    static int a[120000],d[120000],pre_e[120000],vis[120000];
    memset(a,0x3f,sizeof a);
    memset(d,0x3f,sizeof a);
    memset(vis,0,sizeof a);
    memset(pre_e,0,sizeof a);
    *d=0;
    for(q.push(0);!q.empty();){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        if(e[i].cap&&d[e[i].to]>d[u]+e[i].cost){
            d[e[i].to]=d[u]+e[i].cost;
            a[e[i].to]=std::min(a[u],e[i].cap);
            pre_e[e[i].to]=i;
            if(!vis[e[i].to])vis[e[i].to]=1,q.push(e[i].to);
        }
    }
    if(d[T]==0x3f3f3f3f)return 0;
    flow+=a[T];cost=std::max(cost,d[T]);
    for(int i=T;i;i=e[pre_e[i]^1].to){
        e[pre_e[i]].cap-=a[T];
        e[pre_e[i]^1].cap+=a[T];
    }
    return 1;
}
int main(){
    freopen("oldcomputer4.in","r",stdin);
    freopen("oldcomputer4.out","w",stdout);
    scanf("%*d%d%d",&n,&m);
    T=119999;
    for(int i=1;i<=n;++i)
    for(int j=0;j<6;++j)addedge(i+n*j,i+n*j+20000,1,0);
    for(int i=1;i<=n;++i)
    for(int j=0;j<6;++j)addedge(i+n*j,i+n*j+n,inf,0);
    for(int i=51;i<=100;++i)
    for(int j=0;j<6;++j)addedge(i+n*j+20000,T,1,j+1);
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);
        for(int j=0;j<6;++j){
            h[j].push_back(++t0t);
            addedge(u+n*j+20000,t0t,1,0);
            addedge(v+n*j+20000,t0t,1,0);
            addedge(t0t,t0t+1,1,0);
            ++t0t;
            addedge(t0t,v+n*j+n,1,0);
            addedge(t0t,u+n*j+n,1,0);
        }
    }
    int flow=0,cost=0;
    for(int i=1;i<=50;++i)addedge(0,i,1,0);
    while(spfa(flow,cost));
    for(int i=1;i<=50;++i)read[i].push_back(0);
    for(int i=0;i<6;++i)
    for(int t:h[i]){
        int lft=0,rgt=0;
        for(int i=head[t];i;i=e[i].nxt)
        if(e[i].cap&&e[i].to<45003)lft=(e[i].to-20001)%n+1;
        for(int i=head[t+1];i;i=e[i].nxt)
        if(!e[i].cap&&e[i].to<45003)rgt=(e[i].to-1)%n+1;
        if(lft!=rgt)write[lft].push_back(rgt),read[rgt].push_back(lft);
    }
    for(int i=1;i<=n;++i)
    for(int j=0;j<6;++j){
        for(int k=head[i+j*n+20000];k;k=e[k].nxt)
        if(e[k].to==T&&!e[k].cap){
            write[i].push_back(0);
        }
    }
    for(int i=1;i<=n;++i){
        assert(read[i].size()==write[i].size());
        if(read[i].size()){
            printf("node %d\n",i);
            for(int x=0;x<read[i].size();++x)
            printf("read %d a\nwrite a %d\n",read[i][x],write[i][x]);
        }
    }
    return 0;
}

Point 5：

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

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

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

然后考虑构造方案。

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

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

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

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

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

Code：

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<cassert>
int pre[233],vis[233],n,m;
std::vector<int>G[233],read[233],write[233];
std::queue<int>q;
int down[233],up[233],left[233],right[233],dis[233];
int a[233][233];
int main(){
    freopen("oldcomputer5.in","r",stdin);
    freopen("oldcomputer5.out","w",stdout);
    scanf("%*d%d%d",&n,&m);
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v),G[v].push_back(u);
    }
    for(int i=1;i<=10;++i){
        memset(vis,0,sizeof vis);
        memset(dis,0,sizeof dis);
        vis[i]=1;
        for(q.push(i);!q.empty();){
            int u=q.front();q.pop();
            for(int to:G[u])
            if(!vis[to]){
                dis[to]=dis[u]+1;
                vis[to]=1;
                pre[to]=u;
                q.push(to);
            }
        }
        for(int s=90+i;s!=i;s=pre[s])
        down[pre[s]]=s,up[s]=pre[s];
    }
    for(int i=1;i<=10;++i)
    for(int j=i;j;j=down[j])
    for(int u:G[j])if(u!=down[j]&&u!=up[j]&&u!=left[j])right[j]=u,left[u]=j;
    for(int i=1;i<=10;++i){
        a[1][i]=i;
        for(int j=2,nw=i;j<=10;++j){
            nw=down[nw];
            a[j][i]=nw;
        }
    }
    for(int i=1;i<=10;++i)
    read[i].push_back(0);
    for(int i=2;i<=10;++i){
        for(int j=i;j<=10;++j)
        write[a[i-1][j]].push_back(a[i][j]),
        read[a[i][j]].push_back(a[i-1][j]);
    }
    for(int i=1;i<=5;++i){
        for(int j=i;j<11-i;++j)
        write[a[i][j]].push_back(a[i][j+1]),
        read[a[i][j+1]].push_back(a[i][j]);
    }
    for(int i=6;i<=10;++i){
        for(int j=i;j>11-i;--j)
        write[a[i][j]].push_back(a[i][j-1]),
        read[a[i][j-1]].push_back(a[i][j]);
    }
    for(int i=2;i<=10;++i){
        for(int j=11-i;j<10;++j)
        write[a[j][i]].push_back(a[j+1][i]),
        read[a[j+1][i]].push_back(a[j][i]);
    }
    for(int i=1;i<=10;++i)write[a[10][i]].push_back(0);
    for(int i=1;i<=n;++i)
    if(read[i].size()){
        assert(read[i].size()==write[i].size());
        printf("node %d\n",i);
        for(int j=0;j<read[i].size();++j)
        printf("read %d a\nwrite a %d\n",read[i][j],write[i][j]);
    }
    return 0;
}
Powered by Hexo
Theme - Material