Baozii Cup 3 - 做题&补题记录

王负剑，王复健！差不多三个月没打A了，期间除了力扣啥也没写，于是集NTT众人进行复健仪式，复健材料为Baozii Cup 3。本来是想跟邀请赛选拔赛的榜的，误打误撞打成这个了。最后弄出来4题，这比赛还是挺难的感觉。

有一道概率论的题感觉非常典，完了单独总结下 :)

---

D - Xor And Mul

签到。鄙人还是那样非常擅长签到。按二进制考虑，显然某个数取0的时候才能满足题意，两个数从 $0$ 到 $n$ 和从 $0$ 到 $m$ 各取一遍，再减掉同为 $0$ 的情况，答案即为 $n+m+1$ 。

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

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

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

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

B - Odd Cycle

给定可能存在自环和重边的有向图，判断每个点是否在任意奇环上。

另外感觉题意给的奇环定义错得离谱，最后是按样例判断确实是奇环才做下去的。

做法：先SCC缩点，相同分量内部再红蓝染色，如果找到两个颜色相同的点说明分量内部存在奇环，按照题目定义奇环序列的点可以重复，那么总能构造出满足题意的奇环来包含分量内部的任意点，也就是这个分量的所有点都符合题意。

#include <bits/stdc++.h>
using ll = long long;
using i64 = long long;
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> e(n + 1);
    for (int u, v, i = 0; i < m; ++i) {
        cin >> u >> v;
        e[u].push_back(v);
    }
    vector<int> dfn(n + 1), low(n + 1), instk(n + 1), scc(n + 1), sz(n + 1), stk(n + 1);
    int tot{}, cnt{}, cntt{}, top{};
    auto dfs = [&](this auto&& dfs, int u) -> void {
        dfn[u] = low[u] = ++tot;
        stk[++top] = u, instk[u] = 1;
        for (int v : e[u]) {
            if (!dfn[v]) {
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else if (instk[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u]) {
            int v;
            cnt++;
            do {
                v = stk[top--];
                instk[v] = 0;
                scc[v] = cnt;
                sz[cnt]++;
            } while (v != u);
            if (sz[cnt] > 1) cntt++;
        }
    };
    for(int i=1;i<=n;++i)
    {
        if(!dfn[i]){
            dfs(i);
        }
    }
    vector<int> ans(n+1, -1), vis(n+1, -1);
    auto bfs = [&](int s) -> int {
        queue<int> q;
        q.emplace(s);
        vis[s] = 0;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int v:e[u]){
                if(scc[u] != scc[v]){
                    continue;
                }
                if(vis[v] == -1){
                    vis[v] = vis[u]^1;
                    q.emplace(v);
                    continue;
                }
                if(vis[v] == vis[u]){
                    return 1;
                }
            }
        }
        return 0;
    };
    for(int i=1;i<=n;++i){
        if(ans[scc[i]] == -1){
            ans[scc[i]] = bfs(i);
        }
        cout << ans[scc[i]];
    }
    cout << "\n";
    return;
}

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

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

J - Someone’s Favourite Problem

被交互打晕了，但是等老许出了做法以后感觉确实很合理也不难理解。。只能说好久没做了脑子有点锈。

按照题意，要找到一个入度为 $n-1$ 且出度为 $0$ 的点，那么这种点最多存在一个。于是维护一个 $cur$ 表示可能是答案的点，初始值为 $1$，然后从 $2$ 到 $n$ 依次往后判断，如果 $cur$ 到 $i$ 存在边，那么 $cur$ 不可能为答案，令 $cur=i$ ，否则 $i$ 不会是答案， $cur$ 不变。这样询问 $n-1$ 次后，能确定唯一一个可能是答案的点，再做 $2n-2$ 次询问即可，总询问次数 $3n-3$ 满足题意。

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

void solve() {
    int n;
    cin>>n;
    auto query=[&](int u,int v){
        cout<<"? "<<u<<" "<<v<<endl;
        int res;
        cin>>res;
        return res;
    };
    int cur=1;
    for(int i=2;i<=n;++i){
        if(query(cur,i)){
            cur=i;
        }
    }
    int flag=1;
    for(int i=1;i<=n;++i){
        if(i==cur) continue;
        flag &= !query(cur, i);
        flag &= query(i, cur);
    }
    if (!flag) cur = -1;
    cout<<"! "<<cur<<endl;
}

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

    int t = 1;
    cin >> t ;
    while (t--) {
        solve();
    }
}

E - MiniC

什么叫给我MiniC语言解释器让我现场学代码？（x

思洋写的，有空会补。总之是给了个不带控制流和算术操作的语言，只能进行变量自增自减，然后给定一个排列，要找到每个元素之后第一个小于该元素的值对应的下标。

