区块链网站开发价格,贵州省城乡建设厅网站首页,网站制作价格服务,WordPress调用内部js正题
题目链接:https://uoj.ac/problem/454 题目大意 AliceAliceAlice有一个长度为2n2n2n的010101串#xff0c;BobBobBob有nnn个在[1,2n][1,2n][1,2n]位置的下标表示它想要得到010101串中这些位置的值#xff0c;现在两个人可以向对方传输不超过mmm个0/10/10/1字符#xf…正题
题目链接:https://uoj.ac/problem/454 题目大意
AliceAliceAlice有一个长度为2n2n2n的010101串BobBobBob有nnn个在[1,2n][1,2n][1,2n]位置的下标表示它想要得到010101串中这些位置的值现在两个人可以向对方传输不超过mmm个0/10/10/1字符要求使得BobBobBob可以得到答案。
1≤n≤1000,m13501\leq n\leq 1000,m13501≤n≤1000,m1350 解题思路
两种方法都是平均两边的传输信息。 第一种方法是从左到右传输010101串由BobBobBob考虑若一个位置需要传输那么传输111然后AliceAliceAlice传输这个位置给他并考虑下一个位置。否则传输000然后AliceAliceAlice跳过这个位置传输下一个位置给她然后再考虑下一个位置。 不难发现这样对于010101隔开的情况可以省略很多次数所以我们直接随机打乱整个序列然后这样做即可。
第二种方法是将序列分为三块BobBobBob用二进制告诉AliceAliceAlice需要信息最多的那个块。然后剩下两个块由BobBobBob告诉AliceAliceAlice需要传输哪些位置。 这样的次数AliceAliceAlice严格小于23n×2\frac{2}{3}n\times 232n×2BobBobBob严格小于43n2\frac{4}{3}n234n2都在135013501350次内。
因为第二种方法比较普遍所以代码使用的是第一种方法 code
Alice
#include iostream
#include fstream
#include string
#includecstdlib
#includecstdio
#includealgorithmusing 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 Z17;
int randd(){Z;return (Z*1931llZ*Z*3ll)%32767;
}
int main()
{init_t();for(int i1;i2*n;i)r[i]i;for(int i1;i20*n;i)swap(r[randd()%(2*n)1],r[randd()%(2*n)1]);for(int i1;i2*n;i)c[r[i]]s[i-1];int i1;
// for(int i1;i2*n;i)send_bit(c[i]); while(i2*n){char zget_bit();if(zEOF)break;if(z1){send_bit(c[i]);i;}else{i;if(i2*n)break;send_bit(c[i]);i;}}return 0;
}Bob
#include iostream
#include fstream
#includecstdlib
#includecstdio
#includecstring
#includealgorithmusing 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*210],w[N*210];
char s[N1];
ofstream fout;
void answer() {fout.open(bob.out);for(int i1;in;i)fouts[i];foutendl; exit(0);
}
void init_t() {int x;fin.open(bob.in);fin n m;for (x 1; x n; x) fin p[x];
}
int Z17;
int randd(){Z;return (Z*1931llZ*Z*3ll)%32767;
}
int main() {init_t();for(int i1;i2*n;i)r[i]i;for(int i1;i20*n;i)swap(r[randd()%(2*n)1],r[randd()%(2*n)1]);for(int i1;in;i)p[i]r[p[i]],w[p[i]]i;sort(p1,p1n);int z1,i1;while(in){if(p[i]z){send_bit(1);s[w[p[i]]]get_bit();z;i;}else{send_bit(0);z;if(z2*n)break;s[w[p[i]]]get_bit();if(p[i]z)i;z;}}answer();return 0;
}
