河南萌新联赛2024第（一）场

先给出比赛链接： https://ac.nowcoder.com/acm/contest/86639

A 造数

题目问多少次操作可以把0转为n

操作共有三种

$1$
$2$
$\times 2$

能够发现操作的数字最大是2，那么这题就可以考虑二进制。三种操作就能这么理解：

$末位 1$
$倒数第二位 1$
$左移1位$

那么我们就能把n转成2进制来求值以n = 5为例 $n = 5 = (101)_{2}$

$0 \to 10 \to 100 \to 101$

可以发现，当当前位置为0时只需要1次操作就能填好这一位，当当前位置为1时则需要2次操作来填好这一位。

所以我们只需要把n转成二进制01串，然后遍历这个01串（注意不用遍历最高位，因为大于2时最优策略肯定是刚开始先+2）答案加上当前位再加1就行。（注意n为1时需要特判答案为1，为0时则不需要，因为不会进循环）

Show Code A


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    auto to2 = [&](ll n) {
        string res = "";
        while (n) {
            res += n % 2 + '0';
            n /= 2;
        }
        return res;
    };
    ll n = 0;
    cin >> n;
    if (n == 1) {
        cout << 1 << "\n";
    } else {
        int ans = 0;
        string s = to2(n);
        int len = s.size();
        for (int i = 0; i < len - 1; ++ i) {
            ans += 1 + (s[i] - '0');
        }
        cout << ans << "\n";
    }
}

D 小蓝的二进制询问

题目要求区间 [l,r] 中所有整数在二进制下1的个数之和并998244353取模。

对于一个1e18内的数，我们能log级别求出这个数各位上的1的个数那能否快速求出这个数以内的各位上的1的个数呢？这样我们就能通过类似前缀和的操作来求出区间内的所有的1的个数了。事实上是可以的下面是0~16各个数以及它的二进制：（2进制左边为低位）

10进制

2进制

-- | -- $0$ | $000000$ $1$ | $100000$ $2$ | $010000$ $3$ | $110000$ $4$ | $001000$ $5$ | $101000$ $6$ | $011000$ $7$ | $111000$ $8$ | $000100$ $9$ | $100100$ $10$ | $010100$ $11$ | $110100$ $12$ | $001100$ $13$ | $101100$ $14$ | $011100$ $15$ | $111100$ $16$ | $000010$

我们可以发现位权为2^{n}的位,以2^{n 1}为循环

那么我们就能快速的算出总共有几个循环，就能知道循环部分有多少个1了；再加上非循环部分就能知道1~~cur这一位上有多少个1了对每一位求和就能知道1~~cur各位上共有几个1了

但直接这么算由于数据太大很可能会爆ll（即超过ll能表示的数字上限），我们就可以对l - 1 , r分别进行拆位前缀和每一位都用1 ~ r当前位1的个数减去1 ~ l - 1当前位1的个数再取模就不会爆ll了

Show Code D


constexpr ll mod = 998244353;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    vector p(63);
    p[0] = 1ll;
    for (int i = 1; i <= 62; ++ i) {
        p[i] = p[i - 1] * 2ll;
    }
    auto bitprefix = [&](ll n) { // 拆位前缀和
        vector res(64);
        for (int i = 0; i <= 61; ++ i) {
            if (n / p[i] % 2ll == 1ll) { // 当前位需要考虑非循环部分
                res[i] = (n + 1ll) / p[i + 1] * p[i + 1] / 2ll + (n + 1ll) % p[i];// 计算循环部分与非循环部分
            } else { // 当前位不需要考虑非循环部分
                res[i] = (n + 1ll) / p[i + 1] * p[i + 1] / 2ll; // 计算循环部分
            }
        }
        return res;
    };
    auto query = [&](ll l , ll r) {
        ll res = 0;
        vector sl = bitprefix(l - 1ll);
        vector sr = bitprefix(r);
        for (int i = 0; i <= 61; ++ i) {
            res += (sr[i] - sl[i]) % mod;
            res %= mod;
        }
        return res;
    };
    int tt = 1;
    cin >> tt;
    while (tt--) {
        ll l , r;
        cin >> l >> r;
        cout << query(l , r) << "\n";
    }
}

该题的拆位前缀和也能做下面题目

https://ac.nowcoder.com/acm/contest/85639/D

但是该题实际上用F题提到的异或前缀和更方便

F 两难抉择新编

这题与H类似，但是x的上界缩小了，并且求的不是数组和了，而是数组异或和，即所有的数组元素异或和

异或及其性质


异或在C++中的运算符是 ^ 
异或可以理解为按位不进位加法
1.异或的逆运算就是异或本身 如果 a ^ b = c ，那么 c ^ b = a 


2.异或满***换律 即 a ^ b == b ^ a 


3.异或满足结合律 即 (a ^ b) ^ c == a ^ (b ^ c)


4.异或满足分配律 即 a ^ (b & c) == (a ^ b) & (a ^ c)


对于普通加法可以用高斯定律 sn = (1 + n) * n / 2 快速计算1~n的值
对于异或运算来说也有快速计算1~n各数的异或和的方法，即：


s(n)为1到n的数的异或和
s(n) = 1 , n % 4 == 1
s(n) = 0 , n % 4 == 3
s(n) = n , n % 4 == 0
s(n) = n + 1 , n % 4 == 2


代码实现如下：
auto xorprefix = [&](ll n) {
    int flag = n % 4;
    if (flag == 0) {
        return n;
    } else if (flag == 1) {
        return 1;
    } else if (flag == 2) {
        return n + 1;
    } else if (flag == 3) {
        return 0;
    }
};

