二进制¶
一些总和了若干二进制性质的题。
练习 #1 序列合并¶
题目描述
给定一个长度为 \(n\) 的非负整数序列 \(\{a_n\}\)，你可以进行 \(k\) 次操作，每次操作你选择两个相邻的数，把它们合并成它们的按位或。
形式化地，一次操作中，你选择一个下标 \(i\)（\(1 \le i < n\)），然后把原序列变成 \(\{a_1,a_2,\cdots,a_i \operatorname{or} a_{i+1},a_{i+2},\cdots,a_n\}\)。
求 \(k\) 次操作后所有数按位与的最大值。
输入格式
第一行包含两个正整数 \(n,k\)。
第二行包含 \(n\) 个非负整数，其中第 \(i\) 个非负整数为 \(a_i\)。
输出格式
输出一行，包含一个正整数，代表答案。
对于所有数据，保证 \(1 \le k<n \le 2 \times 10^5\)，\(0 \le a_i < 2^{30}\)。
/* Erica N */
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
#define itn int
#define rd read()
int read(){
int xx = 0, ff = 1;char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-')ff = -1; ch = getchar();}
while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
int a[N];
/*
贪心
- 从高位开始考虑，如果要将ans这一位为1，这需要将0都或上1
- 一旦有一位可以操作使ans这一位=1，那么必定操作
我们不要具体深入考虑合并应该向左还是向右，我们直接考虑：当前可以合并除的答案为r，那么r+2^i能否合并出？
判断是否可以合并出r，，即贪心地将序列划分为多的块，使得买一块的或值&r=r。
如果块数>n-K那么就可以。
*/
int n,K;
bool check(int x){
int t=0;
int cnt=0;
for(int i=1;i<=n;i++){
t|=(a[i]);
if((t&x)==x){
t=0;
cnt++;
}
}
return cnt>=n-K;
}
void solve(){
n=rd;
K=rd;
for(int i=1;i<=n;i++){
a[i]=rd;
}
int ans=0;
for(int i=30;~i;i--){
ans+=(1<<i);
if(!check(ans))ans-=(1<<i);
}
cout<<ans<<endl;
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}
练习 #2 Rainbow的信号¶
Freda 发明了传呼机之后，rainbow 进一步改进了传呼机发送信息所使用的信号。
由于现在是数字、信息时代，rainbow 发明的信号用 \(N\) 个自然数表示。
为了避免两个人的对话被大坏蛋 VariantF 偷听，rainbow 把对话分成 \(A、B、C\) 三部分，分别用 \(a、b、c\) 三个密码加密。
现在 Freda 接到了 rainbow 的信息，她的首要工作就是解密。
Freda 了解到，这三部分的密码计算方式如下：
在 \(1 \sim N\) 这 \(N\) 个数中，等概率地选取两个数 \(l、r\)，如果 \(l>r\)，则交换 \(l、r\)。
把信号中的第 \(l\) 个数到第 \(r\) 个数取出来，构成一个数列 \(P\)。
\(A\) 部分对话的密码是数列 \(P\) 的 \(xor\) 和的数学期望值，\(xor\) 和就是数列 \(P\) 中各个数异或之后得到的数； \(xor\) 和的期望就是对于所有可能选取的 \(l、r\)，所得到的数列的 \(xor\) 和的平均数。
\(B\) 部分对话的密码是数列 \(P\) 的 \(and\) 和的期望，定义类似于 \(xor\) 和。
\(C\) 部分对话的密码是数列 \(P\) 的 \(or\) 和的期望，定义类似于 \(xor\) 和。
请你帮忙计算这三个密码。
输入格式
第一行一个正整数 \(N\)。
第二行 \(N\) 个自然数，表示 Freda 接到的信号。
输出格式
一行三个实数，分别表示 \(xor\) 和、\(and\) 和、\(or\) 和的期望，四舍五入保留 \(3\) 位小数，相邻两个实数之间用一个空格隔开。
对于 \(20 \%\) 的数据， \(1 \le N \le 100\) 。 对于 \(40 \%\) 的数据， \(1 \le N \le 1000\) 。 对于另外 \(30 \%\) 的数据, \(N\) 个数为 \(0\) 或 \(1\) 。 对于 \(100 \%\) 的数据, \(1 \le N \le 100000\)，\(N\) 个自然数均不超过 \(10^9\) 。
我们对每一位拆开考虑。
假设当前考虑到了 \(a_x\) 的第 \(i\) 位，我们记为 \(cur\)（值为 \(1\) 或者 \(0\)）。我们只考虑将 \(x\) 作为右端点的情况。使用**期望的定义**。
对于不同的区间，其出现的概率分为以下两种：
-
\(l=r\) 的区间出现的概率为 \(\frac{1}{n^2}\)。
-
\(l≠r\) 的区间出现的概率为 \(\frac{2}{n^2}\)。
我们记 \(pre1\) 为上一个 \(1\) 的下标，\(pre0\) 同理。
下面我们来分类讨论：
-
xor
xor 的情况最为复杂。 我们要记录 \(c0\) 为 \([1,x]\) 中使得区间 \([l,x]\) 的 xor 为 \(0\) 的 \(l\) 的个数。\(c1\) 同理。 如果 \(cur=1\)，左端点可以为 \(c0\)。那么概率就是 \(c0\times \frac{2}{n^2}\)，期望的话再乘上一个
cur<<i即可。交换 \(c1,c0\)。 如果 \(cur=0\)，左端点可以为 \(c1\)。那么概率就是 \(c1\times \frac{2}{n^2}\)，期望的话再乘上一个cur<<i即可。 最后，若 \(cur=0\)，则c0++，否则c1++。 -
and
如果 \(cur=1\)，左端点可以为 \([pre0+1,x]\)。那么概率就是 $ \frac{1}{n^2}+(pre0-x-1)\times \frac{2}{n^2}$，期望的话再乘上一个
cur<<i即可。如果 \(cur=0\)，无贡献。
-
or
如果 \(cur=1\)，左端点可以为 \([1,x]\)。那么概率就是 $ \frac{1}{n^2}+(x-1)\times \frac{2}{n^2}$，期望的话再乘上一个
cur<<i即可。如果 \(cur=0\)，左端点可以为 \([1,pre1]\)。那么概率就是 \(pre1\times \frac{2}{n^2}\)，期望的话再乘上一个
cur<<i即可。
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first
#define ull unsigned long long
#define itn int
// #define inr int
// #define mian main
// #define iont int
#define rd read()
int read() {
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el = '\n';
const bool enable_dbg = 1;
template <typename T, typename... Args>
void dbg(T s, Args... args) {
if constexpr (enable_dbg) {
if (1)
cerr << ' ';
cerr << s;
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) \
do { \
cerr << #x << " -> "; \
err(x); \
} while (0)
void err() { cerr << endl; }
template <template <typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v : a) cerr << v << ' ';
err(x...);
}
template <typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
/*
我们对每一位拆开考虑：
假设当前考虑到了aq_x的第i位，我们记为cur(1/0)。我们只考虑将x作为右端点的情况。使用期望的定义
对于不同的区间，其出现的概率分为以下两种：
- l=r 1/n^2
- l!=r 2/n^2
下面我们来分类讨论：
我们记pre1为上一个1的下标，pre0同理
- xor
xor的情况最为复杂
我们要记录c0为[1,x]中使得区间[l,x]的xor为0的l的个数。c1同理。
如果cur=1，左端点可以为c0。那么概率就是c0*2/n^2，期望的话再乘上一个cur<<i即可。交换c1,c0
如果cur=0，左端点可以为c1。那么概率就是c1*2/n^2，期望的话再乘上一个cur<<i即可。
最后，若cur=0，则c0++，否则c1++
- and
如果cur=1，左端点可以为[pre0+1,x]。那么概率就是1/n^2+(pre0-x-1)*2/n^2，期望的话再乘上一个cur<<i即可。
如果cur=0，无贡献
- or
如果cur=1，左端点可以为[1,x]。那么概率就是1/n^2+(x-1)*2/n^2，期望的话再乘上一个cur<<i即可。
如果cur=0，左端点可以为[1,pre1]。那么概率就是(pre1)*2/n^2，期望的话再乘上一个cur<<i即可。
*/
itn pre[3];
int a[N];
double ansxor, ansor, ansand;
void solve() {
int n = rd;
for (int i = 1; i <= n; i++) {
a[i] = rd;
}
for (itn i = 0; i < 31; i++) {
pre[0] = pre[1] = 0;
int c0 = 0, c1 = 0;
for (int j = 1; j <= n; j++) {
itn cur = (a[j] >> i) & 1;
double res = 1. * (1 << i) / (n * n);
// cdbg(res);
if (cur) {
ansxor += res + 2. * res * c0;
ansand += res + 2. * res * (j - pre[0] - 1);
ansor += res + 2. * (res * (j - 1));
} else {
ansxor += 2. * res * c1;
ansor += 2. * (res * pre[1]);
}
pre[cur] = j;
c0++;
if (cur)
swap(c0, c1);
}
}
printf("%.3lf %.3lf %.3lf\n", ansxor, ansand, ansor);
}
signed main() {
freopen("interval.in", "r", stdin);
freopen("interval.out", "w", stdout);
int T = 1;
while (T--) {
solve();
}
return 0;
}