茶-2025-02

Tea

20250203

Problem

输入 T(≤1e3) 表示 T 组数据。所有数据的 n 之和 ≤2e5，q 之和 ≤2e5。
每组数据输入 n(1≤n≤2e5)，q(1≤q≤2e5)，长为 n 的字符串 s，长为 n 的字符串 t，都只包含小写英文字母。
然后输入 q 个询问，每个询问输入两个数 L 和 R，表示下标从 L 到 R 的子串 (1≤L≤R≤n) s[L..R] 和 t[L..R]。

对于每个询问，你可以修改 s[L..R] 中的若干字母，使得 s[L..R] 和 t[L..R] 排序后相等。
输出最小修改次数。

注意：每个询问互相独立。

进阶：值域更大的情况 Rearrange Query

Example

输入

3
5 3
abcde
edcba
1 5
1 4
3 3
4 2
zzde
azbe
1 3
1 4
6 3
uwuwuw
wuwuwu
2 4
1 3
1 6

输出

Solution

问题相当于计算这两个子串每种字母个数之差的总和。
由于一次操作可以把 s 中的多余字母变成 t 中的缺失字母，所以总和除以 2 便是答案。

字母个数之差可以用前缀和处理。

void solve()
{
    int n,q;
    cin >> n >> q;
    string a,b;
    cin >> a >> b;
    vector<vector<int>> sum(n+1,vector<int>(26));
    for (int i = 0; i < n; i++) {
        sum[i+1] = sum[i];
        sum[i+1][a[i]-'a']++;
        sum[i+1][b[i]-'a']--;
    }
    for (int i = 0; i < q; i++) {
        int l,r;
        cin >> l >> r;
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans += abs(sum[r][i]-sum[l-1][i]);
        }
        cout << ans/2 << endl;
    }
}

20250204

Problem

Iva & Pav

输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤2e5，q 之和 ≤2e5。
每组数据输入 n(1≤n≤2e5) 和长为 n 的数组 a(1≤a[i]≤1e9)，下标从 1 开始。
然后输入 q(1≤q≤1e5) 和 q 个询问，每个询问输入 L(1≤L≤n) 和 k(1≤k≤1e9)。

对于每个询问，输出最大的 R，满足非空连续子数组 a[L]~a[R] 的 AND >= k。
如果不存在这样的 R，输出 -1。

Example

输入

3
5
15 14 17 42 34
3
1 7
2 15
4 5
5
7 5 3 1 7
4
1 7
5 7
2 3
2 2
7
19 20 15 12 21 7 11
4
1 15
4 4
7 12
5 7

输出

1
2
3

2 -1 5
1 5 2 2
2 6 -1 5

Solution

通过每一位计算前缀和，然后二分运算结果，找到最大满足的结果

void solve()
{
    int n;
    cin >> n;
    vi a(n);
    cnv(a);
    vector<vector<int>> prefix(31, vi(n+1,0));
    for (int b = 0; b < 31; ++b) {
        for (int i = 0; i < n; i++) {
            prefix[b][i+1] = prefix[b][i] + ((a[i]>>b)&1);
        }
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l,k;
        cin >> l >> k;
        int left = l - 1;
        if (left >= n) {
            cout << -1 << '\n';
            continue;
        }
        int low = left;
        int high = n - 1;
        int ans = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            int current_and = 0;
            for (int b = 30; b >= 0; --b) {
                int cnt = prefix[b][mid + 1] - prefix[b][left];
                if (cnt == (mid - left + 1)) {
                    current_and |= (1 << b);
                }
                int remaining_bits_mask = (1 << b) - 1;
                int possible_max = current_and | remaining_bits_mask;
                if (possible_max < k) {
                    break;
                }
            }
            if (current_and >= k) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        if (ans != -1) {
            cout << ans + 1 << ' ';
        } else {
            cout << -1 << ' ';
        }
    }
    cout << endl;
}

20250205

Problem

XXOR

输入 n(1≤n≤1e5) k(0≤k≤1e12) 和长为 n 的数组 a(0≤a[i]≤1e12)。

选择一个 [0,k] 中的整数 x，最大化 (x XOR a[1]) + (x XOR a[2]) + … + (x XOR a[n])。
输出这个最大值。

Example

输入

1 2	`3 7 1 6 3`

输出

输入

1 2	`4 9 7 4 0 3`

输出

输入

1 2	`1 0 1000000000000`

输出

1	`1000000000000`

Solution

核心思路：
拆位，对于每个比特位，如果这一位 1 多，那么 x 这一位取 0 更合适；如果这一位 0 多，那么 x 这一位取 1 更合适。
设从低到高第 i 个比特位的 1 的个数是 cnt1[i]，那么这个比特位对答案的贡献是 max(cnt1[i], n-cnt1[i]) << i。

但是，x 的值受到 k 的约束，怎么处理？

为方便计算，下面讨论的是 k+1。
从最高位 i=39 开始枚举。
如果 k+1 在最高位是 1，且 x 在这一位是 0，那么 x 在更低的比特位上可以是 0 也可以是 1（不受 k 的约束）。
直接累加所有 max(cnt1[i], n-cnt1[i]) << j（其中 j < i），更新答案的最大值。
更新之后，剩下需要讨论的是 x 在这一位一定是 1 的情况。我们先把 (n-cnt1[i]) << i 加入变量 pre 中，然后把 i 减一，继续讨论后续的比特位。

