Codeforces H. Binary Median (二进制 / 思维)(Round #644 Div3)

2023-10-31 20:08

本文主要是介绍Codeforces H. Binary Median (二进制 / 思维)(Round #644 Div3),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门

题意: 在2^m 个长为m的二进制串(01串)中删除n个,输出剩下k个二进制串序列的中位数([k - 1] / 2 下取整)。
样例

思路:

  • 找到未删减时的中位数z,因为最多删除100个数,所以再把中位数左右110范围内的数加入答案a区间内。
  • 遍历需要删除的区间,因为二进制的字典序和十进制的排序一致,所以将其转换成十进制数x。
  • 若x < a[0],说明会在中位数左侧删除一个数,删除a[0];同理当x > a.end()的时候删除a.end();若需要删除的数在a区间内部a[0] < x< a.end(),便直接find数x,将其删除便可。
  • 最后答案就是可选区间a的中位数,再将其转换为m位的二进制数就行啦。

代码实现:

#include<bits/stdc++.h>
#define endl '\n'
#define null NULL
#define ll long long
#define int long long
#define pii pair<int, int>
#define lowbit(x) (x &(-x))
#define ls(x) x<<1
#define rs(x) (x<<1+1)
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int way[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
using namespace std;
const int  inf = 0x7fffffff;
const double PI = acos(-1.0);
const double eps = 1e-6;
const ll   mod = 1e9 + 7;
const int  N = 2e5 + 5;int t, n, m;
vector<ll> a;ll trans(string s){ll ans = 0;reverse(s.begin(), s.end());for(int i = 0; i < s.size(); i ++)if(s[i] == '1') ans += pow(2, i);return ans;
}signed main(){IOS;cin >> t;while(t --){a.clear();int n, m;cin >> n >> m;//找到未删除时的中位数ll z = (1LL << (m - 1));//前后110范围的数加入考虑范围for (int i = -110; i < 110; i++)a.push_back(z + i);//开始删除for (int i = 0; i < n; i++) {string s;cin >> s;ll x = trans(s);if (x < a[0]) a.erase(a.begin());else if (x > a.back()) a.erase(a.end() - 1);else a.erase(find(a.begin(), a.end(), x));}//再取中位数ll x = a[(a.size() - 1) / 2];//转换成二进制数for (int i = m - 1; ~i; i --) {if (x & (1LL << i)) cout << "1";else cout << "0";}cout << endl;}return 0;
}

思路2: 其实我最开始其实想的方法是这样的

  • 还是先找到未删除时的中位数z,标记每一个需要删除的数。
  • 后期遍历时:如果删除的数在左侧,就z- -到向左寻找到的第一个未被标记的数,同理处理右边。

但显然没有上面那个方法简便,试了好久都没有实现成功,哭啊~。

这篇关于Codeforces H. Binary Median (二进制 / 思维)(Round #644 Div3)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/317793

相关文章

在Linux终端中统计非二进制文件行数的实现方法

《在Linux终端中统计非二进制文件行数的实现方法》在Linux系统中,有时需要统计非二进制文件(如CSV、TXT文件)的行数,而不希望手动打开文件进行查看,例如,在处理大型日志文件、数据文件时,了解... 目录在linux终端中统计非二进制文件的行数技术背景实现步骤1. 使用wc命令2. 使用grep命令

C语言中的常见进制转换详解(从二进制到十六进制)

《C语言中的常见进制转换详解(从二进制到十六进制)》进制转换是计算机编程中的一个常见任务,特别是在处理低级别的数据操作时,C语言作为一门底层编程语言,在进制转换方面提供了灵活的操作方式,今天,我们将深... 目录1、进制基础2、C语言中的进制转换2.1 从十进制转换为其他进制十进制转二进制十进制转八进制十进

如何将二进制文件流转化为MockMultipartFile文件

《如何将二进制文件流转化为MockMultipartFile文件》文章主要介绍了如何使用Spring框架中的MockMultipartFile类来模拟文件上传,并处理上传逻辑,包括获取二进制文件流、创... 目录一、名词解释及业务解释1.具体业务流程2.转换对象解释1. MockMultipartFile2

uva 575 Skew Binary(位运算)

求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

通信工程学习:什么是2ASK/BASK二进制振幅键控

2ASK/BASK:二进制振幅键控         2ASK/BASK二进制振幅键控是一种数字调制技术,其全称是二进制振幅键控(Binary Amplitude Shift Keying)。该技术通过改变载波的振幅来传递二进制数字信息,而载波的频率和相位则保持不变。以下是关于2ASK/BASK二进制振幅键控的详细解释: 一、2ASK/BASK二进制振幅键控的基本原理 1、振幅键控: