2024牛客暑期多校训练营9

难度梯度 AKI HBC DGE JF

A Image Scaling

题意

给出一个 \(n*m\) 的矩阵，里面有一个 'x' 矩阵。

你需要将 'x' 矩阵扣出来，并将他缩放到最小比例(长比宽为最简分数)。

解题思路

因为只有一个 'x' 矩阵，我们直接计算 'x' 的最大最小的行和列坐标。

这样最大行坐标减去最小行坐标就是 'x' 的宽，最大列坐标减去最小列坐标就是 'x' 的长。

然后对长和宽进行约分，最后输出即可。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
string a[505];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    int mix = 1e6, miy = 1e6, mxx = 0, mxy = 0;
    for (int i = 0 ; i < n ; i++) {
        cin >> a[i];
        for (int j = 0 ; j < m ; j++) {
            if (a[i][j] == 'x') {
                mix = min(mix, i);
                miy = min(miy, j);
                mxx = max(mxx, i);
                mxy = max(mxy, j);
            }
        }
    }
    int h = mxx - mix + 1, w = mxy - miy + 1;
    int g = __gcd(h, w);
    h /= g;
    w /= g;
    for (int i = 0 ; i < h ; i++) {
        for (int j = 0 ; j < w ; j++) {
            cout << "x";
        }
        cout << "\n";
    }
    return 0;
}

B Break Sequence

题意

给你一个长度为 \(n\) 的数组 \(a\)，和一个大小为 \(m\) 的集合 \(S\)。

你可以将数组 \(a\) 划分成任意段，但是每一段都要满足一个要求，

即，每一段中任意元素出现的次数不能在 \(S\) 集合中。

问你有多少种划分方案。

解题思路

一种朴素的dp思路，如果我们能求出所有合法的区间。

那么对于每个区间 \([L,R]\) 都对 \(dp_R\) 贡献 \(dp_{L-1}\)。

这里的区间 \([L,R]\) 要按照 \(R\) 从小到大排序。

所以对于以 \(R\) 为右端的合法区间的左端点 \(L\)，都有 \(dp_R=\sum_{L\text{合法}} dp_{L-1}\)。

这里相当于所有合法的左端点的和。

这里就有两个操作，单点加和区间查询。

这里我们建立一颗线段树，下标 \(i\) 表示 \(dp_{i-1}\) 的值。

我们通过枚举集合 \(S\) 中的数 \(x\)，将数量恰好为 \(x\) 的区间的左端点和右端点存下在，

使用二维数点，从小到大枚举右端点 \(R\)，

对线段树的区间打标记，如果标记不为 \(0\)，说明在这个区间内的左端点都不合法，否则说明有合法的左端点。

最后每次更新 \(dp_R\) 即可。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 200005;
const i64 P = 998244353;
i64 tr[N << 2];
int tag[N << 2];
void pushup(int p) {
    tr[p] = 0;
    if (tag[p << 1] == 0) {
        tr[p] += tr[p << 1];
    }
    if (tag[p << 1 | 1] == 0) {
        tr[p] += tr[p << 1 | 1];
    }
    tr[p] %= P;
}
i64 dp[N];
void modify(int p, int L, int R, int QL, int QR, int k) {
    if (QL <= L && R <= QR) {
        tag[p] += k;
        return;
    }
    int mid = L + R >> 1;
    if (QL <= mid) modify(p << 1, L, mid, QL, QR, k);
    if (QR > mid) modify(p << 1 | 1, mid + 1, R, QL, QR, k);
    pushup(p);
}
void modify1(int p, int L, int R, int pos, int k) {
    if (L == R) {
        tr[p] = k;
        return;
    }
    int mid = L + R >> 1;
    if (pos <= mid) modify1(p << 1, L, mid, pos, k);
    if (pos > mid) modify1(p << 1 | 1, mid + 1, R, pos, k);
    pushup(p);
}
i64 query(int p, int L, int R, int QL, int QR) {
    if (tag[p] != 0) {
        return 0;
    }
    if (QL <= L && R <= QR) {
        return tr[p];
    }
    int mid = L + R >> 1;
    if (QR <= mid) return query(p << 1, L, mid, QL, QR);
    if (QL > mid) return query(p << 1 | 1, mid + 1, R, QL, QR);
    return query(p << 1, L, mid, QL, QR) + query(p << 1 | 1, mid + 1, R, QL, QR);
}
int a[N];
vector<int> pos[N];
vector<array<int, 3>> vec[N];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;

    for (int i = 1 ; i <= n ; i++) {
        pos[i].push_back(0);
    }
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    for (int i = 1 ; i <= n ; i++) {
        pos[i].push_back(n + 1);
    }
    set<int> st;
    for (int i = 0 ; i < m ; i++) {
        int x;
        cin >> x;
        st.insert(x);
    }
    auto add = [&](int L1, int R1, int L2, int R2) {
        vec[L1].push_back({L2, R2, 1});
        vec[R1 + 1].push_back({L2, R2, -1});
    };
    for (auto &x : st) {
        for (int i = 1 ; i <= n ; i++) {
            auto &p = pos[i];
            int len = p.size();
            for (int j = 0 ; j + x < len ; j++) {
                int L1 = p[j - 1] + 1, R1 = p[j];
                int L2 = p[j + x - 1], R2 = p[j + x] - 1;
                swap(L1, L2);
                swap(R1, R2);
                if (L1 <= R1 && L2 <= R2) {
                    add(L1, R1, L2, R2);
                }
            }
        }
    }
    dp[0] = 1;
    for (int i = 1 ; i <= n ; i++) {
        modify1(1, 1, n, i, dp[i - 1]);
        for (auto &[L, R, k] : vec[i]) {
            modify(1, 1, n, L, R, k);
        }
        dp[i] = query(1, 1, n, 1, i) % P;
    }
    cout << dp[n] << "\n";
    return 0;
}