如果 k+1 在第 i 位是 0，那么 x 在这一位也只能是 0，跳过。把 cnt1[i] << i 加入变量 pre 中。
如果 k+1 在第 i 位是 1，且 x 在这一位是 0，那么更低的比特位可以随便选（不受约束），累加 max(cnt1[i], n-cnt1[i]) << j（其中 j < i），再加上 pre 以及 cnt1[i] << i，更新答案的最大值。

代码实现时，可以提前计算低 i 位的所有 max(cnt1[i], n-cnt1[i]) << i 之和，记作 suf[i+1]。

int countTrailingZeros(int x) {
    int count = 0;
    while ((x & 1) == 0 && x > 0) {
        count++;
        x >>= 1;
    }
    return count;
}
void solve()
{
    const int mx = 40;
    int n,k,v,pre=0,ans=0;
    cin >> n >> k;
    vi cnt(mx,0);
    for (int i = 0; i < n; i++) {
        cin >> v;
        for (int j = v; j > 0; j &= (j-1)) {
            cnt[countTrailingZeros(j)]++;
        }
    }
    //print(cnt);cout << endl;
    vi suf(mx+1);
    for (int i = 0; i < mx; i++) {
        suf[i+1] = suf[i] + (max(cnt[i], n-cnt[i])<<i);
    }
    //print(suf);cout << endl;
    k++;
    for (int i = mx - 1; i >= 0; i--) {
        if (((k >> i) & 1) > 0) {
            ans = max(ans, pre+(cnt[i]<<i)+suf[i]);
            pre += (n-cnt[i])<<i;
        } else {
            pre += cnt[i]<<i;
        }
    }
    cout << ans << endl;
}

20250206

Problem

Sum Equals Xor

输入一个长度至多为 1e5+1 的二进制字符串 s，不含前导零。

把 s 当作一个二进制数。
输出有多少对非负整数 (a,b)，满足 a + b <= s 且 a + b = a XOR b。
答案模 1e9+7。

Example

输入

输出

输入

1	`1111111111111111111`

输出

1	`162261460`

Solution

a + b = a XOR b 意味着加法不能有进位，也就是同一个比特位不能都是 1。

下面以 s=100100 为例。

对于最高位的 s[0]=1，如果 a+b 在这一位是 0，那么对于 a+b 来说，右边的每个比特位可以填 0 也可以填 1。也就是 a+b = 0xxxxx。
对于 a 和 b，在 x 填什么，有三种情况：都是 0，一个是 0 另一个是 1。
由于每一位互相独立，有 pow(3, n-1-i) 种方案（其中 n 是 s 的长度，i=0）。

对于另一个 s[3]=1，同理，如果 a+b 在这一位是 0，那么对于 a+b 来说，右边的每个比特位可以填 0 也可以填 1。也就是 a+b = 1000xx。
对于 a 和 b，在 x 填什么，有三种情况：都是 0，一个是 0 另一个是 1。
再算上前面的 s[0]=1 这一位，a 和 b 必须一个是 0 另一个 1，所以有 pow(2, pre1) * pow(3, n-1-i) 种方案（其中 pre1=1，i=3）。

最后算上 a+b 恰好等于 s 的情况，有 pow(2, cnt1) 种方案（其中 cnt1 是 s 中的 1 的个数）。

计算 pow 用快速幂。

void solve()
{
    string s;
    cin >> s;
    int ans = 0,pow2 = 1;
    for (auto c : s) {
        if (c == '1') {
            ans = (ans + pow2*mypow(3, s.size()-1-i)) % mod;
            pow2 = pow2 * 2 % mod;
        }
    }
    cout << (ans + pow2) % mod << endl;
}

20250207

Problem

Digits Paradise in Hexadecimal

输入长度 ≤2e5 的字符串 s 和整数 k(1≤k≤16)。
s 表示一个十六进制数，无前导零。

在 [1,s] 中，有多少个（无前导零的）十六进制数，恰好包含 k 个不同的数字？这里的数字指 0~9 和 A~F。
答案模 1e9+7。

Example

输入 10 1
输出 15

输入 FF 2
输出 225

输入 100 2
输出 226

输入 1A8FD02 4
输出 3784674

输入 DEADBEEFDEADBEEEEEEEEF 16
输出 153954073

Solution

数位 DP。

考虑把填入的数字用位运算状压成一个 mask，这样我们可以知道有多少个不同数字。
但是 (i, mask) 状态个数太多了，如何简化？

如果后续填入的数字，不受到 s 的约束，那么考虑以下两种情况：
前面填的数字有 1,2,3。
前面填的数字有 2,3,4。
虽然填入的数字不同，但是不同数字的个数是相同的，这意味着后面填【其他数字】的方案数是【等价】的：
前面填的数字有 1,2,3 的情况下，后面填 1，不改变 mask；后面填 4，那么 mask 会多一个比特位。
前面填的数字有 2,3,4 的情况下，后面填 2，不改变 mask；后面填 1，那么 mask 会多一个比特位。
这种 mask【是否改变】，对于这两种情况都是等价的（或者说可以找到一一对应关系）。

所以我们只需要记忆化 (i, mask 中的 1 的个数) 这个状态。
于是状态个数大大减少，总体时间复杂度为 O(nk^2)。

注意前导零影响答案，可以写 isNum 参数，或者根据 mask 是否为 0 来判断。

