Petrozavodsk Winter 2021 Day 1 赛后小结
|字数总计:3.3k|阅读时长:13分钟|阅读量:
比赛链接：https://qoj.ac/contest/529
F 队长秒了，I 是个幽默题，队长以为是线性题，给了个结论，然后我瞪了半天，发现结论不对，然后发现时限 20s ，直接调和级数过了，幽默，太幽默了。
然后队长写几何：B 题。
和 Imakf 讨论 C ，发现叶子一定会选，但是还有讨论，什么环上有几个没有叶子的节点等等。
但这里我其实犯了罪，我在其实讨论快结束的时候就去看别的题了，主要原因其实是：最后我参与讨论，讨论完了我可能要写这道题目，基环树一看就很不好写，所以我润了。
但是讨论到最后我还是总结了一下 Imakf 的讨论，然后 Imakf 要上这个题，这个时候我发现题目很难读，然后又看 Imakf 要上这个难写的题目（我也明白这个是怎么讨论的），突然心生忏悔，前面我为了逃避，将写题的任务推给了 Imakf ，这不是双标是什么！于是我让 Imakf 去看题，我去写这个题（说到底心生忏悔是你的谎言，看不懂题才是真正原因）。
但总之，以后无论如何都不能因为不想写题而不参与讨论，快打 WF 还搞这种小心眼，窝里斗，是非常不好的事情，必须牢记！
而后一个小时 WA 了一发，在 3 分钟后过了，原因是少了一个讨论：当环上有两个相邻的无叶子节点时，可以选择两个环上的点。
然后和 Imakf 讨论 K ，在会做后上机，一个半小时开 WA ，15 分钟后过掉。
原因：
- 向上取整写成向下取整。
- 应该在原数组二分而不是前缀和数组。
两个小时队友过 K 。半个小时后队友过 G ，我看 E ，发现是 SB 题。
期间队长和我在和别人聊天，记大过。
然后我上 E ，期间因为公式写错，WA 了三发，然后又因为 1e9 * 10 爆了 int ，WA 了一发，总计四发，警钟长鸣。
三个小时过了。
队友写 J ，我和队长讨论 D ，其实没有讨论，队长直接把 D 秒了，然后我处理做法细节。
四个小时队友 J TLE 了，我上去写 D ，四个半小时，D,J 都过了。
最后战 A 失败，遗憾离场。
我犯的错误：
- 因为不想写题而不参与讨论。
- 比赛时和别人聊天。
- E 不推好公式就上机。
- 没有听队长 A 的吹逼，以为边际距离和贪心没有关系，于是忽略队长讲的话，但是没想到是重要观察，导致我在最后半小时处于完全无用的状态。
队长的错误：
- 比赛时和别人聊天。
- 玩手机。
Imakf 的错误：
- 多开，但是声称是为了弥补今天队友聊天所损失的时间，因此可以理解，不算大的错误。
部分题解：
I
枚举一下因子，时间复杂度：$O(V\log^2{V})$
但是能不能优化呢？能，考虑优化掉 gcd 的时间。
设 $x$ 是 $y$ 的因子，且 $z=x\bigoplus y < y$ ，那么考虑什么时候：
首先，$x$ 整除 $y-z$ 是必要条件，而 $y-z\le x$ 且等号成立当且仅当 $y$ 的二进制完全覆盖 $x$ ，故必要条件是 $y-z=x$ ，注意到这也是充分的。
所以我们得到一个充要条件：$y-z=x$ 。
当然，同时注意到因为 $y-z\le x$ ，故 $gcd(y,z)\le x$ ，所以显然 $x$ 整除于 $z$ 也是一个充要条件。
用哪个都行，时间复杂度：$O(V\log{V})$
跟题解差不多。
C
首先把基环树想象成一堆树，然后把根用环连起来。
那么如果一个点被选了，显然往叶子走不劣，不能往叶子走则子树里面有别的被选点，故其祖先及环上其他树一定没有被选，这个时候把这个点往环上移动更优。
综上，一定存在一个最优方案，使得选择的点要么在叶子，要么在环上。
严谨证明就：先选择环上有点的最优方案，没有就任选一个最优方案，根据上述讨论，这样选择后一定可以把不在环上的点拖到叶子上去，就证完了。
然后如果一个环上的节点被选了，若其所在的树有除了他以外的节点，一定可以不选他，选择其所在树的所有叶子，不劣，所以环上选择的点都是所在树大小 $=1$ 的点。
下面为了方便，将不在环上的叶子节点才叫叶子节点。
于是我们不妨猜测，直接选所有叶子节点就是最优的，不妨讨论环上有多少个节点被选了，显然 $\le 3$。
- $3$ 个节点，显然不能选任何叶子节点，显然有叶子节点一定可以踢掉环上一个叶子节点且不劣。
- $2$ 个节点，显然环上由这两个节点切成的两部分不能同时选叶子节点，故如果两边都有叶子节点，显然再从环上踢掉一个节点更优，如果两边不是同时有叶子，显然可以选择所有的叶子。
- $0/1$ 个节点，显然可以选择所有的叶子节点。
综上，选择所有叶子节点，然后讨论一下环上可以再选多少个节点就行了。
时间复杂度：$O(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
68
69
70
71
72
73
74
75
76
77
| #include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
struct node{
int y, next;
}a[N * 2]; int len, last[N];
void ins(int x, int y){a[++len] = {y, last[x]}; last[x] = len;}
int v[N], sta[N], top;
int dfs1(int x, int fa){
v[x] = 1;
for(int k = last[x]; k; k = a[k].next){
int y = a[k].y;
if(y == fa) continue;
if(!v[y]){
int z = dfs1(y, x);
if(z){
if(z > 0){
sta[++top] = x;
if(z == x) z = -1;
}
return z;
}
}
else if(v[y] == 1){
sta[top = 1] = x;
return y;
}
else assert(false);
}
v[x] = -1;
return 0;
}
bool leaf[N];
void dfs2(int x, int fa){
bool bk = 0;
for(int k = last[x]; k; k = a[k].next){
int y = a[k].y;
if(y == fa || v[y]) continue;
dfs2(y, x);
bk = 1;
}
if(!bk) leaf[x] = 1;
}
int main(){
int T;
cin >> T;
while(T--){
cin >> n;
for(int i = 1; i <= n; i++){
int x, y;
cin >> x >> y;
ins(x, y);
ins(y, x);
}
assert(dfs1(1, 0) == -1);
memset(v, 0, sizeof(v));
for(int i = 1; i <= top; i++) v[sta[i]] = 1;
for(int i = 1; i <= top; i++) dfs2(sta[i], 0);
int cnt = 0, cnt2 = 0;
for(int i = 1; i <= n; i++){
if(!v[i] && leaf[i]) cnt++;
if(v[i] && leaf[i]) cnt2++;
}
int add = 0;
sta[top + 1] = sta[1];
for(int i = 1; i <= top; i++){
if(leaf[sta[i]] && leaf[sta[i + 1]]) add = 2;
else if(leaf[sta[i]]) add = max(add, 1);
}
cnt += max(add, 3 - (top - cnt2));
cout << cnt << "\n";
len = 0;
for(int i = 1; i <= n; i++) last[i] = v[i] = leaf[i] = 0;
}
return 0;
}
|
M
Imakf 告诉我个性质，找最大值是一定是一个连续段，原因是固定最大值，把小值移动上来一定不劣。
那么固定右端点，左端点可以二分。
而且长度本身显然可以二分，扔掉最小值显然不劣。
现在问题是怎么确定一个数字会不会被选。
注意到包含某个数字的方案一定也是要么是一个连续段，要么除了他是个连续段，所以直接枚举最大值，对于最大值而言，最小值能是的数值也能二分，用前缀和处理一下就行了。
时间复杂度：$O(n\log{V})$
E
不是怎么开始推式子了：
这不解个方程就行了？
不知道出这道题目的目的是啥。
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<bits/stdc++.h>
using namespace std;
typedef long double LD;
const int N = 1e5 + 5;
int C, n;
int main(){
int T;
cin >> T;
while(T--){
cin >> C;
cin >> n;
LD l = 0, r = 1e18;
for(int i = 1; i <= n; i++){
LD x, y;
cin >> x >> y;
LD a = 10 * x, b = - 2.0 * C * C, c = 10 * x + y / x * 2 * C * C;
LD delta = b * b - 4 * a * c;
assert(delta >= 0);
LD ll = (- b - sqrt(delta)) / (a + a), rr = (- b + sqrt(delta)) / (a + a);
assert(ll <= rr && rr <= 1e18);
l = max(l, ll);
r = min(r, rr);
}
cout << fixed << setprecision(3) << (l + r) / 2 << "\n";
}
return 0;
}
|
D
显然任何一个最优方案都不会改变强连通内部的边，证明：考虑一个方案，然后把其中一个强连通内的边还原，对于 $x\to y$ 的路径而言，找到第一个和最后一个在这个强连通上的点，将中间的部分换成现在的路径，显然仍然联通，把所有强连通还原即可。
首先强连通缩点，然后把拓扑序搞出来，$a_{1},…,a_{m}$，。
考虑最后一个块 $a_{m}$，其一定会改变一条和前面的连边，考虑改完以后会怎样。
- 如果连向的不是 $a_{m-1}$ ，或者两者的大小有一个不为 $1$ ，改完这条边后这一段变成一个强连通块，变成一个全新的问题。
- 如果连向的是 $a_{m-1}$ ，且两者的大小都为 $1$ ，则有 $a_{m-1},a_{m}$ 调换顺序，接着考虑 $a_{m-1}$ ，显然改变一条向前的连边，而且一定不会是和 $a_{m}$ 的（不会改变一条边两次），而显然这条边能让这一段变成一个强连通块，和上面一样，是一个新的问题。
显然，到一个局面下，一定是前缀和原问题一样，后缀缩成一个强连通块，按照上述过程接着考虑这个全新的问题，注意到这是一个 dp ，可以转移，做完了。
时间复杂度：$O(n^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
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
108
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e3 + 5;
struct node{
int y, next;
}a[N * N]; int len, last[N];
void ins(int x, int y){a[++len] = {y, last[x]}; last[x] = len;}
int dfn[N], low[N], ti;
int sta[N], top;
int belong[N], tot;
vector<int> point[N];
void dfs(int x){
dfn[x] = low[x] = ++ti;
sta[++top] = x;
for(int k = last[x]; k; k = a[k].next){
int y = a[k].y;
if(!dfn[y]){
dfs(a[k].y);
low[x] = min(low[x], low[y]);
}
else if(!belong[y]) low[x] = min(low[x], low[y]);
}
if(dfn[x] == low[x]){
++tot;
belong[x] = tot;
point[tot].push_back(x);
while(sta[top] != x) belong[sta[top]] = tot, point[tot].push_back(sta[top--]);
top--;
}
}
int n, v[N][N];
struct Edge{
int val, x, y;
}d[N][N], nxt[N];
bool operator < (Edge x, Edge y){return x.val < y.val;}
bool operator > (Edge x, Edge y){return x.val > y.val;}
int dp[N];
pair<int, Edge> pre[N];
bool work(){
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> v[i][j];
if(v[i][j]) ins(i, j);
}
}
if(n == 2) return 0;
for(int i = 1; i <= n; i++){
if(!dfn[i]) dfs(i);
}
for(int i = 1; i <= tot; i++){
for(int j = 1; j <= tot; j++) d[i][j].val = 2e9 + 1;
dp[i] = 2e9 + 1;
}
dp[1] = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
d[belong[j]][belong[i]] = min(Edge{v[i][j], i, j}, d[belong[j]][belong[i]]);
}
}
if(tot >= 2 && point[1].size() == 1 && point[2].size() == 1){
for(int i = 3; i <= tot; i++){
if(1ll * d[1][2].val + d[2][i].val < 1ll * d[1][i].val) d[1][i] = Edge{d[1][2].val + d[2][i].val, d[2][i].x, d[2][i].y};
}
}
for(int i = 1; i <= tot; i++){
for(int j = i + 1; j <= tot; j++){
if(i == 1) nxt[j] = d[i][j];
else nxt[j] = min(nxt[j], d[i][j]);
}
for(int j = i + 1 + (i == 1 && point[1].size() == 1 && point[2].size() == 1); j <= tot; j++){
if(1ll * dp[j] > 1ll * dp[i] + nxt[j].val){
dp[j] = dp[i] + nxt[j].val;
pre[j] = {i, nxt[j]};
}
}
}
assert(dp[tot] != 2e9 + 1);
return 1;
}
int main(){
int T;
cin >> T;
while(T--){
if(!work()) cout << "NO\n";
else if(tot == 1) cout << "YES\n0 0\n";
else {
cout << "YES\n";
vector<pair<int, int> > ans;
int now = tot;
while(now > 1){
auto [state, use] = pre[now];
auto [val, x, y] = use;
ans.push_back({x, y});
now = state;
}
if(belong[ans.back().second] == 2) ans.push_back({point[2][0], point[1][0]});
cout << ans.size() << " " << dp[tot] << "\n";
for(auto [x, y] : ans) cout << x << " " << y << "\n";
}
for(int i = 1; i <= n; i++) dfn[i] = low[i] = belong[i] = last[i] = 0;
for(int i = 1; i <= tot; i++) point[i].clear();
len = tot = ti = 0;
assert(!top);
}
return 0;
}
|
A
还没补。
