小白月赛91

A Bingbong 的化学世界

void solve() {
    int cnt = 0;
    for (int i = 0;i < 6;i++)cin >> s[i];
    for (int i = 0;i < 6;i++) {
        for (int j = 0;j < s[i].size();j++) {
            if (s[i][j] == '|')cnt++;
        }
    }
    if (cnt == 3)cout << "m\n";
    if (cnt == 2)cout << "o\n";
    if (cnt == 4)cout << "p\n";
}

B Bingbong 的数数世界

Bing 和 Bong 在玩消数游戏，游戏规则如下：

初始时给定一个数字 n，然后会有编号为 1，2，3... n 的卡牌共 n 张位于桌面上。

Bing 每轮必须选择一个奇数消除，然后可以同时消除一个偶数 (此步可以选择做或者不做）。

Bong 每轮必须选择一个偶数消除，然后可以同时消除一个奇数 (此步可以选择做或者不做）。

Bing 先手操作，谁无法操作时即输掉了游戏，若两人都采取最优策略，请您来告诉他们最终的胜者。

void solve() {
    int n;cin >> n;
    if (n & 1)cout << "Bing\n";
    else {
        n >>= 1;
        if (n & 1)cout << "Bing\n";
        else cout << "Bong\n";
    }
}

C Bingbong 的蛋仔世界

Bingbong 特别喜欢蛋仔派对，但他玩游戏一向很菜，尤其是在生存战中总是败多胜少。这个生存游戏的规则是这样的：在高空万米之上有一个大小为 $n \times m$ 的地图砖块，起初所有块都在原位，之后每单位时间最外圈的砖块会掉落，站在上面的蛋仔会掉落深渊失败。蛋仔们会向四个方向移动，或者选择不动，直到有蛋仔到达地图中心 $(n / 2 + 1, m / 2 + 1)$ 的位置。
有多少蛋仔通过这一关

对于每一只蛋仔，我们只需要计算它到达终点的所需总时间能否小于所在行和列中砖块消失最长时间即可。

void solve {
    int n, m, k;cin >> n >> m >> k;
    int fx = n / 2 + 1, fy = m / 2 + 1;
    int ans = 0;
    for (int i = 1; i <= k; i++) {
        int x, y;cin >> x >> y;
        int time = abs(x - fx) + abs(y - fy);
        if (time < max(fx, fy)) ans++;
    }
    cout << ans << '\n';
}

D Bingbong 的奇偶世界

给出一个只含数字的字符串，求组成不含前导 0 的偶数的方案有多少种 $(\mod 10^{9} + 7)$

Solution

~~没看懂，学 DP 去了

#define int long long
constexpr int mod = 1e9 + 7;
void solve() {
    int n;cin >> n;
    string s;cin >> s;s = ' ' + s;
    int ans = 0, cnt = 0;
    for (int i = 1;i <= n;i++) {
        if (s[i] == '0') {
            ans = (ans + cnt + 1) % mod;cnt = (cnt * 2) % mod;
        } else if ((s[i] - '0') & 1) {
            cnt = (cnt * 2 + 1) % mod;
        } else {
            ans = (ans + cnt + 1) % mod;cnt = (cnt * 2 + 1) % mod;
        }
    }
    cout << ans << '\n';
}

E Bingbong 的字符串世界

给定长度为 $n$ 的由大写字母组成的字符串，在这个字符串中拿出一个长度不小于 $k$ 的字串，要求这个字串的子序列中包含 ACCEPT 且不包含 WA，求这样的子串有多少个。

Solution

字符串/序列自动机

这种类似邻接表的方法叫做子序列自动机，实际上就是记录了第 $i$ 个位置右边出现字符 $c$ 的第一个位置

$f [i] [j]$ 代表的是 $t a r_{i}$ 的右边出现 $t a r_{i + 1}$ 的第一个位置，若不存在这个字符，则为 -1

vector<vector<int>>f(n + 2, vector<int>(27, -1));
for (int i = n;i >= 1;i--) {
	for (int j = 1;j <= 26;j++) {
		f[i][j] = f[i + 1][j];
	}
	f[i][s[i] - 'A' + 1] = i;
}

注意：对于 ACCEPT 含有两个 C 的情况，如果无脑嵌套的话，会被 ACEPTX HACK 掉，所以需要特判。

依次判断 ACCEPT|WA 的匹配情况，每个循环匹配范围为 $[i, n]$ ，代表的是以 $s_{i}$ 为首字母满足要求的子串有多少个。

#define int long long
void solve() {
    int n, k;cin >> n >> k;
    vector<char> s(n + 1);
    for (int i = 1;i <= n;i++)cin >> s[i];
    vector<vector<int>>f(n + 2, vector<int>(27, -1));
    for (int i = n;i >= 1;i--) {
        for (int j = 1;j <= 26;j++) {
            f[i][j] = f[i + 1][j];
        }
        f[i][s[i] - 'A' + 1] = i;
    }
    int ans = 0;
    string tar1 = "ACCEPT", tar2 = "WA";
    for (int i = 1;i <= n;i++) {
        int t1 = i;
        for (int j = 0;j < 6;j++) {
            if (j == 2 && s[t1] == 'C')t1 = f[t1 + 1][tar1[j] - 'A' + 1];
            else t1 = f[t1][tar1[j] - 'A' + 1];
            if (t1 == -1)break;
        }
        if (t1 == -1)continue;//如果没有ACCEPT，则答案直接为0
        int t2 = i;
        for (int j = 0;j < 2;j++) {
            t2 = f[t2][tar2[j] - 'A' + 1];
            if (t2 == -1)break;
        }
        if (t2 != -1 && t2 <= t1)continue;//若WA在ACCEPT前面，则这段答案直接为0
        if (t2 == -1) {//如果后面没有WA了，若后面的长度还够k，则后面都可以计算答案
            if (i + k - 1 > n)continue;
            ans += n - max(i + k - 1, t1) + 1;
        } else {//如果后面有WA，若到WA之前的长度还够k，也可以计算答案，只是不能计算到到WA那里去了
            if (i + k - 1 >= t2)continue;
            ans += t2 - max(t1, i + k - 1);
        }
    }
    cout << ans << '\n';
}

F Bingbong 的幻想世界

给定一个长度为 $n$ 的数组 $a$ ，对于区间 $[l, r]$ 权值 $w$ 满足： $$w=\sum\limits_{i=l}^r\sum\limits_{j=l}^ra_{i}\oplus a_{j}$$
求数组 $a$ 的所有非空子区间权值之和 $(\mod 10^{9} + 7)$

Solution

位运算

与小美的区间异或和本题答案是这个题的两倍，参考代码：

#define int long long
constexpr int mod = 1e9 + 7;
int f[32][2];
void solve() {
    int n;cin >> n;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 0;j <= 30;j++) {
            int t = (a[i] >> j) & 1;
            ans = (ans + f[j][t ^ 1] * (1 << j) % mod * (n - i + 1) % mod) % mod;
            f[j][t] += i;
        }
    }
    cout << ans << '\n';
}

