2020-2021:teams:farmer_john:jjleo:codeforces_round_639_unrated
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:farmer_john:jjleo:codeforces_round_639_unrated [2020/05/07 22:53] jjleo [D] |
2020-2021:teams:farmer_john:jjleo:codeforces_round_639_unrated [2020/05/10 22:07] (当前版本) jjleo [C] |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| =====C===== | =====C===== | ||
| - | * 题意:离 散 数 学，给出$n$个变元和一个由$m$个不等式组成的合取式，每个不等式形如$x_i<x_j$，要求按$1$到$n$的顺序添加$n$个量词（全称量词或存在量词）使得其成为永真式，要求全称量词的数量最少，或判断无解。 | + | * 题意:离 散 数 学，给出$n$个变元和一个由$m$个不等式组成的合取式，每个不等式形如$x_i<x_j$，要求按$1$到$n$的顺序添加$n$个量词（全称量词或存在量词）使得其成为永真式，要求全称量词的数量最**多**，或判断无解。 |
| * 题解:按照不等式建出有向图，如果有环显然无解，因为自己不能小于自己。按照$1$到$n$的顺序遍历每个点，如果这个点能到达的某个点或能到达这个点的某个点已经被访问过了，那么显然这个点不能任意了，否则可以任意。因此先判环，然后建正图和反图，分别dfs即可。注意vis数组对于正图和反图要分别建，比赛的时候合一起就WA了，因为在正图被访问的时候并不能继续访问反图里面能访问的点。 | * 题解:按照不等式建出有向图，如果有环显然无解，因为自己不能小于自己。按照$1$到$n$的顺序遍历每个点，如果这个点能到达的某个点或能到达这个点的某个点已经被访问过了，那么显然这个点不能任意了，否则可以任意。因此先判环，然后建正图和反图，分别dfs即可。注意vis数组对于正图和反图要分别建，比赛的时候合一起就WA了，因为在正图被访问的时候并不能继续访问反图里面能访问的点。 | ||
2020-2021/teams/farmer_john/jjleo/codeforces_round_639_unrated.1588863203.txt.gz · 最后更改: 2020/05/07 22:53 由 jjleo
