兔兔 的 题解 —— 年功序列


年功序列

题目描述

在虚拟国度里多了很多 Virtual oier,为了树立对后辈的威信,从第

11

1 个 Virtual oier 开始的 oier 们搞起了年功序列的制度。
虚拟国度的创始人 oier Chtholly 感觉非常有趣,于是他决定观测

11

1 到

nn

n 这些人,他观测到了一些有趣的现象:虚拟国度里有一些凳子,如果

aa

a 是 的先辈则 能在 前面得到凳子
Chtholly的观测可以构成

mm

m 个序列,每个序列有

kk

k 个元素

a1,a2,a3,,aka_{1}, a_{2}, a_{3}, ······, a_{k}

a1​,a2​,a3​,⋅⋅⋅⋅⋅⋅,ak​。表示在

aia_{i}

ai​ 有凳子前

a1,a2,a3,,ai1a_{1}, a_{2}, a_{3}, ······, a_{i – 1}

a1​,a2​,a3​,⋅⋅⋅⋅⋅⋅,ai−1​ 必须有凳子。(

ai1a_{i – 1}

ai−1​ 是

aia_{i}

ai​ 的前辈)
例如 k = 3 时:

a=123a = 1,2,3

a=1,2,3,表示

33

3 有凳子前

1,21, 2

1,2必须都有凳子,

22

2 有凳子前

11

1 必须有凳子。
但 Chtholly 年纪大了记忆力未必好,如果第

ii

i 个序列与前

i1i – 1

i−1 个序列冲突的话那么就只需要考虑前

i1i – 1

i−1 个序列就好了。(忽略第

ii

i 个序列)
Chtholly 希望知道

11

1 到

nn

n 个人的年功序列的最小字典序。

输入格式

第一行两个数

n,mn, m

n,m
接下来 m 行每行第一个数为

kk

k,接下来

kk

k 个数为这次观测构成的序列

输出格式

输出

nn

n 个数构成的最小字典序。

样例
样例输入

4 3
3 1 2 3
2 4 2
3 3 4 1

样例输出

1 4 2 3

样例解释

第三个观测序列与前两个观测序列冲突不考虑,前两个观测序列可以构成

11

1

44

4

22

2

33

3 或者

44

4

11

1

22

2

33

3 这两个序列,字典序小的为

11

1

44

4

22

2

33

3。

数据范围与提示

3030

30%的数据,

n10,m4n \leq 10, m \leq 4

n≤10,m≤4

5050

50%的数据,

n10000,m5000n \leq 10000, m \leq 5000

n≤10000,m≤5000

100100

100%的数据,

n100000,m50000,knn \leq 100000, m \leq 50000, k \leq n

n≤100000,m≤50000,k≤n

分析

这道题看似很难、很复杂,其实是道简单的拓扑排序。
我们可以把

a[1]a[1]

a[1] ~

a[i1]a[i – 1]

a[i−1] 看成

a[i]a[i]

a[i] 的入度。(下面也这样说明)
但是我们只需要把

a[i1]a[i – 1]

a[i−1] 看成

a[i]a[i]

a[i] 的入度即可。

((

( 因为我们求到

a[i1]a[i – 1]

a[i−1] 的时候,前面的

a[1]a[1]

a[1] ~

a[i2]a[i – 2]

a[i−2] 一定是求过的

((

( 不然不会求到

a[i1]a[i – 1]

a[i−1] 的

))

)

))

)
——但是这道题的难点在于冲突的情况

思路

我们先输入第

ii

i 组的数据 ,把 这组数据 及 以前的数据(没有舍弃的数据) 进行拓扑排序,再判断是否出现了环:

如果出现了,就把 这组数据舍弃 (同时也要把 新加进来的 入度 和 每个点的入度个数 还原)。

代码

正解代码如下:

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 1e5 + 5;
int N, M, K;
int num[MAXN];
vector<int> ans, E[MAXN];
int in[MAXN]; // 每个人的前辈个数
bool vis[MAXN];
struct node
{
int numn;
node(){}
node (int n) { numn = n; }
friend bool operator < (node a, node b) { return a.numn > b.numn; } // 字典序排序
};

void toposort() // 拓扑排序
{
priority_queue<node> q;
for (int i = 1; i <= N; i++)
if (in[i] == 0) q.push(node(i)); // 不一定每个人都有前辈, 所以不需要判断每个人是否被输入
while (!q.empty())
{
int u = q.top().numn; q.pop();
ans.push_back(u);
int siz = E[u].size();
for (int i = 0; i < siz; i++)
{
int v = E[u][i];
--in[v];
if (in[v] == 0) q.push(node(v));
}
}
}

bool check(int u) // 判断是否产生环
{
int siz = E[u].size();
for (int i = 0; i < siz; i++)
{
int v = E[u][i];
if (vis[v]) return 0;
vis[v] = 1;
if (!check(v)) return 0;
}
vis[u] = 0;
return 1;
}

int main()
{
scanf("%d %d", &N, &M);
for (int i = 1; i <= M; i++)
{
scanf("%d", &K);
for (int j = 1; j <= K; j++)
{
scanf("%d", &num[j]);
if (j == 1) continue; // 第1个人没有前辈
E[num[j - 1]].push_back(num[j]), ++in[num[j]];
}
memset(vis, 0, sizeof(vis));
vis[num[1]] = 1;
if (!check(num[1])) // 为什么从第1人开始判断, 就留给读者自己思考了
{
// 还原
for (int j = 2; j <= K; j++)
{
// 删除这个入度
--in[num[j]];
E[num[j - 1]].pop_back();
}
break;
}
}
toposort();
int siz = ans.size();
for (int i = 0; i < siz; i++)
printf("%d ", ans[i]);
return 0;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

兔兔 的 题解 —— 年功序列

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 兔兔 的 题解 —— 年功序列
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