Codeforces Round 1008 (Div. 2) 解题报告

自从南京站打铁之后，道心破碎的我，似乎上个学期就没碰过算法竞赛的任何一点内容了。直到寒假开始想想，要不继续打打cf吧。不过一开始非常烂，先是掉到了绿名( pupil )的水平，打过div4，也算是复健起来了。于是花了一个月的时间，也算是到了蓝名( expert )了。可能是这场运气确实有点好了的原因吧。

那就写个解题报告纪念一下吧，主要也是为了记录当时赛时的思路过程，了解以后如何才能比较快的想到正确思路。

A.Final Verdict

给长度为 $n$ 的序列 $a$ ，每次可以平均分成若干段，然后把分出的每一段合成一个数（这一段数的平均值），最后合成一个数字。给定一个 $x$ ，问是否有一种操作方法让序列变成一个 $x$ 。

因为是A题，盲猜不管怎么操作最后得到的都是一样的，直接取平均值与 $x$ 对照。当然也易证。

code：

#include <bits/stdc++.h>
#define int long long
using namespace std;

int T;

void solve(){
    int n,x,sum = 0;
    cin>>n>>x;
    vector<int> a(n+10);
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        sum += a[i];
    }
    if(sum == x * n){
        cout<<"YES\n";
    }
    else cout<<"NO\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--){

        solve();
    }
    return 0;
}

B.Vicious Labyrinth

相邻房间号 $1$ ~ $n$ ,个房间有一个人和一个传送器，传送器将这个房间里的人传送到目标房间（目标房间不能是自身）。所有人一起传送 $k$ 次。最终代价为每个人距离 $n$ 号房间的距离之和，构造一种传送器方案最小化代价。

$1$ ~ $n-1$ 房间全都传送到 $n$ ， $n$ 传送到 $n-1$ ，可以吗？

不行。hack：3 2。按照这种方案，1和2先被传送到3，3被传送到2，然后两者交换。在 $n-1$ 号房间的人数有2个，代价不是最小。

发现只有第一步，第二步是有用的，后面几步全在重复。所以根据奇偶性进行分类，奇数使用上述方案，偶数的话，除了 $n-1$ 传送到 $n$ ，其他房间全部传送到 $n-1$ 。总代价永远为1，显然最优。

code:

#include <bits/stdc++.h>
#define int long long
using namespace std;

int T;

