Codeforces Good Bye 2023-526互联

A - 2023

直接乘起来显然会爆，但是每个数一定是 \(2023\) 的因子，于是拿一个 \(2023\) 出来，对每个 \(i\) 尝试除掉 \(b_i\)，不能整除直接 No，否则就先补一个剩下的数，然后补 \(k-1\) 个 \(1\) 即可，不用开 long long。

Submission

B - Two Divisors

题目保证有解，那就很好办了。

首先如果 \(a \nmid b\)，那直接输出 \(\text{lcm}(a,b)\) 即可，如果最小公倍数不满足，一定没有其他数能满足。

如果 \(a \mid b\)，那 \(\text{lcm}(a,b) = b\)，这时找最小的质因子乘进去显然可行，但是找质因子很麻烦，而且容易假。观察发现，由于保证有解，于是 \(b\dfrac{b}{a}\) 一定合法，不然 \(a,b\) 中间就还有一个因数。

Submission

C - Training Before the Olympiad

操作相当于求和后舍去 \(sum \bmod 2\)，于是先手希望最小化舍去的值，后手希望最大化舍去的值。根据每个数模 \(2\) 的值分成两类，每次发生舍去一定是一个 \(0\) 和一个 \(1\) 求和，先手希望最小化这种情况，注意到每次操作后总会多出一个 \(0\)，因此先手需要尽快消耗掉所有 \(1\)，那么只要存在 \(2\) 个及以上的 \(1\)，先手都会选 \(1+1\)。后手由于在先手操作后行动，因此一定有 \(0\)，于是只要有 \(1\) 他就会选 \(0+1\) 并使总和减少 \(1\)。

观察到，先后手轮流行动一次后，\(1\) 减少 \(3\) 个，\(0\) 增加 \(1\) 个，于是先把 \(1\) 的个数除掉 \(3\) 并统计周期带来的贡献，剩下的一点模拟一下直到 \(1\) 全部消去即可。

Submission

D - Mathematical Problem

打个表，然后你会发现一个惊人的秘密：在 \(n = 11\) 的时候就已经能找到超过 \(99\) 的解了，于是把 \(n = 1,3,5,7,9,11\) 的数最多的解打个表，\(n\) 超过 \(11\) 就直接在 \(11\) 的解后面加 \(0\) 即可。

打表：

#include <bits/stdc++.h>

using namespace std;
using ll=long long;

vector<vector<ll>> ans;
map<ll,vector<ll>> mp;

void solve(int len,vector<ll> &res) {
    ll liml=1,limr=1;
    for(int i=1;i<len;++i) liml*=10;
    limr=liml*10-1;
    mp.clear();
    for(int i=1;1ll*i*i<=limr;++i) {
        if(1ll*i*i<liml) continue;
        vector<int> d; ll tmp=1ll*i*i;
        while(tmp) d.emplace_back(tmp%10),tmp/=10;
        sort(d.begin(),d.end());
        ll id=0;
        for(auto v:d) id=id*10+v;
        mp[id].emplace_back(1ll*i*i);
    }
    for(auto [id,vec]:mp) {
        if(vec.size()>res.size()) res=vec;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    ans.resize(12);

    for(int i=1;i<=11;i+=2) {
        solve(i,ans[i]);
    }

    cout<<"vector<vector<ll>> ans={";
    for(int i=0;i<12;++i) {
        if(i%2==0) {cout<<"{},"; continue;}
        if(i<11) ans[i].resize(i);
        else ans[i].resize(100);
        ll b=ans[i].back(); ans[i].pop_back();
        cout<<"{";
        for(auto v:ans[i]) cout<<v<<",";
        cout<<b<<"}";
        if(i<11) cout<<",";
    }
    cout<<"};";
    cout<<endl;

    return 0;
}

Submission

E

题目明示我们枚举 LCA，于是考虑枚举 LCA，并在 LCA 向上提的时候动态更新子树信息（下面称题目里的 activity 为颜色）。

于是需要实现的操作就是：对一个到子树根的 \(diff\) 值已知的子树在最上面加入一个颜色为 \(col_u\) 的点 \(u\)，查询子树 \(diff\) 的最大值。

子树查询提示我们把树按照 dfs 序拍平，于是子树查变成了区间查。考虑新加入一个颜色为 \(col_u\) 的点 \(u\) 作为新的根对其所有子树 \(diff\) 的影响，其实等价于对 \(u\) 子树中的所有点先 \(+1\)，然后往下找到第一个和它颜色相同的点（即往下深度优先遍历，遇到同色点就标记并不继续遍历它的子树），把它们子树中的点全部 \(-1\)。

\(+1\) 的复杂度显然正确，对于 \(-1\) 的操作，注意到每个点至多进行一次 \(-1\) 操作，于是在 dfs 时维护出 \(u\) 子树中还没有进行 \(-1\) 的点，每次从中取出颜色为 \(col_u\) 的点做 \(-1\) 并删除即可。

上述操作可以用支持区间加和区间 \(\max\) 的线段树实现，注意题面说选择的两点可能相同，于是答案要和 \(1\) 取 \(\max\)。

Submission