Autosynthesis
算法本质
思维、图
题目大意
给定数组a[]，玩家可以顺序圈出任意元素（可以重复圈出某一元素），在某个操作后停止，根据当前局面得到2个数组：
v1[]：由a[]没有圈中的元素值顺序构成v2[]：由玩家圈元素的下标顺序构成
玩家能否使得上面两个数组相等，如果可以输出相等数组信息（任意一个即可），否则输出-1。
思路推演
下标与值需要相等，这种问题的经常套路就是连接当前元素和其值下标的元素。
为了方便思考，笔者的连接方式是反向的，即当前元素值对应的元素作为元素的父节点。
然后在这个基础上思考，有规则：
- 每个点仅存在一个父节点（这比较合理，也是反向连边的原因）
抽象题意：
思考可知，不用理会圈出元素的顺序，可以将圈出的元素看作涂了黑色，黑色点下的子节点会被默认涂成灰色，则需要满足以下条件：
- 黑子节必须有一个儿子灰节点
- 灰节点的父节点必须是黑节点
- 所有点非黑即灰
抽象之后，再次模拟思考，发现如果是链结构，则十分简单，核心难点在于环结构。
先用topo处理链结构，这里需要注意自环的情况。
接着看环情况。
由于规则的限制，有可能一些环的点，必须是黑色，先检查。
如果存在这样的点，就可以topo求出环，然后检查是否可行即可。
如果不存在，则其所有点性质相同，随机指定一个点赋予颜色即可。
赛时因为图写的太少，思路不够清晰（少部分原因在于思路，大部分原因在于图写少了），结果没出来。
（不过即可出来了，也其实有一个小bug）
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int fu[maxn], chu[maxn]; // 父节点、出度
vector<int> g[maxn]; // 仅存儿子节点
int color[maxn]; // 颜色，1代表灰色、2代表黑色
vector<int> tmpv;
set<int> tmpst;
void dfs(int u) // 找环点
{
if (tmpst.count(u))
return;
else
{
tmpv.push_back(u);
tmpst.insert(u);
dfs(fu[u]);
}
}
int getc(int u) // 根据子节点推理颜色（颜色在子节点都涂色才有效）
{
int cnt1=0, cnt2=0;
for (int v:g[u])
{
if (color[v]==1) cnt1++;
if (color[v]==2) cnt2++;
}
return (cnt1>0 ? 2 : 1); // 儿子有灰色，则必黑色，反之黑色
}
inline void solve()
{
cin>>n;
for (int v=1; v<=n; v++)
{
int u=in();
if (u==v) continue;
fu[v] = u;
g[u].push_back(v);
chu[u]++;
}
flag = 1;
// 处理所有的非环点
queue<int> q;
for (int i=1; i<=n; i++)
if (chu[i]==0)
q.push(i);
vector<bool> vis(n+5);
while (q.size()) // topo处理
{
int u=q.front(); q.pop();
vis[u]=1;
color[u] = getc(u);
chu[fu[u]]--;
if (chu[fu[u]]==0 && fu[u]!=0)
q.push(fu[u]);
}
for (int i=1; i<=n; i++) // 检查非环点是否存在冲突
{
if (vis[i] && fu[i]==0 && color[i]!=2)
flag = 0;
}
if (!flag)
{
cout<<-1<<endl;
return;
}
// 处理环上点
for (int i=1; i<=n; i++)
{
if (vis[i]) continue;
tmpv.clear();
tmpst.clear();
dfs(i);
int num=0;
for (int u:tmpv)
{
if (getc(u)==2) // 因为还有儿子，如果2值，说明必须是黑色，如果1值则不一定
{
color[u]=2;
vis[u] = 1;
chu[fu[u]]--;
num++;
}
}
if (num==0) // 保证环有一个点被打开——才能开始topo
{
int u=tmpv.front();
color[u] = 2;
vis[u] = 1;
chu[fu[u]]--;
num++;
}
queue<int> q;
for (int u:tmpv) // 找环上的叶节点
{
if (vis[u]) continue;
if (chu[u]==0)
q.push(u);
}
while (q.size()) // topo跑环
{
int u=q.front(); q.pop();
vis[u]=1;
color[u] = getc(u);
chu[fu[u]]--;
if (chu[fu[u]]==0)
q.push(fu[u]);
}
for (int u:tmpv) // 检查环点是否存在冲突
if (getc(u)!=color[u])
flag = 0;
}
if (!flag)
{
cout<<-1<<endl;
return;
}
vector<int> ans;
for (int i=1; i<=n; i++)
{
if (color[i]==1) // 灰色
ans.push_back(fu[i]);
}
cout<<ans.size()<<endl;
for (int x:ans)
cout<<x<<" ";
cout<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)