P6123 [NEERC 2016] Hard Refactoring 题解-EW帮帮网

题目描述

对于一个变量 x，给出一些约束条件，形如 x≥a，x≤a 这些约束条件之间用||连接，然后你需要将这些约束条件简化，最后输出简化后的约束条件。

输入格式

输入不超过 $10^3$ 行，每行要么是两个用 && 连接的约束条件，要么就是单个的约束条件。

如果一行有两个约束条件，第一个约束条件总是 x≥a 的形式，第二个约束总是 x≤a 的形式。

除了输入的最后一行，每一行末尾都有一个 ||。

并且所有的字符（除了>=，<=，&&，||）之间均由空格隔开，且没有多余的前置、后置空格。

输出格式

输出若干行，表示最简的约束条件的形式（也就是使输出的行数尽量少），其余格式与输入格式保持一致。

输出的若干行可以不按照特定的顺序输出。

特别地，如果对于任意的 x∈[−32768,32767]，x均能满足约束条件，仅输出一行true，反之，若对于任意的 x∈[−32768,32767]，x均不能满足约束条件，仅输出一行false。

输入输出样例

输入 #1

x >= 5 && x <= 10 ||
x >= 7 && x <= 20 ||
x <= 2 ||
x >= 21 && x <= 25 ||
x >= 8 && x <= 10 ||
x >= 100

输出 #1

x <= 2 ||
x >= 5 && x <= 25 ||
x >= 100

说明/提示

对于所有在这一题中出现的数字（包括 x），都 ≥−32768（− $2^{15}$ ）且 ≤32767（ $2^{15}$ −1）。

代码：

#include <bits/stdc++.h>
using namespace std;

struct Iv {
    int a, b;
    Iv(int x, int y) : a(x), b(y) {}
};

vector<string> split(string s) {
    vector<string> res;
    stringstream ss(s);
    string t;
    while (ss >> t) res.push_back(t);
    return res;
}

vector<Iv> merge(vector<Iv> v) {
    if (v.empty()) return {};
    sort(v.begin(), v.end(), [](Iv x, Iv y) { return x.a < y.a; });
    vector<Iv> res;
    res.push_back(v[0]);
    for (size_t i = 1; i < v.size(); ++i) {
        Iv cur = v[i];
        Iv lst = res.back();
        if (cur.a <= lst.b + 1) {
            res.pop_back();
            res.push_back(Iv(lst.a, max(lst.b, cur.b)));
        } else {
            res.push_back(cur);
        }
    }
    return res;
}

bool full(vector<Iv> v) {
    if (v.empty()) return false;
    int cur = -32769;
    for (auto& iv : v) {
        if (iv.a > cur + 1) return false;
        cur = max(cur, iv.b);
        if (cur >= 32767) break;
    }
    return cur >= 32767;
}

vector<string> output(vector<Iv> v) {
    vector<string> res;
    for (auto& iv : v) {
        if (iv.a == -32768) res.push_back("x <= " + to_string(iv.b));
        else if (iv.b == 32767) res.push_back("x >= " + to_string(iv.a));
        else res.push_back("x >= " + to_string(iv.a) + " && x <= " + to_string(iv.b));
    }
    return res;
}
signed main() {
    vector<Iv> v;
    string line;
    while (getline(cin, line)) {
        vector<string> vs = split(line);
        if (!vs.empty() && vs.back() == "||") vs.pop_back();
        if (vs.empty()) continue;
        if (find(vs.begin(), vs.end(), "&&") != vs.end()) {
            if (vs.size() != 7) continue;
            int x = stoi(vs[2]), y = stoi(vs[6]);
            if (x <= y) v.push_back(Iv(x, y));
        } 
		else {
            if (vs.size() != 3) continue;
            int num = stoi(vs[2]);
            if (vs[1] == ">=") v.push_back(Iv(num, 32767));
            else v.push_back(Iv(-32768, num));
        }
    }

    vector<Iv> ans = merge(v);
    if (full(ans)) {
        cout << "true\n";
        return 0;
    }
    if (ans.empty()) {
        cout << "false\n";
        return 0;
    }

    vector<string> out = output(ans);
    for (size_t i = 0; i < out.size(); ++i) {
        cout << out[i];
        if (i != out.size() - 1) cout << " ||\n";
        else cout << '\n';
    }
}

