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

标签：frac 联赛 int ll cin 数组 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";
    }
}

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题的题解)

标签：frac,联赛,int,ll,cin,数组,2024,异或,萌新
From： https://www.cnblogs.com/Proaes/p/18312275

$ 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\)