Codeforces Round 467 (Div. 2) 解题报告

B:
Codeforces 937B
题意:给两个数 $ p, y $求 $p$到$y$的区间中 不是$2$到$p$之间的倍数的最大数
结论:两个相邻素数之间最大不超过$10^3$(在$10^9$的范围内),而输出的答案一定包含素数,所以肯定会比素数之间距离更大
不严谨的证明:$n$以下的素数个数为$n/logn$级别,所以在平均情况下,两个相邻素数之间平均距离为$logn$大小,但是结论应该更大,这里只是平均

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
#define db double
int p, y;
bool check(int x) {
for (int i = 2; i * i <= x; i++) {
if (i > p) break;
if (x % i == 0) return false;
}
return true;
}
void clean() {}
int solve() {
clean();
for (int i = y; i > p; i--) {
if (check(i)) {
return printf("%d\n", i), 0;
}
}
printf("-1\n");
return 0;
}
int main() {
scanf("%d%d", &p, &y), solve();
return 0;
}

C:
Codeforces 937C
题意:要用微波炉烤一个面包,已知此微波炉开一次能烤$k$分钟,而每过$d$分钟,jury都会检查一次微波炉是否在工作,如果在工作则什么都不做,如果不在工作则把它打开。已知整个面包在微波炉工作的时候需要$t$分钟才能烤熟,若微波炉不工作的时候,依靠余温需要$2t$分钟才能烤熟,问总共需要多少分钟可以烤熟。(初始微波炉是开着的,并且只要一熟就可以拿出来)。

周期问题,寻找一个周期,这个周期是反复重复的,之后再求余模拟即可。

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
#define db double
ll k, d, t;
void clean() {}
int solve() {
clean();
ll r = d;
if (d < k) r = (k / d) * d + (bool)(k % d) * d;
db con = (db)k / (db)t, coff = (db)(r - k) / 2.0 / (db)t;
ll tms = (ll)(1 / (con + coff));
db remaind = 1 - (db)tms * (con + coff);
if (remaind <= con) return printf("%.11f\n", (ll)r * (ll)tms + t * remaind), 0;
else printf("%.11f\n", (ll)r * (ll)tms + (ll)k + 2 * t * (remaind - con)), 0;
return 0;
}
int main() {
scanf("%I64d%I64d%I64d", &k, &d, &t), solve();
return 0;
}

D:
Codeforces 937D
题意:问从$s$点出发能否走奇数条边到一个没有出度的点
坑题,奇数个节点的环可以进去走一圈出来改变原先的奇偶性,这个会坑在$Test 28$,鉴于太难修改,暂时不改了,放一个$WA 28$的程序作参考。
DFS中要完全退出程序只能用$exit(0)$

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
#define db double
int n, m, st;
vector<int> G[100000 + 5];
int now, flag, len[100000 + 5], vis[100000 + 5], step[100000 + 5];
void dfs(int u) {
vis[u] = -1;
step[++now] = u;
if (G[u].size() == 0 && len[u] % 2 == 0) {
printf("Win\n");
for (int i = 1; i <= now; i++) printf("%d ", step[i]);
exit(0);
}
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (vis[v] == -1) {
flag = true;
} else if (vis[v] == 0) {
len[v] = len[u] + 1, dfs(v);
}
}
vis[u] = 1;
step[now--] = 0;
}
void clean() {
now = 0;
flag = false;
for (int i = 0; i <= n; i++) len[i] = vis[i] = 0, G[i].clear();
}
int solve() {
clean();
for (int i = 1; i <= n; i++) {
int c; scanf("%d", &c);
for (int j = 1; j <= c; j++) {
int x; scanf("%d", &x);
G[i].push_back(x);
}
}
scanf("%d", &st);
len[st] = 1, dfs(st);
if (flag) printf("Draw\n"); else printf("Lose\n");
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}

------ 本文结束 ------