2020 ACM - ICPC nanjing 南京站 题解（10 / 13）_[icpc2020 nanjing r] ah, it's yesterday once more

整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

---

比赛链接：https://codeforces.com/gym/102992

• A. 构造
• D. 图论
• E. 构造，爆搜
• F. 期望，三分
• H. 抽屉原理，爆搜打表，组合计数
• I. 计算几何
• J. 博弈论，吉司机线段树
• K. 数论，签到
• L. 思维，签到
• M. 树上背包 $O(n^2)$

A、Ah, It’s Yesterday Once More

Problem

对于给定的 $n\times m$ 的方格，$0$ 代表障碍，$1$ 代表袋鼠。有一串随机生成的长为 $5\times 10^4$的指令，仅包含 $\text{LRUD}$ 字符，分别表示将所有袋鼠同时向某个方向移动（若能移动，即不经过障碍、不超出方格范围）。现要求构造一个 $n\times m$ 方格图，使得对于随机生成的 $500$ 串指令，至少有 $125$ 个满足执行后，所有袋鼠不都在同一个方格。要求构造的袋鼠方格连通、且不含环。

$1\le n,m\le 20$。

Solution

我们只需要执行 $\frac{1}{4}$ 的指令执行即可，也就是每只袋鼠至少有一个方向是墙，所以我们可以构造一个不对称的路径，以及一些分岔路口，例如一些 Z 字形路径。注意袋鼠们必须连通以及不能有环。

#include<bits/stdc++.h>
using namespace std;

