当前位置:网站首页>【UOJ 454】打雪仗(通信题)(分块)
【UOJ 454】打雪仗(通信题)(分块)
2022-08-11 09:38:00 【SSL_TJH】
打雪仗
题目链接:UOJ 454
题目大意
通信题。
两个人 A 有一个 2n 的 01 的字符串,B 有 n 个要知道的位置。
两个人可以传 01 给对方,然后最多的人不能传超过 4/3n(会多一点)个字符。
要你操作,使得 B 知道每个位置是 0 是 1。
思路
发现大概是 2 n 2n 2n 的 2 3 \frac{2}{3} 32,考虑能不能均摊一下了两个人的消费。
(因为你最暴力可以理解为一个人不说话,第二个把所有人都丢给他,考虑让那个不说话也说说话提供信息)
然后不难想到各种 50 分的写法。
然后再看看这个 2 3 \frac{2}{3} 32,我们考虑分块。
给的那个通过一个一开始的信息得到最多的是哪个,然后整块给,然后剩下的就看对面的 01 串是 1 1 1 就表示要,就给。
那这样剩下两个块至多给 2 3 n \frac{2}{3}n 32n 加上你 1 3 2 n \frac{1}{3}2n 312n 刚好 2 3 2 n \frac{2}{3}2n 322n。
然后看看要的那个,那大的块自己挑要的,然后剩下两个就你自己要全给,告诉对面每个位置要不要。
所以就是 2 3 2 n \frac{2}{3}2n 322n,那就也没问题。
(麻了不会编译,只会提交调试绷不住了)
代码
Alice
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream fin;
char get_bit() {
return getchar();
}
void send_bit(char ch) {
putchar(ch);
fflush(stdout);
}
int n, m;
string s;
struct init_t {
init_t() {
fin.open("alice.in");
fin >> n >> m >> s;
}
} init_t;
int L1 = 1, R1 = 666, L2 = 667, R2 = 1332, L3 = 1333, R3 = 2000;
int main() {
// if (get_bit() == '0') {
// for (int x = 0; x < n; ++x) send_bit(s[x]);
// } else {
// for (int x = 0; x < n; ++x) send_bit(s[x + n]);
// }
s = " " + s;
int op = get_bit() - '0' + (get_bit() - '0') * 2;
if (op == 0) {
for (int i = L1; i <= R1; i++) send_bit(s[i]);
for (int i = L2; i <= R2; i++) if (get_bit() == '1') send_bit(s[i]);
for (int i = L3; i <= R3; i++) if (get_bit() == '1') send_bit(s[i]);
}
else if (op == 1) {
for (int i = L1; i <= R1; i++) if (get_bit() == '1') send_bit(s[i]);
for (int i = L2; i <= R2; i++) send_bit(s[i]);
for (int i = L3; i <= R3; i++) if (get_bit() == '1') send_bit(s[i]);
}
else if (op == 2) {
for (int i = L1; i <= R1; i++) if (get_bit() == '1') send_bit(s[i]);
for (int i = L2; i <= R2; i++) if (get_bit() == '1') send_bit(s[i]);
for (int i = L3; i <= R3; i++) send_bit(s[i]);
}
}
Bob
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream fin;
char get_bit() {
return getchar();
}
void send_bit(char ch) {
putchar(ch);
fflush(stdout);
}
ofstream fout;
void answer(string s) {
fout << s << endl, exit(0);
}
const int N = 1000;
int n, m, pos[N + 1];
struct init_t {
init_t() {
int x;
fin.open("bob.in");
fout.open("bob.out");
fin >> n >> m;
for (x = 1; x <= n; ++x) fin >> pos[x];
}
} init_t;
int L1 = 1, R1 = 666, L2 = 667, R2 = 1332, L3 = 1333, R3 = 2000;
int main() {
// if (pos[n] == n) {
// send_bit('0');
// } else {
// send_bit('1');
// }
// string ans = "";
// for (int x = 0; x < n; ++x) {
// ans += get_bit();
// }
int num0 = 0, num1 = 0, num2 = 0;
for (int i = 1; i <= n; i++) {
if (L1 <= pos[i] && pos[i] <= R1) num0++;
if (L2 <= pos[i] && pos[i] <= R2) num1++;
if (L3 <= pos[i] && pos[i] <= R3) num2++;
}
string s = "";
if (num0 >= num1 && num0 >= num2) {
send_bit('0'); send_bit('0');
int now = 1;
for (int i = L1; i <= R1; i++) {
char c = get_bit();
if (now <= n && pos[now] == i) now++, s += c;
}
for (int i = L2; i <= R2; i++)
if (now <= n && pos[now] == i) now++, send_bit('1'), s += get_bit();
else send_bit('0');
for (int i = L3; i <= R3; i++)
if (now <= n && pos[now] == i) now++, send_bit('1'), s += get_bit();
else send_bit('0');
}
else if (num1 >= num0 && num1 >= num2) {
send_bit('1'); send_bit('0');
int now = 1;
for (int i = L1; i <= R1; i++)
if (now <= n && pos[now] == i) now++, send_bit('1'), s += get_bit();
else send_bit('0');
for (int i = L2; i <= R2; i++) {
char c = get_bit();
if (now <= n && pos[now] == i) now++, s += c;
}
for (int i = L3; i <= R3; i++)
if (now <= n && pos[now] == i) now++, send_bit('1'), s += get_bit();
else send_bit('0');
}
else if (num2 >= num0 && num2 >= num1) {
send_bit('0'); send_bit('1');
int now = 1;
for (int i = L1; i <= R1; i++)
if (now <= n && pos[now] == i) now++, send_bit('1'), s += get_bit();
else send_bit('0');
for (int i = L2; i <= R2; i++)
if (now <= n && pos[now] == i) now++, send_bit('1'), s += get_bit();
else send_bit('0');
for (int i = L3; i <= R3; i++) {
char c = get_bit();
if (now <= n && pos[now] == i) now++, s += c;
}
}
answer(s);
}
边栏推荐
- pycharm cancel msyql expression highlighting
- Typora and basic Markdown syntax
- How to determine the neural network parameters, the number of neural network parameters calculation
- Lightweight network (1): MobileNet V1, V2, V3 series
- HDRP shader 获取阴影(Custom Pass)
- tar 命令使用
- MySQL性能调优,必须掌握这一个工具!!!(1分钟系列)
- Song of the Cactus - Massive Rapid Expansion (1)
- HDRP shader gets pixel depth value and normal information
- QTableWidget 使用方法
猜你喜欢
Array, string, date notes [Blue Bridge Cup]
疫情当前,如何提高远程办公的效率,远程办公工具分享
Simple strokes on the Internet
pycharm 取消msyql表达式高亮
Three handshakes and four waves
卷积神经网络梯度消失,神经网络中梯度的概念
音视频+AI,中关村科金助力某银行探索发展新路径 | 案例研究
神经网络参数如何确定的,神经网络参数个数计算
如何在移动钱包中搭建一个小程序应用商店
HDRP Custom Pass Shader Get world coordinates and near clipping plane coordinates
随机推荐
Adobe LiveCycle Designer report designer
Halcon算子解释
Primavera Unifier 自定义报表制作及打印分享
IPQ4019/IPQ4029 support WiFi6 MiniPCIe Module 2T2R 2×2.4GHz 2x5GHz MT7915 MT7975
HDRP shader 获取像素深度值和法线信息
WooCommerce Ecommerce WordPress Plugin - Make American Money
Typora和基本的Markdown语法
Primavera P6 Professional 21.12 登录异常案例分享
IPQ4019/IPQ4029 support WiFi6 MiniPCIe Module 2T2R 2×2.4GHz 2x5GHz MT7915 MT7975
利用mindspore下面mindzoo里面的yolov3-darknet53进行目标识别,模型训练不收敛
大家有遇到这种错吗?flink-sql 写入 clickhouse
大佬们,我有一个MySQL source 通过旁路分流分了两个流,然后转表,现在想sink到两个hb
The no-code platform helps Zhongshan Hospital build an "intelligent management system" to realize smart medical care
mindspore中MindDataset读取mindrecord文件问题
Design of Cluster Gateway in Game Server
Huawei WLAN Technology: AC/AP Experiment
深度学习100例 —— 卷积神经网络(CNN)识别验证码
nodejs worker_threads的事件监听问题
网络流行简笔画图片大全,关于网络的简笔画图片
What is the difference between the qspi interface and the ordinary four-wire SPI interface?