loj#560 Menci的序列

题意

给出一个长为 \(n\) , 由 + 和 * 组成的序列和常数 \(k\) . 对于一个这样的序列 , 定义其权值为 :

• 初始权值为 0 , 从左到右遍历序列
• 如果当前位是 + 就把权值\(+1\)
• 如果当前位是 * 就把权值 \(\times 2\)
• 对 \(2^k\) 取模 .

求原序列的一个子序列 , 最大化其权值 , 以二进制形式输出 .

\(n,k\le 10^6\)

题解

先考虑部分分 : 所有 + 之间都有 * . 考虑如果加入一个 * , 一个 + , 相当于在原数后插入的一个 \(1\) , 如果单独加入一个 * , 相当于在原数后插入了一个 \(0\) . 因此把每个 * 看做可以设置一个二进制位 , 如果后面有 + 表示可以在这一位上放置 \(1\) .

考虑贪心 , 因为有 \(k\) 位数限制 , 如果能填满 \(k\) 位 , 优先在高位放置 \(1\) ; 如果不能填满 \(k\) 位 , 优先最大化位数 .

因此从前向后考虑 , 有 \(1\) 就放 , 如果是 \(0\) 考虑能否填满 , 具体地 , 设当前限制为 \(k\) , 当前位数 ( 从后向前数 ) 为 \(pos\) :

• \(pos\ge k\) , 后面保证可以填满 , 就把 \(1\) 放在第 \(k\) 位上 , 更新限制 \(k\gets k-1\) , 向后进行 .
• \(pos<k\) , 最大化位数 , 就把 \(1\) 放在第 \(pos\) 位上 , 更新限制 \(k\gets pos-1\) .

考虑一般的情况 , 仍然延续部分分的思路 , 把 * 后的的看作可以放在这一位上的数 , 不同的是这个数可能 \(>1\) , 这时会出现进位的问题 .

这时候 , 为了接近部分分的做法 , 可以想到把每一位转化成 \(1\) , 进而联想到用类似进位的思路来处理 .

注意到 , 因为每个* 和 + 都是可选的 , 如果直接进位会出现问题 , 比如 *++ 如果变成 +* , 会少一种情况 : *+ , 也就是 \(\times 2 +1\) , 这提示我们从一个序列的子序列可以表示的运算入手简化问题 .

对于每个 * 后 , 设有 \(k\) 个 + , 表示的意义是 $x\times 2+ w\ (w\le k) $ .

而进位后表示的是 \((x+w_1)\times 2 + w_2 \ (w_1\le \frac{k}{2} , w_2 \le k \mod 2)\)

其中 , 如果表示的 \(w\) 是偶数 , 那么 \(k\) 是可以放心进位的 .

如果表示的 \(w\) 是奇数 , 那么如果 \(w_2\) 不能取到 \(1\) , 说明 \(k\) 是偶数 , 就会少情况 .

解决办法也显然了 , 如果 \(k\) 是偶数 , 不完全进位 , 在当前位留一个 \(2\) , 这样可以把每一位可选值简化到 \(0/1/2\) , 而不会少情况 .

考虑每一位取值为 \(0/1/2\) 时 , 怎样贪心地确定每一位 .

假设当前位 \(pos\) 可取 \(0/1/2\) , 主要讨论是否有可能进位 :

• 如果 \(pos\ge k\) , 那么贡献 \(2\) 是不优的 . 在第 \(k\) 位填 \(1\) , 更新限制 \(k\gets k-1\) .

  因为在能填满的情况下 , 填了 \(2\) 后会产生一个空位 , 后面的要么连续填 \(2\) 用进位补上 , 要么填不了 \(2\) , 会让本来能连续填 \(1\) 的中间产生一个 \(0\) 变得更劣 .

• 如果 \(pos<k\) , 那么要尽可能提高最高位 , 在 \(pos\) 位填 \(2\) , 相当于在 \(pos+1\) 位填 \(1\) . 更新限制 \(k\gets pos\) , 表示当前位 \(pos\) 还可以填数 .

类似地 , 如果当前位 \(pos\) 可取 \(0/1\) , 且 \(pos<k\) , 存在一种情况 , 下一位是 \(2\) , 把\(1\)填到 \(pos\) , 进位到 \(pos+1\) , 将最高位提高一位 , 因此这种情况下更新限制变为 \(k\gets pos\) , 其他不变 .

注意答案要处理进位 .

#include <bits/stdc++.h>
#define file(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define ll long long
#define INF 0x7fffffff
#define INF64 1e18
using namespace std;

constexpr int N = 1e6 + 5;

int n, k;

string s;
int tot;

int a[N], res[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    cin >> s;
    s = '*' + s;
    n++;
    tot = 0;

    for (int i = n; i; i--) {
        if (s[i - 1] == '+') {
            a[tot]++;
        } else
            tot++;
    }

    for (int i = 0; i <= tot; i++) {
        if (a[i] >= 3) {
            a[i]--;
            a[i + 1] += a[i] / 2;
            a[i] %= 2;
            a[i]++;
        }
    }

    while (a[tot + 1]) {
        if (a[tot + 1] >= 3) {
            a[tot + 1]--;
            a[tot + 2] += a[tot + 1] / 2;
            a[tot + 1] %= 2;
            a[tot + 1]++;
        }

        tot++;
    }

    for (int i = tot; i >= 0; i--) {
        if (a[i] == 0)
            continue;

        if (a[i] == 1) {
            if (i >= k - 1)
                res[k - 1]++, k--;
            else
                res[i]++, k = i + 1;
        }

        if (a[i] == 2) {
            if (i >= k - 1)
                res[k - 1]++, k--;
            else
                res[i + 1]++, k = i + 1;
        }
    }

    int tag = 0;

    for (int i = 0; i <= n; i++)
        if (res[i] >= 2)
            res[i + 1] += res[i] / 2, res[i] %= 2;

    for (int i = n; i >= 0; i--)
        if (res[i] == 0) {
            if (tag)
                cout << 0;
        } else {
            cout << 1;
            tag = 1;
        }

    if (!tag)
        cout << 0;

}

总结

这道题最有趣的部分就是简化问题的一部分 , 首先在部分分做法和二进制进位习惯的双端引导下 , 想到直接进位处理 , 然后发现有 Hack 的办法 . 此时优先考虑改进原做法保证正确性 , 因此仔细分析 Hack 的问题出在哪里 , 发现是因为表示的情况缺失 , 进一步从表示的所有情况出发梳理问题 , 改进方法就十分显然了 . 思路其实很自然 .

集训期间写的题解思路不够清晰 , 因为是看完做法后强行生成的思路 . 故重新整理 .