牛客周赛47

A 小红的葫芦

小红有一个长度为 5 的数组，如果数组元素有 3 个相同，另外两个也相同，那么这个数组就是葫芦。例如 $[2, 4, 4, 2, 4]$ 就是葫芦，全相等不是葫芦，例如 $[2, 2, 2, 2, 2]$ 。
小红想知道给定的数组是不是葫芦。

void solve() {
    int a[5] = {};
    for (int i = 0;i < 5;i++)cin >> a[i];
    sort(a, a + 5);
    if (a[0] == a[1] && a[3] == a[4] && a[0] != a[3]) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

B 茉茉的密码

藏宝秘窟的大门上有一把密码锁，需要找到正确的密码才能打开这把锁。
迷窟大门的旁边还有一块石碑，石碑上有 $n$ 个只有小写字母的字符串。茉茉经过非常认真的研究发现，这把锁的密码可能有很多个，但是密码一定是石碑上 $n$ 个字符串的公共子串，且这 $n$ 个字符串的任意一个公共子串都能作为密码打开密码锁。
茉茉需要你帮她找到一个密码，你能告诉她吗？（告诉她任意一个密码即可）
公共子串：公共子串是指在这 $n$ 个字符串中的每一个都出现过的连续的一段子字符串。

这里是公共子串，实际上只需要找到 1 个字符满足都含有这个字符即可。

void solve() {
    int n;cin >> n;
    map<int, int>mp;
    for (int i = 0;i < n;i++) {
        string s;cin >> s;
        int vis[26] = {};
        for (auto ch : s) {
            if (!vis[ch - 'a']) {
                mp[ch]++;vis[ch - 'a'] = 1;
            }
        }
    }
    for (auto [x, y] : mp) {
        if (y == n) {
            cout << (char)x << '\n';return;
        }
    }
}

D 萌萌的好数

萌萌喜欢“好数”，这种“好数“需要满足以下两个条件：

该数对 $3$ 取模不为 $0$
该数的最后一位数字不为 $3$
请你告诉他第 $n$ 个好数是什么。

如果知道一个值 $x$ ，则可以计算 $x$ 前面有多少个数被叉掉了。

被叉掉的个数： $⌊ \frac{x}{3} ⌋ + ⌊ \frac{x - 3}{10} ⌋ - ⌊ \frac{x - 3}{30} ⌋$

则满足： $n + ⌊ \frac{x}{3} ⌋ + ⌊ \frac{x - 3}{10} ⌋ - ⌊ \frac{x - 3}{30} ⌋ = x$

直接枚举答案一定会超时，但由于答案具有单调性(即数字越大，答案越大)，所以可以二分。

#define int long long
void solve() {
    int n;cin >> n;
    int l = 1, r = 1e14;
    while (l < r) {
        int mid = l + r >> 1;
        int x = mid - mid / 3 - (mid - 3) / 10 + (mid - 3) / 30;
        if (x >= n) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << l << "\n";
}

C 苗苗的气球

苗苗有 $n$ 种个不同颜色气球，每种 $a_{i}$ 个，两个不同颜色气球接触后就会一起爆炸。
苗苗不小心把所有的气球混在了一起。于是气球自由的运动着，开始接触并爆炸。气球会一直运动、碰撞，直到没有气球能发生爆炸，即气球没了或者只剩下了一个颜色的气球。
计算出剩下的气球的颜色有多少种可能性。

毒瘤题

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    int sum = accumulate(a.begin(), a.end(), 0);
    int mx = *(max_element(a.begin() + 1, a.end()));
    if (mx >= sum - mx) {
        if (n == 2 && mx == sum - mx) {
            cout << "0\n";return;
        } else {
            cout << "1\n";return;
        }
    }
    int k = 0;
    for (int i = 1;i <= n;i++) {
        if ((sum - a[i]) % 2 == 0 || ((sum - a[i]) % 2 == 1 && a[i] > 1)) {
            k++;
        }
    }
    cout << k << "\n";
}

E 茜茜的计算器

茜茜有一个计算器，这个计算器在显示数字的时候会把所有的前导 0 都显示出来。
在这个计算器上，0-9 分别被显示为：

即，当这个计算器显示屏有 10 位时，让它显示数字 123456 则会显示为“0000123456”。
茜茜发现，这个计算器有时候显示的数字是一个轴对称图形，如“80808”

（“80808”的对称轴可以为横轴，也可以为纵轴。而有一些数字可能只以横轴或纵轴中的一个为对称轴，但这样的仍然是轴对称图形。）

请问，如果这个计算器显示的数有 $n (1 \leq n \leq 10^{9})$ 位时它能显示的数字中有多少种不同的轴对称图形。

Solution

由于 $n \leq 10^{9}$ ，所以一般都是 $O (l o g n) / O (1)$ 求解。

容斥：横对称+纵对称−(横/纵对称)

横对称： $0, 1, 3, 8$ 可以任意组成(横着一定是对称的)，即为 $4^{n}$ .
竖对称：有 $(2, 5), (0, 0), (8, 8), (5, 2)$ 四种可能，只能按照中心对称放置

注： $(1, 1)$ 并不能放进去，在计算器显示中是靠右边的并不对称

若 $n$ 为奇数，中间位置只能放 $0, 8$ 两种，则答案就是 $4^{n / 2} \times 2$ ，偶数则为 $4^{n / 2}$ ，化简后奇偶可以合并为 $2^{n}$

需要减去重复计算了关于横纵都对称的部分，即只有 $(0, 0), (8, 8)$ 任意放置的时候会重复计算，这部分为 $2^{⌈ n / 2 ⌉}$

答案即为 $4^{n} + 2^{n} - 2^{⌈ \frac{n}{2} ⌉}$ ， $O (1)$ 求出。

void solve() {
    int n;cin >> n;
    cout << (qpow(4, n) + qpow(2, n) + mod - qpow(2, (n + 1) / 2)) % mod;
}

F 花花的地图

A 市地图是一个 $n \times m$ 的网格图，字符'#'表示障碍，'.' 表示空地。花花住在左上角 $(1, 1)$ ，花花的朋友萌萌住在右下角 $(n, m)$ 。花花要去萌萌家玩。
花花如果走到空地则不需要任何代价，但是如果要走到障碍点则他需要先摧毁该障碍。每次可以走到相邻的四个方向之一，即从 $(x, y)$ 可以走到 $(x + 1, y)$ ， $(x - 1, y)$ ， $(x, y + 1)$ ， $(x, y - 1)$ 。
花花可以花费 $C_{i}$ 的代价将第 $i$ 列的所有障碍都消灭。
请帮花花计算她去萌萌家最少需要多少代价。

数据范围: $1 \leq n, m \leq 100, 1 \leq c_{i} \leq 10^{5}$

Solution

数位DP / 最短路 dijkstra

最短路思路：每次需要走到含有 # 的地方时，则那一列的代价都是相等的，将这一列的点及其代价全部加入进去。

法一：

{c++}dp[i][j] 为到达 $(i + 1, j + 1)$ 点最少需要花费的代价，则答案为 {c++}dp[n - 1][m - 1]

时间复杂度： $O (n^{3} + n^{2} \log n^{2})$ 若 $n, m \leq 1000$ 时会超时

堆也可以开大根堆，加入时添加一个符号即可。

void solve() {
    int n, m; cin >> n >> m;

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

    vector<int> cost(m);
    for (int i = 0; i < m; i++) cin >> cost[i];

    vector<vector<int>> dp(n, vector<int>(m, INT_MAX));
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;

    if (g[0][0] == '.') {
        pq.push({0,0,0});
        dp[0][0] = 0;
    } else {
        for (int i = 0; i < n; i++) {
            pq.push({cost[0], i,0});
            dp[i][0] = cost[0];
        }
    }

    while (!pq.empty()) {
        auto [c, x, y] = pq.top();pq.pop();
        if (c > dp[x][y]) continue;

        const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
        for (int i = 0;i < 4;i++) {
            int cx = x + dx[i], cy = y + dy[i];
            if (cx < 0 || cx >= n || cy < 0 || cy >= m) continue;
            if (g[cx][cy] == '.') {
                if (dp[cx][cy] > c) {
                    dp[cx][cy] = c;
                    pq.push({dp[cx][cy], cx, cy});
                }
            } else {
                for (int j = 0; j < n; j++) {
                    if (dp[j][cy] > c + cost[cy]) {
                        dp[j][cy] = c + cost[cy];
                        pq.push({dp[j][cy], j, cy});
                    }
                }
            }

        }
    }
    cout << dp[n - 1][m - 1] << '\n';
}

法二：

参见：牛客周赛 Round 47 解题报告 | 珂学家 _牛客博客

时间复杂度为 $O (n^{2} \log n^{2})$ ,当 $n, m \leq 1000$ 时也能通过，

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (auto& s : g) cin >> s;

    vector<int> cost(m);
    for (auto& x : cost) cin >> x;

    vector<vector<int>> dp(n + 1, vector<int>(m, INT_MAX));
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;

    if (g[0][0] == '.') {
        pq.emplace(0, 0, 0);
        dp[0][0] = 0;
    } else {
        pq.emplace(cost[0], n, 0);
        dp[n][0] = cost[0];
    }

    while (!pq.empty()) {
        auto [c, y, x] = pq.top();
        pq.pop();
        if (c > dp[y][x]) {
            continue;
        }

        if (y == n) {
            for (int i = 0; i < n; i++) {
                if (dp[i][x] > c) {
                    dp[i][x] = c;
                    pq.emplace(dp[i][x], i, x);
                }
            }
        } else {
            vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            for (auto& [dy, dx] : dir) {
                int ty = y + dy, tx = x + dx;
                if (0 <= ty && ty < n && 0 <= tx && tx < m) {
                    if (g[ty][tx] == '.' && dp[ty][tx] > c) {
                        dp[ty][tx] = c;
                        pq.emplace(dp[ty][tx], ty, tx);
                    }
                }
            }
            for (int dx = -1; dx <= 1; dx++) {
                int tx = x + dx;
                if (0 <= tx && tx < m) {
                    if (dp[n][tx] > c + cost[tx]) {
                        dp[n][tx] = c + cost[tx];
                        pq.emplace(dp[n][tx], n, tx);
                    }
                }
            }
        }
    }
    cout << dp[n - 1][m - 1] << endl;
}

A 小红的葫芦

B 茉茉的密码

D 萌萌的好数

C 苗苗的气球

E 茜茜的计算器

Solution

F 花花的地图

Solution

法一 ：

法二 ：

法一：

法二：