「WC2019」远古计算机

2023-11-05 20:06:52

description

solution

这是一道五合一的提交答案题。

题面非常恐怖，一大段规则指令，其实有用的只有几个，只用看懂题就不慌了

Subtask 1

即使没看懂题也能完成这一\(Subtask\)，只需要三行：

node 1
read 0 a
write a 0

Subtask 2

只有2个储存单元，因此现场计算斐波那契数比较困难。注意到这样一个条件：第\(k\)项不超过 \(10^9\)，事实上斐波那契数的第\(45\)项就已经超过\(10^9\)，因此可以想到打表，注意到题目中有这样一个操作：

jmp val跳转到整个程序第 val 条语句，语句从程序开头开始，用从\(1\)开始的正整数计数；

因此直接打表输出，\(jmp\)到对应行即可，这里是生成答案的代码：

#include<bits/stdc++.h>
using namespace std;
int f[51];
int main(){
    freopen("oldcomputer2.out","w",stdout);
    puts("node 1");
    puts("read 0 a");
    puts("add a 4");
    puts("jmp a");
    f[0]=0;f[1]=1;
    for(int i=2;i<=44;++i) f[i]=f[i-1]+f[i-2];
    for(int i=0;i<=44;++i) printf("write %d 0\n",f[i]);
	return 0;
}

Subtask 3

要求将数从\(1\)传到\(n\)

我们需要知道轮数尽量少意味着什么：每个点传输信息都会需要一轮时间，我们需要轮数尽量少

因此我们直接\(bfs\)一条从\(1\)到\(n\)的最短路径即可

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int t,n,m,first[N],ru[N],cnt,First[N],Cnt;
struct node{
	int v,nxt;
}e[N<<1],E[N<<1];
inline void add(int u,int v){
	e[++cnt].v=v;e[cnt].nxt=first[u];first[u]=cnt;
}
int vis[N],last[N];
inline void bfs(int s,int t){
	queue<int>q;
	memset(vis,0,sizeof(vis));
	q.push(s);vis[s]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=first[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(!vis[v]){
				last[v]=u;
				vis[v]=1;
				q.push(v);
			}
		}
	}
	int from=0,now=t;
	while(now){
		printf("node %d\n",now);
		printf("read %d a\n",last[now]);
		printf("write a %d\n",from);
		from=now;now=last[now];
	}
}
int b[N],U[N],V[N];
int main(){
	freopen("oldcomputer3.in","r",stdin);
	freopen("oldcomputer3.out","w",stdout);
	scanf("%d%d%d",&t,&n,&m);
	for(int i=1,u,v;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	bfs(1,n);
	return 0;
}

Subtask 4

以\(51-\)\(100\)号点作为源点往回跑最短路，然后从\(1-50\)号点开始，不断将身上的所有信息传递到在最短路中更改自己\(dis\)的点即可，注意一个点可能会收到多条信息，因此额外维护一个时间戳，按顺序输出即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int t,n,m,first[N],ru[N],cnt,First[N],Cnt;
struct node{
	int v,nxt;
}e[N<<1],E[N<<1];
inline void add(int u,int v){
	e[++cnt].v=v;e[cnt].nxt=first[u];first[u]=cnt;
}
int vis[N],last[N],dis[N];
vector<pair<int,int> >ve[N];
inline void SPFA(){
	queue<int>q;
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	for(int i=51;i<=100;++i)
		q.push(i),vis[i]=1,dis[i]=0;
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=0;
		for(int i=first[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	for(int i=1;i<=50;++i) q.push(i),ve[i].push_back(make_pair(0,0));
	while(!q.empty()){
		int u=q.front();q.pop();
		sort(ve[u].begin(),ve[u].end());
		printf("node %d\n",u);
		int v=0;
		for(int i=first[u];i;i=e[i].nxt){
			if(dis[u]==dis[e[i].v]+1){
				v=e[i].v;
				break;
			}
		}
		for(int i=0;i<ve[u].size();++i){
			printf("read %d a\n",ve[u][i].second);
			printf("write a %d\n",v);
			ve[last[u]].push_back(make_pair(ve[u][i].first+1,u));
		}
		if(v) q.push(v);
	}
}
int b[N],U[N],V[N];
int main(){
	freopen("oldcomputer4.in","r",stdin);
	freopen("oldcomputer4.out","w",stdout);
	scanf("%d%d%d",&t,&n,&m);
	for(int i=1,u,v;i<=m;++i)
		scanf("%d%d",&u,&v),add(u,v),add(v,u);
	SPFA();
	return 0;
}

Subtask 5

比较玄学，跑最短路的时候记一下\(used_{i.t}\)数组表示计算机\(i\)在\(t\)时刻是否空闲，那么在用\(u\)松弛\(v\)时，如果\(w=dis[u]+1\)时\(v\)不空闲，那么就不断增加\(w\)，像这样跑\(10\)次\(SPFA\)

但是这个做法不一定是最优的，按顺序加边无法通过，改变一下加边顺序就可以·通过了：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int t,n,m,first[N],ru[N],cnt,First[N],Cnt;
struct node{
	int v,nxt;
}e[N<<1],E[N<<1];
inline void add(int u,int v){
	e[++cnt].v=v;e[cnt].nxt=first[u];first[u]=cnt;
}
int dis[N],vis[N],last[N],used[N][N],tim[N],ans=0;
vector<pair<int,pair<int,int>> > ve[N];
#define mp(a,b,c) make_pair(a,make_pair(b,c))
inline void SPFA(int s,int t){
	queue<int>q;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	q.push(s);dis[s]=0;vis[s]=1;
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=0;
		for(int i=first[u];i;i=e[i].nxt){
			int v=e[i].v;
			int t=dis[u]+1;
			while(used[v][t]||used[v][t+1]) ++t;
			if(t<dis[v]){
				dis[v]=t;last[v]=u;tim[v]=t;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	int from=0;
	while(1){
		used[t][tim[t]]=used[t][tim[t]+1]=1;
		ve[t].push_back(mp(tim[t],last[t],from));
		ans=max(ans,tim[t]);
		from=t;t=last[t];
		if(t==s){
			ve[t].push_back(mp(0,0,from));
			break;
		}
	}
}
int b[N],U[N],V[N];
int main(){
	freopen("oldcomputer5.in","r",stdin);
	freopen("oldcomputer5.out","w",stdout);
	scanf("%d%d%d",&t,&n,&m);
	for(int i=1,u,v;i<=m;++i)
		scanf("%d%d",&U[i],&V[i]);
	for(int i=m;i>=1;--i)
		add(V[i],U[i]),add(U[i],V[i]);
	for(int i=1;i<=10;++i) used[i][0]=used[i][1]=1,b[i]=i;
	for(int i=1;i<=10;++i) SPFA(i,101-i);
	for(int i=1;i<=n;++i){
		if(ve[i].empty()) continue;
		printf("node %d\n",i);
		sort(ve[i].begin(),ve[i].end());
		for(int j=0;j<ve[i].size();++j){
			printf("read %d a\n",ve[i][j].second.first);
			printf("write a %d\n",ve[i][j].second.second);
		}
	}
	return 0;
}

码农公寓