Yurchiu's Blog

P8819 [CSP-S 2022] 星战

Yurchiu 2022-12-24, 14:16:56 2.9k 隐藏左右两栏 展示左右两栏

注:上一次写题解是 2022-03-26,那是退役前的最后一篇题解。

虽然我已经退役了,但是我还是要把这个神奇的题搞一搞!

CCF 用以造数据的脚恐怖如斯,如同加工老坛酸菜。

题意

在这一轮的星际战争中,我方在宇宙中建立了 nn 个据点,以 mm 个单向虫洞连接。我们把终点为据点 uu 的所有虫洞归为据点 uu 的虫洞。

战火纷飞之中这些虫洞很难长久存在,敌人的打击随时可能到来。这些打击中的有效打击可以分为两类:

  1. 敌人会摧毁某个虫洞,这会使它连接的两个据点无法再通过这个虫洞直接到达,但这样的打击无法摧毁它连接的两个据点。
  2. 敌人会摧毁某个据点,由于虫洞的主要技术集中在出口处,这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则不会摧毁

注意:摧毁只会导致虫洞不可用,而不会消除它的存在。

为了抗击敌人并维护各部队和各据点之间的联系,我方发展出了两种特种部队负责修复虫洞:

  • A 型特种部队则可以将某个特定的虫洞修复。
  • B 型特种部队可以将某据点的所有损坏的虫洞修复。

考虑到敌人打击的特点,我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复,处于可用状态,那么这个据点也是可用的。

我方掌握了一种苛刻的空间特性,利用这一特性我方战舰可以沿着虫洞瞬移到敌方阵营,实现精确打击。

为了把握发动反攻的最佳时机,指挥部必须关注战场上的所有变化,为了寻找一个能够进行反攻的时刻。总指挥认为:

  • 如果从我方的任何据点出发,在选择了合适的路线的前提下,可以进行无限次的虫洞穿梭(可以多次经过同一据点或同一虫洞),那么这个据点就可以实现反击
  • 为了使虫洞穿梭的过程连续,尽量减少战舰在据点切换虫洞时的质能损耗,当且仅当只有一个从该据点出发的虫洞可用时,这个据点可以实现连续穿梭
  • 如果我方所有据点都可以实现反击,也都可以实现连续穿梭,那么这个时刻就是一个绝佳的反攻时刻。

总司令为你下达命令,要求你根据战场上实时反馈的信息,迅速告诉他当前的时刻是否能够进行一次反攻

点击查看简略题面

给定 nn 个点 mm 条边的有向图,以及四种操作,共 qq 条:

  1. 删除某条边;
  2. 删除以某个点为终点的所有边;
  3. 恢复某条边;
  4. 恢复以某个点为终点的所有边。

”恢复“指恢复原先删过的边,初始时就不存在的边当然不会恢复。

每次操作后,询问是否满足所有的点出度均为 11

是不是很简略?

对于所有数据保证:1n5×1051 \le n \le 5 \times {10}^51m5×1051 \le m \le 5 \times {10}^51q5×1051 \le q \le 5 \times {10}^5

点击查看题解

题解

45 pts

不可以,总司令。

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	ll n,m,q,u,v;
	void main()
	{
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=m;i++) scanf("%lld%lld",&u,&v);
		scanf("%lld",&q);
		for(ll i=1;i<=q;i++) printf("NO\n");
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}

真的是部分分

最暴力的做法,对于每次 O(n)O(n) 的修改后,O(n)O(n) 扫一遍看是不是所有点出度都是 11O(n2)O(n^2) 枚举所有点判环。

稍微思考之后,即可发现无需判环,因为第一个条件满足后,图即为基环内向树森林。非常详细地充满废话地证明一下:

先讨论图为连通图的情况。所有点出度都是 11,也就是一定有 nn 条边(nn 为点数)。考虑先分配 n1n-1 条无向边,这样形成的是一棵树。给边加方向,由于出度都是 11,所以只允许“多指向一”的结构。这样,必定剩下根的出度是零。再给根分配余下的一条有向边,无论这条边指向的是哪个点,一定形成了一个环。由于第一次分配确保所有点都可以到达根,保证了所有点一定能到达环,所以形成的图必定是一棵基环内向树。

如果图不连通,则必由连通子图组成。由于所有点出度都是 11,所以子图中有多少点就有多少边。故亦可按照上面的逻辑证明。

这样呢,由于免去了判环,我们就有了 O(n2)O(n^2) 的做法。

100 pts

旧版题解收折

旧版题解表述不清。

实际上,按照原题面,要让总司令可以的条件有两个:

  • 所有的点出度均为 11
  • 从任意一个点出发,可以走到一个环中。

但是,第一个条件可以推出第二个条件。证明:

所有点出度均为 11 意味着图必是一个基环内向树森林,所以从任意一个点出发肯定会走到一个环。

从另一方面证明,所有点出度均为 11 意味着你从任意一个点出发,存在一条路径,经过了至少 nn 条边。那么路径中必然就存在重复经过的点了。

所以第二个条件是坑人的!根本不需要判环!我们只需判断何时所有的点出度均为 11


首先想到直接按题意模拟,记录每个点出度个数。删掉一条边,前驱点出度减一。这样,操作 2 和 4 时间复杂度 O(n)O(n)。暴力判断,复杂度也是 O(n)O(n),这样得到 O(qn)O(qn) 的算法。