void solve()
{
    string s;
    int k;
    cin >> s >> k;

    vector<vector<int>> memo(s.length(), vector<int>(k + 1, -1));

    auto dfs = [&](int i, int mask, bool isLimit, auto&& self) -> int {
        int c = __builtin_popcount(mask);
        if (c > k) {
            return 0;
        }
        if (i == s.length()) {
            if (c < k) {
                return 0;
            }
            return 1;
        }
        if (!isLimit && mask > 0) {
            int& res = memo[i][c];
            if (res >= 0) {
                return res;
            }
        }
        int res = 0;
        if (mask == 0) {
            res += self(i + 1, 0, false, self);
        }
        int up = 15;
        if (isLimit) {
            if (s[i] <= '9') {
                up = s[i] - '0';
            } else {
                up = 10 + (s[i] - 'A');
            }
        }
        int d = 0;
        if (mask == 0) {
            d = 1;
        }
        for (; d <= up; d++) {
            res += self(i + 1, mask | (1 << d), isLimit && d == up, self);
            res %= MOD;
        }
        if (!isLimit && mask > 0) {
            memo[i][c] = res;
        }
        return res;
    };

    cout << dfs(0, 0, true, dfs) << endl;
}

20250210

Problem

Make Almost Equal With Mod

输入 T(≤500) 表示 T 组数据。
每组数据输入 n(2≤n≤100) 和长为 n 的数组 a(1≤a[i]≤1e17)。保证所有 a[i] 互不相同。

找到一个在 [1,1e18] 中的 k，使得所有 a[i]%=k 后，a 中恰好有两个不同的数，即 len(set(a)) == 2。
输出这个 k。如果有多个答案，输出任意一个。

可以证明，答案是存在的。

Example

输入

5
4
8 15 22 30
5
60 90 98 120 308
6
328 769 541 986 215 734
5
1000 2000 7000 11000 16000
2
2 1

输出

7
30
3
5000
1000000000000000000

Solution

取模后恰好有两种不同的数？试试二进制。

计算所有二进制 a[i] 的最长公共后缀。
例如下面三个二进制数：
1110
0010
1010
最长公共后缀是 10。
只要取这三个数的低三位（也就是模 8），结果必然是两个不同的数。

如何计算最长公共后缀？
设所有 a[i] 的 OR 为 or，所有 a[i] 的 AND 为 and。
例如上面的三个数，or=1110，and=0010。
从 or 中去掉 and 的比特位，即 or ^= and，可以得到 1100。
这个数的 lowbit 再左移 1 位，就是答案 1000。

void solve()
{
    int n,v;
    cin >> n;
    int o = 0, a = -1;
    for (int i = 0; i < n; i++) {
        cin >> v;
        o |= v;
        a &= v;
    }
    o = o^a;
    cout << ((o&-o)<<1) << endl;
}

20250211

Problem

https://atcoder.jp/contests/abc281/tasks/abc281_d

输入 n(1≤n≤100) k(1≤k≤n) d(1≤d≤100) 和长为 n 的数组 a(0≤a[i]≤1e9)。

从 a 中选出恰好 k 个数，满足元素和恰好是 d 的倍数。

输出元素和的最大值。
如果无法得到 d 的倍数，输出 -1。

Example

输入

1 2	`4 2 2 1 2 3 4`

输出

输入

1 2	`3 1 2 1 3 5`

输出

-1

Solution

恰好装满型二维 0-1 背包。

k 是背包的第一类容量上限，d-1 是背包的第二类容量上限。
a[i] 看成一个体积为 (1,a[i])，价值为 a[i] 的物品。

定义 f[i+1] [j] [s] 表示 a[0]~a[i] 中选 j 个，元素和模 k 的结果为 s 时，所选元素的最大和。如果没有这样的元素和，f[i+1] [j] [s]=-inf。
考虑第 i 个物品 a[i] 选或不选：
不选，问题变成 f[i] [j] [s]。
选，问题变成 f[i] [j-1] [s’]，其中 s’ = ((s - a[i]) % d + d) % d。
两种情况取最大值，得 f[i+1] [j] [s] = max(f[i] [j] [s], f[i] [j-1] [s’]+a[i])。

初始值 f [0] [0] [0] = 0，其余为 -inf。
答案为 f [n] [k] [0]。如果答案为 -inf，输出 -1。

代码实现时，f 的第一个维度可以优化掉，j 需要倒序循环，避免覆盖状态。

注意用 64 位整数。

void solve()
{
    int n,k,d;
    cin >> n >> k >> d;
    vi a(n);
    cnv(a);
    int inf = -INF;
    vector<vi> dp(k + 1, vi(d, inf));
    dp[0][0] = 0;
    for (int num : a) {
        for (int i = k; i >= 1; --i) {
            for (int j = 0; j < d; ++j) {
                if (dp[i-1][j] != inf) {
                    int new_mod = (j + num) % d;
                    dp[i][new_mod] = max(dp[i][new_mod], dp[i - 1][j] + num);
                }
            }
        }
    }
    int result = dp[k][0];  
    cout << (result != inf ? result : -1) << endl; 
}

20250212

Problem

IntegerotS

输入 n(1≤n≤1e5) k(0≤k<2^30) 和 n 个 pair (ai,bi)，其中 0≤ai<2^30，1≤bi≤1e9。

从中选择一些 pair，满足所有 ai 的 OR <= k，并且 bi 之和越大越好。
输出 bi 之和的最大值。

Example

输入

输出

输入

输出

输入

输出

Solution

从高到低分析 k+1 的每一位：
如果是 1，那么如果 OR 的这一位是 0，右边所有比特位可以随便选，把所有这一位不是 1 的数的价值全部加起来，更新答案的最大值。
后续就只需考虑 OR 这一位是 1 的情况下的答案。
如果 k+1 这一位是 0，那么这一位是 1 的数就不能选（因为我们是从高到低考虑的）。
把哪些比特位不能选记录在一个变量 ban 中，所有与 ban 的 AND > 0 的数都不能选。