区间约束简化算法：从问题建模到高效实现

问题抽象与算法设计

本问题需要将多个区间约束条件合并为最简形式，核心思路可分为三步：

1. 约束条件转区间表示
将每个约束条件转换为数学区间：

x >= a && x <= b → 闭区间 [a, b]
x >= c → 右开区间 [c, 32767]
x <= d → 左开区间 [-32768, d]

2. 区间合并
通过排序+线性扫描算法合并相交或相邻的区间，时间复杂度优化至O(n log n)

3. 覆盖性判断
处理合并后的区间集合，判断是否覆盖整个int16范围[-32768, 32767]

代码深度解析

数据结构设计

struct Iv {
    int a, b; // 区间端点 [a, b]
    Iv(int x, int y) : a(x), b(y) {}
};

采用闭区间表示法统一处理各类约束
兼容开区间：用边界值-32768/32767表示无限延伸

输入处理模块

vector<string> split(string s) {
    vector<string> res;
    stringstream ss(s);
    string t;
    while (ss >> t) res.push_back(t);
    return res;
}

智能分割带空格字符串，适应多种输入格式
自动过滤行尾的"||"标识符

输入解析流程图：

$原始输入 → 分割Token → 过滤分隔符 → 构建区间对象$

区间合并算法

vector<Iv> merge(vector<Iv> v) {
    sort(v.begin(), v.end(), [](Iv x, Iv y) { 
        return x.a < y.a; 
    });
    
    vector<Iv> res;
    for (auto& cur : v) {
        if (!res.empty() && cur.a <= res.back().b + 1) {
            res.back().b = max(res.back().b, cur.b); // 合并重叠/相邻区间
        } else {
            res.push_back(cur);
        }
    }
    return res;
}

排序预处理：确保区间按左端点有序
贪心合并：相邻区间相差1时合并（如[1,2]与[3,4]合并为[1,4]）
时间复杂度：O(n log n) 排序 + O(n) 线性扫描

全域覆盖判断

bool full(vector<Iv> v) {
    int coverage = -32769; // 当前覆盖右边界
    for (auto& iv : v) {
        if (iv.a > coverage + 1) return false;
        coverage = max(coverage, iv.b);
        if (coverage >= 32767) break;
    }
    return coverage >= 32767;
}

初始值-32769保证首个区间必须包含-32768
间隙检测：当前区间左端点必须 ≤ 已覆盖右边界+1
提前终止：当覆盖32767时立即返回

输出生成策略

vector<string> output(vector<Iv> v) {
    vector<string> res;
    for (auto& iv : v) {
        string expr;
        if (iv.a == -32768) // 左开区间
            expr = "x <= " + to_string(iv.b);
        else if (iv.b == 32767) // 右开区间
            expr = "x >= " + to_string(iv.a);
        else // 闭区间
            expr = "x >= " + to_string(iv.a) + " && x <= " + to_string(iv.b);
        res.push_back(expr);
    }
    return res;
}

自动识别区间类型
优先使用最简表达式

关键测试案例

案例1：全域覆盖

输入：

x >= -32768 && x <= 32767 ||

输出：

true

处理过程：合并为单个区间[-32768, 32767]，触发full检测

案例2：矛盾约束

输入：

x >= 100 && x <= 50 || // 无效区间被过滤
x >= 200 && x <= 150 ||

输出：

false

关键点：无效区间(a > b)在输入处理阶段被直接过滤

案例3：边界衔接

输入：

x <= 10 ||
x >= 10 && x <= 20 ||

输出：

x <= 20

处理过程：[ -∞,10 ]与[10,20]合并为[ -∞,20 ]

性能优化点

无效区间过滤：在输入解析阶段直接丢弃a > b的区间
提前终止机制：在full检测中，当覆盖32767时立即返回
内存优化：使用vector的引用传递避免拷贝

复杂度分析

模块	时间复杂度	空间复杂度
输入处理	O(n)	O(n)
区间合并	O(n log n)	O(n)
覆盖性判断	O(n)	O(1)
结果生成	O(n)	O(n)

扩展思考

多变量约束如何处理？
非整数域约束的适应性改造？
动态约束更新的场景优化？

P6123 [NEERC 2016] Hard Refactoring 题解