前行 - Codeforces Round 594 (Div.1)

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


Part1. 小结

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

png1

从最开始比初始分还低到后来慢慢涨;然后有一次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时刻接完。

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$ 的优美值。

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

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

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

    比如交换 "(()())()" 的第一个和第六个字符,会使原来 (()()) 中的 ()() 变成最外层,而原本不被第一个和第六个字符包含的第7,8个字符变成第2层。

  2. 交换第二层括号,会使 它包含的第3层括号变成最外层,交换后的左右括号分别与第一层的左右括号配对,其他括号不会受影响。

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

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

C - Queue in the Train

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

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

  1. typ=1 id=i tim=t[i]:第 $i$ 个人在 tim 时刻想去接水了,开始等待;
  2. 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,当前队列中所有人都接完水的时刻。

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

  1. typ=1,则把这个人放入 wat 中;
  2. typ=2,则把这个人移除 que
  3. 每次处理完一个事件,就查看当前的 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*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)

【真的实现得很丑啊!!点击展开/折叠代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/*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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/*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,欢迎提问~

0%