牛客周赛55

A 小红的字符串

小红拿到了一个长度为 $3$ 且仅由小写字母组成的字符串，她每次操作可以修改任意一个字符，小红希望最终所有字符都相同。求出最小的操作次数

void solve() {
    string s;cin >> s;
    set<char>ss;
    for (auto x : s)ss.insert(x);
    cout << ss.size() - 1 << '\n';
}

B 小红的序列乘积

小红有一个长度为 $n$ 的整数序列 ${a_{1}, a_{2}, \dots, a_{n}}$ ，定义 $f_{i} = a_{1} \times a_{2} \times \dots \times a_{i}$ ，即前 $i$ 项的乘积。现在小红想知道 $f_{1}, f_{2}, \dots, f_{n}$ 中，有多少个数的个位数是 $6$ 。

void solve() {
    int n;cin >> n;
    int cnt = 0, mul = 1;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;
        mul *= x % 10;mul %= 10;
        if (mul == 6)cnt++;
    }
    cout << cnt << '\n';
}

C 小红的数组重排

给出一个数字 $n$ 和一个长度为 $n$ 的数组 $[a_{1}, a_{2}, \dots, a_{n}]$ 。现在你可以以任意方式重新排列数组 $a$ ，问是否存在重排后的数组 $a$ 满足： $a_{1} \times a_{2} < a_{2} \times a_{3} < \dots < a_{n - 1} \times a_{n}$ 。

显然，直接排序即可
若出现三个相同的数字，则 $a_{i} = a_{i + 2}$ ，就不满足要求了
若出现 2 个 0，则，前一个式子和后一个式子的结果都为 0，也不满足要求。

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);map<int, int>mp;
    for (int i = 1;i <= n;i++)cin >> a[i], mp[a[i]]++;
    for (auto [x, y] : mp) {
        if (y >= 3) {
            cout << "NO\n";return;
        }
    }
    if (mp[0] >= 2) {
        cout << "NO\n";return;
    }
    cout << "YES\n";
    sort(a.begin() + 1, a.end());
    for (int i = 1;i <= n;i++)cout << a[i] << " \n"[i == n];
}

D 虫洞操纵者

你需要在一个可以上下左右移动的 $n \times n$ 棋盘上解开一个迷宫：棋盘四周都是墙；每个方格要么是可以通过的空方格 $^{'} 0^{'}$ ，要么是不可通过的墙方格 $^{'} 1^{'}$ ；你可以沿着空方格通行；你已经被传送到了迷宫的左上角（第 $1$ 行第 $1$ 列的位置），你知道终点位于迷宫右下角（第 $n$ 行第 $n$ 列的位置）。

别人都不知道的是，你是一个虫洞大师，当你所在的位置能同时看到左右两侧或上下两侧最近的那两面相对的墙时，你可以在这两面墙上开启虫洞，靠近后从一侧进入，穿越它到达另一侧。

现在，你准备好以最短的步数离开迷宫了吗！

普通 BFS+特殊处理，遇到墙了之后反方向移动直到遇到另外一个墙即可

int s[1010][1010], vis[1010][1010];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void solve() {
    int n;cin >> n;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cin >> s[i][j];
        }
    }
    for (int i = 1;i <= n;i++) {
        s[0][i] = 1;
        s[i][0] = 1;
        s[n + 1][i] = 1;
        s[i][n + 1] = 1;
    }
    queue<tuple<int, int, int>>q;q.push({1,1,0});
    vis[1][1] = 1;
    while (q.size()) {
        auto [x, y, step] = q.front();q.pop();
        if (x == n && y == n) {
            cout << step << '\n';return;
        }
        for (int i = 0;i < 4;i++) {
            int a = x + dx[i], b = y + dy[i];
            if (vis[a][b])continue;
            if (!s[a][b]) {
                vis[a][b] = 1;q.push({a,b,step + 1});
            } else {
                int dirx = -1, diry = -1;
                for (int j = 0;j < 4;j++) {
                    if (dx[j] == -dx[i] && dy[j] == -dy[i]) {
                        dirx = dx[j], diry = dy[j];
                    }
                }
                a += dirx, b += diry;
                while (!s[a][b]) {
                    a += dirx, b += diry;
                }
                a -= dirx, b -= diry;
                if (!vis[a][b]) {
                    vis[a][b] = 1;q.push({a,b,step + 1});
                }
            }
        }
    }
    cout << "-1\n";
}

E 小红的序列乘积 2.0

对于一个长度为 $m$ 的整数序列 ${b_{1}, b_{2}, \dots, b_{m}}$ ，定义 $f_{i} = b_{1} \times b_{2} \times \dots \times b_{i}$ ，即前 $i$ 项的乘积。这个序列的权值即为 $f_{1}, f_{2}, \dots, f_{m}$ 中个位数是 $6$ 的数字个数。

小红有一个长度为 $n$ 的整数序列 ${a_{1}, a_{2}, \dots, a_{n}}$ ，她想知道这个序列全部 $2^{n} - 1$ 个非空子序列的权值和是多少。

Solution

$f_{i, j}$ 代表前 $i$ 个数字有多少种以 $j$ 结尾的方案数。

设 $f_{i, j}$ 为当前状态， $f_{i - 1, j}$ 为之前的状态，则：

当前状态一定是包含了之前的状态的，即 $f_{i, j} = f_{i - 1, j} + \dots$

当前数字为 $a_{i}$ ，则 $f_{i, j \times a_{i} % 10}$ 即加入当前数字之后，以 $j \times a_{i} % 10$ 结尾。则：

$f_{i, j \times a_{i} % 10} = f_{i - 1, j} + \dots$

当加入当前数字后，以 6 结尾了，满足要求，设该子序列为 ${1, \dots, i}$ ，则下标更大的序列都可以包含这个子序列，有 $n - i$ 个，每个序列都可以选/不选，则有 $2^{n - i}$ 种方式

#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];a[i] %= 10;
    }
    vector<array<int, 10>> f(n + 1);//代表前i个数字有多少种以j结尾的方案数
    f[0][1] = 1;
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 0;j < 10;j++) {
            if (j * a[i] % 10 == 6) {
                ans += f[i - 1][j] * qpow(2, n - i) % mod;ans %= mod;
            }
            f[i][j] += f[i - 1][j];f[i][j] %= mod;
            f[i][j * a[i] % 10] += f[i - 1][j];f[i][j * a[i] % 10] %= mod;
        }
    }
    cout << ans << '\n';
}

F 的计算几何暗示我该学习计算几何了!