根据异或的性质，我们并不能直接找到一个操作使得使得数组异或和最大但是我们可以写出朴素的做法，即对每个数加或者乘可能的x的值算出此时的数组异或和。通过上面提到的异或的性质我们可以知道，当数组异或和为sumxor时，只需要 sumxor ^ a[i] 就能删掉数组中a[i]的贡献，此时再异或上a[i]改变的值就能求出此时的数组异或和，取最大就行了

然而其实这个朴素做法就能AC此题

注意x \in [1 , \lfloor n / i \rfloor]

这其实是一个比较常见的调和级数优化

$\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{\frac{n}{i}} 1 = \sum\limits_{i = 1}^{n} \frac{n}{i} = n \sum\limits_{i = 1}^{n} \frac{1}{i} < n(1 ln(n))$

下面给出证明：

$\int_{1}^{n} \frac{1}{x} = ln(x) \vert_{1}^{n} = ln(n)$

通过图像法可知

$\sum\limits_{i = 2}^{n} (i - (i - 1)) * \frac{1}{i} = \sum\limits_{i = 2}^{n} \frac{1}{i} < \int_{1}^{n} \frac{1}{x} = ln(x)$

所以

$\sum\limits_{i = 1}^{n} \frac{1}{i} < 1 ln(x)$

这个复杂度是可以容忍的

Show Code F


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    ll n , ans = 0 , sumxor = 0;
    cin >> n;
    vector a(n + 1);
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
        sumxor ^= a[i];
    }
    for (int i = 1; i <= n; ++ i) {
        ll cur = sumxor;
        cur ^= a[i];
        for (int x = 1; x <= n / i; ++ x) {
            ans = max(ans , cur ^ (a[i] + x));
            ans = max(ans , cur ^ (a[i] * x));
        }
    }
    cout << ans << "\n";
}

H 两难抉择

这题让我们对数组进行操作来使得数组总和最大共有两种操作:

$1.选择数组中的一个数使之加上x,~~~ x \in [1 , n]$ $2.选择数组中的一个数使之乘上x,~~~ x \in [1 , n]$

已知数组中元素是恒正的，那么要使数组和最大，且只能操作一次，对于操作1来说，自然是x选择n最大才能对数组的贡献最大（无论对哪个数加x贡献都一样）；对于操作2来说，x选择最大的ai乘上n贡献最大

Show Code H


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    ll n;
    cin >> n;
    vector a(n);
    for (int i = 0; i < n; ++ i) cin >> a[i];
    sort(a.begin(),a.end());
    a[n - 1] = max(a[n - 1] + n , a[n - 1] * n);
    // 求和函数，for循环直接求也可以
    cout << accumulate(a.begin() , a.end() , 0ll) << "\n"; 
}

I 除法移位

题目要求最多t次循环右移，第几次操作使得数组的第一位元素除以其他所有元素的值最大当第一个元素变大时，后面必有某个元素变小了，那么此时值一定大于变化前的值，所有我们只需要找到最多t次循环右移，元素的第一位何时最大就行。

Show Code I


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n , t;
    cin >> n >> t;
    vector a(n + 1);
    for (int i = 0; i < n; ++ i) cin >> a[i];
    a[n] = a[0];
    int maxn = 0 , maxi = 0 , cur = 0;
    for (int i = n; i >= 0 && cur <= t; -- i , ++ cur) {
        // 当有多种答案时，输出最小值，故不能取等号
        if (a[i] > maxn) { 
            maxn = a[i];
            maxi = cur;
        }
    }
    cout << maxi << "\n";
}

K 图上计数（easy）

你有一张 n 个点 m 条边的无向图，你有无数次删除操作来删除任意条边以获得若干个联通块。定义联通块的大小为其所包含点个数。定义这个图的代价是：你有任意次操作，每次操作合并两个联通块，合并后联通块大小为二者之和，最后剩下两个联通块大小的乘积为此图的代价，若只有一个则代价为0。你需要最大化此图代价。

因为你可以任意删边，也可以随意合并，那么就可以随意构造连通块了。

根据基本不等式链

$H_{n} = \frac{n}{\sum\limits_{i = 1}^{n} \frac{1}{x_{i}}} = \frac{n}{ \frac{1}{x_{1}} \frac{1}{x_{2}} \dots \frac{1}{x_{n}}}$

$G_{n} = \sqrt[n]{\prod\limits_{i = 1}^{n} x_{i}} = \sqrt[n]{x_{1} x_{2} \dots x_{n}}$

$A_{n} = \frac{1}{n} \sum\limits_{i = 1}^{n} x_{i} = \frac{ x_{1} x_{2} \dots x_{n} }{n}$

$Q_{n} = \sqrt{ \frac{1}{n} \sum\limits_{i = 1}^{n} x_{i}^{2} } = \sqrt{ \frac{ x_{1}^{2} x_{2}^{2} \dots x_{n}^{2} }{n} }$

H_{x} \leq G_{x} \leq A_{x} \leq Q_{x}

已知连通块之和为定值，那么两个连通块大小越接近，则这两个连通块的乘积越大

即两个联通块相等或者相差仅为1的时候最大

Show Code K


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    ll n , m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++ i) {
        int u , v;
        cin >> u >> v;
    }
    ll ans = ((n) / 2) * ((n + 1) / 2);
    cout << ans << "\n";
}

(PS:菜菜，目前只写了6题的题解)