牛客周赛73题解

A.小红的正整数构造

$\hspace{15pt}$ 小红拿到了一个区间 $[l,r]$ ，她希望你在这个区间内找到一个正整数，满足该正整数是 $x$ 的倍数。你能帮帮她吗？

数据很小，可以直接枚举

将左端点 $l$ 和右端点 $r$ 分别除以x,得到不大于 $l$ 和 $r$ 的 $x$ 的倍数，若这两个是相等的，则说明没有 $x$ 的倍数

特判 $l = r | x$ 的情况,输出比 $l$ 大的第一个 $x$ 的倍数即可

// C++

void solve(){
    int l , r , x;
    cin >> l >> r >> x;
    if(l == r && l % x == 0){
        cout << l << endl;
        return;
    }
    int L = l / x , R = r / x;
    if(L == R){
        cout << -1 << endl;
        return;
    }
    else cout << x * L + x << endl;
}

B.小红的区间构造

$\hspace{15pt}$ 小红拿到了正整数 $x$ ，她希望你找到一个长度为 $k$ 的区间，满足区间内恰好有 $n$ 个数是 $x$ 的倍数。你能帮帮她吗？

假设某一个 $x$ 的倍数为 $x_1$ ,讨论三种情况:

区间刚好略过 $x_1$ 时
区间刚好包含 $x_1$ 时
区间的左端点就是 $x_1$ 时

可以证明，只要这三种情况全不满足条件，那就找不到满足条件的区间

void solve(){
    int n , k , x;
    cin >> n >> k >> x;
    // 枚举3种情况
    for (int l = x - 1; l <= x + 1; ++l) {
        int r = l + k - 1;
        int count = r / x - (l - 1) / x;
        if (count == n) {
            cout << l << " " << r << endl;
            return;
        }
    }
    cout << -1 << endl;
}

C.小红的排列构造

$\hspace{15pt}$ 小红定义一个仅由 $\tt 0$ 和 $\tt 1$ 两个字符构成的 $\tt 01$ 串 $s$ 和一个排列 $p$ 是匹配的，当且仅当满足以下条件：
$\hspace{23pt}\bullet\,$ 若 $s_i = \tt 1$ ，则排列的前 $i$ 项元素恰好也构成一个排列；
$\hspace{23pt}\bullet\,$ 若 $s_i = \tt 0$ ，则排列的前 $i$ 项元素无法构成一个排列；
$\hspace{15pt}$ 现在小红拿到了一个长度为 $n$ 的 $\tt 01$ 串。请你构造一个排列使得它们是匹配的。
$\hspace{15pt}$ 长度为 $n$ 的排列是由 $1 \sim n$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

因为构造出来的数组本身也是一个排列,所以先判断01串最后一位，如果是0,则直接返回-1

由于对于 $s_i$ ,若当前位是1，则数组前 $i$ 位是长度为 $i$ 的排列，包含了 $1\to i$ 的所有整数,而若当前位是0,则前 $i$ 位不包含 $1\to i$ 的所有整数。那么我们不难想到的一种方案是：

对于 $s_i=0$ ,将 $1\to i$ 的整数中的某一个整数藏起来,再遇到 $s_i=1$ 再输出这一个整数

alt

于是我们可以把整个01串分为若干个 $000……1$ 串,我们设他的左端点为 $l$ ,右端点为 $r$ , $[l,r]$ 的区间构成一个 $l\to r$ 的排列,并且从 $l$ 开始的每一个 $0$ ，其在数组的对应位置上都应当缺少一个 $l$ ，而缺少的 $l$ 在1处补上即可

// C++
void solve(){
    int n;
    cin >> n;
    string t;
    cin >> t;
    vector<int> arr;// 存放每一个0000……1串的左端点
    arr.pb(1);// 第一个放入1
    vector<int> a(n , -1);// 存放数组
    vector<int> vis(n + 1 , 0);// 标记左端点已访问
    vector<int> re;// 把剩余的数依次放入数组
    for(int i = 0;i < n;i ++){
        // 当前位置为1,补上左端点对应的值
        if(t[i] == '1'){
            a[i] = arr.back();
            vis[a[i]] = 1;// 标记左端点已访问
            arr.pb(i + 2);// 放入下一个左端点
        }
    }
    // 特判末尾不为0
    if(t[n - 1] == '0'){
        cout << -1 << endl;
        return;
    }
    // 记录剩余的数
    for(int i = 1;i <= n;i ++){
        if(vis[i] == 0) re.pb(i);
    }
    int p = 0;
    for(int i = 0;i < n;i ++){
        if(a[i] == -1) a[i] = re[p] , p ++;// 放入数组中
    }
    for(int i = 0;i < n;i ++){
        cout << a[i] << " \n"[i == n - 1];// 输出数组
    }
}

