T1 字节之和

双休在家的凯凯真的是太无聊了，他准备和他家的猫玩一个游戏。

凯凯随手写下一串 01 数列，定义这串数列的子串和为所有长度为2的子串的和。比如数列=010001，有如下长度为 2 的子串：
01 （前导0， =1）
10
00 （前导0，=0）
00 （前导0，=0）
01 （前导0，=1）

所以和为 1+10+0+0+1 = 12

如果要只是算子串和的话，那对喵喵来说实在是太简单了，所以凯凯准备加大难度。

喵喵有 \(k\) 次机会可以交换数列里的相邻两个数（可以不用完这 \(k\) 次机会），使得交换完之后子串和最小。

这下喵喵不会做了，你可以帮帮它么？

输入为先输入一个t，代表t组。然后分别是n、k，字符串。
input:
3
4 0
1010
7 1
0010100
5 2
00110

output:
21
22
12

对于 01 字符串，分析下它每个 1 的情况，可分为 3 种情况(中间的 \(1\) 必经过 \(1 \times 10 + 1 \times 1\))：

1. 1 出现在字符串首部，贡献为 10
2. 1 出现在字符串中部，贡献为 11
3. 1 出现在字符串尾部，贡献为 1

通过以上分析可知，我们只要把 1 替换到首尾就可获得做小的和。

代码

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

int main() {
    ios::sync_with_stdio(false);

    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;

        int one = 0;
        for(int i = 0; i < n; i++) {
            if(s[i] == '1') one++;
        }

        if(one == 0) {
            cout << 0 << endl;
            continue;
        }

        int ans = 0;
        ans += one * 11;

        // 先将 1 尽量替换到 尾部，因为尾部的 1 贡献为 1，更小
        int rneed = 0;
        for(int i = n-1; i >=0; i--) {
            if(s[i] != '1') {
                rneed++;
            } else {
                break;
            }
        }

        // 如果 k 足够大，那么必有一个 1 贡献由 11 变为 1
        if(k >= rneed ) {
            k -= rneed;
            ans -= 10;
            // 替换后的字符串
            s[n-1] = '1';
            s[n-1-rneed] = '0';
        }

        // 替换 1 到首部，贡献由 11 减为 10
        int need = 0;
        for(int i = 0; i < n; i++) {
            if(s[i] != '1') {
                need++;
            } else {
                break;
            }
        }

        // 必有一个 1 贡献由 10 降为 1，前提是 1 不能从尾部替换到首部
        if(k >= need && (need != n-1)) {
            ans -= 1;
        }

        cout << ans << endl;
    }
}

T2 迷宫问题

第一行输入两个整数 n 和 m ，表示迷宫的长和宽。

接下来 n 行，每行 m 个字符， 用于描述迷宫构造，每个字符可能为以下几种：

. 表示空地， 玩家在空地时可以选择往 [上，下，左，右] 中的某个方向移动一格。U，D，L，R 分别表示朝向[上，下，左，右] 的传送带，站在传送带上的人会被强制移动到其指向的下一个位置，如果下一个位置还是传送带，会被继续传下去。如果传送带指向迷宫外，玩家会撞在墙上，昏过去，游戏结束，无法再到达出口。O 表示迷宫出口

请你找到有多少点按照规则行走不能到达终点。

input:
5 5
.....
.RRD.
.U.DR
.ULL.
....O

output:
10

解这道题的思路来自于 Leetcode 417. Pacific Atlantic Water Flow 。从出口 O 反向遍历，找到所有可以从 O 反向到达的点，答案即为 \(n \times m - count(O)\) 。

出口 O 并不总是在右下角!!

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

