1985(952div4)

A. Creating Words

马修得到了长度均为 $3$ 的两个字符串 $a$ 和 $b$ 。交换 $a$ 的第一个字符和 $b$ 的第一个字符来创建两个新词特别有趣。他想让你在交换后输出 $a$ 和 $b$ 。

void solve() {
    string a, b;cin >> a >> b;
    swap(a[0], b[0]);
    cout << a << " " << b << '\n';
}

B. Maximum Multiple Sum

给定整数 $n (2 \leq n \leq 100)$ ，求一个整数 $x$ ，使得：

$2 \leq x \leq n$ .
小于或等于 $n$ 的 $x$ 的倍数之和最大。形式上， $x + 2 x + 3 x + \dots + k x$ 中的 $k x \leq n$ 在 $x$ 的所有可能值中最大。

void solve() {
    int n;cin >> n;
    int ans = 0, idx = 0;;
    for (int i = 2, k = n / i;i <= n;i++) {
        if ((k + 1) * k * i / 2 > ans) {
            ans = (k + 1) * k * i / 2;
            idx = i;
        }
    }
    cout << idx << '\n';
}

C. Good Prefixes

亚历克斯认为，如果存在某个元素可以表示为所有其他元素之和（如果没有其他元素，所有其他元素之和为 $0$ ），那么这个数组就是好数组。例如，数组 $[1, 6, 3, 2]$ 是好数组，因为 $1 + 3 + 2 = 6$ 。此外，数组 $[0]$ 也是好数组。然而，数组 $[1, 2, 3, 4]$ 和 $[1]$ 却不是好数组。

亚历克斯有一个数组 $a_{1}, a_{2}, \dots, a_{n}$ 。帮他计算数组 $a$ 的非空前缀的个数。换句话说，数出长度为 $i$ 的前缀（即 $a_{1}, a_{2}, \dots, a_{i}$ ）的整数 $i$ ( $1 \leq i \leq n$ 的个数。

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    int sum = 0, mx = -1, ans = 0;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;
        sum += x;
        mx = max(mx, x);
        if (sum - mx == mx)ans++;
    }
    cout << ans << '\n';
}

D. Manhattan Circle

给定一个由'.'和'#'字符组成的 $n$ 乘 $m$ 网格，网格上存在一个完整的曼哈顿圆。网格左上角的坐标为 $(1, 1)$ ，右下角的坐标为 $(n, m)$ 。

点（ $a, b$ ）属于以（ $h, k$ ）为中心的曼哈顿圆，如果 $| h - a | + | k - b | < r$ ，其中 $r$ 是一个正常数。

在网格上，属于曼哈顿圆的点集标记为 "#"。求圆心坐标。

将这个图形的下标都存下来，然后取中间即可。

void solve() {
    int n, m;cin >> n >> m;
    vector<string> s(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> s[i];s[i] = ' ' + s[i];
    }
    set<pair<int, int>>st;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (s[i][j] == '#') {
                st.insert({i,j});
            }
        }
    }
    int mihx = 1e6, mxhx = 0;
    int mihy = 1e6, mxhy = 0;
    for (auto [x, y] : st) {
        mihx = min(mihx, x);
        mxhx = max(mxhx, x);
        mihy = min(mihy, y);
        mxhy = max(mxhy, y);
    }
    cout << (mihx + mxhx) / 2 << " " << (mihy + mxhy) / 2 << '\n';
}

E. Secret Box

Ntarsis 有一个边长为 $x$ 、 $y$ 和 $z$ 的方格 $B$ 。它位于三维坐标平面中，从 $(0, 0, 0)$ 延伸到 $(x, y, z)$ 。

恩塔西斯有一个秘密盒子 $S$ 。他希望选择的尺寸是：所有边长都是正整数， $S$ 的体积是 $k$ 。他可以将 $S$ 放置在 $B$ 中的某处，以便：

$S$ 与所有轴平行。
$S$ 的每个角都位于一个整数坐标上。

$S$ 具有魔力，因此将其放置在 $B$ 内的整数位置时，它不会掉落到地面上。

在选择 $S$ 尺寸的所有可能方法中，确定他在 $B$ 内放置秘密盒子 $S$ 所能选择的多个不同位置。一旦选择了 $S$ 的边长，Ntarsis 就不会旋转 $S$ 。

枚举两维第三维即可确定，确定了一个 $S$ 后，则在 $B$ 中的方案数容易确定

#define int long long
void solve() {
    int x, y, z, v;cin >> x >> y >> z >> v;
    int ans = 0;
    for (int i = 1;i <= x;i++) {
        for (int j = 1;j <= y;j++) {
            int k = v / (i * j);
            if (i * j * k != v || k > z)continue;
            ans = max(ans, (x - i + 1) * (y - j + 1) * (z - k + 1));
        }
    }
    cout << ans << '\n';
}

