「UOJ 454」打雪仗

发表于 | | 阅读次数:
字数统计: 787 字

Description

题目链接：UOJ 454

这是一道通信题。

小 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$

Solution

我们把这 $2n​$ 个下标分为 $k​$ 块，定义第 $i​$ 个块中小 B 需要的下标有 $s_i​$ 个。由于小 B 知道的 $n​$ 个下标是总数的一半，那么至少有一个块中 $s_i​$ 不小于块的长度的一半。我们考虑这样一个策略：

  • 把这 $k$ 个块中的其中 $c$ 个块让小 A 暴力发送给小 B。其余块中的下标让小 B 告诉小 A 是否要发送。

  • 为了最大化暴力发送的效率，我们要选择 $s_i$ 最大的那 $c$ 个块。考虑最坏情况：$s_i$ 均为块长度的一半。

  • 通过简单计算我们可以得到：

    小 A 的发送次数：$n+\frac{c}{k}\cdot n$

    小 B 的发送次数：$2n-\frac{c}{k}\cdot 2n$

  • 计算不等式得到：$0.325\le \frac{c}{k}\le 0.35$。

  • 这样一来我们取 $\frac{c}{k}=\frac{1}{3}=0.333\dots$ 就行了。

时间复杂度：$O(n)$

发送字符数：不超过 $\frac{4}{3}n$ 个字符。

Code

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
 
#include <cstdio>
#include <algorithm>

const int N=2e3+5;
FILE *in=fopen("alice.in","r");
int n;
char s[N];

void send(int x) {
    putchar(x+'0'),fflush(stdout);
}
int get() {
    return getchar()^48;
}
void solve(int l,int r) {
    for(int i=l;i<=r;++i) send(s[i]-'0');
    for(int i=1;i<=n;++i) if(i<l||i>r) {
        if(get()) send(s[i]-'0');
    }
}
int main() {
    fscanf(in,"%d%*d%s",&n,s+1),n<<=1;
    int l1=1,r1=n/3,l2=r1+1,r2=n/3*2,l3=r2+1,r3=n;
    int opt=2*get()+get();
    if(opt==1) solve(l1,r1);
    if(opt==2) solve(l2,r2);
    if(opt==3) solve(l3,r3);
    return 0;
}

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
 
#include <cstdio>
#include <algorithm>
{
const int N=2e3+5;
FILE *in=fopen("bob.in","r"),*out=fopen("bob.out","w");
int n,p[N],vis[N],ans[N];

void send(int x) {
    putchar(x+'0'),fflush(stdout);
}
int get() {
    return getchar()^48;
}
int calc(int l,int r) {
    int ans=0;
    for(int i=l;i<=r;++i) ans+=vis[i];
    return ans;
}
void solve(int l,int r,int o1,int o2) {
    send(o1),send(o2);
    for(int i=l;i<=r;++i) ans[i]=get();
    for(int i=1;i<=n;++i) if(i<l||i>r) {
        send(vis[i]);
        if(vis[i]) ans[i]=get();
    }
}
int main() {
    fscanf(in,"%d%*d",&n);
    for(int i=1;i<=n;++i) {
        fscanf(in,"%d",&p[i]);
        vis[p[i]]=1;
    }
    n<<=1;
    int l1=1,r1=n/3,l2=r1+1,r2=n/3*2,l3=r2+1,r3=n;
    int c1=calc(l1,r1),c2=calc(l2,r2),c3=calc(l3,r3);
    int mx=std::max(c1,std::max(c2,c3));
    mx==c1?solve(l1,r1,0,1):mx==c2?solve(l2,r2,1,0):solve(l3,r3,1,1);
    for(int i=1;i<=n;++i) if(vis[i]) fprintf(out,"%d",ans[i]);
    return 0;
}
0%