Hello 2025

Hello 2025

A. MEX Table

题意：

给出 0 到 n ∗ m − 1 的数字，排列成 n × m 的表格，最大化 ∑ i = 1 n mex ⁡ ( { a i , 1 , a i , 2 , … , a i , m } ) + ∑ j = 1 m mex ⁡ ( { a 1 , j , a 2 , j , … , a n , j } ) 给出0到n*m-1的数字，排列成n×m的表格，最大化\sum\limits_{i = 1}^{n} \operatorname{mex}(\{a_{i,1}, a_{i,2}, \ldots, a_{i,m}\}) + \sum\limits_{j = 1}^{m} \operatorname{mex}(\{a_{1,j}, a_{2,j}, \ldots, a_{n,j}\}) 给出0到n∗m−1的数字，排列成n×m的表格，最大化i=1∑n​mex({ai,1​,ai,2​,…,ai,m​})+j=1∑m​mex({a1,j​,a2,j​,…,an,j​})

思路：

$取行列中最大的值m，0所在的另一行/列为1，其余均为0，最大值$
$为m+1。$

AC code:

void solve() {   
    int n, m; cin >> n >> m;
    cout << max(n, m) + 1 << endl;
} 

B. Gorilla and the Exam

题意：

$定义将数组b清空的方式，每次选取任意长度区间并任选一个值x将$
$区间中等于x的元素删除;$

$现在可以将数组b中最多k个元素任意改变，求操作后最少需要多少$
$次操作可以删除数组b。$

思路：

$每次删除操作即删除当前数组中相同的元素，map记录一下不同元$
$素的个数，从数量少的元素开始修改即可。$

AC code:

void solve() {   
    int n, k; cin >> n >> k;
    vector<int> v(n + 1);
    map<int, int> mp;
    for (int i = 1; i <= n; i ++) {
        cin >> v[i];
        mp[v[i]] ++;
    }
    vector<int> ca;
    for (auto [x, y] : mp) ca.push_back(y);
    sort(ca.begin(), ca.end());
    int ans = ca.size();
    for (auto x : ca) {
        if (x > k) break;
        k -= x; 
        ans --;
    }
    cout << max(1LL, ans) << endl;
} 

C. Trip to the Olympiad

题意：

$从l到r的区间内任选三个不同的元素，使得(a\oplus b)+(b\oplus c)+(a\oplus c)的值最大$

思路：

$首先通过打表可以发现最大值情况的三元素总会出现相邻的情况，$
$所以可以通过定位其中一个元素的方式来找到其余两个；$

$通过由高到低逐位比较最大最小元素的二进制前缀，找到最高的不$
$同位，在这之前的相同前缀无贡献；$

$所取的值要在范围内尽可能的大，所以累加无贡献但存在的位，$
$以及不同的最高位，即为定位的元素；$

$找到定位元素x取其前后即为所求，特殊的，对于定位元素x为边界$
$值r时，取x-2,x-1$

AC code:

void solve() { 
    int l, r; cin >> l >> r;
    int sum = 0, pos = 30;
    while (pos --) {
        int now = (1LL << pos);
        if ((l & now) != (r & now)) break;
        if ((l & now)) sum += now;
    }
    int cnt = (1LL << pos) + sum;
    if (r == cnt) cout << cnt - 2 << ' ' << cnt - 1 << ' ' << cnt << endl;
    else cout << cnt - 1 << ' ' << cnt << ' ' << cnt + 1 << endl;
}