春节比赛好题集锦

发表于 2023-01-25 分类于题解

ARC154D. A + B > C ?

题意：**交互题。**有一个长度 $2000$ 以内的排列 $p$ ，你每次可以询问 $i,j,k$ ，交互库 $p_i+p_j>p_k$ ，返回 Yes/No。在 $25000$ 次询问内得出排列。

可以想到，如果能询问 $p_i>p_j$ 是否成立，就可以直接通过 $n\log n$ 次询问将下标排序，从而还原排列 $p$ 。由于排列的数互不相同，所以这是能够做到的：加入找到了 $p_x=1$ 的 $x$ ，那么询问 $i,x,j$ ，效果等同于判断 $p_i\ge p_j$ 是否成立。将询问作为比较函数扔到 sort 里即可。对于找 $x$ ，可以考虑 $1$ 的特殊性质： $1,1,i$ 永远返回 No，而 $i,i,1$ 永远返回 Yes，且 $1$ 是唯一满足任一性质的数。有了这两个性质，可以依次考虑排列的某一位 $i$ ，并维护当前扫到的最有可能成为 $1$ 的数 $mn$ ，询问 $mn,mn,i$ ，如果是 Yes 则更改 $mn$ ，否则不变。正确性容易证明。

By zhoukangyang

const int N = 1e6 + 7;
int n;
int p[N];
mt19937_64 orz(time(0) ^ *new int);
int ask(int i, int j, int k) {
    cout << "? " << i << ' ' << j << ' ' << k << endl;
    string w;
    cin >> w;
    return w == "Yes" ? 1 : 0;
    return p[i] + p[j] > p[k];
}
int ord[N];
int main () {
    ios :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    p[1] = 3, p[2] = 1, p[3] = 2, p[4] = 4;
    int cur = 1;
    L(i, 2, n)
        if(ask(cur, cur, i)) {
            cur = i;
        }
    L(i, 1, n) {
        ord[i] = i;
    }
    stable_sort(ord + 1, ord + n + 1, [&] (int x, int y) {
        if(x == y) return false;
        return !ask(x, cur, y);
    });
    L(i, 1, n)
        p[ord[i]] = i;
    cout << "! ";
    L(i, 1, n)
        cout << p[i] << ' ';
    cout << endl;
    return 0;
}

CF1777D. Score of a Tree

题目传送门

题意：有一棵 $n$ 个节点的树，每个节点有 $0/1$ 两种权值。对于一种状态，下一秒每个节点的权值都会同时变成儿子的权值的异或和（即儿子原来的权值的异或和），叶子结点的权值会变为 $0$ 。对于每一种初始状态求和：从该初始状态开始，每一时刻的权值和之和。对 $998244353$ 取模。

考虑一个节点的权值会如何变化。第 $0$ 秒为初始状态；第 $1$ 秒为所有儿子初始状态的异或；第 $2$ 秒为所有儿子第 $1$ 秒状态的异或，由于异或的结合律，等于所有“孙子”初始状态的异或；同理，第 $k$ 秒为所有 $k$ 级儿子初始状态的异或（如果没有 $k$ 级儿子则为 $0$ ）。

考虑在所有的初始状态下，一个节点在第 $k$ 秒的权值和：有多少种方案， $k$ 级儿子初始状态的异或为 $1$ 。即有多少种方案，在 $k$ 级儿子内有奇数个 $1$ 。根据组合数的结论，选奇数个和选偶数个的方案数相同，所以方案数为 $\frac{1}{2}\cdot 2^n$ 。

由此可见，只要存在 $k$ 级儿子，无论数量多少，异或为 $1$ 的方案数总为 $2^{n-1}$ 。所以答案为，对于每个节点，考虑从该节点开始的最深的深度 $x$ ，该节点的总贡献为 $2^{n-1}\cdot (x+1)$ 。

By cxm1024

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> a[200010];
int dep[200010];
void dfs(int now,int fa) {
    dep[now]=0;
    for(int v:a[now])
        if(v!=fa) dfs(v,now),dep[now]=max(dep[now],dep[v]+1);
}
const int mod=1e9+7;
int ksm(int a,int b,int res=1) {
    for(;b;a=a*a%mod,b>>=1)
        if(b&1) res=res*a%mod;
    return res;
}
signed main() {
    int t;
    cin>>t;
    while(t--) {
        int n,ans=0;
        cin>>n;
        for(int i=1;i<=n;i++) a[i].clear();
        for(int i=1;i<n;i++) {
            int u,v;
            cin>>u>>v;
            a[u].push_back(v);
            a[v].push_back(u);
        }
        dfs(1,0);
        int all=ksm(2,n-1);
        for(int i=1;i<=n;i++)
            (ans+=all*(dep[i]+1)%mod)%=mod;
        cout<<ans<<endl;
    }
    return 0;
}

CF1777E. Edge Reverse

题目传送门

题意：有一张简单有向图，边有边权，你可以反转若干条边，代价为这些边的权值 $\max$ 。问使原图存在源点的最小代价（即存在一个点能到达所有点）。