一个小技巧：拆位计算，如 $7 \oplus 9 = 14$ ，即为 $(0111 \oplus 1001) \to (1, 1)_{0}, (1, 0)_{1}, (1, 0)_{2}, (0, 1)_{3}$

计算过程： $2^{1} + 2^{2} + 2^{3} = 14$ ，显然可以发现：当两个数某位相同时不算入贡献，位不同时算入 $2^{b i t}$ 贡献

这个题同理。

假如 $a_{i}$ 二进制的第 $b$ 位是 1，则 $a_{i}$ 左右数字第 $b$ 位是 0 才可以作出贡献，反之是 1 才能作出贡献，作出的贡献即为 $2^{i}$

则可以计算当前位为 0|1 的前缀和，到 $a_{i}$ 时就可以查询 $a_{i}$ 前面有多少与自己可以作出贡献的下标的前缀和，由于这里只计算了 $a_{i}$ 前面的数字，由对称性，答案乘以 2 即可。

换句话说：

当计算到 $a_{i}$ 第 $b$ 位即 $a_{i}^{(b)} = 1$ 时，在区间 $[0, i - 1]$ 中当前位为 $0$ 的个数为 $p_{0}$ 个，在所有区间中会影响的区间个数为 $n - i + 1$ (只要该区间包含了 $[0, i]$ ，则那个区间即被影响)，贡献为 $p_{0} \times (n - i + 1) \times 2^{b} \times 2$ ，当 $a_{i}^{(b)} = 0$ 时同理。

#define int long long
constexpr int mod = 1e9 + 7;
void solve() {
    int n;cin >> n;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    int ans = 0;
    for (int b = 0;b <= 20;b++) {
        int p0 = 0, p1 = 0;
        for (int i = 1;i <= n;i++) {
            if ((a[i] >> b) & 1) {
                ans = (ans + p0 * (n - i + 1) % mod * (1 << b) % mod * 2 % mod) % mod;
                p1 += i, p1 %= mod;
            } else {
                ans = (ans + p1 * (n - i + 1) % mod * (1 << b) % mod * 2 % mod) % mod;
                p0 += i, p0 %= mod;
            }
        }
    }
    cout << ans << '\n';
}