前行 - Codeforces Round 594 (Div.1)

第一次正式打 Div1 诶…… 现在还是只做出来了 A~D……
~~开赛前慌得一 bi，感觉肯定要掉分了，最后还是分数真香~~

Part1. 小结

Codeforces 也打了好久了，看到自己的 Rating 曲线也还是比较曲折的……

从最开始比初始分还低到后来慢慢涨；然后有一次Div2打的比较开心（把F题玩出来了，瞬间跑到rank 24去了~）可以看到就是在紫名下面一点点；下一场就上紫了；后来也是非常爆炸，连续挂了两场（第二次FST了两道 QwQ）……

终于到现在 rating 还是处于 1979 的状态~

毕竟还是第一次正式参加 Div1（注册比赛的时候本来想注册 Div2，结果都不允许我注册~~，当时心态就崩了~~），感觉还是不一样，有种打 AGC 的感觉……不过确实，少了 Div2 的 AB 两道水题，后面的题就更有价值了。

Part2. 中文题面

当然是简化了的

A - Ivan the Fool and the Probability Theory

给一个 $n\times m$ 的方格图染色，每个格子只能染成白色或黑色，要求任意格子需要满足“与它相邻的格子中最多只有一个与它颜色相同”，这里的“相邻”指的是四联通（上下左右）。

求染色的方案数模 $10^9+7$。

数据规模：$1\le n,m\le10^5$。

B - The World Is Just a Programming Task (Hard Version)

一来就 Hard Version 了……

给出一个长度为 $n$ 的括号字符串 $S$，你需要交换 $S$ 的两个位置的字符得到字符串 $S’$（交换的两个位置可以相同，相当于不变）。

对一个括号字符串 $T$，定义一个优美值：
满足 $0\le i<n$ ，且“将 $T$ 旋转 $i$ 次后，是一个正则括号序列”的 $i$ 的个数。其中“旋转 $i$ 次”是指把 $T$ 的末尾 $i$ 个字符移动到开头，比如 "abcdef" 旋转 $2$ 次就是 "efabcd"。

求 $S’$ 的优美值最大是多少，取得最大值时，交换了 $S$ 的哪两个位置的字符得到 $S’$（输出任意解）。

数据规模：$1\le n\le300000$。

C - Queue in the Train

这是一道阅读理解题

火车上有 $n$ 个人依次坐在标号为 $1$ 到 $n$ 的座位上。第 $i$ 个人从 $t_i$ 时刻开始想去接水，每个人接水都需要花费时间 $T$。由于只有一个水龙头，人们可能会排成一个队伍等待接水。

但是显然大家都不想排队，当第 $i$ 个人想去接水时，他会先看第 $1$ 到 $i-1$ 个人有没有去排队接水。如果都没有去（或者已经接完水回来了），他就会去排队接水；否则他会留在座位上等待。

有一个潜规则是：如果在同一时间，有多个人想去接水，而且他们前面都没有人去排队接水，他们中编号最小的那个人会去排队，而其他人会留在座位上等待。

现在给出 $n,T$ 以及 $t_i$，求每个人接完水的时刻分别为多少。（假设人从座位上去排队花费的时间忽略不计，且当一个人接完水，下一个人立即开始接水）

数据规模：$1\le n\le10^5$,$1\le T\le10^9$,$0\le t_i\le10^9$。

两个栗子，帮助理解：

Input Output Explain

3 10
2 1 0 30 20 10 第③个人在时刻0发现①②都没有排队，就去接水；
第②个人在时刻1发现①没有排队，就排在③的后面；
第①个人在时刻2发现前面没有人，就排在②的后面。

5 314
0 310 942 628 0 314 628 1256 942 1570 ①⑤在0时刻同时想去接水且发现前面没有人在排队，按照潜规则，①去排队，而⑤等待；
②在310时刻想去接水，但是①还在接水，继续等待；314时刻①回来了，②⑤都想去接水，则②去排队，⑤继续等待；
②在628时刻接完水，同时④想去接水了，此时④⑤都想接水，则④去排队，⑤仍然等待；
④在942时刻接完水，同时③想去接水了，此时③⑤都想去接水，则③去排队；
③在1256时刻接完水，然后⑤看到前面的人都接完水了，去接水，在1570时刻接完。

Input	Output	Explain
3 10 2 1 0	30 20 10	第③个人在时刻0发现①②都没有排队，就去接水；第②个人在时刻1发现①没有排队，就排在③的后面；第①个人在时刻2发现前面没有人，就排在②的后面。
5 314 0 310 942 628 0	314 628 1256 942 1570	①⑤在0时刻同时想去接水且发现前面没有人在排队，按照潜规则，①去排队，而⑤等待； ②在310时刻想去接水，但是①还在接水，继续等待；314时刻①回来了，②⑤都想去接水，则②去排队，⑤继续等待； ②在628时刻接完水，同时④想去接水了，此时④⑤都想接水，则④去排队，⑤仍然等待； ④在942时刻接完水，同时③想去接水了，此时③⑤都想去接水，则③去排队； ③在1256时刻接完水，然后⑤看到前面的人都接完水了，去接水，在1570时刻接完。