这里权值的定义非常奇怪，为权值 $\max$ ，也就意味着如果一条边被反转，权值比他小的边都可以任意反转而不增加代价。考虑二分答案，二分钦定只能反转权值前 $k$ 小的边，是否能达到效果。对于判定，仔细想一下可以发现，只需要将前 $k$ 小的边改为无向边即可。然后考虑原图存在源点。显然一个强连通分量可以缩点，缩成一个 DAG 后从入度为 $0$ 的点开始 DFS 即可。

By cxm1024

#include<bits/stdc++.h>
using namespace std;
//#define int long long
void chkmax(int &a,int b) {a=a>b?a:b;}
void chkmin(int &a,int b) {a=a<b?a:b;}
int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) f=(ch=='-'?-1:f),ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,m;
struct edge {
    int u,v,w;
} e[200010];
vector<int> a[200010];
int dfn[200010],low[200010],col[200010],colcnt,cnt;
bool ins[200010],vis[200010];
stack<int> st;
void tarjan(int now) {
    low[now]=dfn[now]=++cnt,st.push(now),ins[now]=1;
    for(int v:a[now]) {
        if(!dfn[v]) tarjan(v),chkmin(low[now],low[v]);
        else if(ins[v]) chkmin(low[now],dfn[v]);
    }
    if(low[now]==dfn[now]) {
        ++colcnt;
        while(st.top()!=now)
            col[st.top()]=colcnt,ins[st.top()]=0,st.pop();
        col[st.top()]=colcnt,ins[st.top()]=0,st.pop();
    }
}
vector<int> tr[200010];
bool hav[200010];
void dfs(int now) {
    if(hav[now]) return;
    hav[now]=1;
    for(int v:tr[now]) dfs(v);
}
bool check(int x) {
    for(int i=1;i<=n;i++)
        dfn[i]=low[i]=col[i]=ins[i]=vis[i]=hav[i]=0;
    colcnt=cnt=0;
    for(int i=1;i<=n;i++)
        a[i].clear(),tr[i].clear();
    for(int i=1;i<=x;i++) {
        a[e[i].u].push_back(e[i].v);
        a[e[i].v].push_back(e[i].u);
    }
    for(int i=x+1;i<=m;i++)
        a[e[i].u].push_back(e[i].v);
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=m;i++) {
        if(col[e[i].u]==col[e[i].v]) continue;
        tr[col[e[i].u]].push_back(col[e[i].v]),vis[col[e[i].v]]=1;
    }
    for(int i=1;i<=colcnt;i++)
        if(!vis[i]) {
            dfs(i);
            for(int j=1;j<=colcnt;j++)
                if(!hav[j]) return 0;
            return 1;
        }
    return 0;
}
signed main() {
    int t=read();
    while(t--) {
        n=read(),m=read();
        for(int i=1;i<=m;i++)
            e[i].u=read(),e[i].v=read(),e[i].w=read();
        sort(e+1,e+m+1,[](edge x,edge y) {
            return x.w<y.w;
        });
        int l=0,r=m+1;
        while(l<r) {
            int mid=(l+r)/2;
            if(check(mid)) r=mid;
            else l=mid+1;
        }
        if(l>m) cout<<-1<<endl;
        else cout<<e[l].w<<endl;
    }
    return 0;
}

二分同样可以对边权二分，钦定只反转边权在某值一下的边。代码实现相对简单。

By jiangly

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::vector<int> u(m), v(m), w(m);
    for (int i = 0; i < m; i++) {
        std::cin >> u[i] >> v[i] >> w[i];
        u[i]--, v[i]--;
    }

    auto check = [&](int x) {
        std::vector<std::vector<int>> adj(n);
        for (int i = 0; i < m; i++) {
            adj[u[i]].push_back(v[i]);
            if (w[i] <= x) adj[v[i]].push_back(u[i]);
        }

        int cnt = 0, comp = 0;
        std::vector<int> dfn(n, -1), low(n), bel(n, -1), stk;
        auto dfs = [&](auto self, int x) -> void {
            stk.push_back(x);
            dfn[x] = low[x] = cnt++;
            for (auto y : adj[x]) {
                if (dfn[y] == -1) {
                    self(self, y);
                    low[x] = std::min(low[x], low[y]);
                } else if (bel[y] == -1) {
                    low[x] = std::min(low[x], dfn[y]);
                }
            }
            if (dfn[x] == low[x]) {
                int y;
                do {
                    y = stk.back();
                    bel[y] = comp;
                    stk.pop_back();
                } while (y != x);
                comp++;
            }
        };
        for (int i = 0; i < n; i++) {
            if (dfn[i] == -1) {
                dfs(dfs, i);
            }
        }

        std::vector<int> deg(comp);
        for (int i = 0; i < n; i++) {
            for (auto j : adj[i]) {
                if (bel[i] != bel[j]) {
                    deg[bel[j]]++;
                }
            }
        }

        return std::count(deg.begin(), deg.end(), 0) == 1;
    };

    int lo = 0, hi = 1E9 + 1;
    while (lo < hi) {
        int x = (lo + hi) / 2;
        if (check(x)) hi = x;
        else lo = x + 1;
    }

    int ans = lo;
    if (ans > 1E9) ans = -1;
    std::cout << ans << "\n";
}

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

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}