自动搬运

查看原文

来自洛谷，原作者为

	C1942huangjiaxu 我将终究顺流入大海

搬运于2025-08-24 22:55:48，当前版本为作者最后更新于2024-03-19 19:27:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目中要求不能使用全局变量，但因为 CTS 是 IOI 赛制，这里认为在调用 transmit 函数时可以知道 $n,m$ 的值。

先考虑逐位确定答案，具体如下 :

• 第一轮，$0$ 号将 $a_0$ 的第 $0$ 位信息传给 $1$ 号。
• 第二轮，$1$ 号将 $0$ 号的信息加上，可以确定 $a_0+a_1$ 的第 $0$ 位信息，$1$ 号将这个信息传给 $2$ 号，同时这一轮 $0$ 号将第 $1$ 位信息传给 $1$ 号。
• 第 $j$ 轮，$i$ 号将 $j-i-1$ 位的信息传给第 $i+1$ 号。

最后答案的位数是 $O(m+\log n)$ 的，从 $0$ 将信息传到 $n$ 需要 $n$ 秒，所以总共秒数是 $m+n+\log n$，可以得到 $49$ 分。

参考代码

#include "mpc.h"
int precalc(int n,int m){
	int t=0;
	while((1<<t)<n)++t;
	return n+m+t;
}
bool transmit(player &player, int round,int position){
	int np=round-position-1;
	if(np<0)return 0;
	int o=player.last_message;
	if(o){
		int l=np;
		while(player.memory[l])player.memory[l]=0,++l;
		player.memory[l]=1;
	}
	return player.memory[np];
}

考虑到上述做法中，在第 $j+1$ 轮前，$j$ 号都没有信息可以传给 $j+1$ 号，浪费了很多的时间。

考虑我们同步进行两轮加法，后面一轮不必要从第 0 位开始，但要在第 $m+\log n$ 位结束，相当于是我们从 $\log n$ 的位置砍掉了一个三角形，这样前一轮的答案就变为 $O(m+\log\log n)$ 位了，总共秒数是 $n+m+\log\log n$ ，可以获得 $80$ 分。

参考代码

#include "mpc.h"
int N,M;
int precalc(int n,int m){
	N=n,M=m;
	return n+m+4;
}
bool transmit(player &player, int round,int position){
	int np=round-position-1,o=player.last_message,lp;
	if(np<0)np=np+M+11;
	if(np<0)return 0;
	if(o){
		lp=np;
		while(player.memory[lp])player.memory[lp]=0,++lp;
		player.memory[lp]=1;
	}
	bool u=player.memory[np];
	if(position!=N)player.memory[np]=0;
	return u;
}

既然两次不够，考虑同时进行三轮加法，把最后面的三角形往后移，中间再从 $O(\log\log n)$ 的位置砍一刀，这样就可以通过了，对参数的限制不是特别严格。

参考代码

#include "mpc.h"
const int B=8,C=4;
int N,M;
int precalc(int n,int m){
	N=n,M=m;
	return n+m+3;
}
bool transmit(player &player, int round,int position){
	int np=round-position-1,o=player.last_message,lp;
	if(np<0){
		if(np>=-B)np=np+M+C;
		else np=np+M+B+11;
	}
	if(np<0)return 0;
	if(o){
		lp=np;
		while(player.memory[lp])player.memory[lp]=0,++lp;
		player.memory[lp]=1;
	}
	bool u=player.memory[np];
	if(position!=N)player.memory[np]=0;
	return u;
}