外观
CF2146
台风停课,打把 CF 压压惊。
A. Equal Occurrences
题意
求一个序列的最长子序列,使得这个子序列的任意元素出现次数相同。
顺序无关,所以可以转化成多重集上问题。开个桶 ci,枚举子序列出现次数 C=cj,可得
ans=C=cjmaxC #{i∣ci≥C}ci降序jmaxjcj
总时间复杂度 O(nlogn)(懒得写桶排),不知道为什么数据规模给得这么松。
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn=128;
int c[maxn];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
memset(c, 0, sizeof c);
for (int i=1; i<=n; i++) {
int a;
cin >> a;
c[a]++;
}
sort(c+1, c+n+1, greater<int>());
int ans = 0;
for (int i=1; i<=n; i++) {
ans = max(ans, i*c[i]);
}
cout << ans << '\n';
}
return 0;
}B. Merging the Sets
题意
给定 n 个集合 Si⊆U={1,…,m},问是否存在至少三个 T 使得 i∈T⋃Si=U。
贪心地选择 T0={1,…,n},Tj=T0∖{j},问题转化为判断 T0 是否合法且是否至少存在两个 Ti=0 合法。
设 c(x)=1≤i≤n∑[x∈Si],则 Ti 合法当且仅当 x∈Si⟶c(x)>1。
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4+10, maxm = 1e5+10;
vector<int> S[maxn];
int c[maxm];
int n, m;
bool solve() {
for (int i=1; i<=m; i++) {
if (!c[i]) {
return false;
}
}
int cnt = 0;
for (int i=1; i<=n; i++) {
bool ok = true;
for (int a: S[i]) {
if (c[a] < 2) {
ok = false;
break;
}
}
cnt += ok;
if (cnt == 2) {
return true;
}
}
return false;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
cin >> n >> m;
for (int i=1; i<=m; i++) {
c[i] = 0;
}
for (int i=1; i<=n; i++) {
int l;
cin >> l;
S[i].clear();
for (int j=1; j<=l; j++) {
int a;
cin >> a;
S[i].push_back(a);
c[a]++;
}
}
cout << (solve()? "YES\n": "NO\n");
}
return 0;
}C. Wrong Binary Search
注
给定一个长度为 n 的 01-串 s,求是否存在长度为 n 的排列 p,使得随机二分查找函数 find 满足 sx=1⟺P(find(x)=x)=1?
随机二分查找的过程如下:
function find(int x):
l := 1
r := n
while l <= r:
m := random integer of [l, r]
if p[m] == x:
return m
if p[m] > x:
r := m - 1
else:
l := m + 1
return undefined // not found注意到 P(find(x)=x)=1 当且仅当 p1,…,px−1 是 1,…,x−1 的排列,px=x,且 px+1,…,pn 是 x+1,…,n 的排列。
由此,对于一段极长的全 0 段 [i,j],都有 pi,…,pj 是 i,…,j 的排列。
除此之外,还需要保证 sx=0⟹P(find(x)=x)=1。不妨使 px=x,错排每一个极长全 0 段即可。
众所周知,长度大于 1 的排列总有错排,于是该解只在不存在长度为 1 的极长全 0 段时可用。不难证明存在长度为 1 的极长全 0 段时无解。
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
int head0[maxn];
char s[maxn];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n >> (s+1);
s[0] = s[n+1] = '1';
bool ok = true;
for (int i=1; i<=n; i++) {
if (s[i] == '1') {
continue;
}
if (s[i-1] == '0') {
head0[i] = head0[i-1];
continue;
}
head0[i] = i;
if (s[i+1] == '1') {
ok = false;
}
}
cout << (ok? "YES\n": "NO\n");
if (!ok) {
continue;
}
for (int i=1; i<=n; i++) {
if (s[i] == '1') {
cout << i << ' ';
continue;
}
cout << (s[i+1] == '1'? head0[i]: i+1) << ' ';
}
cout << '\n';
}
return 0;
}D. Max Sum OR
题意
给定 l,r,设 n=r−l+1,有 b=[l,…,r],求 b 的排列 a,最大化
i=1∑nai∨bi
其中 ∨ 表示按位或。
初见杀的观察样例题。记得很久以前在 CF 上看过类似 Easy Version 的题。
由容斥原理 ai∨bi=ai+bi−(ai∧bi),问题转化为最小化 ai∧bi。
以下,我们等价地研究 bi↦ai 的映射。
Easy Version
此时 l=0。
当 l=0,r=2k−1 时,显然有映射 x↦2k−1−x 满足 x∧(2k−1−x)=0。
r<2k−1 时,映射 x↦2k−1−x 不能完全配对,但是不难注意到,未配对的数 [0,2k−2−r] 是一个更小的子问题,可以递归求解。这种方法同样能保证 ∑ai∧bi=0。
Hard Version
在 Hard Version 中,映射 x↦2k−1−x 不一定会减小问题的规模。
此时一定不存在 2k∈[l,r](否则可以取 x↦2k+1−1−x),即区间内所有数拥有相同的最高位。
去掉最高位之后即可作为一个更小的子问题递归求解。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+100;
unordered_map<int, int> ans;
inline int highbit(int x) {
while ((x&-x) != x) {
x ^= (x&-x);
}
return x;
}
void solve(int l, int r, int h) {
// printf("solve(%d, %d, %d)\n", l, r, h);
if (l > r) {
return;
}
if (l==0 && r==0) {
ans[h] = h;
return;
}
int hl = highbit(l), hr = highbit(r);
if (hl == hr) {
solve(l-hl, r-hr, h+hl);
} else {
int b = 2*hr-1, ml = max(l, b-r), mr = min(r, b-l);
for (int i=ml; i<=mr; i++) {
ans[i+h] = b-i+h;
}
if (ml == l) {
solve(mr+1, r, h);
} else {
solve(l, ml-1, h);
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
int l, r;
cin >> l >> r;
ans.clear();
solve(l, r, 0);
int s = 0;
for (int i=l; i<=r; i++) {
s += i | ans[i];
}
cout << s << '\n';
for (int i=l; i<=r; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
}
return 0;
}