P8819 CSP 2022 S T3 星战

· · 题解

\tt Link。

简要题意

有一个 n 个点 m 条有向边的图，每条边有可用和不可用两个状态。有 q 个操作：

每次操作之后，如果同时满足

就输出 YES，否则输出 NO。

60 分的部分分

暴力太简单不讲。

首先我们分析条件 \tt2，发现这应该是一棵内向基环树。

而内向基环树是一个环上挂着若干棵儿子向父亲连有向边的树，每个点可以先沿着有向边走上环，然后在环上无限走。所以必然满足条件 \tt1。

那么最后只需要判断条件 \tt2 即可。

我们维护一个出度数组。发现操作 \tt1 和 \tt3 对出度数组的改变都是 O(1) 的。于是暴力模拟出度数组的变化并动态维护出度为 1 的点的个数，拿到 \tt50pts。

然后发现如果只有操作 \tt2，q 次操作一共只会最多删掉 O(m) 条边，对出度数组产生最多 O(m) 的改变。所以同上，结合均摊分析，拿到 \tt60pts。

虽然笔者的思考止步于此，但是我拿的分可不止 \tt60pts。

于是靠着官方数据用脚造以及官方少爷机的神速，\tt85pts 翻身了。

评测链接。

正解

对条件 \texttt{1,2} 的分析还是同上。但 \texttt{2,4} 操作并不是暴力模拟。

我们对每个点定义一个权值，它是一个随机数。

然后对于每一个点 v，记录 a_v=\sum w_u[\text{exist }\texttt{edge}\{u\to v\}]。

然后操作 \texttt{1,3} 就让 a_v 减去或加上 w_u。

操作 \texttt{2,4} 记录原来的 a 数组 a^\prime，然后让 a_u\gets0 或者 a_u\gets a^\prime_u。

在更改的过程中动态维护 \sum a_u 的值。

如果 \sum a_u=\sum w_u，那么每个点只有一个出边。

总结

用到了哈希的思想，正解写起来比 \tt60pts 代码还短。

哈希思维难度大于部分分？但是想下来其实挺简单的。果然自己的思维还是有不足之处。

代码

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

const int N = 5e5 + 5;

int n,m,q,a[N];
long long to[N],sum[N],tot,ans;

int main(){
    mt19937 rnd(time(0));
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i) ans += (a[i] = rnd());
    for(int i = 1,u,v;i <= m;++i)
        scanf("%d%d",&u,&v),to[v] += a[u],sum[v] = to[v],tot += a[u];
    scanf("%d",&q);
    for(int i = 1,t,u,v;i <= q;++i){
        scanf("%d%d",&t,&u);
        if(t == 1) scanf("%d",&v),to[v] -= a[u],tot -= a[u];
        if(t == 2) tot -= to[u],to[u] = 0;
        if(t == 3) scanf("%d",&v),to[v] += a[u],tot += a[u];
        if(t == 4) tot += sum[u] - to[u],to[u] = sum[u];
        puts(tot == ans ? "YES" : "NO");
    }
    return 0;
}