正題

題目鏈接: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]打雪仗【通信题】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。