xyq0220

未归档

题解(3)

/ 注册

全部文章 / 未归档（共2篇）

codeforces1213F tarjan缩点+拓扑排序

题意给定两个长度为n的排列p和q，构造一个字符串s满足\(s[p_i]<=s[p_{i+1}]\)和\(s[q_i]<=s[q_{i+1}]\)，且满足字符串中不同字符的个数不少于k。分析建一个有向图，\(p_i\)到\(p_{i+1}\)连一条有向边，\(q_i\)到\(q...

tarjan 拓扑排序

2019-10-23

0 399

Gym-101987 2018-2019 ACM-ICPC, Asia Seoul Regional Contest K-TV Show Game 2-sat，tarjan

题意 \(k\)盏灯，每盏灯有两种颜色R，B。有\(n\)个人，每个人猜三盏灯的颜色，让你求这\(k\)盏灯的颜色，使每个人都至少猜对两盏灯的颜色。分析转化成\(two-sat\)问题，对于每个人若猜错其中一盏灯，那么另外两盏灯的颜色必须猜对，建边，跑\(tarjan\)，输出答案。 C...

2-sat tarjan

2020-07-13

0 678