发现维护入度可以做到 O(1)O(1) 维护,而可以同时维护所有点的出度之和(入度和=出度和)。

显然,所有的点出度均为 11 可以推出出度和是 nn,但是不能反推。

怎么办?哈希!

对每一个点随机一个权值。定义 f(u)f(u) 为结点 uu 的前驱点权之和。f(u)f(u) 是可以被非常容易地维护的。另外定义变量 sumsum 为所有节点的前驱点权之和,也就是 f(u)\sum f(u)

显然,所有的点出度均为 11 时,sumsum 的值就等于所有点的点权之和。但是不能反推。

怎么就显然了???

此时,对于任意一个结点 uu,有且只有一个结点 vv,满足有向边 <u,v><u,v> 存在。这样,uu 的点权会且只会贡献一次,贡献给 f(v)f(v)。这样,sumsum 的值自然就等于所有点的点权之和了。

虽然不能反推,但是当 sumsum 的值等于所有点的点权之和时,很大概率满足所有的点出度均为 11。如果不放心,可以写多重哈希。

这样,这道题就解决了。


我们不想每次操作完之后,都要进行一遍线性复杂度的判断。我们不想让维护操作的复杂度为线性。达到这两个目标之后,就会有线性的正解做法了。

一个自然的想法是,我们能不能记录出度和呢?所有点的出度都是 11,可以推出出度和为 11;但是反过来不一定对。但是,我们可以碰碰运气试一试。

记录出度和,就是记录有多少边。考虑所有点的出度不易维护,而入度很好维护,可以维护所有点的入度,进而维护边数。具体地,维护一个存储所有点目前入度的数组 a[],以及一个变量 cnt,记录全局边数。对于边的操作,直接改就行;对于点的操作,删点就是对应的 a[i] 置为零,恢复点的操作就是让对应地的 a[i] 置为初始值。进行这些操作的同时,cnt 也可以一并维护。每次操作维护之后,判断 cnt 是不是等于 n。这样,时间复杂度就是线性的。

但是这样做,准确率太低了!怎么办?提高准确率!怎么提高?用哈希!

完了。这样你就可以 AC 了。

怎么哈?考虑到根据边数,显然无法判断这些边是不是有的是同一个点发出的。如何解决?给每一条边都赋予一个哈希值,使得同一个点发出的边的哈希值相等(实现时,是直接给点赋哈希值)。把上面数组、变量的意义都由原来的和改为哈希值和。每次操作维护之后,判断 cnt 是不是等于所有点的哈希值和。如果等于,那么表明什么呢?那就表明 cnt 大概率是 n 条由 n 个互不相同的点发出的边的哈希值和。那不就是表示这 n 个点的出度都是一嘛。

这样,这道题就做完了。本题是一个阅读理解+套路题,首先需要提炼信息;然后,给点赋哈希值的 trick,是我所从来没碰到过的,也是没有想出过的。所以此题虽然数据极水,价值还是有的。


代码实现非常容易。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=500000+10;
	ll n,m,q,a[N],in[N],tmp[N],jud=0,now=0;
	mt19937 rnd(time(0));
	ll rand(){return rnd()%N;}
	void main()
	{
		ll u,v,t;
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=n;i++)
		{
			a[i]=rand();
			jud+=a[i];
		}
		for(ll i=1;i<=m;i++)
		{
			scanf("%lld%lld",&u,&v);
			in[v]+=a[u]; tmp[v]+=a[u];
			now+=a[u];
		}
		scanf("%lld",&q);
		for(ll i=1;i<=q;i++)
		{
			scanf("%lld",&t);
			if(t==1)
			{
				scanf("%lld%lld",&u,&v);
				now-=a[u]; tmp[v]-=a[u];
			}
			else if(t==2)
			{
				scanf("%lld",&u);
				now-=tmp[u]; tmp[u]=0;
			}
			else if(t==3)
			{
				scanf("%lld%lld",&u,&v);
				now+=a[u]; tmp[v]+=a[u];
			}
			else
			{
				scanf("%lld",&u);
				now+=in[u]-tmp[u]; tmp[u]=in[u];
			}
			if(jud==now) printf("YES\n");
			else printf("NO\n");
		}
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}
点击查看简略代码

本段代码来自于:https://www.luogu.com.cn/record/94328325

#import<iostream>
#define t std::cin>>n
int n,m,r[1<<20],w[1<<20],s,k;main(){for(t>>m,s=n*=n+3;m--;w[k]=r[k]+=++n,s-=n*2)t>>k;for(t;t>>k;s+=m*2,w[n]-=m,puts(s?"NO":"YES"))m=n&1?++k*=2-n,t,k:w[k]-n/4*r[n=k];}




本文作者:Yurchiu

本文链接:https://yz-hs.github.io/0828a0ba2790/

版权声明:本博客中所有原创文章除特别声明外,均允许规范转载,转载请注明出处。所有非原创文章,按照原作者要求转载。


By Yurchiu.
其他物件杂物收纳
Hitokoto

Yurchiu 说,除了她以外的人都很强!嘤嘤嘤~~
博客信息
文章数目
158
最近更新
08-21
本站字数
350.6k
文章目录