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$，仅包含正整数（一开始为空），给出两种询问。
- 加入一个正整数进入$S$，新加的数一定不比已有的数小。
- 找到$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;
}
|