D.小红的01子序列构造(easy)

$\hspace{15pt}$ 小红拿到了一个仅由 $\tt 0$ 和 $\tt 1$ 两个字符构成的 $\tt 01$ 串 $s$ ，她希望你找到一个区间，满足该区间内有恰好 $k$ 个 $\tt 01$ 子序列。
$\hspace{15pt}$ 子序列为从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串。

区间问题,考虑使用滑动窗口

思考窗口两端对区间的贡献

alt

观察上图我们发现：

在右端点右移的过程中，如果新加入的字符为"0"，由于01子序列必须由0开始，所以对区间01子序列数量没有影响

而新加入的字符"1"可以和区间内已有的所有"0"匹配成一对01子序列

即右端的0的贡献为0，右端的1的贡献为 $cnt_0$ ， $cnt_0$ 表示区间内0的数量

在左端点右移的过程中，如果移除的字符为"1"，由于01子序列必须由1结束，所以对区间01子序列数量没有影响

而移除的字符"0"会和区间内已有的所有"1"失去配对

即左端的1的贡献为0，右端的0的贡献为 $cnt_1$ ， $cnt_1$ 表示区间内1的数量

// C++
void solve(){
    int n , k;
    cin >> n >> k;
    string s;
    cin >> s;
    int l = 0 , r = 0;
    int cnt = 0 , cnt0 = 0 , cnt1 = 0;
    while(r < n){
        // 移动右端点
        while(r < n && cnt < k){
            cnt1 += (s[r] == '1');
            cnt0 += (s[r] == '0');// 利用布尔表达式更新cnt1和cnt0,表达式成立+1，不成立+0
            cnt += (s[r] == '1')?cnt0:0;// 计算右端点贡献
            r ++;
        }
        // 区间01子序列个数为k，直接输出答案
        if(cnt == k){
            cout << l << " " << r << endl;
            return;
        }
        // 移动左端点
        while(cnt > k){
            cnt1 -= (s[l] == '1');
            cnt0 -= (s[l] == '0');// 利用布尔表达式更新cnt1和cnt0,表达式成立-1，不成立-0
            cnt -= (s[l] == '0')?cnt1:0;// 计算左端点贡献
            l ++;
        }
    }
    // 没找到，输出-1
    cout << -1 << endl;
}

E.小红的二分图构造

$\hspace{15pt}$ 小红希望你构造一个二分图，满足第 $i$ 个节点的度数恰好等于 $d_i$ 。你能帮帮她吗？
$\hspace{15pt}$ 二分图是一张满足如下条件的图：它的节点可以被分成两个不相交的集合 $U$ 与 $V$ ，使得图中的每一条边都连接 $U$ 中的一个节点与 $V$ 中的一个节点。

由于图中的每一条边都连接 $U$ 中的一个节点与 $V$ 中的一个节点，设一条边 $g$ 连接了 $u$ 点和 $v$ 点， $g$ 的搭建会同时占用 $u$ 的度数和 $v$ 的度数

这意味着集合 $U$ 中的度数总和 $sum_u$ 与集合 $V$ 中的度数总和 $sum_v$ 必须是相等的

因为如果 $sum_u \neq sum_v$ ，我们假设 $sum_u > sum_v$ ，我们搭建边把 $V$ 中所有点的度数占满后， $U$ 中仍会存在无法连接的边

所以我们只要将所有的点分成两个总度数相等的集合，然后暴力连边即可

// C++
void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int sum = 0;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
        sum += a[i];
    }
    // 总度数是奇数，直接输出-1
    if(sum & 1){
        cout << -1 << endl;
        return;
    }
    sum = sum >> 1;// 取一半作为U和V的总度数
    // 01背包
    vector<vector<int>> dp(n + 1 , vector<int>(sum + 1 , 0));// 构建dp表，dp[i][j]表示前i个元素是否可以凑出j的总和
    dp[0][0] = 1;// 0个元素可以凑出0的总和
    for(int i = 1;i <= n;i ++){
        dp[i] = dp[i - 1];// 继承前一个的状态
        for(int j = sum;j >= a[i];j --){
            dp[i][j] |= dp[i  - 1][j - a[i]];// 状态转移，如果不选第i个元素可以凑出j-a[i],则选了就可以凑出j
        }
    }
    // 无法分成两半，直接输出-1
    if(!dp[n][sum]){
        cout << -1 << endl;
        return;
    }
    // 回溯01背包，找到具体方案
    int val = sum;// 暂存sum
    vector<int> u , v;
    for(int i = n;i >= 1;i --){
        // 选不选没影响的，放入U
        if(dp[i][val] == dp[i - 1][val]){
            u.emplace_back(i);
        }
        // 有影响(说明在01背包的过程中选中了)放入v
        else{
            v.emplace_back(i);
            val -= a[i];// 更新剩余需要的度数
        }
    }
    vector<pair<int , int>> ans;// 存储答案
    // 遍历U，使其所有节点连满
    for(int U : u){
        while(a[U]){
            // 遍历v
            for(int V : v){
                // 两个点都没连满，将他们连起来
                if(a[U] && a[V]){
                    a[U] --;
                    a[V] --;
                    ans.emplace_back(U , V);
                }
            }
        }
    }
    cout << ans.size() << endl;
    for(int i = 0;i < ans.size();i ++) {
        cout << ans[i].first << " " << ans[i].second << endl;
    } 
}

