T1假期计划

[CSP-S 2022] 假期计划

题目描述

小熊的地图上有 \(n\) 个点，其中编号为 \(1\) 的是它的家、编号为 \(2, 3, \ldots, n\) 的都是景点。部分点对之间有双向直达的公交线路。如果点 \(x\) 与 \(z_1\)、\(z_1\) 与 \(z_2\)、……、\(z_{k - 1}\) 与 \(z_k\)、\(z_k\) 与 \(y\) 之间均有直达的线路，那么我们称 \(x\) 与 \(y\) 之间的行程可转车 \(k\) 次通达；特别地，如果点 \(x\) 与 \(y\) 之间有直达的线路，则称可转车 \(0\) 次通达。

很快就要放假了，小熊计划从家出发去 \(4\) 个不同的景点游玩，完成 \(5\) 段行程后回家：家 \(\to\) 景点 A \(\to\) 景点 B \(\to\) 景点 C \(\to\) 景点 D \(\to\) 家且每段行程最多转车 \(k\) 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点 A \(\to\) 景点 B 的这段行程中，转车时经过的点可以是家、也可以是景点 C，还可以是景点 D \(\to\) 家这段行程转车时经过的点。

假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。

输入格式

第一行包含三个正整数 \(n, m, k\)，分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。

第二行包含 \(n - 1\) 个正整数，分别表示编号为 \(2, 3, \ldots, n\) 的景点的分数。

接下来 \(m\) 行，每行包含两个正整数 \(x, y\)，表示点 \(x\) 和 \(y\) 之间有道路直接相连，保证 \(1 \le x, y \le n\)，且没有重边，自环。

输出格式

输出一个正整数，表示小熊经过的 \(4\) 个不同景点的分数之和的最大值。

样例 #1

样例输入 #1

8 8 1
9 7 1 8 2 3 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1

样例输出 #1

27

样例 #2

样例输入 #2

7 9 0
1 1 1 2 3 4
1 2
2 3
3 4
1 5
1 6
1 7
5 4
6 4
7 4

样例输出 #2

7

提示

【样例解释 #1】

当计划的行程为 \(1 \to 2 \to 3 \to 5 \to 7 \to 1\) 时，\(4\) 个景点的分数之和为 \(9 + 7 + 8 + 3 = 27\)，可以证明其为最大值。

行程 \(1 \to 3 \to 5 \to 7 \to 8 \to 1\) 的景点分数之和为 \(24\)、行程 \(1 \to 3 \to 2 \to 8 \to 7 \to 1\) 的景点分数之和为 \(25\)。它们都符合要求，但分数之和不是最大的。

行程 \(1 \to 2 \to 3 \to 5 \to 8 \to 1\) 的景点分数之和为 \(30\)，但其中 \(5 \to 8\) 至少需要转车 \(2\) 次，因此不符合最多转车 \(k = 1\) 次的要求。

行程 \(1 \to 2 \to 3 \to 2 \to 3 \to 1\) 的景点分数之和为 \(32\)，但游玩的并非 \(4\) 个不同的景点，因此也不符合要求。

【样例 #3】

见附件中的 holiday/holiday3.in 与 holiday/holiday3.ans。

【数据范围】

对于所有数据，保证 \(5 \le n \le 2500\)，\(1 \le m \le 10000\)，\(0 \le k \le 100\)，所有景点的分数 \(1 \le s_i \le {10}^{18}\)。保证至少存在一组符合要求的行程。

解析

【算法1】首先需要预处理出任意点对之间的距离，显然很容易想到Floyd算法，并能以O(n^3)的算法复杂度预处理出任意点对之间的距离，然后即可用dfs暴力更新出所有可能的路径。算法复杂度O(n!)，预计得分25分，实际得分60分，参考代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=2555;
typedef long long ll;
int n,m,k;
int a[N][N],b[N],d[N][N],vis[N],c[N]; 
ll ans;
void dfs(int u,int pre,ll sum)
{

//	printf("u=%d,pre=%d\n",u,pre);
	if(u==5)
	{
		
		if(a[pre][1]>k+1) return ;
		if(ans<sum)
		{
			ans=sum;
//			for(int i=1;i<=4;i++) cout<<c[i]<<" ";cout<<endl;
		}
		return ;
	}
	for(int i=2;i<=n;i++)
	{
		if(vis[i]) continue;
		if(a[pre][i]<=k+1)
		{
			vis[i]=1;
			c[u]=i;
			dfs(u+1,i,sum+b[i]);
			vis[i]=0;
		}
	}
}
int main()
{
	memset(a,0x3f,sizeof(a));
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++) cin>>b[i];
	for(int i=1;i<=n;i++) a[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		a[x][y]=a[y][x]=1;
	}
	for(int kk=1;kk<=n;kk++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				a[i][j]=min(a[i][j],a[i][kk]+a[kk][j]);
	dfs(1,1,0);
	cout<<ans<<endl;
	return 0;	
} 

