2020ACM-ICPCnanjing 南京站题解（1013）
整理的算法模板合集：
A. 构造D. 图论E. 构造，爆搜F. 期望，三分H. 抽屉原理，爆搜打表，组合计数I. 计算⼏何J. 博弈论，吉司机线段树K. 数论，签到L. 思维，签到
M. 树上背包 A 、Ah, It’s Yesterday Once More
Problem
对于给定的 的⽅格， 代表障碍， 代表袋⿏。有⼀串随机⽣成的长为 的指令，仅包含 字符，分别表⽰将所有袋⿏同时向某个⽅向移动（若能移动，即不经过障碍、不超出⽅格范围）。现要求构造⼀个 ⽅格图，使得对于随机⽣成的 串指令，⾄少有 个满⾜执⾏后，所有袋⿏不都在同⼀个⽅格。要求构造的袋⿏⽅格连通、且不含环。 。
Solution
我们只需要执⾏ 的指令执⾏即可，也就是每只袋⿏⾄少有⼀个⽅向是墙，所以我们可以构造⼀个不对称的路径，以及⼀些分岔路⼝，例如⼀些 Z 字形路径。注意袋⿏们必须连通以及不能有环。
O (n )
2n ×m 015×104LRUD n ×m 5001251≤n ,m ≤2041
#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;
}
D 、Degree of Spanning Tree
Problem
给出⼀个⽆向图，寻它的⼀棵⽣成树，要求⽣成树上每个点的度数都要⼩于等于 。
Solution
⾸先随便到⼀棵⽣成树，寻它度数最⼤的点，在所有节点中，度数⼤于 的节点最多只有⼀个，若不到直接输出，到了则令其为根节点，对所有不在⽣成树上的边进⾏枚举，若这条边的起点终点在树上的lca是根节点，则说明这条边的加⼊可以令根节点度数-1，但是在两个点都是根节点的⼉⼦节点的情况下，会令选择的另⼀边的节点度数+1，所以在删边加边的过程中要判断是否会导致其他节点度数⼤ 于 。
动态加边删边求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;
2n
2n
2n
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;
difint 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());
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;
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;
}
E 、Evil Coordinate
Problem
在⼀个直⾓坐标系中，给定起点 ，⼀个障碍 以及⼀串长度为 的指令，仅包含 字符，分别表⽰向左右上下移动，请你调整指令顺序让移动过程不经过 ，有解输出指令字符，⽆解输出 。
。
Solution
开始想的是左右⾛完，然后上下，发现可以先上下再左右，然后⼜发现反例，然后也可以先左再上再下再右，明⽩了，所有的⽅向排列⼀共有 种，直接求全排列，然后对于每⼀个排列，分别判断即可。
#include <bits/stdc++.h>
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;
bool cal (int x ,int y , int l ,int r ,int u , int d ,vector <int > v )
{
string res ;
for (int i = 0;i < v .size ();++i ){
if (v [i ] == 1) while (l --) res .push_back ('L');
if (v [i ] == 2) while (r --) res .push_back ('R');
if (v [i ] == 3) while (u --) res .push_back ('U');
if (v [i ] == 4) while (d --) res .push_back ('D');
}
int flag = 0;
int nx = 0,ny = 0;
for (int i = 0;i < res .size ();++i ){
if (res [i ] == 'L') nx --;
if (res [i ] == 'R') nx ++;(0,0)(m ,m )x y n L / R / U / D (m ,m )x y impossible 1≤n ≤10,−10≤59m ,m ≤x y 10,n ≤9∑i 1064!=24
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议