F.小红的01子序列构造(hard)

拼尽全力战胜他!!!!!

$\hspace{15pt}$ 小红希望你构造一个长度为 $n$ 的 $\tt 01$ 串，满足 $m$ 个性质：对于 $i \in [1, m]$ ，区间 $[l_i, r_i]$ 有恰好 $x_i$ 个 $\tt 0$ ， $y_i$ 个 $\tt 1$ ， $k_i$ 个 $\tt 01$ 子序列。
$\hspace{15pt}$ 给定的限制区间为两两包含关系。即对于 $i \neq j$ ，若 $l_i \leq l_j$ ，则 $r_i \geq r_j$ ，反之亦然。
$\hspace{15pt}$ 子序列为从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串。

题目中说到，给定的限制区间为两两包含关系，即大区间必定完全包含小区间，那么我们应从小到达构造字符串，让大区间在小区间的基础上构造

先解决如何在小区间内给定x , y , k构造字符串

假设 $x=3,y=2$ ，我们观察两种不同的构造方式：

$00011$ ，此时 $k=6=x\times y$

$11000$ ，此时 $k=0$

很显然上面两种情况分别是k可能的最大值和可能的最小值，即 $k\in [0,x\times y]$

由于每个0的后面都可能有 $0$ ~ $y$ 个1，所以 $k$ 可以表示为：

k=a_1y a_2(y - 1) a_3(y-2) … a_{y 1}\\ 其中\sum ^{y}_{i=1} a_i=x\\ 即k=xy-C,C只跟a_i的数值分配有关\\ 而a_i的分配没有其他限制，是任意的\\ 所以k的值可以任意分布在[0,x\times y]之间

至此，我们证明了，对于 $x、y$ 和 $\forall k \in [0,x\times y]$ 都必定可以构造出符合条件的字符串

接下来我们思考对于任意的k,如何构造符合条件的字符串

alt 可以采用动态规划的方式，假设对于一个区间 $[l,r]$ 上的一个点 $i$ ,假设 $i$ 之前的字符串都已经构造完成了，剩下还需要填入 $y'$ 个1,配出 $k'$ 个01子序列假设这一位填0，则其可以和后面所有的 $y'$ 个1构成01子序列，即这一位的0的贡献为 $y'$

填上0之后，需要配出的01子序列的数量变成了 $k'-y'$ ，我们当然不希望这个值变成负数，因此，当这一位的0的贡献超过了 $k'$ 时，我们改为在这一位填入1即可最终在小区间构造01串的算法写成函数变为：

vector<int> a(N);// 创建数组用于存放01
// 需要判断这个区间是否可以构造出符合条件的字符串，所以函数返回类型为布尔型
bool build(int l , int r , int x , int y , int k) {
    if(max(x , max(y , k)) == 0) return true;// 区间长度为0，不需要构造，直接返回true即可
    if(k > x * y) return false;// 无法构造，返回false
    for(int i = l;i <= r;i ++) {
        // 填0的贡献不超过k,填0并更新x和k
        if(k >= y) {
            s[i] = 0;
            x --;
            k -= y;
        }
        // 填1并更新y
        else {
            s[i] = 1;
            y --;
        }
    }
    // 返回true表示构造成功
    return true;
}

实现了对小区间的构造后，我们解决小区间确定了的情况下，如何构造大区间的问题

由于所有区间都是两两包含关系，所以小区间会将大区间分为3个部分：

alt

我们设已经构造好的区间为 $last$ 区间，左边的区间为 $L$ 区间，右边的区间为 $R$ 区间

可以得到 $L$ 区间的长度为 $last_l - 1 - L_l 1 = last_l-L_l$

$R$ 区间的长度为 $R_r - (last_r 1) 1=R_r-last_r$

已知已经构造好的区间里有 $last_x$ 个 $0$ 和 $last_y$ 个 $1$ ,当前大区间里有 $cur_x$ 个 $0$ 和 $cur_y$ 个 $1$

设 $L$ 区间有 $L_x$ 个 $0$ 和 $L_y$ 个 $1$ ， $R$ 区间有 $R_x$ 个 $0$ 和 $R_y$ 个 $1$