【算法2】考虑优化预处理任意点对之间的距离，由于是无向图，完全可以暴力枚举起点，然后对这个起点跑一遍bfs预处理出任何一个点到当前点的距离，显然这样做的复杂度是O(n*(n+m))。由于题目固定是经过4个景点，所以直接暴力枚举这4个中间点即可，算法复杂度O(n^4)，预计得分70分，实际得分60分。

#include<bits/stdc++.h>
using namespace std;
const int N=2505;
int n,m,k;
int d[N][N];
long long a[N];
vector<int>g[N]; 
void bfs(int s)
{
	queue<pair<int,int> >q;
	q.push(make_pair(s,-1));
	int vis[N]={0};
	vis[s]=1;
	d[s][s]=-1;
	while(q.size())
	{
		int u=q.front().first;q.pop();
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i];
			if(vis[v]) continue;
			d[s][v]=d[s][u]+1;
			vis[v]=1;
			q.push(make_pair(v,d[s][v]));
		}
	}
}
int main()
{
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++) cin>>a[i];
	memset(d,0x3f,sizeof(d));
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;i++) bfs(i);
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=n;j++)
//			printf("d[%d][%d]=%d ",i,j,d[i][j]);
//		printf("\n");
//	}
	int vis[N]={0};
	long long ans=0;
	for(int v1=2;v1<=n;v1++)
	{
		if(d[1][v1]>k) continue;
		vis[v1]=1;
		for(int v2=2;v2<=n;v2++)
		{
			if(d[v1][v2]>k||vis[v2]) continue;
			vis[v2]=1;
			for(int v3=2;v3<=n;v3++)
			{
				if(d[v2][v3]>k||vis[v3]) continue;
				vis[v3]=1;
				for(int v4=2;v4<=n;v4++)
				{
					if(d[v3][v4]>k||d[v4][1]||vis[v4]) continue;
					ans=max(ans,a[v1]+a[v2]+a[v3]+a[v4]);
				}
				vis[v3]=0; 
			}
			vis[v2]=0;
		}
		vis[v1]=0;
	}
	cout<<ans<<endl;
	return 0;	
}

在这里学习一中避免TLE的方法。由于这里是最优化问题，在更新的过程中有一定的概率已经更新出了最优解，所以在快超时的时候，与其让它超时，还不如直接输出当前答案。
代码中值得一提的是使用了CLOCKS_PER_SEC这个常量，含义是1秒。代码clock()-start<2*CLOCKS_PER_SEC*0.95的含义是当前时间减去程序开始的时间小于时限的95%的意思。参考代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=2505;
int n,m,k;
int d[N][N];
long long a[N];
vector<int>g[N]; 
double start=clock();
int check()
{
	return clock()-start<2*CLOCKS_PER_SEC*0.95;
}
void bfs(int s)
{
	queue<pair<int,int> >q;
	q.push(make_pair(s,-1));
	int vis[N]={0};
	vis[s]=1;
	d[s][s]=-1;
	while(q.size())
	{
		int u=q.front().first;q.pop();
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i];
			if(vis[v]) continue;
			d[s][v]=d[s][u]+1;
			vis[v]=1;
			q.push(make_pair(v,d[s][v]));
		}
	}
}
int main()
{
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++) cin>>a[i];
	memset(d,0x3f,sizeof(d));
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;i++) bfs(i);
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=n;j++)
//			printf("d[%d][%d]=%d ",i,j,d[i][j]);
//		printf("\n");
//	}
	int vis[N]={0};
	long long ans=0;
	for(int v1=2;v1<=n;v1++)
	{
		if(!check()) break;
		if(d[1][v1]>k) continue;
		vis[v1]=1;
		for(int v2=2;v2<=n;v2++)
		{
			if(!check()) break;
			if(d[v1][v2]>k||vis[v2]) continue;
			vis[v2]=1;
			for(int v3=2;v3<=n;v3++)
			{
				if(!check()) break;
				if(d[v2][v3]>k||vis[v3]) continue;
				vis[v3]=1;
				for(int v4=2;v4<=n;v4++)
				{
					if(!check()) break;
					if(d[v3][v4]>k||d[v4][1]||vis[v4]) continue;
					ans=max(ans,a[v1]+a[v2]+a[v3]+a[v4]);
				}
				vis[v3]=0; 
			}
			vis[v2]=0;
		}
		vis[v1]=0;
	}
	cout<<ans<<endl;
	return 0;	
}