void solve(){
    int n,k;
    cin>>n>>k;
    if(k % 2 == 1){
        for(int i = 1;i<=n;i++){
            if(i != n)cout<<n<<" ";
            else cout<<n-1<<"\n";
        }
    }
    else{
        for(int i = 1;i<=n;i++){
            if(i != n-1)cout<<n-1<<" \n"[i==n];
            else cout<<n<<" ";
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

C.Breach of Faith

似乎也是div1的A题。对我来说是一道还算可以，不怎么难做的div2C题。

有 $2n+1$ 个两两不同的正数，现在给出 $2n$ 个数，要求找到剩下的一个数，满足这一堆数中的一个数，是通过剩下 $2n$ 个数中两两分组做差后，求和得到。

这个构造里面有几个难点：

必须都是正数
两两必须不同
满足数量关系

其实最简单的是满足数量关系，因为我们只要把它像解方程一样解出来就行了。

怎么保证全都是正数?

比较好想的办法是，没告诉我们的剩下的那个数，正好就是求和得到的数。为了保证它是正数，我们只要把前 $n$ 大的数当成被减数，前 $n$ 小的数当成减数就一定是正数。

两个条件都满足了，能否满足两两不同？

不能。hack：1 6 3 2。 $6+3-2-1=6$ ，是之前出现过的数。我们会发现，上述构造方式不合法，当且仅当前 $n$ 小的数之和，等于前 $n$ 大的数（除去最大的那个数）之和。

这是一个特殊情况。有没有针对它的别的构造方法？

有的兄弟，有的。我们把求和得到的那个数，设为这 $2n$ 个数中最小的那个数，然后把前 $n$ 大的数全都当减数，这样，剩下的那个数一定比所有数都大（经计算，不会超过数据范围）。这样就合法了。

当然，前面有个特殊情况就是 $n=1$ 的时候。简单特判一下（

code:

#include <bits/stdc++.h>
#include <iostream>
#define int long long
using namespace std;

int T;

void solve(){
    int n;
    cin>>n;
    n = n*2 ;
    if(n == 2){
        int a,b;
        cin>>a>>b;
        if(a < b)swap(a,b);
        if(a == b*2){
            cout<<a<<" "<<b*3<<" "<<b<<"\n";
        }
        else{
            cout<<a-b<<" "<<a<<" "<<b<<"\n";
        }
        return;
    }
    vector<int> b(n+1);
    map<int, int> mp;
    for(int i = 1;i<=n;i++){
        cin>>b[i];
        mp[b[i]] = 1;
    }
    sort(b.begin(),b.end());
    int sum = 0;
    for(int i = n; i > n/2;i--){
        sum += b[i];
    }
    for(int i = n/2; i >= 1;i--){
        sum -= b[i];
    }
    if(mp.count(sum)){
        sum = b[1];
        for(int i = n; i > n/2;i--){
            sum += b[i];
        }
        for(int i = n/2; i > 1;i--){
            sum -= b[i];
        }
        cout<<b[1]<<" "<<sum<<" ";
        for(int i = 2;i<=n/2;i++){
            cout<<b[i+n/2]<<" "<<b[i]<<" ";
        }
        cout<<b[n/2+1]<<"\n";
        return;
    }
    cout<<sum<<" ";
    for(int i = n; i >n/2;i--){
        cout<<b[i]<<" "<<b[i-n/2]<<" \n"[i==n/2+1];
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

赛后发现，这个几十多分钟想出来的思路简直歪到姥姥家去了。其实只要最大n+1个数-最小n-1个数就能直接完美搞定这道题目。

D.Scammy Game Ad

当时没仔细看题目，一看这图片和样例就发现：这不就是平常刷的抽象小游戏广告嘛，就明白题意了。

不过题意还是和平常那个小游戏不太一样：首先，左右两通道各有一人。第二，已经选定通道的人不能更改位置，只有新增的人能够自由选择位置。并且，乘法只可能是 $2$ 或者 $3$ 。

这数据范围 $n \leq 30$ 可给我整怕了，本来以为是搜索，或者三分啊什么的。后来再捋了一下思路。

如果说没有乘法，只有加法会怎样？我们会发现，新生成的小人放在哪里根本无所谓。所以说，只有乘法是需要我们明确放置小人的。所以，我们可以手里放一些位置悬而未决的小人，以后可以同意决策。

我们需不需要为了未来考虑，去提前放一些小人在加法的通道上？不需要。因为即使是最小的 $\times 2$ 操作，把空闲的小人全都放过去，就可以全部回收。换句话说，只有尽量多的小人进行乘法操作，我们才可能有多余的收益。

既然不需要为了未来考虑，那直接贪心就完事了，没想到n这么小的一个题目居然复杂度是 $O(n)$ 的，想必只是为了防止数字过大罢，出题还是挺有良心的（笑）。

code:

#include <bits/stdc++.h>
#define int long long
using namespace std;

int T;

void solve(){
    int n;
    cin>>n;
    int l = 1, r= 1, res = 0;
    while(n--){
        char a,c;
        int b,d;
        cin>>a>>b>>c>>d;
        if(a == '+' && c == '+'){
            res += b+d;
        }
        else if(a == 'x' && c == '+'){
            l += res;
            res = l * (b - 1);
            res += d;
        }
        else if(a == '+' && c == 'x'){
            r += res;
            res = r * (d - 1);
            res += b;
        }
        else{
            if(b==d){
                res *= b;
                res += (l+r) * (b-1);
            }
            else if (b == 2 && d == 3){
                r += res;
                res = (r * (d - 1));
                res += (l * (b-1));
            }
            else{
                l += res;
                res = l * (b - 1);
                res += (r * (d-1));
            }
        }
        //cerr<<l<<" "<<r<<" "<<res<<"\n";
    }
    cout<<l+r+res<<"\n";
    //cerr<<l<<" "<<r<<" "<<res<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

写完D题还有一个多小时，EF想了个十几二十分钟，估计这不是我能场上做出来的题就睡觉了。明天，哦不是，今天还得晨跑呢（悲）。

E.Finding OR Sum

当时看过题数，又是交互题真的被吓到了，回来补题的时候发现，原来这题还真的挺简单的。

有两个数 $n,m$ ，你可以询问两个 $x$ , 每一次询问会返回 $(n|x) + (m|x)$ 的值。询问完之后，题目给定一个 $y$ ,输出 $(n|y) | (m|y)$ 的值。

只能询问两次其实给我们一个相当大的提示了。我们可以发现，如果给的x的某一位是0，那么运算后这意味就是n位上的数+m位上的数。如果给的是1，那么固定就是2。这样会产生一个进位的问题，而解决进位问题也相当简单，只要第一次询问 $010101....$ 第二次询问 $101010...$ 就行。这样每个数都有两位的空间来让我们看，这一位上n位上的数+m位上的数究竟是多少。

code:

#include <bits/stdc++.h>
#define int long long
using namespace std;

int T;
int od, ev;

void solve(){
    cout<<od<<endl;
    int odi, evi;
    cin>>odi;
    cout<<ev<<endl;
    cin>>evi;
    odi -= 2* od;
    evi -= 2* ev;
    cout<<"!"<<endl;
    int cnt[40] {};
    for(int i = 0;i<30;i++){
        cnt[i] = 0;
        if(i%2){
            if((odi>>i) & 1)cnt[i] = 1;
            else if((odi>>(i+1)) & 1)cnt[i] = 2;
        }
        else{
            if((evi>>i) & 1)cnt[i] = 1;
            else if((evi>>(i+1)) & 1)cnt[i] = 2;
        }
    }
    int cop;
    cin>>cop;
    int ans = 0;
    for(int i = 0;i<30;i++){
        if((cop >> i) & 1)ans += (2<<i);
        else ans += cnt[i] * (1<<i);
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(int i = 0;i<30;i++){
        if(i % 2)ev |= (1<<i);
        else od |= (1<<i);
    }
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

F.Binary Subsequence Value Sum

有点难。但是当时看榜居然这题过的比E多，不可思议。

一个长度为 $n$ 的由 $1$ 和 $-1$ 组成的串，定义一个子序列的价值为将这个序列分成两段之后，把每段的求和乘起来得到的最大值。

有 $q$ 次询问，每次可以改变某一位的值，每次询问完后，求所有子序列的价值之和（带取模）。

我理解了好几天这个解法，看jiangly老师录播的时候真感觉惊为天人。一下子就写出来了。

最后的解法是这样：首先，我们可以确定的是，不管这个序列的 $-1$ 和 $1$ 分布如何，最后的价值一定是这个序列的总和，平方，再除4。（先只考虑偶数情况）。总之，肯定是将它拆分为求和基本一样的两段（基本不等式，易证）。

对于奇数的情况呢？假如总和是 $2n+1$ 那么价值就是 $n(n+1)$ 。但是这样写不方便求平方，可以写成 $\frac{(2n+1)^2-1}{4}$ 。那么，对于偶数（ $2n$ ）的情况也就是 $\frac{(2n)^2}{4}$ 。

总结： $ val(x) = \frac{1}{4} [x^2 - (x \mod 2)] $

我们对于特定的和的价值已经了解，接下来需要求总价值，也就转化为了一个计数问题。

我们怎样求求和为某一个特定的数的子序列的数量呢？

假设序列中 $-1$ 的数量为 $x$ 。可以说，所有子序列中，代价最大的，肯定要么全是1，要么全是-1。接下来就是这个解法的妙处所在了：

假如说，我们默认全取-1。我们如果多改变默认值中的一个，比如说，把原来应该取的-1不取了，或者把原来不应该取的1给取了，那么子序列的总和就会减少1。于是，我们原先推得的式子里面， $x$ 就应代换成 $x-1$ 。改变 $i$ 个，就代换成 $ x-i $ 。

还有一点，改变 i 个的子序列一共有多少个？ $C^i_n $ 个。$这样，我们针对所有的子序列都能直接计算价值了。

$val(s) = \frac{1}{4}\sum^n_ {i=0}\mathrm{C}^i_n( [(x-i)^2 - ((x-i) \mod 2)] )$

为了以 $O(1)$ 的速度求出它，我们需要把平方项拆开，然后分别求和，这一步就相当简单了。

code:

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

#define int long long 

template<class T>
constexpr T power(T a, u64 b, T res = 1) {
    for (; b != 0; b /= 2, a *= a) {
        if (b & 1) {
            res *= a;
        }
    }
    return res;
}

template<u32 P>
constexpr u32 mulMod(u32 a, u32 b) {
    return u64(a) * b % P;
}

template<u64 P>
constexpr u64 mulMod(u64 a, u64 b) {
    u64 res = a * b - u64(1.L * a * b / P - 0.5L) * P;
    res %= P;
    return res;
}

constexpr i64 safeMod(i64 x, i64 m) {
    x %= m;
    if (x < 0) {
        x += m;
    }
    return x;
}

constexpr std::pair<i64, i64> invGcd(i64 a, i64 b) {
    a = safeMod(a, b);
    if (a == 0) {
        return {b, 0};
    }
    
    i64 s = b, t = a;
    i64 m0 = 0, m1 = 1;

    while (t) {
        i64 u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        
        std::swap(s, t);
        std::swap(m0, m1);
    }
    
    if (m0 < 0) {
        m0 += b / s;
    }
    
    return {s, m0};
}

template<std::unsigned_integral U, U P>
struct ModIntBase {
public:
    constexpr ModIntBase() : x(0) {}
    template<std::unsigned_integral T>
    constexpr ModIntBase(T x_) : x(x_ % mod()) {}
    template<std::signed_integral T>
    constexpr ModIntBase(T x_) {
        using S = std::make_signed_t<U>;
        S v = x_ % S(mod());
        if (v < 0) {
            v += mod();
        }
        x = v;
    }
    
    constexpr static U mod() {
        return P;
    }
    
    constexpr U val() const {
        return x;
    }
    
    constexpr ModIntBase operator-() const {
        ModIntBase res;
        res.x = (x == 0 ? 0 : mod() - x);
        return res;
    }
    
    constexpr ModIntBase inv() const {
        return power(*this, mod() - 2);
    }
    
    constexpr ModIntBase &operator*=(const ModIntBase &rhs) & {
        x = mulMod<mod()>(x, rhs.val());
        return *this;
    }
    constexpr ModIntBase &operator+=(const ModIntBase &rhs) & {
        x += rhs.val();
        if (x >= mod()) {
            x -= mod();
        }
        return *this;
    }
    constexpr ModIntBase &operator-=(const ModIntBase &rhs) & {
        x -= rhs.val();
        if (x >= mod()) {
            x += mod();
        }
        return *this;
    }
    constexpr ModIntBase &operator/=(const ModIntBase &rhs) & {
        return *this *= rhs.inv();
    }
    
    friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs) {
        lhs *= rhs;
        return lhs;
    }
    friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs) {
        lhs += rhs;
        return lhs;
    }
    friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs) {
        lhs -= rhs;
        return lhs;
    }
    friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs) {
        lhs /= rhs;
        return lhs;
    }
    
    friend constexpr std::istream &operator>>(std::istream &is, ModIntBase &a) {
        i64 i;
        is >> i;
        a = i;
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const ModIntBase &a) {
        return os << a.val();
    }
    
    friend constexpr bool operator==(const ModIntBase &lhs, const ModIntBase &rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr std::strong_ordering operator<=>(const ModIntBase &lhs, const ModIntBase &rhs) {
        return lhs.val() <=> rhs.val();
    }
    
private:
    U x;
};

template<u32 P>
using ModInt = ModIntBase<u32, P>;
template<u64 P>
using ModInt64 = ModIntBase<u64, P>;

struct Barrett {
public:
    Barrett(u32 m_) : m(m_), im((u64)(-1) / m_ + 1) {}

    constexpr u32 mod() const {
        return m;
    }

    constexpr u32 mul(u32 a, u32 b) const {
        u64 z = a;
        z *= b;
        
        u64 x = u64((u128(z) * im) >> 64);
        
        u32 v = u32(z - x * m);
        if (m <= v) {
            v += m;
        }
        return v;
    }

private:
    u32 m;
    u64 im;
};

template<u32 Id>
struct DynModInt {
public:
    constexpr DynModInt() : x(0) {}
    template<std::unsigned_integral T>
    constexpr DynModInt(T x_) : x(x_ % mod()) {}
    template<std::signed_integral T>
    constexpr DynModInt(T x_) {
        int v = x_ % (int)(mod());
        if (v < 0) {
            v += mod();
        }
        x = v;
    }
    
    constexpr static void setMod(u32 m) {
        bt = m;
    }
    
    static u32 mod() {
        return bt.mod();
    }
    
    constexpr u32 val() const {
        return x;
    }
    
    constexpr DynModInt operator-() const {
        DynModInt res;
        res.x = (x == 0 ? 0 : mod() - x);
        return res;
    }
    
    constexpr DynModInt inv() const {
        auto v = invGcd(x, mod());
        assert(v.first == 1);
        return v.second;
    }
    
    constexpr DynModInt &operator*=(const DynModInt &rhs) & {
        x = bt.mul(x, rhs.val());
        return *this;
    }
    constexpr DynModInt &operator+=(const DynModInt &rhs) & {
        x += rhs.val();
        if (x >= mod()) {
            x -= mod();
        }
        return *this;
    }
    constexpr DynModInt &operator-=(const DynModInt &rhs) & {
        x -= rhs.val();
        if (x >= mod()) {
            x += mod();
        }
        return *this;
    }
    constexpr DynModInt &operator/=(const DynModInt &rhs) & {
        return *this *= rhs.inv();
    }
    
    friend constexpr DynModInt operator*(DynModInt lhs, const DynModInt &rhs) {
        lhs *= rhs;
        return lhs;
    }
    friend constexpr DynModInt operator+(DynModInt lhs, const DynModInt &rhs) {
        lhs += rhs;
        return lhs;
    }
    friend constexpr DynModInt operator-(DynModInt lhs, const DynModInt &rhs) {
        lhs -= rhs;
        return lhs;
    }
    friend constexpr DynModInt operator/(DynModInt lhs, const DynModInt &rhs) {
        lhs /= rhs;
        return lhs;
    }
    
    friend constexpr std::istream &operator>>(std::istream &is, DynModInt &a) {
        i64 i;
        is >> i;
        a = i;
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const DynModInt &a) {
        return os << a.val();
    }
    
    friend constexpr bool operator==(const DynModInt &lhs, const DynModInt &rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr std::strong_ordering operator<=>(const DynModInt &lhs, const DynModInt &rhs) {
        return lhs.val() <=> rhs.val();
    }
    
private:
    u32 x;
    static Barrett bt;
};

template<u32 Id>
Barrett DynModInt<Id>::bt = 998244353;
using Z = ModInt<998244353>;

struct Comb {
    int n;
    std::vector<Z> _fac;
    std::vector<Z> _invfac;
    std::vector<Z> _inv;
    
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

void solve() {
    int n, q;
    cin>>n>>q;
    string s;
    cin>>s;
    int x = -count(s.begin(), s.end(),'0');
    Z a[2], b[2], c[2];
    for(int p = 0;p<=1;p++){
        for(int i = 0;i<=n;i++){
            a[p] += comb.binom(n, i);
            b[p] += comb.binom(n, i) * 2 * i;
            c[p] += comb.binom(n, i) * i * i;
            if((i+p)%2 == 1)c[p]-=comb.binom(n, i);
        }
    }
    while(q--){
        int p;
        cin>>p;
        if(s[p-1] == '0')x++;
        else x--;
        s[p-1] ^=1;
        Z ans = 0;
        int od = x  & 1;
        ans = a[od] * x * x + b[od] * x + c[od] ;
        ans = ans / 4;
        cout<<ans<<"\n";
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

后记

感觉前面几年的学习还不如这一个月来的效率高呢。我之前到底在做什么？我真的在前进吗？？

希望我做的这些微薄努力能在一小点程度上稍微扭转我早已烂掉的命运罢…

技术向

#ACM #算法 #Codeforces

Codeforces Round 1008 (Div. 2) 解题报告

http://blog.bluspace.ren/2025/03/11/Codeforces Round 1008 (Div. 2) 解题报告/

作者

Blauter

发布于

2025年3月11日

许可协议

就那么一点点的生成函数与多项式上一篇

【碎碎念】耳机全丢了下一篇