constexpr static int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int main() {
    // freopen("bytecode002.txt", "r", stdin);
    ios::sync_with_stdio(false);
    
    int n, m;
    cin >> n >> m;

    vector<vector<char>> mmap(m, vector<char>(n));

    queue<pii> q;

    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            cin >> mmap[i][j];
            if(mmap[i][j] == 'O') {
                q.emplace(i, j);
            }
        }
    }

    while(!q.empty()) {
        pii cur = q.front();
        q.pop();
        int x = cur.first, y = cur.second;

        // O 处可达
        if(x-1 >= 0 && (mmap[x-1][y] == '.' || mmap[x-1][y] == 'D')) {
            q.emplace(x-1, y);
            mmap[x-1][y] = 'O';
        }

        if(x+1 < n && (mmap[x+1][y] == '.' || mmap[x+1][y] == 'U')) {
            q.emplace(x+1, y);
            mmap[x+1][y] = 'O';
        }

        if(y-1 >=0 && (mmap[x][y-1] == '.' || mmap[x][y-1] == 'R')) {
            q.emplace(x, y-1);
            mmap[x][y-1] = 'O';
        }

        if(y+1 < m && (mmap[x][y+1] == '.' || mmap[x][y+1] == 'L')) {
            q.emplace(x, y+1);
            mmap[x][y+1] = 'O';
        }
    }

    int count_O = 0;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(mmap[i][j] == 'O') {
                count_O++;
            }
        }
    }

    cout << n*m - count_O << endl;

}

T3 广告投放

在广告平台中，为了给广告主一定的自由性和效率，允许广告主在创造标题的时候以通配符的方式进行创意提交。线上服务的时候，会根据用户的搜索词触发的 bidword 对创意中的通配符（通配符是用成对 {} 括起来的字符串）进行替换（用0个或者多个字符替换通配符），用来提升广告投放体验。例如：{末日血战}，上线送 SSR 英雄，三天集鲚无敌阵容！”，会被替换成“帝国时代下载上线送 SSR 英雄，三天集齐无敌阵容！”。给定一个含有通配符的创意和一句标题，判断这句标题是否从该创意替换生成的。

输入一个 n，有 n 个标题。第一行是带有通配符的创意，下面n行是所有标题。对于每一行标题，如果可以用通配符匹配，输出 True 否则输出 False。

input:
4
ad{XYZ}cdc{Y}f{x}e
adcdcefdfeffe
adcdcefdfeff
dcdcefdfeffe
adcdcfe
 
output:
True
False
False
True

简单正则表达式处理

#include<iostream>
#include<regex>
#include<vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    string tpl;
    cin >> tpl;

    vector<string> mch(n);
    for(int i = 0; i < n; i++) {
        cin >> mch[i];
    }

    regex reg("\\{[a-zA-Z]+\\}");
    string ntpl = regex_replace(tpl, reg, "\\w*");

    regex new_reg(ntpl);
    smatch m;
    for(int i = 0; i < n; i++) {
        if(regex_match(mch[i], m, new_reg)) {
            cout << "True" << endl;
        } else {
            cout << "False" << endl;
        }
    }

    return 0;
}

T4 摇骰子游戏

小明和小红在玩摇骰子游戏，每个骰子有固定的面数 \(k(2 \le k \le 8)\),每一面对应的点数分别为 \(1,2,.…,k\)。

小明有 \(n (1 \le n \le 20)\)个骰子，对于骰子 \(i (1 \le i \le n)\) ，它的面数为 \(a_i (2 \le a_i \le 8)\),摇到每一面的概率都是 \(\frac{1}{a_i}\)。

小红有 \(m (1 \le m \le 20)\) 个骰子，对于骰子 \(j(1 \le j \le m)\)，它的面数为 \(b_j (2 \le bj \le 8)\),摇到每一面的概率都是 \(\frac{1}/{b_j}\)。

小明和小红分别摇各自拥有的全部骰子，然后把骰子朝上那一面的点数相加，最后比较谁的点数和最大，大的获胜，相同平手，小的获败。小明和小红只摇一把，平手不会继续重摇，小明想知道他获胜的概率，你能帮帮他吗？

输入 n、m。然后输入 n 个骰子和 m 个骰子

输出获胜概率，保留小数点后 3 位。

input:
1 3
8
2 3 4

output:
0.255