UER #8 —— 通信题:打雪仗

T1题目链接

大意:Alice 有一个长度为 $2n$ 的 $01$ 串 $s_{1..2n}$,Bob 有 $n$ 个下标 $p_{1..n}$,Alice 和 Bob 只能用 $01$ 通信,需要在每人各 $m$ 个 bit 内使 Bob 输出 $s_{p_1..p_n}$ .

$n=1000, m=1350$

Part 1 通信题

只是说一下我做了这道题后对通信题的理解,可能有误。

赛时:通信题是啥???

作为一个从未做过通信题的选手,遇到这题自然是百度了一下“通信题”。如果你尝试一下,会搜到《移动通信试题库》。

尝试搜索 “通信题 OI”——OI是什么意思? - 问通信专家;”通信题 CSDN”——通信原理考试题-CSDN下载。

ok,只能自己看样例程序了。

于是我比赛的第一个小时就在对着样例代码懵逼中度过了…..

然后发现我sb了,忘记了一件事:标准输入是会等待输入的! 可能是我 OI 题做傻了,以为输入一定要一连串不停地输入…导致我一直没有理解为什么两个程序之间可以来回通信…

上面那段话纯属我sb了,请跳过不看

通信题是……

根据我的理解,通信题就是:两个程序,分别从文件读入数据,从标准输入读入另一个程序的标准输出。最后其中一个程序按要求输出到文件。

(好像跟题面描述的差不多…)

那就说说我sb了而卡住的地方好了..一个程序 getchar() 的时候会暂停执行,直到另一个程序输出,就跟手动输入数据时等待回车一样。

关于调试

广二机房是 win7,不太方便复制…

于是只好手动输入了,只不过感觉 copy 两个程序的输出看它们相互配合着工作,还是蛮有趣的。

Part 2 解法

其实我 $5min$ 就想到怎么做了..(但好像做法比最短解那些神仙做法麻烦的多?)其实也不是很难写,但由于第一次写通信题不太习惯,各种细节写挂,最后写了一个小时才A…

解决问题

可以想到这样一个做法(如果想不到也没关系..看懂就好了):选择一个区间 $[l,r]$ ,Bob 用一个长度为 $r-l+1$ 的 $01$ 串告诉 Alice 这个区间内每个位置是否是一个下标,对于每个下标 Alice 告诉 Bob 对应的值;对于不在 $[l,r]$ 内的其它部分,Alice 把所有值(不管是不是一个下标)都告诉 Bob .

优化通信数

考虑一下,这样做需要的 bit 数是多少:

Bob 给 Alice 的:首先 Bob 要告诉 Alice $l$ 和 $r$ , 用二进制表示,需要 $22$ 个 bit;其次,Bob 要询问 $[l,r]$ ,需要 $r-l+1$ 个 bit 。

Alice 给 Bob 的:首先 Alice 要回答 Bob 在 $[l,r]$ 内的询问,需要 “ $[l,r]$ 内下标个数” 个 bit;其次,Alice 要告诉 Bob 除了 $[l,r]$ 其它区域的所有值,需要 $n-(r-l+1)$ 个 bit 。

那么,我们需要最小化:$\max(r-l+23, [l,r]\text{ 内下标个数}+n-r+l-1)$ 。

用 $[l,l+len)$ 来表示会简洁一些,所以下文都使用这种方式,即需要最小化:$\max(len+22, [l,l+len)\text{ 内下标个数}+n-len)$ 。

预处理前缀和即可快速算出 $[l,l+len)$ 内的下标个数,$O(n^2)$ 枚举区间取最小值即可。

参考代码

Bob

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

ifstream fin("bob.in");
ofstream fout("bob.out");

char rd() //读入一个bit
{
return getchar();
}

void wt(int x) //输出一个bit
{
putchar(x+'0');
fflush(stdout);
}

int n,m,p[1010],rk[4010],pre[4010],minn=0x7fffffff,l,len;
char ans[1010];

int main()
{
int i,j,t;

fin>>n>>m;

for (i=1;i<=n;++i) //读入并记录是第几个下标(便于存答案),并且复制一份拼在后面,这样如果询问的区间跨过首尾可以方便地处理
{
fin>>p[i];
rk[p[i]]=rk[p[i]+2*n]=i;
}

for (i=1;i<=4*n;++i) //预处理前缀和
{
pre[i]=pre[i-1]+(rk[i]>0);
}

for (i=1;i<=2*n;++i) //枚举找最优方案
{
for (j=1;j<=2*n;++j)
{
t=max(pre[i+j-1]-pre[i-1]+2*n-j,j+22);
if (t<minn)
{
minn=t;
l=i;
len=j;
}
}
}

for (i=10;i>=0;--i) //告诉Alice l和len
{
wt(bool((1<<i)&l));
}

for (i=10;i>=0;--i)
{
wt(bool((1<<i)&len));
}

for (i=l;i<l+len;++i) //询问区间
{
if (rk[i])
{
wt(1);
ans[rk[i]-1]=rd(); //存答案
}
else
{
wt(0);
}
}

for (i=l+len;i<l+2*n;++i) //读取剩余部分
{
if (rk[i])
{
ans[rk[i]-1]=rd();
}
else
{
rd();
}
}

fout<<ans;

return 0;
}

Alice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <fstream>
#include <cstdio>

using namespace std;

ifstream fin("alice.in");

int rd() //为了方便,两个程序中rd()和wt()的char/int是反的
{
return getchar()-'0';
}

void wt(char x)
{
putchar(x);
fflush(stdout);
}

int n,m;
char s[4010];

int main()
{
int i,l=0,len=0;

fin>>n>>m>>(s+1);

for (i=2*n+1;i<=4*n;++i) //复制一遍放在后面
{
s[i]=s[i-2*n];
}

for (i=0;i<=10;++i) //读入l和len
{
l=l*2+rd();
}

for (i=0;i<=10;++i)
{
len=len*2+rd();
}

for (i=l;i<l+len;++i) //回答询问
{
if (rd())
{
wt(s[i]);
}
}

for (i=l+len;i<l+2*n;++i) //告诉Bob剩下的部分
{
wt(s[i]);
}

return 0;
}

Part 3 证明

取询问区间为 $[l,l+1318]$ ,这样的话 Bob 发给 Alice 的 bit 数就为 $1319+22=1341$ .

区间 $[l,l+1318]$ 内下标的期望个数为 $\frac{1319}2$ ,所以一定存在某个区间使得下标个数小于等于 $659$ ,再加上剩余部分 $681$ ,Alice 发给 Bob 的 bit 数就为 $1340$ 。

事实上,我提交的评测记录里通信次数最多的就是 $1341+1340$ 。

Part 4 优化

只取 $len=1325$ ,少枚举一维,可以优化到时间复杂度 $O(n)$ ;少传 $11$ 个 bit,可以优化到最大通信次数 $1336+1337$ 。证明从略。

提交记录