CodeForces 1213F (强联通分量分解+拓扑排序)
2024-10-08 04:30:43
•题意
给你两个数组 p,q ,分别存放 1~n 的某个全排列;
让你根据这两个数组构造一个字符串 S,要求:
(1)$\forall i \in [1,n-1],S_{pi}\leq S _{pi+1} ,\forall i \in [1,n-1],S_{qi} \leq S _{qi+1}$
(2)字符串 S 至少包含 k 个不同的小写字母;
•思路
类似于牛客第五场的H
不过由于这个不知道字母是什么,需要利用强联通分解,
把属于同一个强联通块的位置置于同一个字母,
然后根据前后关系建图连边
•代码
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof a)
const int maxn=2e5+;
int n,m;
int a[maxn];
struct Edge
{
int to,next;
}G[maxn*];
int head[maxn],cnt;
void addEdge(int u,int v)
{
G[++cnt].to=v;
G[cnt].next=head[u];
head[u]=cnt;
} int col[maxn];
struct SCC///强联通分量分解
{
bool vis[maxn];
vector<int> vs; void DFS(int u)
{
vis[u]=true;
for(int i=head[u];i;i=G[i].next)
{
int v=G[i].to;
if(!(i&)||vis[v])
continue;
DFS(v);
}
vs.push_back(u);
} void REDFS(int u,int k)
{
vis[u]=true;
col[u]=k;
for(int i=head[u];i;i=G[i].next)
{
int v=G[i].to;
if((i&)||vis[v])
continue;
REDFS(v,k);
}
} int scc()
{
vs.clear();
mem(vis,false);
for(int i=;i<=n;i++)
if(!vis[i])
DFS(i); mem(vis,false);
int k=;
for(int i=vs.size()-;i>=;i--)
if(!vis[vs[i]])
REDFS(vs[i],++k); return k;
}
}_scc; Edge newG[maxn*];
int head2[maxn];
void addnew(int u,int v)
{
newG[++cnt].to=v;
newG[cnt].next=head2[u];
head2[u]=cnt;
}
int Indu[maxn];
char ch[maxn];
queue<int >q;
void topsort(int k)///拓扑排序
{
while(!q.empty())
q.pop();
for(int i=;i<=k;i++)
if(!Indu[i])
q.push(i); int now=;
while(!q.empty())
{
int u=q.front();
ch[u]='a'+now;
///>=m个不同字母,那就正好m个,后面的都置为同一个
if(now<m-)
now++;
q.pop();
for(int i=head2[u];i;i=newG[i].next)
{
int v=newG[i].to;
Indu[v]--;
if(!Indu[v])
q.push(v);
}
}
}
int main()
{
cin>>n>>m;
for(int i=;i<=;i++)
{
for(int j=;j<=n;j++)
cin>>a[j];
for(int j=;j<=n-;j++)
{
addEdge(a[j],a[j+]);
addEdge(a[j+],a[j]);
}
}
int k=_scc.scc();
if(k<m)
puts("NO");
else
{
puts("YES");
cnt=; ///缩点,把每一个联通快看做一个点
///利用点col[i]之间的关系建图,跑拓扑序
for(int u=;u<=n;u++)
{
for(int i=head[u];i;i=G[i].next)
{
int v=G[i].to;
if(!(i&)||col[u]==col[v])
continue;
addnew(col[u],col[v]);
Indu[col[v]]++;
}
}
topsort(k); for(int i=;i<=n;i++)
cout<<ch[col[i]];
}
}
最新文章
- 也来谈谈wap端瀑布流布局
- 【GoLang】GoLang 错误处理 -- 异常处理思路示例
- 检查C++内存泄露
- Mysql 组合查询 UNION 与 UNION ALL
- python - 类成员修饰符
- [妙味DOM]第四课:Event-事件详解2
- Hadoop集群的JobHistoryServer详解(转载)
- 从Excel获取请求体
- wx支付
- 朱晔的互联网架构实践心得S1E8:三十种架构设计模式(下)
- P1908 逆序对
- asp.net mvc session锁问题
- 2018 ACM 网络选拔赛 沈阳赛区
- 《EMCAScript6入门》读书笔记——24.编程风格
- 【hdoj_1865】1sting(递推+大数)
- HDU 5642 King&#39;s Order 动态规划
- easyui内嵌iframe问题解决
- python-memcached模块
- Intent跳转系统的应用
- Amr and Chemistry