P8819 [CSP-S 2022] 星战
P8819洛谷。
题目描述
在这一轮的星际战争中，我方在宇宙中建立了 nn 个据点，以 mm 个单向虫洞连接。我们把终点为据点 uu 的所有虫洞归为据点 uu 的虫洞。
战火纷飞之中这些虫洞很难长久存在，敌人的打击随时可能到来。这些打击中的有效打击可以分为两类：
- 敌人会摧毁某个虫洞，这会使它连接的两个据点无法再通过这个虫洞直接到达，但这样的打击无法摧毁它连接的两个据点。
- 敌人会摧毁某个据点，由于虫洞的主要技术集中在出口处，这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则不会摧毁。
注意：摧毁只会导致虫洞不可用，而不会消除它的存在。
为了抗击敌人并维护各部队和各据点之间的联系，我方发展出了两种特种部队负责修复虫洞：
- A 型特种部队则可以将某个特定的虫洞修复。
- B 型特种部队可以将某据点的所有损坏的虫洞修复。
考虑到敌人打击的特点，我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复，处于可用状态，那么这个据点也是可用的。
我方掌握了一种苛刻的空间特性，利用这一特性我方战舰可以沿着虫洞瞬移到敌方阵营，实现精确打击。
为了把握发动反攻的最佳时机，指挥部必须关注战场上的所有变化，为了寻找一个能够进行反攻的时刻。总指挥认为：
- 如果从我方的任何据点出发，在选择了合适的路线的前提下，可以进行无限次的虫洞穿梭（可以多次经过同一据点或同一虫洞），那么这个据点就可以实现反击。
- 为了使虫洞穿梭的过程连续，尽量减少战舰在据点切换虫洞时的质能损耗，当且仅当只有一个从该据点出发的虫洞可用时，这个据点可以实现连续穿梭。
- 如果我方所有据点都可以实现反击，也都可以实现连续穿梭，那么这个时刻就是一个绝佳的反攻时刻。
总司令为你下达命令，要求你根据战场上实时反馈的信息，迅速告诉他当前的时刻是否能够进行一次反攻。
输入格式
输入的第一行包含两个正整数 n,mn,m。
接下来 mm 行每行两个数 u,vu,v，表示一个从据点 uu 出发到据点 vv 的虫洞。保证 u \ne vu=v，保证不会有两条相同的虫洞。初始时所有的虫洞和据点都是完好的。
接下来一行一个正整数 qq 表示询问个数。
接下来 qq 行每行表示一次询问或操作。首先读入一个正整数 tt 表示指令类型：
- 若 t = 1t=1，接下来两个整数 u, vu,v 表示敌人摧毁了从据点 uu 出发到据点 vv 的虫洞。保证该虫洞存在且未被摧毁。
- 若 t = 2t=2，接下来一个整数 uu 表示敌人摧毁了据点 uu。如果该据点的虫洞已全部 被摧毁，那么这次袭击不会有任何效果。
- 若 t = 3t=3，接下来两个整数 u, vu,v 表示我方修复了从据点 uu 出发到据点 vv 的虫洞。保证该虫洞存在且被摧毁。
- 若 t = 4t=4，接下来一个整数 uu 表示我方修复了据点 uu。如果该据点没有被摧毁的虫洞，那么这次修复不会有任何效果。
在每次指令执行之后，你需要判断能否进行一次反攻。如果能则输出 YES 否则输出 NO。
输出格式
输出一共 qq 行。对于每个指令，输出这个指令执行后能否进行反攻。
60 分的部分分
暴力太简单不讲。
首先我们分析条件 \tt22，发现这应该是一棵内向基环树。
而内向基环树是一个环上挂着若干棵儿子向父亲连有向边的树，每个点可以先沿着有向边走上环，然后在环上无限走。所以必然满足条件 \tt11。
那么最后只需要判断条件 \tt22 即可。
我们维护一个出度数组。发现操作 \tt11 和 \tt33 对出度数组的改变都是 O(1)O(1) 的。于是暴力模拟出度数组的变化并动态维护出度为 11 的点的个数，拿到 \tt50pts50pts。
然后发现如果只有操作 \tt22，qq 次操作一共只会最多删掉 O(m)O(m) 条边，对出度数组产生最多 O(m)O(m) 的改变。所以同上，结合均摊分析，拿到 \tt60pts60pts。
虽然笔者的思考止步于此，但是我拿的分可不止 \tt60pts60pts。
于是靠着官方数据用脚造以及官方少爷机的神速，\tt85pts85pts 翻身了。
。
正解
对条件 \texttt{1,2}1,2 的分析还是同上。但 \texttt{2,4}2,4 操作并不是暴力模拟。
我们对每个点定义一个权值，它是一个随机数。
然后对于每一个点 vv，记录 a_v=\sum w_u[\text{exist }\texttt{edge}\{u\to v\}]av=∑wu[exist edge{u→v}]。
然后操作 \texttt{1,3}1,3 就让 a_vav 减去或加上 w_uwu。
操作 \texttt{2,4}2,4 记录原来的 aa 数组 a^\primea′，然后让 a_u\gets0au←0 或者 a_u\gets a^\prime_uau←au′。
在更改的过程中动态维护 \sum a_u∑au 的值。
如果 \sum a_u=\sum w_u∑au=∑wu，那么每个点只有一个出边。
代码
#include
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;
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！