F. Final Boss

您正在面对您最喜欢的视频游戏中的最终 Boss。敌人的生命值为 $h$ 。你的角色有 $n$ 次攻击。 $i$ 的攻击会对敌人造成 $a_{i}$ 的伤害，但冷却时间为 $c_{i}$ 回合，也就是说，如果你当前的回合是 $x$ ，那么下一次使用该攻击的时间是 $x + c_{i}$ 回合。每个回合，你都可以使用当前未冷却的所有攻击，一次。如果所有攻击都处于冷却状态，则该回合你什么也不做，跳到下一回合。

最初，所有攻击都不在冷却时间内。要花多少回合才能打败老板？

显然有技能就放就是最优的，直接二分答案计算最小的回合即可(本题 $h \leq 2 \times 19^{5}$ ，所以可以直接模拟，若 $h \leq 10^{9}$ 则一定需要二分答案了)

时间复杂度 $n \log n$

注：本题数据计算过程中最大的数据要达到 $(2 \times 10^{5})^{2} \times \frac{l + r}{2} \leq 4 \times 10^{23}$ ，会爆 {c++}long long，可以开 {c++}int128 或者当计算结果大于 $h$ 后就直接下一轮

#define int long long
void solve() {
    int h, n;cin >> h >> n;
    vector<int> a(n + 1), c(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)cin >> c[i];
    __int128_t hh = h;
    int l = 1, r = 1e13;
    while (l < r) {
        int mid = l + r >> 1;
        __int128_t sum = 0;
        for (int i = 1;i <= n;i++) {
            sum += (mid + c[i] - 1) / c[i] * a[i];
        }
        if (sum >= hh)r = mid;
        else l = mid + 1;
    }
    cout << l << '\n';
}

G. D-Function

让 $D (n)$ 表示 $n$ 的数位之和。有多少个整数 $n$ 其中的 $10^{l} \leq n < 10^{r}$ 满足 $D (k \cdot n) = k \cdot D (n)$ ?输出以 $10^{9} + 7$ 为模数的答案。

当 $k \geq 10$ 时， $D (k \cdot n) \neq 10 \cdot D (n)$ 恒成立，所以没有方案

当 $k \in [1, 9]$ 时，若对于 $n$ 的每一位 $b_{i}$ 都满足 $k \cdot b_{i} < 10$ ，则是一个方案

以

k = 2

为例：

即要求 $n \in [10^{l}, 10^{r})$ 区间内满足每一位都 $\leq 4$ 的个数

若 $n$ 位数为 $l + 1$ (即和 $10^{l}$ 同数量级)，则除了第一位是 4 种选择，其他数都是 5 种选择，方案数为 $4 \times 5^{l}$

同理，位数为 $l + 2$ ，方案数为 $4 \times 5^{l + 1}$

依次类推，位数为 $r$ 时方案数为 $4 \times 5^{r - 1}$

则总方案数为： $4 \times 5^{l} + 4 \times 5^{l + 1} \times \dots \times 4 \times 5^{r - 1} = 5^{r} - 5^{l}$

答案为 ${⌈ \frac{10}{k} ⌉}^{r} - {⌈ \frac{10}{k} ⌉}^{l} mod 10^{9} + 7$

constexpr int mod = 1e9 + 7;
void solve() {
    cout << (qpow((10 + k - 1) / k, r) - qpow((10 + k - 1) / k, l) + mod) % mod << '\n';
}

H. Maximize the Largest Component

给定一个 $n \times m (n \times m \leq 10^{6})$ 的网格，可以从任意 # 单元格出发到其他 # 单元格，方向为上下左右，构成了若干连通块。

{c++}easy version:可以将某一行或某一列全变为 #

{c++}hard version: 可以将某一行和某一列全变为 #

求最大连通部分的最大可能大小。

Solution

easy version

我的想法：先将所有的连通块找出来，再枚举 $n$ 行 $m$ 列看填满哪种情况最大。

代码：

