最近比赛时间太晚了没打，这是补上的。
比赛地址
官方题解
Problem A. Olympiad
题目大意
有一场$n$个人参加的比赛，每个人有一个分数。
至少要有一个人得到奖励，分数为零的不能得到奖励，若一个人得到了奖励，则分数大于等于其的人都必须得到奖励。
问有几种奖励方式。
题目分析
3秒钟水题。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<bits/stdc++.h>
using namespace std;
inline 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;
}
int n,a[105];
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
sort(a+1,a+n+1);
int tot=unique(a+1,a+n+1)-a-1;
printf("%d\n",tot-(a[1]==0));
return 0;
}
|
Problem B. Vile Grasshoppers
题目大意
询问在$2\sim p$中最大的一个数使其不是$2\sim y$的倍数。
题目分析
$i$从$p$往前枚举，直到$i$的最小因数 $\gt y$。
因为$10^9$以内的素数间隔最大为$300$，而素数一定满足条件，故时间复杂度为：$O(300\sqrt p)$。
代码
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
| #include<bits/stdc++.h>
using namespace std;
inline 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;
}
int p,y;
int main() {
p=Get_Int();
y=Get_Int();
for(; y>p; y--) {
int x=y;
for(int i=2; i<=sqrt(y); i++)if(y%i==0) {x=i;break;}
if(x>p) {printf("%d\n",y);return 0;}
}
puts("-1");
return 0;
}
|
Problem C. Save Energy!
题目大意
你在宿舍做饭，用了一个炉子，这个炉子一开始会加热$k$秒，之后会保持保温状态，在加热时加热的效率为$\frac 1t$，保温时的效率为$\frac 1{2t}$，你每隔$d$秒会看一下炉子，若此时炉子是关着的，你就会把它打开，问你要花多久时间做好饭。
题目分析
特判题！！！
画个数轴开始特判。
代码
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
| #include<bits/stdc++.h>
using namespace std;
inline long long Get_Int() {
long long 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;
}
double k,d,t;
int main() {
k=Get_Int();
d=Get_Int();
t=Get_Int();
double x=ceil(k/d)*d,delta=x-k;
double period=k*1.0+delta*0.5;
double times=floor(t/period);
double remain=t-times*period,ans=times*x;
if(k>remain)printf("%0.1lf\n",ans+remain);
else printf("%0.1lf\n",ans+k+(remain-1.0*k)/0.5);
return 0;
}
|
Problem D. Sleepy Game
题目大意
你和你的朋友在一个图上玩组合游戏，这张图有$n$个点$m$条有向边。
已经指定了起点，每个玩家沿着边轮流移动，若某个玩家不能再移动了就输了。
然而现在你的朋友睡着了，于是你帮他移动（wtf）。
若$10^6$轮后仍不能结束，游戏判为平局。
问你是否有最优策略，若没有最优策略，能否达成平局？
题目分析
智障游戏，实际上就是让你求是否有一条长度为奇数的到出度为$0$点的路径。
随手敲个Dfs即可知道是否能赢。
平局只需要看能否走到环即可，因为题目的条件“若$10^6$轮后仍不能结束，游戏判为平局”，可以直接Bfs判环。
代码
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
| #include<bits/stdc++.h>
using namespace std;
inline 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,maxs=1000005;
int n,s,size,bj,times=0,ans[maxs];
bool vst[maxn][2];
vector<int> edges[maxn];
void Dfs(int Now,int depth) {
if(bj==1)return;
ans[depth]=Now;
vst[Now][depth&1]=1;
for(int Next:edges[Now]) {
if(vst[Next][(depth&1)^1])continue;
Dfs(Next,depth+1);
}
if((depth&1)&&!edges[Now].size()) {size=depth;bj=1;return;}
if(!(depth&1)&&!bj) {bj=2;return;}
}
int main() {
n=Get_Int();
Get_Int();
for(int i=1; i<=n; i++) {
int num=Get_Int();
for(int j=1; j<=num; j++) {
int x=Get_Int();
edges[i].push_back(x);
}
}
queue<int> Q;
Q.push(s=Get_Int());
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int Next:edges[Now])Q.push(Next),times++;
if(times>=1000000) {
bj=3;
break;
}
}
Dfs(s,0);
if(bj==1) {
puts("Win");
for(int i=0; i<=size; i++)printf("%d ",ans[i]);
putchar('\n');
} else puts(bj==2?"Lose":"Draw");
return 0;
}
|
Problem E. Lock Puzzle
题目大意
给你一个长度为$n$的字符串s，现在要你把他变成字符串t。
变化的方法为$\text{shift}(x)$，规则为选中s的后缀$\rm {suffix}(n-x+1)$，将其翻转并拼接在串的最前端。如ABBBBCD经过$\text{shift}(3)$可以变成DCBABBB。
输出一种变化方法，要求操作次数$\le6100$。$n\le2000$。
题目分析
构造题。
首先无解很好判，每种字符个数不等即可。
对于其他情况，我们可以构造一种方法：
假设当前的s串为：
其中$A,B$均为$s$的一段子串。
现在我们要将$t_i$放到$s$的最前面去，假设$t_i$所在$s$串的位置为$j$。
首先翻转$s$串，$\text{shift}(n)$：
其中$A^T$表示$A$串的翻转串。
然后将$t_i$放到最后，$\text{shift}(j)$：
最后把$t_i$提到最前面即可，$\text{shift}(1)$：
大功告成，操作次数严格$3n$。
代码
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
| #include<bits/stdc++.h>
using namespace std;
inline 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=2005;
int n,sum[26];
string A,B;
vector<int> ans;
int main() {
ios::sync_with_stdio(false);
cin>>n>>A>>B;
for(int i=0; i<n; i++)sum[A[i]-'a']++,sum[B[i]-'a']--;
for(int i=0; i<26; i++)if(sum[i]) {puts("-1");return 0;}
for(int i=0; i<n; i++)
for(int j=i; j<n; j++)
if(A[j]==B[n-1-i]) {
string L=A.substr(0,j),ch=A.substr(j,1),R=A.substr(j+1);
reverse(R.begin(),R.end());
A=ch+L+R;
ans.push_back(n),ans.push_back(j),ans.push_back(1);
break;
}
printf("%d\n",ans.size());
for(int x:ans)printf("%d ",x);
return 0;
}
|