void solve()
{
    int n,k,ban=0,ans=0;
    cin >> n >> k;
    vector<pii> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    k++;
    for (int i = 30; i >= 0; i--) {
        if ((k >> i) & 1) {
            ban ^= (1 << i);
            int s = 0;
            for (auto p: a) {
                if ((p.first&ban) == 0) {
                    s += p.second;
                }
            }
            ans = max(ans, s);
        }
        ban ^= 1 << i;
    }
    cout << ans << endl;
}

20250213

Problem

Dist Max 2

输入 n(2≤n≤2e5) 和 n 个二维坐标点，范围 [0,1e9]。保证所有点互不相同。

定义两点 (xi,yi) 和 (xj,yj) 的距离为 min(|xi-xj|,|yi-yj|)。

输出两点之间的最大距离。

【灵茶の试炼】题目&题解
https://docs.qq.com/sheet/DWGFoRGVZRmxNaXFz

Example

输入

输出

输入

输出

输入

输出

Solution

问题分析：我们需要找到两个点，使得它们的x坐标差和y坐标差中的最小值最大。直接暴力遍历的话时间复杂度为O(n^2),不可行。
观察：最大的距离d一定满足存在两个点，它们的x坐标差和y坐标差都至少为d。因此可以考虑二分确定最大的d。
优化：
- 点按x坐标排序
- 预处理前缀和后缀数组来快速查询区间内的最小和最大y坐标
- 二分确定d，检查是否存在满足条件的点对