【正解】预处理的时间复杂度显然已经满足题目数据量要求了，接下来考虑优化直接暴力枚举4个景点的部分。不难想到，4个景点可以折半搜索。具体怎么做呢？对于1->a->b->c->d->1。可以先暴力枚举出1能到达的任意两个景点(a,b)以及1->a->b的路径最短长度。接下来可以发现1->d->c也可以跟前面一样处理，但是有可能会出现d=a,c=b的这种非法情况。稍微思考一下就可以发现，我们只要保存1能到达的任意两个景点(a,b)以及1->a->b的路径前3短的长度及其对应的顶点就绝对能找出4个景点不同的1->a->b->c->d->1路线。这样我们就先以O(n^{2)的算法复杂度预处理出前半段，再以O(n}2)的复杂度匹配后半段即可。总算法复杂度O(n*(n+m)+n^2)代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=2555;
typedef long long ll;
int n,m,k;
ll a[N];
int d[N][N];
pair<ll,int>Max[N][3];
vector<int>g[N];
void bfs(int s)
{
	queue<pair<int,int> >q;
	q.push(make_pair(s,-1));
	int vis[N]={0};
	d[s][s]=-1;
	vis[s]=1;
	while(q.size())
	{
		int u=q.front().first;q.pop();
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i];
			if(vis[v]==0)
			{
				vis[v]=1;
				d[s][v]=d[s][u]+1;
				q.push(make_pair(v,d[s][v]));
			}
		}
	}
}
int main()
{
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	memset(d,0x3f,sizeof(d));
	for(int i=1;i<=n;i++) bfs(i);
//	for(int i=1;i<=n;i++)
//		for(int j=1;j<=n;j++) printf("%d%c",d[i][j],j==n?'\n':' ');
	for(int i=2;i<=n;i++)
	{
		if(d[1][i]>k) continue;
		for(int j=2;j<=n;j++)
		{
			if(d[i][j]>k||i==j) continue;
			if(a[i]+a[j]>Max[j][0].first)
			{
				Max[j][2]=Max[j][1];
				Max[j][1]=Max[j][0];
				Max[j][0]=make_pair(a[i]+a[j],i);
			}
			else if(a[i]+a[j]>Max[j][1].first)
			{
				Max[j][2]=Max[j][1];
				Max[j][1]=make_pair(a[i]+a[j],i);
			}
			else if(a[i]+a[j]>Max[j][2].first)
			{
				Max[j][2]=make_pair(a[i]+a[j],i);
			}
		}
	}
	ll ans=0;
	for(int i=2;i<=n;i++)
	{
		for(int j=2;j<=n;j++)
		{
			if(d[i][j]>k||i==j) continue;
			for(int p=0;p<3;p++)
			{
				for(int q=0;q<3;q++)
				{
					int v1=Max[i][p].second;ll w1=Max[i][p].first;
					int v4=Max[j][q].second;ll w2=Max[j][q].first;
					if(v1!=v4&&v1!=i&&v1!=j&&v4!=i&&v4!=j&&d[v4][1]<=k&&d[v1][1]<=k)
					{
						ans=max(ans,w1+w2);
					}
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;	
} 

T2 策略游戏

[CSP-S 2022] 策略游戏

题目描述

小 L 和小 Q 在玩一个策略游戏。

有一个长度为 \(n\) 的数组 \(A\) 和一个长度为 \(m\) 的数组 \(B\)，在此基础上定义一个大小为 \(n \times m\) 的矩阵 \(C\)，满足 \(C_{i j} = A_i \times B_j\)。所有下标均从 \(1\) 开始。

游戏一共会进行 \(q\) 轮，在每一轮游戏中，会事先给出 \(4\) 个参数 \(l_1, r_1, l_2, r_2\)，满足 \(1 \le l_1 \le r_1 \le n\)、\(1 \le l_2 \le r_2 \le m\)。

游戏中，小 L 先选择一个 \(l_1 \sim r_1\) 之间的下标 \(x\)，然后小 Q 选择一个 \(l_2 \sim r_2\) 之间的下标 \(y\)。定义这一轮游戏中二人的得分是 \(C_{x y}\)。

小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。

请问：按照二人的最优策略，每轮游戏的得分分别是多少？

输入格式

第一行输入三个正整数 \(n, m, q\)，分别表示数组 \(A\)，数组 \(B\) 的长度和游戏轮数。

第二行：\(n\) 个整数，表示 \(A_i\)，分别表示数组 \(A\) 的元素。

第三行：\(m\) 个整数，表示 \(B_i\)，分别表示数组 \(B\) 的元素。

接下来 \(q\) 行，每行四个正整数，表示这一次游戏的 \(l_1, r_1, l_2, r_2\)。

输出格式

输出共 \(q\) 行，每行一个整数，分别表示每一轮游戏中，小 L 和小 Q 在最优策略下的得分。

样例 #1

样例输入 #1

3 2 2
0 1 -2
-3 4
1 3 1 2
2 3 2 2

样例输出 #1

0
4

样例 #2

样例输入 #2

6 4 5
3 -1 -2 1 2 0
1 2 -1 -3
1 6 1 4
1 5 1 4
1 4 1 2
2 6 3 4
2 5 2 3

样例输出 #2

0
-2
3
2
-1

提示

【样例解释 #1】

这组数据中，矩阵 \(C\) 如下：

在第一轮游戏中，无论小 L 选取的是 \(x = 2\) 还是 \(x = 3\)，小 Q 都有办法选择某个 \(y\) 使得最终的得分为负数。因此小 L 选择 \(x = 1\) 是最优的，因为这样得分一定为 \(0\)。

而在第二轮游戏中，由于小 L 可以选 \(x = 2\)，小 Q 只能选 \(y = 2\)，如此得分为 \(4\)。

【样例 #3】

见附件中的 game/game3.in 与 game/game3.ans。

【样例 #4】

见附件中的 game/game4.in 与 game/game4.ans。

【数据范围】

对于所有数据，\(1 \le n, m, q \le {10}^5\)，\(-{10}^9 \le A_i, B_i \le {10}^9\)。对于每轮游戏而言，\(1 \le l_1 \le r_1 \le n\)，\(1 \le l_2 \le r_2 \le m\)。

其中，特殊性质 1 为：保证 \(A_i, B_i > 0\)。
特殊性质 2 为：保证对于每轮游戏而言，要么 \(l_1 = r_1\)，要么 \(l_2 = r_2\)。

解析

首先，考虑暴力枚举，算法复杂度O(qnm)，预计得分25分，实际得分60分。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,q,a[N],b[N];
int main()
{
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	while(q--)
	{
		int l1,r1,l2,r2;
		cin>>l1>>r1>>l2>>r2;
		long long ans=-1e18;
		for(int i=l1;i<=r1;i++)
		{
			long long tmp=1e18;
			for(int j=l2;j<=r2;j++)
			{
				tmp=min(tmp,1ll*a[i]*b[j]);
			}
			ans=max(ans,tmp);
		}
		cout<<ans<<endl;
	}
	return 0;	
} 

考虑正解。肯定先思考 B 再思考 A，因为 A 会思考 B 的思考。
B 的行为就是对于 \(x\)，找到一个 \(b[l_2 \cdots r_2]\) 中的 \(y\)，使得 \(x \times y\) 最小。
具体地：

\(x \ge 0\) 时，B 会选择最小的 \(y\)；
\(x < 0\) 时，B 会选择最大的 \(y\)。

那么 A 的行为是什么呢？还是按照正负分类讨论：
如果 A 这次想让 \(x \ge 0\)，那么 B 会选择最小的 \(y\)。如果这个 \(y \ge 0\)，那么 A 一定会选最大的 \(x\)；如果这个 \(y < 0\)，那么 A 一定会选最小的非负数 \(x\)（别忘了当前制约条件 \(x \ge 0\)）。
如果 A 这次想让 \(x < 0\)，那么 B 会选择最大的 \(y\)。如果这个 \(y \ge 0\)，那么 A 一定会选最大的负数 \(x\)；如果这个 \(y <0\)，那么 A 一定会选最小的 \(x\)。
因此 A 的行为只有四种：选择最大的 \(x\)；最小的 \(x\)，最大的负数 \(x\)，最小的非负数 \(x\)。
分别讨论 A 选择四种行为时 B 的选择，答案取最大值即可。
然后就变成了静态区间最值的板子。使用 6 个 ST 表分别存储以下信息：

\(a\) 的区间最大值；
\(a\) 的区间最小值；
\(a\) 的负数区间最大值；

具体是把所有满足 \(a_i \ge 0\) 的 \(a_i\) 全部替换为 \(-\infty\) 代表这个位置不存在数，至于为何是 \(-\infty\) 请读者自己思考。

\(a\) 的非负数区间最小值；

具体是把所有满足 \(a_i < 0\) 的 \(a_i\) 全部替换为 \(+\infty\) 代表这个位置不存在数。

\(b\) 的区间最大值；
\(b\) 的区间最小值。

时间复杂度 \(\mathcal{O}(n\log n + q)\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,q;
ll amax[N][20],amin[N][20],bmax[N][20],bmin[N][20],azmin[N][20],afmax[N][20],lg[N];
int main()
{
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++) 
	{
		int x;
		cin>>x;
		amin[i][0]=amax[i][0]=x;
		if(x>=0) azmin[i][0]=x,afmax[i][0]=LONG_LONG_MIN;
		else azmin[i][0]=LONG_LONG_MAX,afmax[i][0]=x;
	}
	for(int i=1;i<=m;i++) 
	{
		int x;
		cin>>x;
		bmin[i][0]=bmax[i][0]=x;
	}
	for(int i=2;i<=max(n,m);i++) lg[i]=lg[i/2]+1;
	for(int j=1;j<=lg[n];j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
		{
			int p=i+(1<<(j-1));
			amax[i][j]=max(amax[i][j-1],amax[p][j-1]);
			afmax[i][j]=max(afmax[i][j-1],afmax[p][j-1]);
			amin[i][j]=min(amin[i][j-1],amin[p][j-1]);
			azmin[i][j]=min(azmin[i][j-1],azmin[p][j-1]);
		}
	for(int j=1;j<=lg[m];j++)
		for(int i=1;i+(1<<j)-1<=m;i++)
		{
			int p=i+(1<<(j-1));
			bmax[i][j]=max(bmax[i][j-1],bmax[p][j-1]);
			bmin[i][j]=min(bmin[i][j-1],bmin[p][j-1]);
		}
	while(q--)
	{
		int l1,r1,l2,r2;
		cin>>l1>>r1>>l2>>r2;
		int ka=lg[r1-l1+1],kb=lg[r2-l2+1];
		int pa=r1-(1<<ka)+1,pb=r2-(1<<kb)+1;
		ll a_max=max(amax[l1][ka],amax[pa][ka]);
		ll a_min=min(amin[l1][ka],amin[pa][ka]);
		ll af_max=max(afmax[l1][ka],afmax[pa][ka]);
		ll az_min=min(azmin[l1][ka],azmin[pa][ka]);
		ll b_max=max(bmax[l2][kb],bmax[pb][kb]);
		ll b_min=min(bmin[l2][kb],bmin[pb][kb]);
		ll ans=LONG_LONG_MIN;
		ans=max(ans,a_max*(a_max>=0?b_min:b_max));
		ans=max(ans,a_min*(a_min>=0?b_min:b_max));
		if(af_max!=LONG_LONG_MIN) ans=max(ans,af_max*(af_max>=0?b_min:b_max));
		if(az_min!=LONG_LONG_MAX) ans=max(ans,az_min*(az_min>=0?b_min:b_max));
		cout<<ans<<endl;
	}
	return 0;	
} 

T3 星战

先翻译一下题目：
\(n\) 个点 \(m\) 条边的有向图，每条边都有激活和失活两种状态，初始时均为激活状态。四种操作：

失活某条边；
失活以某个点为终点的所有边；
激活某条边；
激活以某个点为终点的所有边。

然后问：如果只考虑激活的边，是否满足：

所有的点出度均为 \(1\)；
所有的点都满足，从这个点出发，可以走到一个环中。

首先我们发现，如果所有点的出度均为 \(1\)，那么所有点都满足从这个点出发能走到一个环里。这是因为所有点的出度都是 \(1\)，因此一条路径可以一直走下去，而只要走 \(n\) 步就一定会遇到先前走过的一个节点（总共只有 \(n\) 个点），此时环就出现了。
因此压根不用判环，只用判断所有点出度是否均为 \(1\)。

事实上，所有点出度均为 \(1\) 的有向图称作基环内向森林，它由若干个弱联通块（将所有有向边看成无向边后的联通块）构成，每个弱联通块称作基环内向树。对于基环内向树，它可以被认为是由有向环和长在环上的若干条链构成。这些链单向导通到环上。更多有关定义可以自行阅读 OI Wiki 的图论相关概念。

我们观察到，一、三操作可以用 \(\mathcal{O}(1)\) 的效率修改一个点的出度（修改目标边的终点出度即可），而二、四操作只能用 \(\mathcal{O}(n)\) 的效率（因为终点为 \(v\) 的边有很多，对应的起点最多有 \(n\) 个，它们的出度都需要被修改）。
不过，前 8 个测试点，是支持我们用最坏时间复杂度 \(\mathcal{O}(nq)\) 的暴力维护出度的，所以 40 分已经到手。
然后 9 和 10 两个测试点还是保证没有二、四操作的。单次操作可以做到 \(\mathcal{O}(1)\)。因此这两个测试点用 \(\mathcal{O}(q)\) 的复杂度解决，50 分到手。
这里是我的 50 分代码。

思考许久后我发现，容易维护的不是出度，而是入度。具体来说：
设原图上点 \(u\) 的入度为 \(g(u)\)，当前点 \(u\) 入度为 \(r(u)\)：

失活 \((u, v)\)：\(r(v) \gets r(v) - 1\)；
失活以 \(v\) 为终点的所有边：\(r(v) \gets 0\)；
激活 \((u, v)\)：\(r(v) \gets r(v) + 1\)；
激活以 \(v\) 为终点的所有边：\(r(v) \gets g(v)\)。

这些都可以 \(\mathcal{O}(1)\) 完成。
那么入度和出度有什么关系呢？
一张图里，所有点的入度和等于出度和。我们的目标是所有出度都是 \(1\)，那么所有出度的和都是 \(n\)。因此入度的和也必须是 \(n\)。
于是我们得到所有出度均为 \(1\) 的一个必要条件：入度和为 \(n\)。然而这个条件并不充分，因为入度和为 \(n\) 可以推出出度和为 \(n\)，但不能再进一步推出所有出度均为 \(1\)。
比如，如果有三个点，点 \(1\) 出度为 \(2\)，点 \(2\) 出度为 \(1\)，点 \(3\) 没有出度，我们如果单纯地去计算它的入度和，发现它等于 \(n\)，就判断现在每个点出度都是 \(1\)，这明显是错误的。
但是，我们可以利用 哈希 使得这个条件的充分性有极大概率是正确的，进一步使得这个条件的充要性极大概率正确，通过本题。

我们初始给每个点随机一个权值 \(w(u)\)。重新定义，一个点 \(v\) 对应的 \(r(v)\)，表示直接连向 \(v\) 的所有 \(u\) 的 \(w(u)\) 之和，即：
\(r(v) = \sum_{(u, v) \in E}w(u)\)而 \(g(v)\) 代表初始所有边都被激活时的 \(r(v)\) 的值，且之后不改变（静态）。
重新设计：

失活 \((u, v)\)：\(r(v) \gets r(v) - w(u)\)；
失活以 \(v\) 为终点的所有边：\(r(v) \gets 0\)；
激活 \((u, v)\)：\(r(v) \gets r(v) + w(u)\)；
激活以 \(v\) 为终点的所有边：\(r(v) \gets g(v)\)。

这个过程中，所有点的 \(r\) 值之和 \(\sum r(u)\) 可以在每次操作时 \(\mathcal{O}(1)\) 地维护。更进一步地：

设 \(\{u_1, u_2, \ldots\}\) 是 \(v\) 的入点集合，则 \(r(v) = w(u_1) + w(u_2) + \ldots\)。理由是 \(r(v)\) 的定义。
如果所有点 \(u\) 的出度都是 \(1\)，那么 \(u\) 只会出现在它所连向的 \(v\) 的入点集合中。因此，将所有入点集合的权值加起来，即 \(\sum r(u)\)，我们应该恰好得到 \(\sum w(u)\)。也即，\(\sum r(u) = \sum w(u)\)。

因此，\(\sum r(u) = \sum w(u)\) 是每个点出度都为 \(1\) 的一个必要条件。那么，这个条件充分吗？
一般地，我们设点 \(u\) 的出度为 \(k(u)\)，意味着 \(w(u)\) 恰好在最终的 \(\sum r(u)\) 中出现 \(k(u)\) 次。也即 \(\sum r(u) = \sum k(u) \times w(u)\)。因此我们可以将判断条件 \(\sum r(u) = \sum w(u)\) 改写为：\(\sum k(u) \times w(u) = \sum w(u)\)。
显然所有 \(k(u) = 1\) 是一个解。有其它的解吗？
有，但是这样的一组 \(k\) 跟 \(w\) 高度相关，除非出题人精心构造数据使得目前的局面形成的 \(k\) 存在一个不等于 \(1\) 还恰好满足这个方程，否则你可以认为当这个方程成立的时候，目前的 \(k\) 都等于 \(1\)。
又因为你的 \(w\) 是随机的，所以数据是没法对着你的代码卡的，除非你的 \(w\) 正好随机到一个能把你代码卡掉的数据，这种可能太小了基本可以忽略不计，因为随机的值域已经相当大了。
这就是哈希的原理了：判定时构造一个必要不充分条件，但这个“不充分”实际上有非常大非常大的概率充分，以至于不充分性可以忽略不计，从而达到充要判定的效果。读者应当熟悉的字符串哈希，也是同样的原理。
这种哈希似乎一般称作“和哈希”（sum hash）。
代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
typedef long long ll;
ll in[N],a[N],w[N];
int main()
{
	int n,m;
	cin>>n>>m;
	ll s=0;
	for(int i=1;i<=n;i++) w[i]=rand(),s+=w[i];
	ll t=0;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		in[v]+=w[u];
		a[v]=in[v];
		t+=w[u];
	}
	int q;
	cin>>q;
	while(q--)
	{
		int op,u,v;
		cin>>op;
		if(op==1) cin>>u>>v,in[v]-=w[u],t-=w[u];
		else if(op==2) cin>>v,t-=in[v],in[v]=0;
		else if(op==3) cin>>u>>v,in[v]+=w[u],t+=w[u];
		else cin>>v,t+=a[v]-in[v],in[v]=a[v];
		if(t==s) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

本栏目推荐文章
• openpyxl模块---------------------------------------------提取身份证信息及计算年龄
• AtCoder World Tour 2022 B The Greatest Two
• 2021-2022 ICPC Northwestern European Regional Programming Contest (NWERC 2021)
• CSP-J/S 2023 游记
• JFinal学生信息管理系统
• 【LeetCode 2701. 连续递增交易】MySQL用户变量编程得到严格递增连续子序列的开始位置，结束位置，长度等统计信息
• 初中信息奥赛模拟测试
• Qt/C++编写视频监控系统83-自定义悬浮条信息
• 多态和虚函数 [补档-2022-10-23]
• 深拷贝和浅拷贝的问题 [补档-2022-10-22]

真题 CSP-S 信息 2022 CSP真题csp-s信息2022 游记csp-s 2022 csp 错题 初赛csp-s 2022 题解p8817 csp-s 2022 p8819 csp-s 2022 csp p8817 csp-s 2022 csp 题解p8819 csp-s 2022 csp-s 2022 csp csp-s 2022 csp t1 题解p8820 csp-s 2022