D - Catowice City

有 $n$ 个人，每个人有一只猫。每个人都熟知自己的猫，但有人还认识其他一些人的猫。

现在要组织一场猫赛(??)，要从这 $n$ 个人中选出几个裁判、从这 $n$ 只猫中选出一些参加猫赛。为了保证公平，需要满足没有任何一个裁判认识任何一只参赛的猫。而且显然至少要有一只猫参加比赛、至少有一个裁判。还要要求裁判和参加比赛的猫的总数恰好为 $n$。

给出 $n$ 和 $m$ 条认识关系 i j，表示第 $i$ 个人认识第 $j$ 个人的猫（并不说明第 $j$ 个人认识第 $i$ 个人的猫），保证每个人都认识自己的猫。

求是否存在一种选择人和猫的方案，满足上述条件。如果存在，输出选择了多少个人和多少个猫，以及选择的是哪些人、哪些猫。

（多组数据）

数据规模：

数据不超过 $10^5$ 组，所有数据的 $n$ 之和以及 $m$ 之和均不超过 $10^6$；单组数据 $1\le n\le m\le10^6$。

Part3. 解析

A - Ivan the Fool and the Probability Theory

这是一道结论题，结论我打表打出来的……

大概就是“斐波那契数列第$n$项和第$m$项之和乘 2”。

B - The World Is Just a Programming Task (Hard Version)

代码实现得非常丑陋，不要看 qwq

对于一个括号串，其实它的优美值就是它“最多能够被分成多少连续的段使得每一段都是正则括号串”。比如说 "(()())()" 最多能够分成 "(()())" 和 "()"，它的优美值是 $2$。其实就是最外层括号的数量。

先计算出不交换（也就是交换相同位置）的情况下 $S$ 的优美值。

然后考虑交换，首先应该 交换原本匹配的一对括号，否则会使原来分离的两个（或多个）正则括号串合并成一个正则括号串，根据我们新定义的优美值，这样一定是不比原来优的。

其次，为了改变括号串的优美值，我们 要么交换最外层的一对括号，要么交换第二层的一对括号。

交换最外层的一对括号，会使 交换的括号内的原本的第2层括号变为最外层、原本在该括号之外的最外层括号变为第2层。

比如交换 "(()())()" 的第一个和第六个字符，会使原来 (()()) 中的 ()() 变成最外层，而原本不被第一个和第六个字符包含的第7,8个字符变成第2层。
交换第二层括号，会使 它包含的第3层括号变成最外层，交换后的左右括号分别与第一层的左右括号配对，其他括号不会受影响。

比如交换"((())())" 中的第 2,5 个字符，得到 "()()(())"，原本是第3层的第3,4个括号变成了最外层，交换后的第 2 个字符与原来最外层的第 1 个字符构成一对最外层括号、第 5 个字符与原来最外层的第 8 个字符构成一对最外层括号。

这样的话，$O(n)$ 枚举然后计算就好了。

C - Queue in the Train

不难想到先把所有人按 $t_i$ 排个序；

然后参考了叶ID 的思路，将操作“事件化”，就有以下两种事件：

typ=1 id=i tim=t[i]：第 $i$ 个人在 tim 时刻想去接水了，开始等待；
typ=2 id=i tim：第 $i$ 个人在 tim 时刻接完了水，回到座位上。

所有事件都按发生时间 tim 排序。如果有一个 typ=1 的事件与 typ=2 的事件同时发生，应该先处理 typ=2 的事件，因为实际上应该是一个人先接完水回来，然后想去接水的人发现自己前面没有正在排队的人，然后就去排队。如果有多个 typ=1 的事件同时发生，根据潜规则，应该按 id 较小的排在前面。

可以用 priority_queue 维护事件，然后用一个 set 维护当前正在排队的人、用一个 priority_queue 维护当前想去接水但正在等待的人。一开始有 $n$ 个 typ=1 事件，即第 $i$ 个人在 $t_i$ 时刻想接水了。

Tab. “正在排队的人” 的 set 的变量名是 que；“正在等待的人”的 priority_queue 的变量名是 wat。

除此之外还要处理两个变量：Ntim，当前时刻；Etim，当前队列中所有人都接完水的时刻。

接下来就依次处理事件：如果当前事件是

typ=1，则把这个人放入 wat 中；
typ=2，则把这个人移除 que；
每次处理完一个事件，就查看当前的 wat 的堆顶，如果堆顶表示的这个人前面没有人排队，就把他放入 que 中，并且计算他接完水的时间为 max(Ntim,Etim)+T，并且更新 Ntim,Etim。