int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
void solve() {
    int n, m;cin >> n >> m;
    vector<string> s(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> s[i];s[i] = ' ' + s[i];
    }

    map<pair<int, int>, pair<int, int>>vis;
    int cnt = 0;//第几个连通块

    auto bfs = [&](int sx, int sy) {
        int sum = 0;//连通块大小
        queue<pair<int, int>>q;cnt++;
        q.push({sx,sy});
        vis[{sx, sy}] = {cnt,++sum};
        while (q.size()) {
            auto [x, y] = q.front();q.pop();
            for (int i = 0;i < 4;i++) {
                int a = x + dx[i], b = y + dy[i];
                if (a<1 || b<1 || a>n || b>m || vis.count({a,b}) || s[a][b] == '.')continue;
                vis[{a, b}] = {cnt,++sum};q.push({a,b});
            }
        }
        q.push({sx,sy});
        vis[{sx, sy}] = {cnt,sum};
        map<pair<int, int>, int>mp;
        while (q.size()) {
            auto [x, y] = q.front();q.pop();
            for (int i = 0;i < 4;i++) {
                int a = x + dx[i], b = y + dy[i];
                if (a<1 || b<1 || a>n || b>m || s[a][b] == '.' || mp.count({a,b}))continue;
                if (vis.count({a,b})) {
                    vis[{a, b}] = {cnt,sum};q.push({a,b});mp[{a, b}] = 1;
                }
            }
        }
        };
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (s[i][j] == '#' && !vis.count({i,j})) {
                bfs(i, j);
            }
        }
    }
    int ans = 0;
    for (auto [x, y] : vis) {
        ans = max(ans, y.second);
    }

    for (int i = 1;i <= n;i++) {
        map<int, int>st;
        int sum = 0;
        for (int j = 1;j <= m;j++) {
            if (!vis.count({i,j})) {
                sum++;
            } else {
                if (!st.count(vis[{i, j}].first)) {
                    sum += vis[{i, j}].second;st[vis[{i, j}].first] = 1;
                }
            }
            if (vis.count({i - 1,j})) {
                if (!st.count(vis[{i - 1, j}].first)) {
                    sum += vis[{i - 1, j}].second;st[vis[{i - 1, j}].first] = 1;
                }
            }
            if (vis.count({i + 1,j})) {
                if (!st.count(vis[{i + 1, j}].first)) {
                    sum += vis[{i + 1, j}].second;st[vis[{i + 1, j}].first] = 1;
                }
            }
        }
        ans = max(ans, sum);
    }
    for (int j = 1;j <= m;j++) {
        map<int, int>st;
        int sum = 0;
        for (int i = 1;i <= n;i++) {
            if (!vis.count({i,j})) {
                sum++;
            } else {
                if (!st.count(vis[{i, j}].first)) {
                    sum += vis[{i, j}].second;st[vis[{i, j}].first] = 1;
                }
            }
            if (vis.count({i ,j - 1})) {
                if (!st.count(vis[{i, j - 1}].first)) {
                    sum += vis[{i, j - 1}].second;st[vis[{i, j - 1}].first] = 1;
                }
            }
            if (vis.count({i ,j + 1})) {
                if (!st.count(vis[{i, j + 1}].first)) {
                    sum += vis[{i, j + 1}].second;st[vis[{i, j + 1}].first] = 1;
                }
            }
        }
        ans = max(ans, sum);
    }
    cout << ans << '\n';
}

当 # 特别多的时候会 TLE

先将整个网格含 # 的用并查集连成若干连通块，再和之前思路一样分别考虑即可。

// 模板整理——并查集
void solve() {
    int n, m;
    cin >> n >> m;

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

    const int N = n * m;
    DSU dsu(N);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i + 1 < n && s[i][j] == '#' && s[i + 1][j] == '#') {
                dsu.merge(i * m + j, (i + 1) * m + j);
            }
            if (j + 1 < m && s[i][j] == '#' && s[i][j + 1] == '#') {
                dsu.merge(i * m + j, i * m + j + 1);
            }
        }
    }

    vector<int> vis(N, -1);
    int ans = 0;
    for (int r = 0; r < n; r++) {
        int res = 0;
        for (int i = 0; i < m; i++) {
            if (s[r][i] == '.') {
                res++;
            }
            for (int x = max(0, r - 1); x <= min(n - 1, r + 1); x++) {
                if (s[x][i] == '#') {
                    int u = dsu.find(x * m + i);
                    if (vis[u] != r) {
                        vis[u] = r;
                        res += dsu.size(u);
                    }
                }
            }
        }
        ans = max(ans, res);
    }
    vis.assign(N, -1);
    for (int c = 0; c < m; c++) {
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (s[i][c] == '.') {
                res++;
            }
            for (int y = max(0, c - 1); y <= min(m - 1, c + 1); y++) {
                if (s[i][y] == '#') {
                    int u = dsu.find(i * m + y);
                    if (vis[u] != c) {
                        vis[u] = c;
                        res += dsu.size(u);
                    }
                }
            }
        }
        ans = max(ans, res);
    }

    cout << ans << "\n";
}

hard version

...