台风停课，打把 CF 压压惊。

Equal Occurrences

题意

求一个序列的最长子序列，使得这个子序列的任意元素出现次数相同。

顺序无关，所以可以转化成多重集上问题。开个桶 $c_i$，枚举子序列出现次数 $C=c_j$，可得

$$\mathrm{ans} = \max_{C=c_j} C\ \#\{i \mid c_i \ge C\} \xlongequal{c_i \text{降序}} \max_{j} jc_j$$

总时间复杂度 $O(n \log n)$（懒得写桶排），不知道为什么数据规模给得这么松。

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;
}

Merging the Sets

题意

给定 $n$ 个集合 $S_i \subseteq U=\{1, \dots, m\}$，问是否存在至少三个 $T$ 使得 $\displaystyle\bigcup_{i\in T} S_i = U$。

贪心地选择 $T_0 = \{1, \dots, n\}$，$T_j = T_0 \setminus \{j\}$，问题转化为判断 $T_0$ 是否合法且是否至少存在两个 $T_{i\ne0}$ 合法。

设 $c(x) = \displaystyle\sum_{1\le i \le n} [x \in S_i]$，则 $T_i$ 合法当且仅当 $x\in S_i \longrightarrow 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;
}

Wrong Binary Search

注

给定一个长度为 $n$ 的 01-串 $s$，求是否存在长度为 $n$ 的排列 $p$，使得随机二分查找函数 $\mathrm{find}$ 满足 $s_x=1 \iff P \bigl( \mathrm{find}(x)=x \bigr) = 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 \bigl( \mathrm{find}(x)=x \bigr) = 1$ 当且仅当 $p_1, \dots, p_{x-1}$ 是 $1, \dots, x-1$ 的排列，$p_x=x$，且 $p_{x+1}, \dots, p_n$ 是 $x+1, \dots, n$ 的排列。

由此，对于一段极长的全 $0$ 段 $[i, j]$，都有 $p_i, \dots, p_j$ 是 $i, \dots, j$ 的排列。

除此之外，还需要保证 $s_x = 0 \Longrightarrow P(\mathrm{find}(x) = x) \ne 1$。不妨使 $p_x \ne 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;
}

Max Sum OR

题意

给定 $l, r$，设 $n=r-l+1$，有 $b = [l, \dots, r]$，求 $b$ 的排列 $a$，最大化

$$\sum_{i=1}^{n} a_i \lor b_i$$

其中 $\lor$ 表示按位或。

初见杀的观察样例题。记得很久以前在 CF 上看过类似 Easy Version 的题。

由容斥原理 $a_i \lor b_i = a_i + b_i - (a_i \land b_i)$，问题转化为最小化 $a_i \land b_i$。

以下，我们等价地研究 $b_i \mapsto a_i$ 的映射。

Easy Version

此时 $l=0$。

当 $l=0, r=2^k-1$ 时，显然有映射 $x \mapsto 2^k-1-x$ 满足 $x \land (2^k-1-x) = 0$。

$r < 2^k - 1$ 时，映射 $x \mapsto 2^k-1-x$ 不能完全配对，但是不难注意到，未配对的数 $[0, 2^k-2-r]$ 是一个更小的子问题，可以递归求解。这种方法同样能保证 $\sum a_i \land b_i = 0$。

Hard Version

在 Hard Version 中，映射 $x \mapsto 2^k-1-x$ 不一定会减小问题的规模。

此时一定不存在 $2^k \in [l,r]$（否则可以取 $x \mapsto 2^{k+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;
}