int main(){
   
    char ans[21][21] = {
   
    "20 20",
    "11011111011111011111",
    "10110100110100110100",
    "11101101101101101101",
    "10011011011011011001",
    "10110110110110110111",
    "01101101101101101101",
    "11011011011011011011",
    "10110110110110110110",
    "11101101101101101101",
    "10011011011011011001",
    "10110110110110110111",
    "01101101101101101101",
    "11011011011011011011",
    "10110110110110110110",
    "11101101101101101101",
    "10011011011011011001",
    "10110110110110110111",
    "01101101101101101101",
    "01011001011001011001",
    "11110111110111110111",
    };
    for(int i = 0; i <= 20; ++i){
   

        cout << ans[i] << endl;
    }
    return 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

D、Degree of Spanning Tree

Problem

给出一个无向图，寻找它的一棵生成树，要求生成树上每个点的度数都要小于等于 $\frac{n}{2}$ 。

Solution

首先随便找到一棵生成树，寻找它度数最大的点，在所有节点中，度数大于 $\frac{n}{2}$ 的节点最多只有一个，若找不到直接输出，找到了则令其为根节点，对所有不在生成树上的边进行枚举，若这条边的起点终点在树上的lca是根节点，则说明这条边的加入可以令根节点度数-1，但是在两个点都是根节点的儿子节点的情况下，会令选择的另一边的节点度数+1，所以在删边加边的过程中要判断是否会导致其他节点度数大于 $\frac{n}{2}$。

动态加边删边求lca实在是不会…但是还好可以用并查集来做，首先将根节点的所有子树各自构成集合，集合祖先为根节点的儿子节点，每次遍历边查询两端点是否在同一集合即可。

Code

#include <bits/stdc++.h>
#define reg register
#define ios ios::sync_with_stdio(false)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const double eps = 1e-10;
const int maxn = 2e5 + 10;
const double pi = acos(-1.0);
const ll mod = 1e9 + 7;

vector<pair<int,int>> es;
map<pair<int,int>,int> mp;
struct Edge{
   
    int to,nxt;
}edges[maxn << 2];

int head[maxn], idx;
int deg[maxn];
void add(int u,int v)
{
   
    edges[idx] = {
   v,head[u]}, head[u] = idx++;
    edges[idx] = {
   u,head[v]}, head[v] = idx++;
}
int pre[maxn];
int chose[maxn];

int fi(int x) {
   return x == pre[x] ? x : pre[x] = fi(pre[x]);}

void dfs(int u,int fa, int sig)
{
   
    pre[u] = sig;
    for(int i = head[u];~i;i = edges[i].nxt){
   
        int v = edges[i].to;
        if(v == fa) continue;
        dfs(v,u,sig);
    }
}

void init(int n,int m)
{
   
    mp.clear();
    es.clear();
    for(int i = 0;i <= n;++i){
   
        head[i] = -1;
        deg[i] = 0;
        pre[i] = i;
    }
    for(int i = 0;i <= m;++i){
   
        chose[i] = 0;
    }
    idx = 0;
}

int main()
{
   
    
    int t;
    scanf("%d",&t);
    while(t--){
   
        int n,m;
        scanf("%d %d",&n,&m);
        init(n,m);
        for(int i = 0;i < m;++i){
   
            int u,v;
            scanf("%d%d",&u,&v);
            if(u > v) swap(u,v);
            es.push_back({
   u,v});
        }
        sort(es.begin(),es.end());
        es.erase(unique(es.begin(),es.end()),es.end());
        m = static_cast<int>(es.size()); // 删除重边自环
        for(int i = 0;i < m;++i){
   
            int u = es[i].first;
            int v = es[i].second;
            mp[{
   u,v}] = mp[{
   v,u}] = i;
            int fu = fi(u),fv = fi(v);
            if(fu != fv){
    
                add(u,v);		//kruskal 建生成树
                pre[fu] = fv;
                deg[u]++;
                deg[v]++;
                chose[i] = 1;
            }
        }
        int flag = 0;
        for(int i = 2;i <= n;++i){
   
            if(fi(i) != fi(1))  flag = 1;
        }
        if(flag) {
   
            puts("No");
            continue;
        }

        int rt = -1;
        for(int i = 1;i <= n;++i){
   
            if(deg[i] > n/2){
   
                rt = i;
                break;
            }
        }
        if(rt == -1){
   
            puts("Yes");
            for(int i = 0;i < m;++i){
   
                if(chose[i]){
   
                    printf("%d %d\n",es[i].first,es[i].second);
                }
            }
            continue;
        }
        for(int i = 1;i <= n;++i) pre[i] = i;
        for(int i = head[rt];~i;i = edges[i].nxt){
   
            dfs(edges[i].to,rt,edges[i].to);
        }
        for(int i = 0;i < m;++i){
   
            if(chose[i]) continue;
            int u = es[i].first, v = es[i].second;
            int fu = fi(u), fv = fi(v);
            if(fu == fv || u == rt || v == rt) continue;
            deg[rt]--;
            deg[u]++;
            deg[v]++;
            deg[fu]--;
            if(deg[u] > n/2 || deg[v] > n/2){
   	//检测是否可行，不可行就恢复
                deg[fu]++;
                deg[fv]--;
                if(deg[u] > n/2 || deg[v] > n/2){
   
                    deg[rt]++;
                    deg[u]--;
                    deg[v]--;
                    deg[fv]++;
                    continue;
                }
                else{
   
                    pre[fv] = fu;
                    chose[i] = 1;
                    chose[mp[{
   rt,fv}]] = 0;
                }
            }
            else{
   
                pre[fu] = fv;
                chose[i] = 1;
                chose[mp[{
   rt,fu}]] = 0;
            }
            if(deg[rt] <= n/2) break;
        }
        if(deg[rt] <= n/2){
   
            puts("Yes");
            for(int i = 0;i < m;++i){
   
                if(chose[i]){
   
                    printf("%d %d\n",es[i].first,es[i].second);
                }
            }
        }
        else puts("No");
        
    }

    return 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
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198

E、Evil Coordinate

Problem

在一个直角坐标系中，给定起点 $(0,0)$，一个障碍 $(m_x,m_y)$ 以及一串长度为 $n$ 的指令，仅包含 $\text{L / R / U / D}$ 字符，分别表示向左右上下移动，请你调整指令顺序让移动过程不经过 $(m_x,m_y)$，有解输出指令字符，无解输出 $\text{impossible}$ 。

1 ≤ n ≤ 1 0 5 , − 1 0 9 ≤ m x , m y ≤ 1 0 9 , ∑ n i ≤ 1 0 6 1\le n \le 10^5, -10^9 \le m_x, m_y \le 10^9, \sum n_i \le 10^6 1≤n≤105,−109≤m