昨晚 CF D
2026-07-17 09:14:17
发布于：广东
18阅读
0回复
0点赞
这场真是酣畅淋漓，让我回想起了第一次切 D 的那场。
2h 后还在过题，真是神了。
难度不会评（
D1
为方便表示，记“非负”为正。
注意到 ，则每个点都有连向自己的一条边。我们又知道 的正负性与 相同，所以这其实就是告诉我们每个点的点权符号，让你判断这个合不合法。
我们看到其它边。以 的边为例， 的边同理。
考虑建个新图，表示 的大小关系。
- 若 ，则 一定 ，这条边没有用。
- 若 ，则 一定 ，与这条边矛盾，不合法。
- 若 ，则移个项，，也就是说，这个约束其实代表 。然后呢？我们将新图中 连向 。
- 同理。
注意到，新图中的边两点一定满足一正一负一正一负，而且正常来说这是个 DAG。如果出现了环，显然有矛盾。
然后我们随便拓扑排序一下，就可以求出任意解了。
namespace cjdst{
void solve(){
int n, m;
std::cin >> n >> m;
struct node{
int x, y, z;
};
std::vector <node> edge;
std::vector <int> f(n + 5);
for(int i = 1; i <= m; i++){
int x, y, z;
std::cin >> x >> y >> z;
if(y == z){
f[y] = x;
}else{
edge.push_back({x, y, z});
}
}
std::vector <std::vector <int>> v(n + 5);
std::vector <int> in(n + 5), ans(n + 5);
for(auto i:edge){
if(f[i.y] != i.x && f[i.z] != i.x){
std::cout << "NO\n";
return;
}
if(f[i.y] == i.x && f[i.z] == i.x) continue;
if(f[i.y] == i.x){
v[i.z].push_back(i.y);
in[i.y]++;
}else{
v[i.y].push_back(i.z);
in[i.z]++;
}
}
int ct = 0;
std::queue <int> q;
for(int i = 1; i <= n; i++){
if(!in[i]) ans[i] = (f[i] == 1 ? 0 : -1), q.push(i);
}
while(!q.empty()){
int head = q.front();
ct++, q.pop();
for(int i:v[head]){
if(f[i] == 1){
ans[i] = std::max(ans[i], -ans[head]);
}else{
ans[i] = std::min(ans[i], -ans[head] - 1);
}
if(!(--in[i])) q.push(i);
}
}
if(ct < n){
std::cout << "NO\n";
return;
}
std::cout << "YES\n";
for(int i = 1; i <= n; i++){
std::cout << ans[i] << ' ';
}
std::cout << '\n';
}
}
时间复杂度：。
D2
现在， 的符号未知了。但是如果你能求出一种可能的 符号方案，那么就可以套 D1 了。
显然，对于一条 的边，一定需要满足 或 ；对于一条 的边，一定需要满足 或 。
所以，我们可以考虑通过这个跑一个 2-SAT。
但这么做为什么是对的？不会有些 2-SAT 有解，但原问题无解吗？
我们看回 D1 是如何判断不合法的。
- 同号但与连向 的边异号：你都跑 2-SAT 了，这种情况还能发生？
- 建的新图有环：这个是有可能 2-SAT 有解的，但是思考一下，这种情况一定是原来的边满足形如 ，这种情况下无论如何构造都不可能满足的，所以大胆输出
NO即可。
所以跑 2-SAT 即可。
fun fact：我场上不会 2-SAT，现场学的。所以这题是我切的第一道 2-SAT 题。
namespace cjdst{
void solve(){
int n, m;
std::cin >> n >> m;
struct node{
int x, y, z;
};
std::vector <node> edge;
std::vector <std::vector <int>> v0(n * 2 + 5);
for(int i = 1; i <= m; i++){
int x, y, z;
std::cin >> x >> y >> z;
if(y != z) edge.push_back({x, y, z});
x &= 1;
v0[(y + (x ^ 1) * n)].push_back(z + x * n);
v0[(z + (x ^ 1) * n)].push_back(y + x * n);
}
std::vector <int> dfn(n * 2 + 5), low(n * 2 + 5), scc(n * 2 + 5);
std::vector <int> stack;
int curdfn = 0, curscc = 0;
auto tarjan = [&](auto &&self, int cur) -> void{
curdfn++;
low[cur] = dfn[cur] = curdfn;
stack.push_back(cur);
for(int i:v0[cur]){
if(scc[i]) continue;
if(!dfn[i]) self(self, i);
low[cur] = std::min(low[cur], low[i]);
}
if(low[cur] == dfn[cur]){
curscc++;
while(stack.back() != cur){
scc[stack.back()] = curscc;
stack.pop_back();
}
scc[stack.back()] = curscc;
stack.pop_back();
}
};
for(int i = 1; i <= n * 2; i++){
if(!scc[i]) tarjan(tarjan, i);
}
std::vector <int> f(n + 5);
for(int i = 1; i <= n; i++){
if(scc[i] == scc[i + n]){
std::cout << "NO\n";
return;
}
f[i] = (scc[i] > scc[i + n] ? 1 : 2);
}
std::vector <std::vector <int>> v(n + 5);
std::vector <int> in(n + 5), ans(n + 5);
for(auto i:edge){
if(f[i.y] == i.x && f[i.z] == i.x) continue;
if(f[i.y] == i.x){
v[i.z].push_back(i.y);
in[i.y]++;
}else{
v[i.y].push_back(i.z);
in[i.z]++;
}
}
int ct = 0;
std::queue <int> q;
for(int i = 1; i <= n; i++){
if(!in[i]) ans[i] = (f[i] == 1 ? 0 : -1), q.push(i);
}
while(!q.empty()){
int head = q.front();
ct++, q.pop();
for(int i:v[head]){
if(f[i] == 1){
ans[i] = std::max(ans[i], -ans[head]);
}else{
ans[i] = std::min(ans[i], -ans[head] - 1);
}
if(!(--in[i])) q.push(i);
}
}
if(ct < n){
std::cout << "NO\n";
return;
}
std::cout << "YES\n";
for(int i = 1; i <= n; i++){
std::cout << ans[i] << ' ';
}
std::cout << '\n';
}
}
时间复杂度：。
有帮助，赞一个