正题

题目链接:https://uoj.ac/problem/454

---

题目大意

$Alice$有一个长度为$2n$的$01$串，$Bob$有$n$个在$[1,2n]$位置的下标表示它想要得到$01$串中这些位置的值，现在两个人可以向对方传输不超过$m$个$0/1$字符，要求使得$Bob$可以得到答案。

$1\le n\le 1000,m=1350$

---

解题思路

两种方法，都是平均两边的传输信息。
第一种方法是从左到右传输$01$串，由$Bob$考虑若一个位置需要传输，那么传输$1$，然后$Alice$传输这个位置给他并考虑下一个位置。否则传输$0$，然后$Alice$跳过这个位置传输下一个位置给她然后再考虑下一个位置。
不难发现这样对于$01$隔开的情况可以省略很多次数，所以我们直接随机打乱整个序列然后这样做即可。

第二种方法是将序列分为三块，$Bob$用二进制告诉$Alice$需要信息最多的那个块。然后剩下两个块由$Bob$告诉$Alice$需要传输哪些位置。
这样的次数$Alice$严格小于$\frac{2}{3}n\times 2$，$Bob$严格小于$\frac{4}{3}n+2$，都在$1350$次内。

因为第二种方法比较普遍所以代码使用的是第一种方法

---

code

Alice

#include <iostream> #include <fstream> #include <string> #include<cstdlib> #include<cstdio> #include<algorithm>using namespace std;ifstream fin; char get_bit() {return getchar(); } void send_bit(char ch) {putchar(ch);fflush(stdout); }int n, m,c[2100],r[2100]; string s; void init_t() {fin.open("alice.in");fin >> n >> m >> s; } int Z=17; int randd(){Z++;return (Z*1931ll+Z*Z*3ll)%32767; } int main() {init_t();for(int i=1;i<=2*n;i++)r[i]=i;for(int i=1;i<=20*n;i++)swap(r[randd()%(2*n)+1],r[randd()%(2*n)+1]);for(int i=1;i<=2*n;i++)c[r[i]]=s[i-1];int i=1; // for(int i=1;i<=2*n;i++)send_bit(c[i]); while(i<=2*n){char z=get_bit();if(z==EOF)break;if(z=='1'){send_bit(c[i]);i++;}else{i++;if(i>2*n)break;send_bit(c[i]);i++;}}return 0; }

Bob

#include <iostream> #include <fstream> #include<cstdlib> #include<cstdio> #include<cstring> #include<algorithm>using namespace std;ifstream fin; char get_bit() {return getchar(); } void send_bit(char ch) {putchar(ch);fflush(stdout); }const int N = 1000;int n, m, p[N + 1],r[N*2+10],w[N*2+10]; char s[N+1]; ofstream fout; void answer() {fout.open("bob.out");for(int i=1;i<=n;i++)fout<<s[i];fout<<endl; exit(0); } void init_t() {int x;fin.open("bob.in");fin >> n >> m;for (x = 1; x <= n; ++x) fin >> p[x]; } int Z=17; int randd(){Z++;return (Z*1931ll+Z*Z*3ll)%32767; } int main() {init_t();for(int i=1;i<=2*n;i++)r[i]=i;for(int i=1;i<=20*n;i++)swap(r[randd()%(2*n)+1],r[randd()%(2*n)+1]);for(int i=1;i<=n;i++)p[i]=r[p[i]],w[p[i]]=i;sort(p+1,p+1+n);int z=1,i=1;while(i<=n){if(p[i]==z){send_bit('1');s[w[p[i]]]=get_bit();z++;i++;}else{send_bit('0');z++;if(z>2*n)break;s[w[p[i]]]=get_bit();if(p[i]==z)i++;z++;}}answer();return 0; }

总结

以上是生活随笔为你收集整理的UOJ#454-[UER #8]打雪仗【通信题】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。