注:上一次写题解是 2022-03-26,那是退役前的最后一篇题解。
虽然我已经退役了,但是我还是要把这个神奇的题搞一搞!
CCF 用以造数据的脚恐怖如斯,如同加工老坛酸菜。
题意
在这一轮的星际战争中,我方在宇宙中建立了 个据点,以 个单向虫洞连接。我们把终点为据点 的所有虫洞归为据点 的虫洞。
战火纷飞之中这些虫洞很难长久存在,敌人的打击随时可能到来。这些打击中的有效打击可以分为两类:
- 敌人会摧毁某个虫洞,这会使它连接的两个据点无法再通过这个虫洞直接到达,但这样的打击无法摧毁它连接的两个据点。
- 敌人会摧毁某个据点,由于虫洞的主要技术集中在出口处,这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则不会摧毁。
注意:摧毁只会导致虫洞不可用,而不会消除它的存在。
为了抗击敌人并维护各部队和各据点之间的联系,我方发展出了两种特种部队负责修复虫洞:
- A 型特种部队则可以将某个特定的虫洞修复。
- B 型特种部队可以将某据点的所有损坏的虫洞修复。
考虑到敌人打击的特点,我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复,处于可用状态,那么这个据点也是可用的。
我方掌握了一种苛刻的空间特性,利用这一特性我方战舰可以沿着虫洞瞬移到敌方阵营,实现精确打击。
为了把握发动反攻的最佳时机,指挥部必须关注战场上的所有变化,为了寻找一个能够进行反攻的时刻。总指挥认为:
- 如果从我方的任何据点出发,在选择了合适的路线的前提下,可以进行无限次的虫洞穿梭(可以多次经过同一据点或同一虫洞),那么这个据点就可以实现反击。
- 为了使虫洞穿梭的过程连续,尽量减少战舰在据点切换虫洞时的质能损耗,当且仅当只有一个从该据点出发的虫洞可用时,这个据点可以实现连续穿梭。
- 如果我方所有据点都可以实现反击,也都可以实现连续穿梭,那么这个时刻就是一个绝佳的反攻时刻。
总司令为你下达命令,要求你根据战场上实时反馈的信息,迅速告诉他当前的时刻是否能够进行一次反攻。
点击查看简略题面
给定 个点 条边的有向图,以及四种操作,共 条:
- 删除某条边;
- 删除以某个点为终点的所有边;
- 恢复某条边;
- 恢复以某个点为终点的所有边。
”恢复“指恢复原先删过的边,初始时就不存在的边当然不会恢复。
每次操作后,询问是否满足所有的点出度均为 。
是不是很简略?
对于所有数据保证:,,。
点击查看题解
题解
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;
}
真的是部分分
最暴力的做法,对于每次 的修改后, 扫一遍看是不是所有点出度都是 , 枚举所有点判环。
稍微思考之后,即可发现无需判环,因为第一个条件满足后,图即为基环内向树森林。非常详细地充满废话地证明一下:
先讨论图为连通图的情况。所有点出度都是 ,也就是一定有 条边( 为点数)。考虑先分配 条无向边,这样形成的是一棵树。给边加方向,由于出度都是 ,所以只允许“多指向一”的结构。这样,必定剩下根的出度是零。再给根分配余下的一条有向边,无论这条边指向的是哪个点,一定形成了一个环。由于第一次分配确保所有点都可以到达根,保证了所有点一定能到达环,所以形成的图必定是一棵基环内向树。
如果图不连通,则必由连通子图组成。由于所有点出度都是 ,所以子图中有多少点就有多少边。故亦可按照上面的逻辑证明。
这样呢,由于免去了判环,我们就有了 的做法。
100 pts
旧版题解收折
旧版题解表述不清。
实际上,按照原题面,要让总司令可以的条件有两个:
- 所有的点出度均为 。
- 从任意一个点出发,可以走到一个环中。
但是,第一个条件可以推出第二个条件。证明:
所有点出度均为 意味着图必是一个基环内向树森林,所以从任意一个点出发肯定会走到一个环。
从另一方面证明,所有点出度均为 意味着你从任意一个点出发,存在一条路径,经过了至少 条边。那么路径中必然就存在重复经过的点了。
所以第二个条件是坑人的!根本不需要判环!我们只需判断何时所有的点出度均为 。
首先想到直接按题意模拟,记录每个点出度个数。删掉一条边,前驱点出度减一。这样,操作 2 和 4 时间复杂度 。暴力判断,复杂度也是 ,这样得到 的算法。
发现维护入度可以做到 维护,而可以同时维护所有点的出度之和(入度和=出度和)。
显然,所有的点出度均为 可以推出出度和是 ,但是不能反推。
怎么办?哈希!
对每一个点随机一个权值。定义 为结点 的前驱点权之和。 是可以被非常容易地维护的。另外定义变量 为所有节点的前驱点权之和,也就是 。
显然,所有的点出度均为 时, 的值就等于所有点的点权之和。但是不能反推。
怎么就显然了???
此时,对于任意一个结点 ,有且只有一个结点 ,满足有向边 存在。这样, 的点权会且只会贡献一次,贡献给 。这样, 的值自然就等于所有点的点权之和了。
虽然不能反推,但是当 的值等于所有点的点权之和时,很大概率满足所有的点出度均为 。如果不放心,可以写多重哈希。
这样,这道题就解决了。
我们不想每次操作完之后,都要进行一遍线性复杂度的判断。我们不想让维护操作的复杂度为线性。达到这两个目标之后,就会有线性的正解做法了。
一个自然的想法是,我们能不能记录出度和呢?所有点的出度都是 ,可以推出出度和为 ;但是反过来不一定对。但是,我们可以碰碰运气试一试。
记录出度和,就是记录有多少边。考虑所有点的出度不易维护,而入度很好维护,可以维护所有点的入度,进而维护边数。具体地,维护一个存储所有点目前入度的数组 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/
版权声明:本博客中所有原创文章除特别声明外,均允许规范转载,转载请注明出处。所有非原创文章,按照原作者要求转载。