题目描述

这是一道通信题。

UOJ 又来到了新的一年，今年鸽子们不出意外的把比赛鸽到了12月月底。今年鸽子们决定玩点不一样的：它们要来打（tong）雪（xin）仗（ti)。

小 \(A\) (Alice)，小 $ B $ (Bob) 和小 $ C $ (Cplusplus) 计划进行一场打雪仗比赛，第二名的将要请其他人一顿饭。为了不取得第二名，三人都付出了自己的努力：小 $ A $ 和小 $ B $ 为了获得第三名，每天在家睡觉，水平不断退步；而小 $ C $ 勤加苦练，为了取得第一名而努力着。直到比赛将至，小 $ A $ 和小 $ B $ 才意识到第二名很大概率要在两人之间诞生。因此，小 $ A $ 和小 $ B $ 决定齐心协力，将小 $ C $ 安排到第二名！

为了完成这样的伟业，小 $ A $ 和小 $ B $ 打算窃取小 $ C $ 的作战计划。比赛时，小 \(B\) 将打败小 \(C\) 获得冠军，而小 \(A\) 将继续睡大觉获得第三。

小 $ C $ 的作战计划可以视为长度为 \(2n\) 的一个 01 串，下标从 \(1, \dots, 2n\) 编号。小 $ C $ 选取了这 \(2n\) 个下标中的 \(n\) 个，并只在这 \(n\) 个位置中存储了作战计划的相关信息，而其他的位置都是用来混淆视听的。不幸的是，小 $ A $ 和小 $ B $ 只来得及分别完成了自己的任务——小 $ A $ 得到了长度为 \(2n\) 的字符串，而小 $ B $ 得到了 \(n\) 个下标，而他们已经来不及将信息汇总到一起了！好在，他们可以通过打雪仗前的热身赛传递信息：热身赛中每个人有恰好 \(m\) 个雪球，如果向上向对方抛球表示传递字符 "1"，而向下向对方抛球可以传递字符 "0"。只要你设计一种传递信息的方式，使得小 \(B\) 最终知道了他所拿到的 \(n\) 个下标所对应的字符，他们的计划就可以得逞了！

简要题意： 小 $ A $ 有一个长度为 $ 2n $ 的 $ 01 $ 字符串 $ S $ ，小 $ B $ 有 \(\{1, \dots, 2n\}\) 这些下标中的 $ n $ 个：\(p_1, \dots, p_n\)。小 \(A\) 和 小 \(B\) 可以相互之间可以发送字符（但只能发送 "0" 或者 "1" 两种）。请为小 \(A\) 和小 \(B\) 设计一种通信方式，使得小 $ B $ 最终能知道这 \(n\) 个下标所对应的字符 \(S[p_1], S[p_2], \dots, S[p_n]\)。两人中发送字符数较多的那一个不应发送超过 \(m\) 个字符。

\(n=1000,m=1350\)

题解

很妙的题

m=2000直接让A把整个串发过去

m=1600可以让B发0/1表示跳一格或两格，A每次把跳到的发过去

可以发现\(1350 \approx \frac{4}{3}n \approx 2*\frac{2}{3}n\)

把2n划分成三个区，每个区\(\frac{2}{3}n\)个

让B把需要最多的区（至少有\(\frac{1}{3}n\)个）告诉A，A把对应的区整块发给B

之后B把另外两个块中需要询问的位告诉A（直接发），A再把需要的告诉B

分析一下，A的次数为 一块的大小\(\frac{2}{3}n\)+剩余需要的\(\frac{2}{3}n\)=\(\frac{4}{3}n\)

B的次数为 2+两块的大小\(2*\frac{2}{3}n\)=\(\frac{4}{3}n\)

code

c++的freopen开了之后再关掉就不能直接输入了，所以要用fin和fout

用法见代码

A：

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define ll long long
#define file
using namespace std;

ifstream fin;//这两句要加上
ofstream fout;
char a[2001],c1,c2;
int n,m,i,j,k,l,r;

void Read()
{
    fin.open("alice.in");
    
    fin>>n>>m;
    fo(i,1,n+n)
    fin>>a[i];
}

char Get()
{
    return getchar();
}

void Put(char ch)
{
    putchar(ch);
    cout.flush();
}

int main()
{
    Read();
    
    c1=Get(),c2=Get();
    if (c1=='0' && c2=='0')
    l=1,r=666;
    else
    if (c1=='0' && c2=='1')
    l=667,r=1332;
    else
    if (c1=='1' && c2=='1')
    l=1333,r=2000;
    
    fo(i,l,r) Put(a[i]);
    i=1;
    while (i<=n+n)
    {
        if (i>=l && i<=r)
        i=r+1;
        if (i>n+n) break;
        
        if (Get()=='1')
        Put(a[i]);
        
        ++i;
    }
}

B：

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define ll long long
#define file
using namespace std;

ifstream fin;
ofstream fout;
char a[2001],c1,c2;
int p[1001],n,m,i,j,k,l,s1,s2,s3,r;
bool bz[2001];

void Read()
{
    fin.open("bob.in");
    
    fin>>n>>m;
    fo(i,1,n)
    {
        fin>>p[i];
        bz[p[i]]=1;
        
        if (p[i]<=666)
        ++s1;
        else
        if (p[i]<=1332)
        ++s2;
        else
        ++s3;
    }
}
void Write()
{
    fout.open("bob.out");
    
    fo(i,1,n)
    fout<<a[p[i]];
    fout<<endl;
    
    exit(0);
}

char Get()
{
    return getchar();
}
void Put(char ch)
{
    putchar(ch);
    cout.flush();
}

int main()
{
    Read();
    
    if (s1>=s2 && s1>=s3)
    l=1,r=666,Put('0'),Put('0');
    else
    if (s2>=s1 && s2>=s3)
    l=667,r=1332,Put('0'),Put('1');
    else
    l=1333,r=2000,Put('1'),Put('1');
    
    fo(i,l,r)
    a[i]=Get();
    
    i=1;
    while (i<=n+n)
    {
        if (i>=l && i<=r)
        i=r+1;
        if (i>n+n) break;
        
        if (bz[i])
        {
            Put('1');
            a[i]=Get();
        }
        else
        Put('0');
        
        ++i;
    }
    
    Write();
}