Codeforces Round 464 题解(全解锁) | Bill Yang's Blog

Codeforces Round 464 题解(全解锁)

ECR38 和 CR464 共涨了$117$ rating,very good。

丢几个链接
比赛地址
官方题解

Problem A. Love Triangle

题目大意

给$n$个点,每一个点有一条出边(不形成自环),询问图中是否存在三元环。

题目分析

我写复杂了,不需要tarjan,直接检查一遍所有三元组即可。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=5005;
int n,step=0,top=0,Dfn[maxn],Lowlink[maxn],Stack[maxn];
bool Instack[maxn],bj=0;
vector<int> edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Tarjan(int Now) {
Dfn[Now]=Lowlink[Now]=++step;
Stack[++top]=Now;
Instack[Now]=1;
for(int Next:edges[Now]) {
if(!Dfn[Next]) {
Tarjan(Next);
Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);
} else if(Instack[Next])Lowlink[Now]=min(Lowlink[Now],Dfn[Next]);
}
if(Dfn[Now]==Lowlink[Now]) {
int y,size=0;
do {
y=Stack[top--];
Instack[y]=0;
size++;
} while(y!=Now);
if(size==3)bj=1;
}
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)AddEdge(i,Get_Int());
for(int i=1; i<=n; i++)if(!Dfn[i])Tarjan(i);
puts(bj?"YES":"NO");
return 0;
}

Problem B. Hamster Farm

题目大意

给$n$只仓鼠,有$k$种箱子。
用箱子装仓鼠,只能选一种箱子装仓鼠,一个箱子必须装满仓鼠,若仓鼠有剩余,舍弃掉多的仓鼠。
询问最多能装多少仓鼠?输出选择的箱子种类与所需个数。

题目分析

嘿嘿嘿,卖仓鼠。
模拟一下即可。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int ans1,k;
LL n,ans2,Max=0;
int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<=k; i++) {
LL x=Get_Int(),tmp=n/x;
if(tmp*x>=Max) {
ans1=i;
ans2=tmp;
Max=tmp*x;
}
}
printf("%d %I64d\n",ans1,ans2);
return 0;
}

Problem C. Convenient For Everybody

题目大意

一天有$n$个小时($1\rightarrow n$小时),也有$n$个时区,时差均为$1$小时,第$i$个时区有$a_i$个人。
如果比赛开始时间在当地时间$[s,f)$之间,这个时区的人就会参加比赛。
确定$1$时区的比赛开始时间,使得参加人数最多。

题目分析

做个前缀和,把环拆成链,模拟一下即可。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=200005;
int n,s,t,a[maxn],sum[maxn],Max=0,ans=INT_MAX;
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int(),sum[i]=sum[i-1]+a[i];
for(int i=n+1; i<=2*n; i++)sum[i]=sum[i-1]+a[i-n];
s=Get_Int();
t=Get_Int();
for(int i=1; i<=2*n-(t-s); i++) {
int tmp=((s-i+1)%n+n)%n;
if(tmp==0)tmp=n;
if(Max<sum[i+(t-s)-1]-sum[i-1]||(Max==sum[i+(t-s)-1]-sum[i-1]&&tmp<ans)) {
ans=tmp;
Max=sum[i+(t-s)-1]-sum[i-1];
}
}
printf("%d\n",ans);
return 0;
}

Problem D. Love Rescue

题目大意

给两个串$s_1,s_2$,你可以指定一些变换$c_1\rightarrow c_2$,可以使字母$c_1$变成$c_2$,每种变换可以用无穷次。
指定一些变换,使得$s_1$和$s_2$可以变成一样的字符串,同时变换的种类数最少。

题目分析

随便输出一棵生成树即可。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=35;
#define pii pair<int,int>
#define mp make_pair
char s1[100005],s2[100005];
bool vst[maxn];
vector<int> edges[maxn];
vector<pii> ans;
int n;
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Dfs(int Now) {
vst[Now]=1;
for(int Next:edges[Now]) {
if(vst[Next])continue;
ans.push_back(mp(Now,Next));
Dfs(Next);
}
}
int main() {
n=Get_Int();
scanf("%s%s",s1+1,s2+1);
for(int i=1; i<=n; i++)
if(s1[i]!=s2[i]) {
AddEdge(s1[i]-'a',s2[i]-'a');
AddEdge(s2[i]-'a',s1[i]-'a');
}
for(int i=0; i<26; i++)if(!vst[i])Dfs(i);
printf("%d\n",ans.size());
for(pii x:ans)printf("%c %c\n",x.first+'a',x.second+'a');
return 0;
}

Problem E. Maximize!

题目大意