还是比较好写的 ~

D - Catowice City

因为一共要选出 $n$ 个人和猫，而每个人认识的自己的猫，所以每个人要么是人去当裁判，要么是他的猫去参加比赛。

所以我们只要决定有哪些人是他的猫去参加比赛即可。

由于认识关系是单向的（即 i 认识 j 的猫但 j 不一定认识 i 的猫），我们可以把认识关系转成一个有向图：如果 i 认识 j 的猫，就连接 i 到 j 的有向边（但是不连接自环）。

这样的话，我们要决定把点分为“人”和“猫”两类，使得不存在从“人”指向“猫”的边。

于是有一种情况是有向图中出现了环，那么环上的所有点都必须选相同的，否则环上一定有从人指向猫的点。如果所有 $n$ 个点都在环上，就一定无解，因为选不出“人”或“猫”来。

如果存在一个（缩点后）入度为零的环，我们就可以把这个环全部选成“猫”，而其他点都选为“人”，显然不会有“人”指向“猫”的边。这一点想通后，除此之外的其他情况无解也就可以理解了。

如果没有环，那就直接选择一个入度为零的点作为“猫”就可以了。

其实总结起来，无论是入度为零的点还是环，都是一个强连通分量，因此先 Tarjan 把强连通块缩点，然后判断每个点的入度就可以了。

（然后其实这就是 2-sat，每个点有“人”和“猫”两种状态；“ i 认识 j 的猫”限制了“如果 i 选人，那 j 就不能选猫”）

Part4. 源代码

A - Ivan the Fool and the Probability Theory

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

const int MOD=int(1e9+7);

int n,m;
int main(){
	scanf("%d%d",&n,&m);
	long long x=0,y=2;
	for(int i=1;i<=n;i++){
		x=(x+y)%MOD;
		swap(x,y);
	}
	long long ans=y;
	x=0;y=2;
	for(int i=1;i<=m;i++){
		ans=(ans+x)%MOD;
		x=(x+y)%MOD;swap(x,y);
	}
	printf("%lld\n",ans);
	return 0;
}

B - The World Is Just a Programming Task (Hard Version)

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

const int N=3e5;

int n,ans;
int Dpos[N+3];
char str[N+10],Nstr[N+10];

int main(){
	scanf("%d%s",&n,str+1);
	int Ncnt=0,Ned=n,Nmin=0;
	for(int i=1;i<=n;i++){
		if(str[i]=='(') Ncnt++;
		else Ncnt--;
		if(Nmin>Ncnt){
			Nmin=Ncnt;
			Ned=i;
		}
	}
	if(Ncnt) printf("0\n1 1\n"),exit(0);
	int Npos=1;
	for(int i=Ned+1;i<=n;i++) Dpos[Npos]=i,Nstr[Npos++]=str[i];
	for(int i=1;i<=Ned;i++) Dpos[Npos]=i,Nstr[Npos++]=str[i];
	for(int i=1,Icnt=0;i<=n;i++){
		if(Nstr[i]=='(') Icnt++;
		else Icnt--;
		if(!Icnt) ans++;
	}
	int fans=ans;
	int ansl=1,ansr=1;
	for(int i=1;i<=n;){
		int Pcnt=0;
		int j;
		for(j=i;j<=n;j++){
			if(Nstr[j]=='(') Pcnt++;
			else Pcnt--;
			if(!Pcnt) break;
		}
		vector< pair<int,int> > vec;
		Pcnt=0;
		int Ptot=0;
		for(int k=i+1;k<j;k++){
			if(Nstr[k]=='(') Pcnt++;
			else Pcnt--;
			if(Pcnt==0){
				if(vec.empty()) vec.push_back(make_pair(i+1,k));
				else vec.push_back(make_pair(vec.back().second+1,k));
			}
		}
		for(auto it : vec){
			int L=it.first,R=it.second;
			int Kcnt=0,Ktot=0;
			for(int k=L+1;k<=R-1;k++){
				if(Nstr[k]=='(') Kcnt++;
				else Kcnt--;
				if(!Kcnt) Ktot++;
			}
			if(ans<fans-1+2+Ktot){
				ans=fans-1+2+Ktot;
				ansl=L;ansr=R;
			}
		}
		Ptot=vec.size();
		if(ans<Ptot+1){
			ans=Ptot+1;
			ansl=i;ansr=j;
		}
		i=j+1;
	}
	ansl=Dpos[ansl];ansr=Dpos[ansr];
	if(ansl>ansr) swap(ansl,ansr);
	printf("%d\n%d %d\n",ans,ansl,ansr);
	return 0;
}

C - Queue in the Train