C Change Matrix

题意

有一个 \(n*n\) 的矩阵，第 \(i\) 行第 \(j\) 列的初始值为 \(\gcd(i,j)\)。

有 \(q\) 次操作，每次操作选择第 \(x\) 行/列，使这一行/列的值全部乘上 \(y\)。

每次操作后，问矩阵所有值的和模 \(1e9+7\)。

\(n,q\le10^5\)

保证操作是随机生成的。

解题思路

由欧拉反演可以知道 \(\gcd(i,j)=\sum_{d|\gcd(i,j)}\varphi(d)\)。

那么对于 \(\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)=\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid\gcd(i,j)}\varphi(d)\)，

考虑枚举 \(d\)，得原式 \(=\sum_{d=1}^n\varphi(d)*(\sum_{i=1}^n[d\mid i])*(\sum_{j=1}^n[d\mid j])\)。

那么对于行和列的贡献是完全可以分开的。

我们这里只考虑行，我们定义 \(rsum_i\) 为 \(d=i\) 时的 \(\sum_{i=1}^n[d\mid i]\)，\(csum_i\) 为 \(d=i\) 时的 \(\sum_{j=1}^n[d\mid j]\)。

那么如果对第 \(x\) 行操作，那么在式子里只影响 \(i=x\)，

当 \(i=x\) 时，\(d\) 一定是 \(x\) 的约数，所以我们要对所有 \(x\) 的约数操作，

对于所有的 \(d\) 我们还需要存一个乘过了多少，即 \(rmul_{d,i},cmul_{d,i}\)。

因为对于 \(d\) 来说，只需要修改 \(d\) 的倍数，所以上述 \(rmul,cmul\) 的 \(i\) 一定不超过 \(\frac{n}{i}\) 个数。

所以在操作随机的条件下，时间复杂度是 \(O(q\log V)\) 的。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int h[256];
i64 sum[2][100005];
vector<i64> mul[2][100005];
int phi[100005];
bool vis[100005];
vector<int> prime;
vector<int> factors[100005];
const i64 P = 1000000007;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    phi[1] = 1;
    for (int i = 2 ; i <= 100000 ; i++) {
        if (!vis[i]) {
            prime.push_back(i);
            phi[i] = i - 1;
        }
        for (auto &x : prime) {
            if (1LL * i * x > 100000) break;
            vis[i * x] = true;
            if (i % x == 0) {
                phi[i * x] = phi[i] * x;
                break;
            }
            phi[i * x] = phi[i] * phi[x];
        }
    }
    for (int i = 1 ; i <= 100000 ; i++) {
        for (int j = i ; j <= 100000 ; j += i) {
            factors[j].push_back(i);
        }
    }
    h['R'] = 0;
    h['C'] = 1;
    int n, q;
    cin >> n >> q;
    i64 ans = 0;
    for (int i = 1 ; i <= n ; i++) {
        for (auto x : {0, 1}) {
            mul[x][i].resize(n / i + 1, 1);
            sum[x][i] += n / i;
        }
        ans = (ans + (i64) phi[i] * sum[0][i] % P * sum[1][i]) % P;
    }
    while (q--) {
        char ch;
        int x, y;
        cin >> ch >> x >> y;
        int z = h[ch];
        for (auto &k : factors[x]) {
            int idx = x / k;
            ans = (ans - (i64) phi[k] * sum[0][k] % P * sum[1][k] % P + P) % P;
            sum[z][k] = (sum[z][k] - mul[z][k][idx] + P) % P;
            mul[z][k][idx] = (i64) mul[z][k][idx] * y % P;
            sum[z][k] = (sum[z][k] + mul[z][k][idx]) % P;
            ans = (ans + (i64) phi[k] * sum[0][k] % P * sum[1][k]) % P;
        }
        cout << ans << "\n";
    }
    return 0;
}

H Two Convex Polygons

题意

在两维平面，有凸包 \(A\) 和凸包 \(B\)，凸包 \(A\) 固定，

凸包 \(B\) 可以任意旋转，平移，反转，但是凸包 \(B\) 必须和凸包 \(A\) 有交。