struct Point {
    int x,y;
};
vector<Point> points;
int n;
vi pre_min, pre_max, suf_min, suf_max;
bool check (int d) {
    for (int i = 0; i < n; ++i) {
        int x_i = points[i].x;
        int y_i = points[i].y;

        // 左边区间 x_j <= x_i - d
        int left = x_i - d;
        int low = 0, high = i - 1, k = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (points[mid].x <= left) {
                k = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        if (k != -1) {
            if (pre_max[k] >= y_i + d || pre_min[k] <= y_i - d) {
                return true;
            }
        }

        // 右边区间 x_j >= x_i + d
        int right = x_i + d;
        low = i + 1;
        high = n - 1;
        int m = n;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (points[mid].x >= right) {
                m = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        if (m < n) {
            if (suf_max[m] >= y_i + d || suf_min[m] <= y_i - d) {
                return true;
            }
        }
    }
    return false;
}
void solve()
{
    cin >> n;
    points.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].x >> points[i].y;
    }
    sort(points.begin(), points.end(), [](const Point& a,const Point& b) {
        return a.x < b.x;
    });
    pre_min.resize(n);
    pre_max.resize(n);
    suf_min.resize(n);
    suf_max.resize(n);

    pre_min[0] = points[0].y;
    pre_max[0] = points[0].y;
    for (int i = 1; i < n; ++i) {
        pre_min[i] = min(pre_min[i-1], points[i].y);
        pre_max[i] = max(pre_max[i-1], points[i].y);
    }

    suf_min[n-1] = points[n-1].y;
    suf_max[n-1] = points[n-1].y;
    for (int i = n-2; i >= 0; --i) {
        suf_min[i] = min(suf_min[i+1], points[i].y);
        suf_max[i] = max(suf_max[i+1], points[i].y);
    }
     int max_x = points.back().x - points[0].x;
    int global_min_y = pre_min.back();
    int global_max_y = pre_max.back();
    int max_y_diff = global_max_y - global_min_y;

    int left = 0, right = max(max_x, max_y_diff);
    int ans = 0;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (check(mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    cout << ans << endl;
}

20250214

Problem

输入 n k (1≤k≤n≤3000)。

输出有多少个多重集合，满足如下条件：

恰好有 n 个元素。
每个元素都是 1/2^i，即 1, 1/2, 1/4, 1/8, … 中的一个。
这 n 个数的和恰好等于 k。
答案模 998244353。

Example

输入 4 2
输出 2
解释 {1,1/2,1/4,1/4} 和 {1/2,1/2,1/2,1/2} 这两个多重集合满足要求。

输入 2525 425
输出 687232272

Solution

定义 f[i] [j] 表示 i 个数且元素和为 j 的多重集合个数，并且这 i 个数都是 1, 1/2, 1/4, …
如果这 i 个数里面至少有 1 个 1，那么去掉这个 1，问题变成 i-1 个数且元素和为 j-1 的多重集合个数，即 f[i-1] [j-1]。
如果这 i 个数里面没有 1，那么（举例）1=1/2+1/4+1/4 等价于 2=1+1/2+1/2，所以问题等价于 i 个数且元素和为 2j 的多重集合个数，即 f[i] [2j]。
注：2j 的意义在于让这 i 个数都是 1, 1/2, 1/4, …，从而【符合状态的定义】。

所以有
f[i] [j] = f[i-1] [j-1] + f[i] [2j]

根据转移方程，j 要倒序遍历。
如果 i<j，那么 f[i] [j] = 0。所以 j 最大是 i。

初始值 f[0] [0] = 1。
答案为 f[n] [k]。

代码实现时，可以去掉第一个维度，那么 f[j] = f[j-1] 相当于在 f 数组最前面插入了一个 0。

void solve()
{
    int n,k;
    cin >> n >> k;
    vi f(1, 1);
    for (int i = 1; i <= n; ++i) {
        f.insert(f.begin(), 0); 
        for (int j = i / 2; j > 0; j--) {  
            f[j] = (f[j] + f[j * 2]) % mod;  
        } 
    }
    cout << f[k] << endl;
}

20250217

Problem

Sum of Two Numbers

输入 T(≤1e4) 表示 T 组数据。
每组数据输入 n(1≤n≤1e9)。

定义 digsum(a) 表示 a 的数位和。
构造两个非负整数 x 和 y，满足 x + y = n 且 |digsum(x) - digsum(y)| <= 1。

可以证明，这样的 x 和 y 一定存在。

Example

输入

输出

Solution

每一位单独考虑，出现奇数x和y的数位每次交替增加

void solve()
{
    ll n;
    cin>>n;
    ll x=0,y=0,i=0,flag=0;
    while(n>0){
        ll dig=n%10;
        if(dig%2==0){
            x+=((dig/2)*pow(10,i));
            y+=((dig/2)*pow(10,i));
        }
        else if(flag==0){
            x+=((dig/2)*pow(10,i));
            y+=((dig/2+1)*pow(10,i));
            flag=1;
        }
        else{
            x+=((dig/2+1)*pow(10,i));
            y+=((dig/2)*pow(10,i));
            flag=0;
        }
 
        n/=10;
        i++;
    }
    cout<<x<<" "<<y<<"\n";
}

20250218

Problem

Ingenuity-2

输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤2e5。
每组数据输入 n(1≤n≤2e5) 和长为 n 的字符串 s，只包含 NSEW 四种字母，表示北南东西四个方向。

有两个机器人，一开始都在坐标原点。
选择 s 中的某些字母分配给第一个机器人，其余字母分配给第二个机器人。
机器人按照字母方向移动，一个字母移动一个单位长度。
如何分配字母，可以让两个机器人最终在同一个位置？
注意：两个机器人都至少要走一步。

输出一个长为 n 的字符串 t，其中 t[i]=’R’ 表示 s[i] 分给了第一个机器人，t[i]=’H’ 表示 s[i] 分给了第二个机器人。
多解输出任意解。
如果无法做到，输出 NO。

Example

输入

10
6
NENSNE
3
WWW
6
NESSWS
2
SN
2
WE
4
SSNN
4
WESN
2
SS
4
EWNN
4
WEWE

输出

RRHRRH
NO
HRRHRH
NO
NO
RHRH
RRHH
RH
RRRH
RRHH

Solution

设一共有 a 个 W（左）和 b 个 E（右）。
如果 a 和 b 的奇偶性不同，那么直接输出 NO。
如果 a=2,b=4，那么可以平均分配，每个机器人都往左走 a/2 步，往右走 b/2 步。
如果 a=3,b=5 呢？多出来的 1 步都给同一个机器人，这样两个人的横坐标仍然是相同的。
纵坐标同理。

实现的时候，可以用一个 who 数组记录当前轮到谁走，who[s[i]] = 0 表示 s[i] 给第一个机器人，who[s[i]] = 1 表示 s[i] 给第二个机器人。
走完之后把 who[s[i]] 取反，从而做到均匀分配。

为了保证两个机器人都至少走一步，可以初始化南北方向 who[‘N’] = who[‘S’] = 0，东西方向 who[‘E’] = who[‘W’] = 1。

最后再检查一遍：统计 ‘R’ 的个数，判断两个机器人是否都至少走一步。
小技巧：通过判断最终 who[‘N’] = who[‘S’] 和 who[‘E’] = who[‘W’] 是否成立，来判断奇偶性（是否需要输出 NO）。

void solve()
{
    int n;
    string s;
    cin >> n >> s;
    int x = 0, y = 0;
    for (auto ch : s) {
        if (ch == 'E') {
            x++;
        } else if (ch == 'W') {
            x--;
        } else if (ch == 'N') {
            y++;
        } else if (ch == 'S') {
            y--;
        }
    }

    string ans(n, 'R');

    if (x % 2 != 0 || y % 2 != 0) {
        cout << "NO\n";
        return;
    }

    if (x == 0 && y == 0) {
        if (n == 2) {
            cout << "NO\n";
        } else {
            char ch;
            if (s[0] == 'E') {
                ch = 'W';
            } else if (s[0] == 'W') {
                ch = 'E';
            } else if (s[0] == 'N') {
                ch = 'S';
            } else if (s[0] == 'S') {
                ch = 'N';
            }
            ans[0] = ans[s.find(ch)] = 'H';
            cout << ans << '\n';
        }
        return;
    }

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'E' && x > 0) {
            x -= 2;
            ans[i] = 'H';
        } else if (s[i] == 'W' && x < 0) {
            x += 2;
            ans[i] = 'H';
        } else if (s[i] == 'N' && y > 0) {
            y -= 2;
            ans[i] = 'H';
        } else if (s[i] == 'S' && y < 0) {
            y += 2;
            ans[i] = 'H';
        }
    }

    cout << ans << '\n';
}

20250219

Problem

Patisserie ABC

输入 n(1≤n≤1000) m(0≤m≤n) 和一个 n 行 3 列的矩阵 a。

从 n 行中选择 m 行，输出 abs(第一列元素和) + abs(第二列元素和) + abs(第三列元素和) 的最大值。

Example

输入

输出

输入

输出

Solution

假设第一列元素和 >= 0，第二列元素和 < 0，第三列元素和 >= 0。
去掉绝对值，要计算的式子就是：
第一列元素和 - 第二列元素和 + 第三列元素和
= sum(a[i][0] - a[i][1] + a[i][2])
要让答案尽量大，按照 a[i][0] - a[i][1] + a[i][2] 从大到小排序，计算前 m 项的 abs(第一列元素和) + abs(第二列元素和) + abs(第三列元素和)。