/*Lucky_Glass*/
#include<bits/stdc++.h>
using namespace std;
#define uheap(x) x,vector<x>,greater<x>

const int N=1e5;

int n,tim;
int per[N+3];
long long ans[N+3];

struct EVENT{
	int id,typ;
	/*
	typ=1 -> someone add to the waiting queue
	typ=2 -> someone finish filling the water(leave waiting queue)
	*/
	long long tim;
	EVENT(){}
	EVENT(int _i,int _typ,long long _tim):id(_i),typ(_typ),tim(_tim){}
	bool operator >(const EVENT &B)const&{
		if(B.tim!=tim) return tim>B.tim;
		if(B.typ!=typ) return typ==2;
		return id>B.id;
	}
};
priority_queue< uheap(EVENT) > evt; //小根堆
priority_queue< uheap(int) > wat;
set<int> que;

int main(){
	scanf("%d%d",&n,&tim);
	for(int i=1;i<=n;i++){
		scanf("%d",&per[i]);
		evt.push(EVENT(i,1,per[i]));
	}
	long long Ntim=0,Etim=0;
	while(!evt.empty()){
		EVENT ev=evt.top();evt.pop();
		Ntim=ev.tim;
		if(ev.typ==1) wat.push(ev.id);
		else que.erase(ev.id);
		while(!wat.empty() && (que.empty() || wat.top()<*que.begin())){
			int now=wat.top();wat.pop();
			que.insert(now);
			ans[now]=max(Ntim,Etim)+tim;
			evt.push(EVENT(now,2,ans[now]));
			Etim=ans[now];
		}
	}
	for(int i=1;i<=n;i++){
		printf("%lld",ans[i]);
		if(i==n) printf("\n");
		else printf(" ");
	}
	return 0;
}

D - Catowice City

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

const int N=1e6;

struct GNODE{int to;GNODE *nxt;};
struct GRAPH{
	GNODE Gpol[N*3],*Gtop[N+3],*Gcnt;
	void Init(int Gn){
		Gcnt=Gpol;
		for(int i=0;i<=Gn;i++) Gtop[i]=NULL;
	}
	void AddEdge(int u,int v){
		GNODE *p=++Gcnt;
		*p=(GNODE){v,Gtop[u]};Gtop[u]=p;
	}
	GNODE*& operator [](int id){return Gtop[id];}
}Ggrp;

int n,m,ndfn,nblk;
stack<int> stk;
bool instk[N+3];
int dfn[N+3],low[N+3],blk[N+3],siz[N+3],du[N+3];
//blk[u] 是 u 所属的强连通分量的编号；siz[i] 是编号为 i 的强连通分量的大小
vector<int> ans[2];

void Tarjan(int u){
	dfn[u]=low[u]=++ndfn;
	stk.push(u);
	instk[u]=true;
	for(GNODE *it=Ggrp[u];it;it=it->nxt){
		int v=it->to;
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else
			if(instk[v])
				low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		nblk++;
		int x=0;
		while(x!=u){
			x=stk.top();stk.pop();
			instk[x]=false;
			blk[x]=nblk;
			siz[nblk]++;
		}
	}
}
int main(){
	int cas;scanf("%d",&cas);
	while(cas--){
		scanf("%d%d",&n,&m);
		
		/*Init*/
		Ggrp.Init(n);
		while(!stk.empty()) stk.pop();
		fill(instk,instk+n+1,false);
		fill(dfn,dfn+n+1,0);
		fill(low,low+n+1,0);
		fill(siz,siz+n+1,0);
		fill(blk,blk+n+1,0);
		fill(du,du+n+1,0);
		ndfn=nblk=0;
		ans[0].clear();ans[1].clear();
		
		/*Build Graph*/
		for(int i=1;i<=m;i++){
			int u,v;scanf("%d%d",&u,&v);
			Ggrp.AddEdge(u,v);
		}
		
		/*Tarjan*/
		for(int i=1;i<=n;i++)
			if(!dfn[i])
				Tarjan(i);
		for(int u=1;u<=n;u++)
			for(GNODE *it=Ggrp[u];it;it=it->nxt){
				int v=it->to;
				if(blk[u]!=blk[v])
					du[blk[v]]++;
			}
        
        /*Get Answer*/
		if(siz[1]==n){
			printf("NO\n");
			continue;
		}
		for(int i=1;i<=nblk;i++){
			if(du[i]==0){
				printf("YES\n");
				for(int j=1;j<=n;j++)
					ans[blk[j]==i].push_back(j);
				printf("%d %d\n",ans[0].size(),ans[1].size());
				for(auto it : ans[0]) printf("%d ",it);printf("\n");
				for(auto it : ans[1]) printf("%d ",it);printf("\n");
				goto finish;
			}
		}
		printf("NO\n");
		finish: ;
	}
	return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com，欢迎提问~