题解：P11050 [IOI 2024] 消息篡改者（暂无法评测）

现有公开的做法，好像都本质相同啊——又能有几种做法呢？有将近一半的位置会被修改，我们甚至不知道 Cleopatra 对它们做了什么——

哦不对，其实我们知道 Cleopatra 做了什么。没错，send_packet 函数是有返回值的。

来一个依赖返回值的，极其高手的做法。感谢 lmh 老师和 dx 老师的讨论和指导 /qq

坐稳了！

下面称不会被 Cleopatra 修改的位是好的（记为

1

），会被修改的位是坏的（记为

0

），将位置

i

的状态记为

C_i

。注意这里数字记号和题面是反的，~~如果你绕不过来就别看了反正也没啥好看的。~~

将一个数据包的长度记为

N

，它等于

31

。

由于信息长度不固定，我们先补一个

1

，再补一串

0

，直到长度

=1025

。显然这样可以区分长度，最后把多出来的部分删了就行。而满足

C_i=1

的位总共可以传输

1056

个位，还剩下

31

个。

我们的思路是这样的：

确定一个好的位；
利用这个位置找到所有好的位；
用找到的好位传送信息。

整个通信的过程看似是离线的，但是我们一定要摆脱离线的思维定势。因为我们有获得返回值的能力，所以我们可以得知 Basma 具体收到了什么，进而改变发送的内容，也就是将离线强制转为在线。

在一次发送信息的过程中，可以让一个位

u

记录位置

v

的类型——令

A_u=C_v

即可。如果

u

是好的，那么结果一定真实；否则，结果可能被 Cleopatra 篡改。称其为一次询问。如果

C_u=1

则为有效询问，否则为无效询问。

由于

1

是绝对众数，我们考虑摩尔投票。具体而言，维护一个栈，按顺序扫描每个位

i

：

如果栈为空，直接加入 $i$ ；
否则，在下一个发送的数据包中，让栈顶位置 $t$ $t$ 记录 $i$ $i$ 的类型。
- 如果在 Cleopatra 修改过后这一位是 $0$ ，那么 $C_i=0$ 和 $C_t=0$ 至少有一个成立。此时弹出栈顶元素 $t$ 。
- 否则，将 $i$ 加入栈。

显然最后栈中

1

比

0

更多，而且不可能出现连续的

10

。证明是简单的：如果出现

C_u=1

之后紧跟

C_v=0

，那么在处理

v

的时候应该将它们一起弹出去。所以最后栈顶一定是一个好位置。

这个过程是可以实现的原因是，我们每次得到了返回值。所以说 A 可以预测到 B 的行为，而 B 只需要顺着既定流程走就行了，并不会改变历史。

现在有一个问题——一次询问就会消耗一个二进制位，而这样做完之后最坏情况下已经进行了

30

次询问，如何用剩下的询问确定所有好的的位置呢？

首先可以观察到，无效询问不会占用信息量，因为这个位本来就传不了信息。

现在忘掉之前的栈，考虑如下问题：我们已经进行了多次询问，它们的结果全部已知；我们还知道一个

C_i=1

的

i

；接下来需要用更多的询问确定所有

C_i

，但是有效询问至多只能有

31

个，而且总的询问次数

\le 66

。

对操作建树，如果

u

查询

v

，就从

u

向

v

连一条有向边，连成一条森林，显然这个森林当中所有节点满足

fa_i<i

（除非

i

为树根）。

设已经确定的那个好位为

s

。我们每次找到编号最小的

p

，满足

p

还未确定。通过一次询问

(u=s,v=p)

来判断

p

的实际好坏。若

p

是一个好位置，那么因为

p

说真话，所以

p

的所有儿子都可以根据刚刚的询问直接确定。这样的关系可以递归下去，因此可以一次性填好所有能确定的位置，再重复这个过程，直到所有位置都被确定为止。

考虑每个有效询问，发现它恰好确定了一个点的状态。并且每个节点只会被一个有效询问更新——首先在维护栈的过程中，每个节点最多被询问一次；而如果这个询问有效，那么遍历到它之前它的父亲一定已经被确定了，这样它也会被确定下来，就不会被多次访问了。

这样询问的总数

\le 2N

，其中有效询问至多只有

N

次。

因此我们在

66

包内解决了这个问题！！！！！！！！！！

CPP

#include"message.h"
#include<bits/stdc++.h>
using namespace std;
void send_message(vector<bool> M,vector<bool> C){
	for (int i=0;i<31;++i) C[i]=!C[i];
	M.emplace_back(1);
	while(M.size()<66*16) M.emplace_back(0);
	int pos_M=0,cnt=0,bad=0;
	vector<bool> A(31);
	vector<int> vis(31),fa(31,-1),stk;
	for (int i=0;i<31;++i){
		if (stk.empty()){stk.push_back(i);continue;}
		else{
			A[stk.back()]=C[i];
			bad+=C[stk.back()];
			fa[i]=stk.back();
			for (int j=0;j<31;++j) if (C[j]&&(j!=stk.back())) A[j]=M[pos_M++];
			auto vec=send_packet(A);
			++cnt;
			if (vec[stk.back()]==0){
				stk.pop_back();
			}
			else stk.emplace_back(i);
		}
	}
	assert(stk.size());
	int lst=stk.back();vis[lst]=1;
	for (++cnt;cnt<=66;++cnt){
		int p=-1;
		for (int i=0;i<31;++i) if (!vis[i]){p=i;break;}
		if (p!=-1) A[lst]=C[p],++bad;
		for (int i=0;i<31;++i) if (C[i]&&(i!=lst||p==-1)) A[i]=M[pos_M++];
		send_packet(A);
		if (p==-1) continue;
		vis[p]=1;
		for (int i=p+1;i<31;++i) if (fa[i]!=-1&&C[fa[i]]&&vis[fa[i]]) vis[i]=1;
	}
	assert(pos_M>=1025);
}
vector<bool> receive_message(vector<vector<bool> > R){
	vector<bool> ans;
	vector<int> ok[66],vis(31),qry(31),C(31),stk,fa(31,-1);
	for (int i=0;i<66;++i) ok[i].resize(31);
	int L=0,bad=0;
	for (int i=0;i<31;++i){
		if (stk.empty()){stk.push_back(i);continue;}
		else{
			int x=stk.back();fa[i]=x;
			int k=qry[i]=R[L][x];ok[L++][x]=1;++bad;
			if (k) stk.emplace_back(i);
			else{
				stk.pop_back();
			}
		}
	}
	assert(stk.size());
	int lst=stk.back();C[lst]=vis[lst]=1;
	for (;L<66;++L){
		int p=-1;
		for (int i=0;i<31;++i) if (!vis[i]){p=i;break;}
		if (p==-1) break;
		int k=R[L][lst];ok[L][lst]=1;++bad;
		C[p]=k;vis[p]=1;
		if (k) for (int i=p+1;i<31;++i) if (vis[i]==0&&fa[i]!=-1&&C[fa[i]]){
			vis[i]=1;C[i]=qry[i];
		}
	}
	for (int i=0;i<66;++i) for (int j=0;j<31;++j) if (ok[i][j]==0&&C[j]) ans.emplace_back(R[i][j]);
	assert(ans.size()>=1025);
	while(ans.back()==0) ans.pop_back();ans.pop_back();
	return ans;
}

题解：P11050 [IOI 2024] 消息篡改者（暂无法评测）

文章操作

相关推荐

评论

题解：P11050 [IOI 2024] 消息篡改者（暂无法评测）