一般地，枚举 2^3=8 种元素和的正负号组合，这样可以把绝对值拆开，方便我们做式子变形 + 排序。

struct Point {  
    int x, y, z;  
}; 
void solve()
{
    int n,m,ans=0;
    cin >> n >> m;
    vector<Point> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y >> a[i].z;
    }
    for (int i = -1; i <= 1; i += 2) {  
        for (int j = -1; j <= 1; j += 2) {  
            for (int k = -1; k <= 1; k += 2) {  
                sort(a.begin(), a.end(), [&](const Point&p1,const Point&p2) {  
                    return p1.x * i + p1.y * j + p1.z * k > p2.x * i + p2.y * j + p2.z * k;  
                });  

                int s1 = 0, s2 = 0, s3 = 0;  
                for (int idx = 0; idx < m; idx++) {  
                    s1 += a[idx].x;  
                    s2 += a[idx].y;  
                    s3 += a[idx].z;  
                }  
                ans = max(ans, abs(s1) + abs(s2) + abs(s3));  
            }  
        }  
    }
    cout << ans << endl;  
}

20250220

Problem

Blocked Roads

输入 n(2≤n≤400) m(1≤m≤n*(n-1))，表示一个 n 点 m 边的有向图。保证图中无自环和重边。
然后输入 m 条边，每条边输入 x y，表示一条 x 到 y 的有向边，边权为 1。节点编号从 1 开始。

输出 m 个数，其中第 i 个数表示删除输入的第 i 条边后，从 1 到 n 的最短路长度。如果无法从 1 到达 n，输出 -1。

样例太长，请在原题查看。

【灵茶の试炼】题目&题解
https://docs.qq.com/sheet/DWGFoRGVZRmxNaXFz

Example

输入

输出

1
2
3

1
2
1

输入

输出

输入

输出

Solution

首先找到任意一条从 1 到 n 的最短路。

分类讨论：
如果删除的边不在这条最短路上，那么最短路长度不变。
如果删除的边在这条最短路上，直接重新算一遍最短路长度。由于最短路至多有 n-1 条边，所以至多重新算 n-1 次。
时间复杂度 O(nm)。

怎么求任意一条最短路？由于图中边权都是 1，这可以通过一次 BFS 完成。
BFS 更新 dis 的时候记录转移来源 from。最后从终点 n 出发，根据 from 倒着走到起点 1，就知道路径上有哪些边了。

void solve()
{
    int n,m;
    cin >> n >> m;
    vector<vector<Edge>> g(n);
    for (int i = 0; i < m; i++) {
        int v,w;
        cin >> v >> w;
        g[v-1].push_back({w-1,i});
    }
    vector<Edge> from(n);
    vector<int> dis(n);

    auto bfs = [&](int ban) -> int {
        fill(dis.begin(), dis.end(), -1);
        dis[0] = 0;
        queue<int> q;
        q.push(0);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (const auto& e : g[v]) {
                int w = e.to;
                if (e.i != ban && dis[w] < 0) {
                    dis[w] = dis[v] + 1;
                    if (ban < 0) {
                        from[w] = {v, e.i};
                    }
                    q.push(w);
                }
            }
        }
        return dis[n-1];
    };

    int res = bfs(-1);
    vector<int> ans(m, res);
    if (res != -1) {
        for (int v = n - 1; v != 0; v = from[v].to) {
            ans[from[v].i] = bfs(from[v].i);
        }
    }
    for (int v : ans) {
        cout << v << endl;
    }
}

20250221

Problem

path pass i

输入 n(1≤n≤2e5) 和长为 n 的数组 a(1≤a[i]≤n)。
然后输入一棵无向树的 n-1 条边，节点编号从 1 到 n。
节点 i 的颜色是 a[i]。

定义 f(c) = 包含颜色 c 的简单路径的数目。注：只有 1 个点也算路径。
输出 f(1),f(2),…,f(n)。

Example

输入

输出

1
2
3

5
4
0

输入

1
2

1
1

输出

输入

1
2
3

2
1 2
1 2

输出

1
2

2
2

输入

输出

输入

8
2 7 2 5 4 1 7 5
3 1
1 2
2 7
4 5
5 6
6 8
7 8

输出

Solution

正难则反，计算不包含颜色 c 的简单路径数。
所有路径数减去不包含颜色 c 的路径数就是答案。

去掉颜色 c 节点后，树分成了若干连通块。
对于大小为 m 的连通块，其中有 m*(m+1)/2 条简单路径。

如何快速计算各个连通块的大小？

如图，去掉粉色节点后，考虑包含节点 y 的连通块，它的大小等于：
子树 y 的大小，减去子树 z1,z2,z3 的大小之和。

如何计算子树 z1,z2,z3 的大小之和？
额外用一个数组 size[c] 记录以颜色 c 为根的子树的大小之和。

这对吗？考虑 x 更上面的节点，这样做 z1,z2,z3 的子树大小岂不是会和 x 的子树大小相加？
为了避免重复累加子树大小，直接用子树 x 的大小「覆盖」子树 z1,z2,z3 的大小之和。
具体来说，在 dfs(x) 的开头，用临时变量 old 记录 size[c]；在 dfs(x) 的末尾，覆盖 size[c] = old + 子树 x 的大小。