#include<bits/stdc++.h>
std::string program = R"(
int n;
int p[1010];
int q[1010];
func nop{}

func finput[2];
int arrinput[1010];
int iinput;
func input{
    read p[iinput];
    int t;
    t = p[iinput];
    t++;
    q[t] = iinput;
    iinput++;
    call finput[arrinput[iinput]];
}

int cur;
int ans;
int vis[1010];
func fclear[2];
int arrclear[1010];
int iclear;
func clear{
    vis[iclear] = 0;
    iclear++;
    call fclear[arrclear[iclear]];
}
func finit[2];
int arrinit[1010];
int iinit;
func init{
    iinit++;
    vis[q[iinit]] = 1;
    call finit[arrinit[iinit]];
}
func ffill[2];
int ifill;
func fill{
    ifill++;
    int t;
    t = ifill;
    call ffill[vis[ifill]];
    vis[t] = 1;
}
func floop[2];
int arrloop[1010];
int iloop;
func loop{
    ffill[0] = fill;
    ffill[1] = nop;
    ifill = q[iloop];
    call fill;
    iloop--;
    call floop[arrloop[iloop]];
}
func ffind[2];
int ifind;
func findans{
    ans = ifind;
}
func find{
    ifind++;
    call ffind[vis[ifind]];
}
func get{
    fclear[1] = nop;
    fclear[0] = clear;
    iclear = cur;
    arrclear[n] = 1;
    call clear;

    finit[1] = nop;
    finit[0] = init;
    iinit = p[cur];
    int t;
    t = n;
    t++;
    arrinit[t] = 1;
    call init;

    vis[cur] = 1;
    vis[n] = 1;

    floop[1] = nop;
    floop[0] = loop;
    iloop = p[cur];
    arrloop[0] = 1;
    call floop[arrloop[iloop]];

    vis[n] = 0;
    ffind[1] = find;
    ffind[0] = findans;
    ifind = cur;
    call find;
}

func fsolve[2];
int arrsolve[1001];
int isolve;
func solve{
    cur = isolve;
    call get;
    println ans;
    isolve++;
    call fsolve[arrsolve[isolve]];
}

func main{
    read n;
    finput[1] = nop;
    finput[0] = input;
    iinput = 0;
    arrinput[n] = 1;
    call input;

    fsolve[1] = nop;
    fsolve[0] = solve;
    isolve = 0;
    arrsolve[n] = 1;
    call solve;
}
)";
int main(){
    std::cout << program << "\n";
}

L - Perimeter

重头戏。场上没写出来，但是感觉非常典于是一定要补。

给定 $n\times m$ 的网格，进行 $k$ 次操作，每次随机选择一个格子，若为白则染黑。问最后得到的黑色联通块的周长和的期望。

直接做很难，我们分解成每个黑色格子对答案的贡献。一个黑格子会贡献 $4$ 的周长，但同时两个相邻的黑格子会相互抵消 $2$ 的周长。因此周长 $P = 4X - 2A$ ，其中 $X$ 是黑格子数量，$A$ 是相邻黑格子对数。

根据期望的线性性，我们得到 $E(P) = 4E(X)-2E(A)$ ，我们分成两部分来求。

第一部分求 $E(X)$ ，同样地，直接整体递推太难了，我们考虑每个格子的贡献。一个格子被染成黑色的概率 $P(u 黑) = 1-P(u白)=1-(\frac{nm-1}{nm})^k$ 。那么 $E(X)=nmP(u黑)$ 。

第二部分求 $E(A)$ ，依旧考虑每对格子同时为黑的概率。$P(u黑v黑)=1-P(u白)-P(v白)+P(u白v白)=1-2(\frac{nm-1}{nm})^k+(\frac{nm-2}{nm})^k$ 。那么 $E(A) = \left(n(m-1)+m(n-1)\right)P(u黑v黑)$。

整理得到最终答案 $E(P)=2(n+m)+4(nm-n-m)(\frac{nm-1}{nm})^k-2(2nm-n-m)(\frac{nm-2}{nm})^k$ 。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

constexpr int N = 2e5 + 10;
constexpr int MOD = 1'000'000'007;

i64 ksm(i64 a, i64 b) {
    i64 res{1};
    a %= MOD;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void solve() {
    i64 n, m, k;
    cin >> n >> m >> k;
    i64 inv = ksm(n * m, MOD - 2);
    i64 ans = 2 * (n + m) % MOD;
    ans = (ans + 4 * (n * m % MOD - n - m) % MOD * ksm((n * m - 1) % MOD * inv, k)) % MOD;
    ans = (ans - 2 * (2 * n * m % MOD - n - m) % MOD * ksm((n * m - 2) % MOD * inv, k)) % MOD;
    ans = (ans + MOD) % MOD;
    cout << ans << "\n";
}

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

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}