Circular Spanning Tree
算法本质
思维
题目大意
n个点顺序围成了一个环，给定长度n的01串s，现在玩家需要连接n-1条边，需要满足：
- 形成连通所有点的树结构
- 所有的边的交点只能在节点上
s[i]是01分别表示第i个点的度是偶数、奇数
输出连接方案
思路推演
核心在于奇偶
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
string s;
cin>>n>>s;
int cnt = count(s.begin(), s.end(), '1');
if (cnt==0 || cnt%2)
{
cout<<"NO"<<endl;
return;
}
vector<pair<int, int>> ans;
int p=s.find_first_of('1'); // 找到一个字符作为起点
vector<int> cod;
for (int l=p, r; l<p+n; l=r)
{
r = l+1;
while (s[r%n]=='0')
{
ans.push_back({(r-1)%n, r%n});
r++;
}
cod.push_back((r-1)%n);
}
for (int i=1; i<cod.size(); i++)
ans.push_back({cod[0], cod[i]});
cout<<"YES"<<endl;
for (auto [u,v]:ans)
cout<<u+1<<' '<<v+1<<endl;
return;
}Unordered Swaps
算法本质
思维、图论基础
题目大意
给定长度n排列p[]，Alice执行了m次交换操作使得p[]升序（保证m是最小操作次数），每次操作记录交换元素下标。
现在将这m次操作乱序后给出，玩家需要恢复其顺序使其合法。（恢复的顺序可以使得p[]升序）
思路推演
对于排列交换、形式与[1, 2, ... , n]有关的，都可以将其分组。
分组的方式：
对于任意p来说。a[p]、a[ a[p] ]在同一集合，且可以视作a[p] --> a[ a[p] ]每组会必然形成一个环
利用分组进行观察，使其升序的本质是每个元素单独一组。
为了尽可能少的交换，我们需要保证每次交换操作都是选择两个同组的元素操作，这样可以将一个组打破成两个组。
难点在于，操作是固定的，我们是分配其顺序，需要保证所有的操作都是打破组，或者说所有操作的元素都是同组的。
那么，对于一次x y的交换来说，其对于环来说的意义是什么。
在组里，元素值和下标随时都在转换，它既是元素值、也是另一元素的下标！
模拟：
a[]: 2 4 1 5 3
这个数组仅会形成一个环：2 --> 4 --> 5 --> 3 --> 1
如果交换(2, 5)则会变成：2 3 1 5 4
即：2 --> 3 --> 1 和 5 --> 4多次使用可以发现，选择(x, y)，则会以x y为起点分裂出两个环。
如果有两个(x, y1)和(x, y2)，则显然我们需要先使用举例x较远的y，这样至少对于有x的操作来说，其不会犯错。
进一步思考可以发现，对于任意两个交换操作，若其在同一环上出现，则其仅有包含、相离这两种情况，不会出现存在部分交集的情况。
否则其就不符合使用最小次数使得p[]升序。
于是我们就可以随意组合其他的操作顺序。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n>>m;
vector<int> a(n+5);
vector<vector<pair<int, int>>> g(n+5);
for (int i=1; i<=n; i++)
cin>>a[i];
for (int i=1; i<=m; i++)
{
int u, v;
cin>>u>>v;
g[u].push_back({v, i});
g[v].push_back({u, i});
}
vector<int> vis(n+5), pos(n+5); // vis[x]记录元素值x是否使用，pos[x]记录元素值x在环的相对位置
vector<vector<int>> g2(m+5); // g2以id1为key值记录边的topo图
vector<int> ru(m+5), ans; // g2图的入度
for (int i=1; i<=n; i++)
{
int x = a[i];
if (vis[x]) continue;
vector<int> v; // v[]用于记录当前环的元素值
set<int> cod; // cod用于维护当前轮次g2图的入度0的id
int siz=0;
while (vis[x]==0)
{
vis[x] = 1;
pos[x] = siz++; // 每个环的下标
v.push_back(x);
x = a[x];
}
for (int u:v) // 依次处理环的每个值
{
sort(g[u].begin(), g[u].end(),
[&](const pair<int,int> &a, const pair<int,int> &b) { // 距离u相对远的放在前
int v1=a.first, v2=b.first;
return (pos[v1] - pos[u] + siz) % siz < (pos[v2] - pos[u] + siz) % siz;
});
for (int j=1; j<g[u].size(); j++)
{
int id1=g[u][j-1].second, id2=g[u][j].second;
g2[ id1 ].push_back(id2);
ru[id2]++;
}
if (g[u].size()) // 记录可能的入度0的id
cod.insert(g[u][0].second);
}
queue<int> q;
for (int id:cod)
if (ru[id]==0)
q.push(id);
while (q.size())
{
int u=q.front(); q.pop();
ans.push_back(u);
for (int v:g2[u])
if (--ru[v]==0)
q.push(v);
}
}
for (int x:ans)
cout<<x<<" ";
cout<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)