问凸包 \(B\) 所有可能位置的并区域的外周长。

解题思路

可以知道最外围一定是凸包 \(A\) 与凸包 \(B\) 恰好相交，那么就是围着凸包 \(A\) 向外扩凸包 \(B\) 的直径。

那么此时外周长其实就是凸包 \(A\) 的周长加上一个圆，这个圆的半径是凸包 \(B\) 的直径。

我们可以通过旋转卡壳来求得凸包 \(B\) 的直径，然后就可以计算外周长了。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using Tdouble = long double;
const Tdouble eps = 1e-9;
const Tdouble PI = acos(-1.0);
int sgn(Tdouble x) {
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}
struct Point {
    i64 x, y;
    Point() = default;
    Point(int x, int y) : x(x), y(y) {}
    Point(i64 x, i64 y) : x(x), y(y) {}
};
Point operator-(const Point A, const Point B) {
    return Point{A.x - B.x, A.y - B.y};
}
struct Line {
    Point v, p1, p2;
    Line(Point a1, Point a2) {
        v = a2 - a1;
        p1 = a1;
        p2 = a2;
    }
};
i64 cross(Point A, Point B) {
    return A.x * B.y - A.y * B.x;
}
i64 distance2(Point A, Point B) {
    return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}
Tdouble distance(Point A, Point B) {
    return sqrtl(distance2(A, B));
}
Tdouble RoatingCalipers(const vector<Point> &p) {
    i64 ans = 0;
    int len = p.size(), cur = 0;
    for (int i = 0 ; i < len ; i++) {
        Line line(p[i], p[(i + 1) % len]);
        while (llabs(cross(p[cur] - line.p1, line.v)) <= llabs(cross(p[(cur + 1) % len] - line.p1, line.v))) {
            cur = (cur + 1) % len;
        }
        ans = max({ans, distance2(p[i], p[cur]), distance2(p[(i + 1) % len], p[cur])});
    }
    return sqrtl(ans);
}
void solve() {
    int n;
    cin >> n;
    vector<Point> A, B;
    for (int i = 0 ; i < n ; i++) {
        int x, y;
        cin >> x >> y; 
        Point t{x, y};
        A.push_back(t);
    }
    int m;
    cin >> m;
    for (int i = 0 ; i < m ; i++) {
        int x, y;
        cin >> x >> y;
        Point t{x, y};
        B.push_back(t);
    }
    Tdouble r = RoatingCalipers(B);
    Tdouble ans = 0;
    for (int i = 0 ; i < n ; i++) {
        ans += distance(A[i], A[(i + 1) % n]);
    }
    ans += 2 * PI * r;
    cout << fixed << setprecision(20) << ans << "\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

I Interesting Numbers

题意

给你一个 \(L\)，

解题思路

解题代码

代码

Python
n = int(input())
L, R = map(int, input().split())
def find(x):
    L = 0
    R = x
    while L < R:
        mid = (L + R + 1) // 2
        if mid * mid <= x:
            L = mid
        else:
            R = mid - 1
    return L + 1
def s(y):
    d = 10 ** (n // 2)
    pre = y // d
    lst = y % d
    z = find(pre) - 1
    ans = 0
    if z * z == pre:
        ans = ans + find(lst)
    zz = 10 ** (n // 2)
    ans = ans + (find(pre - 1) - find(zz // 10 - 1)) * find(zz - 1)
    return ans
if L == 10 ** (n / 2):
    print(s(R))
else:
    print(s(R) - s(L - 1))

K Kill The Monsters

题意

有 \(n\) 只怪物，血量分别为 \(a_i\)。

血量为 \(0\) 代表怪物死亡。

你有两种攻击方式：

① 使所有怪物的血量减一。

② 选择一个怪物的血量使得 \(a_i=\lfloor\dfrac{a_i}{k}\rfloor\)。

问杀死所有怪物的最少的攻击次数。

解题思路

可以发现，① 和 ② 没有先后顺序。

所以我们肯定是先用 ② 再用 ①。

然后我们可以发现当 \(k>1\) 时， ② 的操作次数不可能超过 \(50n\)。

那么我们可以枚举 ② 的次数，每次都选择血量最高的怪物进行攻击。

然后计算答案。

对于 \(k=1\) 的情况，我们肯定只用 ① 最优。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    int mx = 0;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    if (k == 1) {
        cout << mx << "\n";
    } else {
        priority_queue<i64> que;
        for (int i = 1 ; i <= n ; i++) {
            que.push(a[i]);
        }
        i64 ans = que.top();
        for (int i = 1 ; ; i++) {
            if (que.empty()) {
                break;
            }
            i64 x = que.top();
            que.pop();
            x /= k;
            if (x > 0) {
                que.push(x);
            }
            if (que.empty()) {
                ans = min<i64>(ans, i);
                break;
            } else {
                ans = min(ans, i + que.top());
            }
        }
        cout << ans << "\n";
    }
    return 0;
}