有：

L_x last_x R_x=cur_x\\ L_y last_y R_y=cur_y\\ 即L_x R_x=cur_x-last_x\\ L_y R_y=cur_y-last_y

$L_x$ 固定后，其余的所有量都固定了

那么我们可以枚举 $L_x$ ,判断是否可以构造即可

对于 $L_x、L_y、last_x、last_y、R_x、R_y$

我们可以算出无论 $L$ 区间和 $R$ 区间如何排列，该区间的贡献至少为：

$k'=L_x\times (last_y R_y) R_y\times last_x$

因此我们只需要让 $L_k R_k=cur_k-k'$

由于对于一个小区间，可能的 $k$ 分布在 $[0,x\times y]$ 之间，所以 $R_k$ 越小越有可能构造出符合要求的01串

那么我们只需要对每一个 $L_x$ ，让 $L_k$ 尽可能大，然后尝试构造即可

// C++
vector<int> a;// 创建数组用于存放01
vector<int> l , r;// 创建数组用于存放每一次询问的左右边界
// 需要判断这个区间是否可以构造出符合条件的字符串，所以函数返回类型为布尔型
bool build(int l , int r , int x , int y , int k) {
    if(x == 0 && y == 0 && k == 0) return true;// 区间长度为0，不需要构造，直接返回true即可
    if(k > x * y || r - l + 1 != x + y) return false;// 无法构造，返回false
    for(int i = l;i <= r;i ++) {
        // 填0的贡献不超过k,填0并更新x和k
        if(k >= y) {
            a[i] = 0;
            x --;
            k -= y;
        }
        // 填1并更新y
        else {
            a[i] = 1;
            y --;
        }
    }
    // 返回true表示构造成功
    return true;
}
// 构造cmp规则，按区间大小升序
bool cmp(int i , int j){
    return r[i] - l[i] < r[j] - l[j];
}
void solve(){
    int n , m;
    cin >> n >> m;
    a.resize(n + 1);
    l.resize(m);
    r.resize(m);
    vector<int> x(m) , y(m) , k(m) , p(m);
    for(int i = 0;i < m;i ++){
        cin >> l[i] >> r[i] >> x[i] >> y[i] >> k[i];
        p[i] = i;
    }
    // 根据区间的大小对每次询问排序
    sort(p.begin() , p.end() , cmp);
    for(int j = 0;j < m;j ++){
        int i = p[j];
        // 如果是最小的区间，直接构造
        if(j == 0){
            if(!build(l[i] , r[i] , x[i] , y[i] , k[i])){
                cout << -1 << endl;
                return;
            }
        }
        else{
            int last = p[j - 1];
            int lastl = l[last];
            int lastr = r[last];
            int lastx = x[last];
            int lasty = y[last];
            int lastk = k[last];// 获取上一次构造的信息
            int Ll = l[i] , Lr = lastl - 1 , Ld = Lr - Ll + 1;
            int Rl = lastr + 1 , Rr = r[i] , Rd = Rr - Rl + 1;// 获取L区间和R区间的范围和大小
            int flag = 0;
            // 枚举每一种可能的Lx
            for(int Lx = max(0 , x[i] - lastx - Rd);Lx <= min(Ld , x[i] - lastx);Lx ++){
                int Rx = x[i] - lastx - Lx;
                int Ly = Ld - Lx;
                int Ry = Rd - Rx;// 计算对应的左右区间的xy
                int K = Lx * (lasty + Ry) + Ry * lastx + lastk;// 计算区间最小的贡献
                int dk = k[i] - K;// 计算需要的贡献
                int Lk = min(Lx * Ly , dk) , Rk = dk - Lk;
                if(dk < 0) continue;// 无法构造，继续枚举
                if(build(Ll , Lr , Lx , Ly , Lk) && build(Rl , Rr , Rx , Ry , Rk)){
                    flag = 1;
                    break;
                }
            }
            if(!flag){
                cout << -1 << endl;
                return;
            }
        }
    }
    for(int i = 1;i <= n;i ++) cout << a[i];
    cout << endl;
}

总结

最近的周赛确实越来越难了，这次的题对思维能力有很大的要求

A题唯一的签到题，不用多说

B题是一个非常烦的题，如果没有想到合适的方法可能会卡很久很久(初见端倪)

C题可能比B题还要简单()，是众多名字里带构造的题里唯一一个正常的构造题，用正常的构造题思路去写没有太大的难度

D题考验我们对滑动窗口的掌握和对端点贡献的判断，本质上是一道简单的题

E题要求我们对图论的基本知识足够了解，只要基本功扎实就没什么问题

F题重量级，同时考察了：构造、动态规划、动态规划和动态规划，非常难非常好，sukisuki🥰🥰🥰

题解 | 牛客周赛73#A-F#详解