void solve()
{
    int n;
    cin >> n;
    vi a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<vector<int>> g(n);
    for (int i = 1; i < n; ++i) {
        int v,w;
        cin >> v >> w;
        v--;
        w--;
        g[v].pb(w);
        g[w].pb(v);
    }
    vi ans(n),size(n);
    function<int(int, int)> dfs = [&](int v, int fa) -> int {
        int c = a[v] - 1;
        int old = size[c];
        int sz = 1;
        for (int w : g[v]) {
            if (w != fa) {
                size[c] = 0;
                int szW = dfs(w, v);
                sz += szW;
                int m = szW - size[c];
                ans[c] += m * (m + 1) / 2;
            }
        }
        size[c] = old + sz;
        return sz;
    };

    dfs(0, -1);
    for (int i = 0; i < n; ++i) {
        int m = n - size[i];
        cout << n * (n + 1) / 2 - ans[i] - m * (m + 1) / 2 << endl;
    }
}

20250224

Problem

Flipping Game

输入 n(1≤n≤100) 和长为 n 的数组 a，只包含 0 和 1。

从 a 中选一个非空连续子数组，把其中的 0 变成 1，1 变成 0。
这个操作必须恰好执行一次。

输出操作后 a 中 1 的个数的最大值。

Example

输入

1 2	`5 1 0 0 1 0`

输出

输入

1 2	`4 1 0 0 1`

输出

Solution

找到0比1数量最多的反转区间，如果找不到就必须反转一个1导致数量减一

void solve()
{
    int n;
    cin >> n;
    vi a(n);
    int count1=0,count0=0,flip=0,ans=-1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] == 1) {
            count1++;
            flip--;
        } else {
            count0++;
            flip++;
        }
        ans = max(ans, flip);
        if (flip < 0) {
            flip = 0;
        }
    }
    cout << count1 + ans << endl;
}

20250225

Problem

输入 n(1≤n≤2e5) 和长为 n 的数组 a(1≤a[i]≤n)。

定义 f(i,j) 为连续子数组 a[i]~a[j] 中的不同元素个数。

输出所有 f(i,j) 之和，其中 i<=j。

Example

输入

1
2

3
1 2 2

输出

输入

1 2	`9 5 4 2 2 3 2 4 4 1`

输出

Solution

我们需要计算所有连续子数组中不同元素个数的总和。直接暴力枚举所有子数组的方法时间复杂度为O(n²)，对于较大的n来说不可行。因此，我们需要一种更高效的方法。

逆向思维：计算每个元素在多少个子数组中出现过至少一次。总和即为每个元素在所有子数组中出现次数的总和。具体步骤如下：

记录每个元素的位置：使用unordered_map记录每个元素在数组中的出现位置。
计算总子数组数目：总子数组数目为n*(n+1)/2。
计算不包含某元素的子数组数目：对于每个元素，找到其所有出现位置，将数组分割成多个不包含该元素的区间，计算这些区间的子数组数目之和。
计算元素贡献：用总子数组数目减去不包含该元素的子数组数目，即为该元素的贡献。累加所有元素的贡献即为结果。

void solve()
{
    int n;
    cin >> n;
    vi a(n);
    unordered_map<int, vi> pos_dict;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        pos_dict[a[i]].pb(i);
    }
    int total_arrays = n * (n + 1) / 2;
    int result = 0;
    for (const auto& entry : pos_dict) {
        const vi& position = entry.second;
        int prev = -1;
        int sum_not = 0;
        for (int p : position) {
            int start = prev + 1;
            int end = p - 1;
            if (start <= end) {
                int length = end - start + 1;
                sum_not += length * (length + 1) / 2;
            }
            prev = p;
        }
        int start = prev + 1;
        int end = n - 1;
        if (start <= end) {
            long long length = end - start + 1;
            sum_not += length * (length + 1) / 2;
        }
        
        long long contribution = total_arrays - sum_not;
        result += contribution;
    }
    cout << result << endl;
}

20250226

Problem

Minimize Sum of Distances

输入 n(1≤n≤1e5)。
输入一棵无向树的 n-1 条边，边权为 1，节点编号从 1 到 n。
输入长为 n 的数组 a(1≤a[i]≤1e9)。

定义 f(x) = sum(dist(x, i) * a[i] for i in [1, n])，其中 dist(x, i) 表示 x 到 i 的最短路长度。

输出 f(1),f(2),…,f(n) 中的最小值。

Example

输入

输出

输入

1
2
3

2
2 1
1 1000000000

输出

输入

7
7 3
2 5
2 4
3 1
3 6
2 1
2 7 6 9 3 4 6

输出

Solution

换根dp

第一次DFS（后序）：计算每个子树的总权值 sum_a_subtree 和以该节点为根的初始总距离权值 sum_dist。
第二次DFS（前序）：利用父节点的结果，通过公式 f(v) = f(u) + (总权值 - 2 * 子树v的权值) 递推计算所有子节点的结果。