给出一个可重集合$S$,仅包含正整数(一开始为空),给出两种询问。

  1. 加入一个正整数进入$S$,新加的数一定不比已有的数小。
  2. 找到$S$的一个子集$s$,使得$\max(s)-mean(s)$最大,其中$\max(s)$表示$s$中的最大值,$mean(s)$表示$s$的平均数。

题目分析

发现第一个条件保证了有序性。
对于$\max(s)-mean(s)$,贪心地,我们肯定是选择$S$的最大值,与若干个尽量小的值。
因此,我们只需要找到最小的$mean(s)$即可。
这一部分可以使用分数规划解决,通过二分答案,问题转化为找到符合要求的$mean(s)$。
因为原序列有序,故前缀的$mean(s)$也是有序的,可以再一次使用二分查找解决该子问题。

时间复杂度$O(q\log^2 n)$。

可能错因

  • 可能TLE错因:精度别开大了,$1e-6$已经足够。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=5e5+5;
const double eps=1e-6;
int n,q;
LL a[maxn],sum[maxn];
double ans=0;
bool Check(double m) {
int Left=1,Right=n,pos=-1;
while(Left<=Right) {
int mid=(Left+Right)>>1;
if(m>a[mid]) {
pos=mid;
Left=mid+1;
if(m*pos-sum[pos]+m-a[n]>=0)return true;
} else Right=mid-1;
}
if(~pos)return m*pos-sum[pos]+m-a[n]>=0;
return false;
}
int main() {
q=Get_Int();
while(q--) {
int opt=Get_Int();
if(opt==1) {
int x=Get_Int();
a[++n]=x;
sum[n]=sum[n-1]+x;
double Left=0,Right=1e9;
while(Right-Left>eps) {
double mid=(Left+Right)/2;
if(Check(x-mid))Left=mid;
else Right=mid;
}
ans=(Left+Right)/2;
} else printf("%0.10lf\n",ans);
}
return 0;
}

Problem F. Cutlet

题目大意

有一个两面的煎饼,每一面各需要烤$n$秒钟,现在给出若干个不相交的可以翻面的时间区间。
在保证两面切好烤了$n$秒钟的前提下,使得翻面次数尽量少。

题目分析

设$f(i,j)$表示第$i$秒钟,其中一面烤了$j$秒的最少翻面次数。
不难发现可以有转移:

注意到其中有一些状态的意义相同。
比如$f(i,j)$与$f(i,i-j)$,其状态意义是一样的,故节约掉两个转移:

但是这样的转移是$O(n^2)$的。

观察上面的转移式,我们发现只有在可以翻面的时间区间中才会有第二种转移,而第一种转移的第二维是相同的!
又注意到,在同一个时间区间内最多翻面两次,若更多

故我们可以修改一下状态定义:
设$f(i,j)$表示第$r_i$秒钟,其中一面烤了$j$秒的最少翻面次数。

这个转移式可以用单调队列进行优化,因为cf机子快,所以也可以用线段树优化。
时间复杂度$O(nk)/O(nk\log n)$。

因为本题良心,所以不需要开滚动数组,然而我开了。
注意边界问题。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005,maxk=105;
int n,k,f[2][maxn],l[maxk],r[maxk];
int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<=k; i++)l[i]=Get_Int(),r[i]=Get_Int();
f[0][0]=0;
for(int i=1; i<=n; i++)f[0][i]=INT_MAX/2;
deque<int> Q;
int now=0,pre=1;
for(int i=1; i<=k; i++) {
swap(now,pre);
for(int j=0; j<=n; j++)f[now][j]=f[pre][j];
Q=deque<int>();
Q.push_back(0);
for(int j=1; j<=min(n,r[i]); j++) {
while(!Q.empty()&&Q.front()<j-(r[i]-l[i]))Q.pop_front();
if(!Q.empty())f[now][j]=min(f[now][j],f[pre][Q.front()]+2);
if(j<=n) {
while(!Q.empty()&&f[pre][j]<=f[pre][Q.back()])Q.pop_back();
Q.push_back(j);
}
}
Q=deque<int>();
Q.push_back(0);
for(int j=r[i]; j>=0; j--) {
while(!Q.empty()&&Q.front()<l[i]-j)Q.pop_front();
if(j<=n&&!Q.empty())f[now][j]=min(f[now][j],f[pre][Q.front()]+1);
if(r[i]-j+1<=n) {
while(!Q.empty()&&f[pre][r[i]-j+1]<=f[pre][Q.back()])Q.pop_back();
Q.push_back(r[i]-j+1);
}
}
}
if(f[k&1][n]==INT_MAX/2)puts("Hungry");
else printf("Full\n%d\n",f[k&1][n]);
return 0;
}
0%