题解 | 小红的01子序列构造（hard）

审题难度大于具体实现难度的一道题。

首先，考虑没有内层约束，就只有x个0、y个1这样的约束的01串，能够取的01子序列个数k。可以发现取值范围即[0, x*y]。

然后注意到从里到外第i个区间[l_i, r_i]内字符串的构造只受第i-1个区间[l_{i-1}, r_{i-1}]的影响，则将第i个区间分成三段，[l_i, l_{i-1}-1], [l_{i-1}, r_{i-1}], {r_{i-1}+1, r_i], 分别称为左、中、右，设最左边区间中0的个数为z，然后对z枚举求k上下界并构造即可。当然你去按照二次函数最大点在不在区间内讨论也可以，但是我没想清楚怎么选取构造就没用这个方法，反正时空限制给的大，这样就够过了。

最后不要忘记在最外层约束外补01。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Restriction {
    int l, r, x, y;
    long long k;
};

class Solution {
private:
	//返回一个01字符串，满足其含有x个0，y个1，k个01子序列（01子序列即一对0、1使得0在1前）
    string construct_string(int x, int y, long long k) {  //0 <= k <= x * y
        string res_string = "";
        if (x == 0) {
            for (int i = 0; i < y; i++) {
                res_string += "1";
            }
            return res_string;
        }
	/*即从字符串为“x个1 y个0”开始（此时k=0，即"11...100...0"），
	先把n1 = k / x(整除）个1移到所有0的右边，再把一个1移到恰好n1 = k % x个0的右边。
	结果为res_string = "x - n1 - n3个1， n2个0， n3个1， y - n3个0，n1个1" 
	(n3 = (n2 == 0) ? 0 : 1; 即 n2 == 0 的时候 n3 = 0, 否则 n3 = 1 。)
	*/
        int n1 = k / x, n2 = k % x, n3 = (n2 == 0) ? 0 : 1;
        for (int i = 0; i < y - n1 - n3; i++) {
            res_string += "1";
        }
        for (int i = 0; i < n2; i++) {
            res_string += "0";
        }
        for (int i = 0; i < n3; i++) {
            res_string += "1";
        }
        for (int i = 0; i < x - n2; i++) {
            res_string += "0";
        }
        for (int i = 0; i < n1; i++) {
            res_string += "1";
        } 
        return res_string;
    }
public:
	/*主函数，根据约束restrictions生成对应的1个字符串，或当不存在这样的字符串时返回"-1"。
  我把restrictions按照约束区间从里到外顺序排列，然后构造也是这样一层层向外构造。
  最后不要忘了，如果最外层约束的l和r不是1和n，则需要在前后补上任意的01使长度为n，补全字符串。
  （之前忘了这个，一直6/33，非常郁闷-^-！）
  */
    string generate_Zero_One_Substring(int n, vector<Restriction>& restrictions) {
        string ans_string = "";
        if (restrictions.empty()) {
            for (int i = 0; i < n; i++) {
                ans_string += "0";
            }
            return ans_string;
        }
        
        auto [l, r, x, y, k] = restrictions[0];
        if (k <= (long long) x * y) {
            ans_string = construct_string(x, y, k);
        }
        else{
            return "-1";
        }
        int l_next, r_next, x_next, y_next; long long k_next;
        for (int i = 1; i < restrictions.size(); i++) {
            Restriction restriction = restrictions[i];
            auto [l, r, x, y, k] = restrictions[i - 1];
            l_next = restriction.l, r_next = restriction.r, x_next = restriction.x, y_next = restriction.y;
            k_next = restriction.k;
            int d1 = l - l_next, d2 = r_next - r, delta_x = x_next - x, delta_y = y_next - y;
            if (delta_x < 0 || delta_y < 0 || d1 + d2 != delta_x + delta_y) return "-1";
            bool existConstruction = false;
            for (int z = max(0, delta_x - d2); z <= min(d1,delta_x); z++) { 
//对[l_i, l_{i-1}-1]这一段中的0的个数z进行枚举，
//计算第i个区间中给定z对应的k的取值范围
//（在内层第1~i-1个区间内的约束都被满足之后）
                long long lower_bound = (long long)z * y + z * (d2 - delta_x + z) + x * (d2 - delta_x + z), 
                    upper_bound = lower_bound + z * (d1 - z) + (delta_x - z) * (d2 - delta_x + z);
                if (lower_bound <= k_next - k && upper_bound >= k_next - k) {
                    existConstruction = true;
                    int delta = k_next - k - lower_bound;
                    if (delta < z * (d1 - z)) {
                        ans_string = construct_string(z, d1 - z, delta) + ans_string + 
                        construct_string(delta_x - z, d2 - delta_x + z, 0);
                    }
                    else{
                        ans_string = construct_string(z, d1 - z, z * (d1 - z)) + ans_string + 
                        construct_string(delta_x - z, d2 - delta_x + z, delta - z * (d1 - z));
                    }
                    break;
                }
            }
		  //如果枚举后不存在满足约束的构造，返回"-1"。
            if (existConstruction == false) return "-1";
            
        }
        //补全最外层约束以外的字符串
        for (int i = 0; i < l_next - 1; i++) {
            ans_string = "1" + ans_string;
        }
        for (int i = r_next; i < n; i++) {
            ans_string = ans_string + "0";
        }
        return ans_string;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<Restriction> restrictions(m);
    int l, r, x, y; long long k;
    for (int i = 0; i < m; i++) {
        cin >> l >> r >> x >> y >> k;
        restrictions[i] = Restriction {l, r, x, y, k};
    }
    sort(restrictions.begin(), restrictions.end(), [] (const Restriction& a, const Restriction& b) {
        if (a.l != b.l) {
            return a.l > b.l;
        }
        else {
            return a.r < b.r;
        }
    });
    Solution solution;
    cout << solution.generate_Zero_One_Substring(n, restrictions) << endl;

    return 0;
}