void solve()
{
    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u,v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    vi a(n+1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    vi sum_a_tree(n + 1);
    vi sum_dist(n+1);
    function<void(int, int)> dfs1 = [&](int u, int p) {
        sum_a_tree[u] = a[u];
        sum_dist[u] = 0;
        for (int v : adj[u]) {
            if (v != p) {
                dfs1(v, u);
                sum_a_tree[u] += sum_a_tree[v];
                sum_dist[u] += sum_dist[v] + sum_a_tree[v];
            }
        }
    };
    dfs1(1, -1);
    int total_a = sum_a_tree[1];
    function<void(int, int)> dfs2 = [&](int u, int p) {
        for (int v : adj[u]) {
            if (v != p) {
                sum_dist[v] = sum_dist[u] + (total_a - 2 * sum_a_tree[v]);
                dfs2(v, u);
            }
        }
    };
    dfs2(1, -1);
    int min_f = *min_element(sum_dist.begin() + 1, sum_dist.end());
    cout << min_f << endl;
}

图可视化网站：https://csacademy.com/app/graph_editor/

20250227

Problem

#(subset sum = K) with Add and Erase

输入 q(1≤n≤5000) 和 k(1≤k≤5000)。
一开始有一个空箱子。输入 q 个操作：
“+ v”：把一个写有数字 v 的小球放入箱子。
“- v”：从箱子中移除一个写有数字 v 的小球，保证箱子中有这样的小球。
v 的范围是 [1,5000]。

每次操作后，输出有多少种方案，从盒子中选取一些球，元素和恰好等于 k。答案模 998244353。
注意球是有区分的。

Example

输入

15 10
+ 5
+ 2
+ 3
- 2
+ 5
+ 10
- 3
+ 1
+ 3
+ 3
- 5
+ 1
+ 7
+ 4
- 3

输出

Solution

动态规划（背包问题）：使用动态规划数组dp，其中dp[i]表示当前箱子中的小球组成和为i的方案数。初始化dp[0] = 1（空集的方案数为1）。
添加操作（+v）：相当于扩展背包容量。对于每个可能的和i（从k到v逆序遍历），更新dp[i] += dp[i - v]。逆序保证每个小球只被计算一次。
移除操作（-v）：需要撤销该小球的影响。对于每个可能的和i（从v到k正序遍历），更新dp[i] -= dp[i - v]。正序确保正确减去包含该小球的方案数，处理负数时加上模数保证非负。
复杂度分析：每次操作的时间复杂度为O(k)，总时间复杂度为O(qk)。

void solve()
{
    int n,k;
    cin >> n >> k;
    vi dp(k + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        char op;
        int v;
        cin >> op >> v;
        if (op == '+') {
            for (int i = k; i >= v; i--) {
                dp[i] = (dp[i] + dp[i-v]) % MOD;
            }
        } else {
            for (int i = v; i <= k; ++i) {
                dp[i] = (dp[i] - dp[i-v] + MOD) % MOD;
            }
        }
        cout << dp[k] << endl;
    }
}

20250228

Problem

Nuske vs Phantom Thnook

输入 n(1≤n≤2000) m(1≤m≤2000) q(1≤q≤2e5) 和一个 n 行 m 列的 01 网格图。
其中 0 表示白色格子，1 表示蓝色格子。
保证每个由蓝色格子构成的（四方向）连通块都是树。

然后输入 q 个询问，每个询问输入 4 个数，表示一个子矩形的左上角行列坐标和右下角行列坐标（下标从 1 开始）。
输出这个子矩形中，有多少个蓝色连通块。

Example

输入

输出

输入

输出

Solution

问题分析：
- 每个蓝色连通块都是树结构，即无环连通块。树的性质是点数等于边数加1。
- 对于子矩形内的所有蓝色点，连通块的数量等于点数减去边数。
关键观察：
- 使用二维前缀和数组快速计算子矩形内的点数。
- 预处理横向边和纵向边的数量，使用二维前缀和数组快速计算子矩形内的边数。
预处理步骤：
- sum数组：存储每个位置及其左上区域内的蓝色点总数。
- h数组和h_sum数组：存储每个位置及其右侧的横向边数量。
- v数组和v_sum数组：存储每个位置及其下方的纵向边数量。
查询处理：
- 使用前缀和数组快速计算子矩形内的点数（S）。
- 计算横向边（H）和纵向边（V）的数量，得到总边数（E = H + V）。
- 结果即为点数减去边数（S - E）。

const int MAXN = 2005;
int sum[MAXN][MAXN];
int h[MAXN][MAXN], h_sum[MAXN][MAXN];
int v[MAXN][MAXN], v_sum[MAXN][MAXN];
char grid[MAXN][MAXN];
void solve()
{
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", grid[i] + 1);
    }

    // Precompute sum array for 1's
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + (grid[i][j] == '1' ? 1 : 0);
        }
    }

    // Precompute h and v arrays for edges
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // Horizontal edges (right)
            if (j < m && grid[i][j] == '1' && grid[i][j+1] == '1') {
                h[i][j] = 1;
            } else {
                h[i][j] = 0;
            }
            // Vertical edges (down)
            if (i < n && grid[i][j] == '1' && grid[i+1][j] == '1') {
                v[i][j] = 1;
            } else {
                v[i][j] = 0;
            }
        }
    }

    // Precompute prefix sums for h and v
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            h_sum[i][j] = h_sum[i-1][j] + h_sum[i][j-1] - h_sum[i-1][j-1] + h[i][j];
            v_sum[i][j] = v_sum[i-1][j] + v_sum[i][j-1] - v_sum[i-1][j-1] + v[i][j];
        }
    }

    while (q--) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

        int S = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];

        int H = 0;
        int j1 = y1, j2 = y2 - 1;
        if (j1 <= j2 && x1 <= x2) {
            H = h_sum[x2][j2] - h_sum[x1-1][j2] - h_sum[x2][j1-1] + h_sum[x1-1][j1-1];
        }

        int V = 0;
        int i1 = x1, i2 = x2 - 1;
        if (i1 <= i2 && y1 <= y2) {
            V = v_sum[i2][y2] - v_sum[i1-1][y2] - v_sum[i2][y1-1] + v_sum[i1-1][y1-1];
        }

        int E = H + V;
        printf("%d\n", S - E);
    }
}

codeforces

#acm

茶-2025-02

https://www.polarishaw.top/2025/02/05/Tea202502/

作者

Polaris

发布于

2025年2月5日

许可协议

CMU15445-lecture14 上一篇

茶-2025-01 下一篇