茶-2025-01

Tea

20250107

Problem

Kevin and Binary Strings

输入 T(≤1e3) 表示 T 组数据。所有数据的字符串长度之和 ≤5000。

每组数据输入长度 ≤5000 的 01 字符串 s。保证 s 的第一个字符是 ‘1’。

你需要在 s 中选择两个非空子串（可以重叠，可以有前导零），将其视作两个二进制数，计算 XOR。

目标是最大化 XOR。

输出你选择的两个子串的左右端点 l1 r1 l2 r2，下标从 1 开始。

如果答案不止一种，输出其中任意一个。

Example

Input

5
111
1000
10111
11101
1100010001101

Output

Solution

1.其中一个子串必然是 s，如果比 s 还短，那 XOR 必然比 s 小。

2.找到 s 的最左边的 0，这个 0 一定要改成 1，得到的 XOR 一定比不改更大。

3.设这个 0 的下标为 i，那么另一个子串的长度必须恰好等于 n-i，因为我们要【右对齐】计算 XOR。

4.暴力枚举所有长为 n-i 的子串。

5.如果 s 没有 0，那么输出 1 n 1 1。

void solve()
{
    string s;
    cin >> s;
    int n = s.size(), idx = n - 1;
    vi ans(4);
    ans[0] = 1;
    ans[1] = n;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            idx = i;
            break;
        }
    }
    int len = n - idx, mx = 0;
    ans[2] = ans[3] = idx + 1;
    for (int i = 0; i < idx && i + len <= n; i++) {
        if (s[i] == '1') {
            int j = i + 1, k = idx + 1;
            while (k < n && s[k] != s[j]) {
                j++;
                k++;
            }
            int sz = j - i;
            if (sz > mx) {
                mx = sz;
                ans[2] = i + 1;
                ans[3] = i + len;
            }
        }
    }
    for (int i = 0; i < 4; i++) {
        cout << ans[i] << " \n"[i==3];
    }
}

20250108

Problem

Scrambled Scrabble

输入长度 ≤5000 的字符串 s，只包含大写英文字母。

字母 AEIOU 是元音。Y 可以是元音也可以是辅音。
其余字母为辅音。特别地，可以把 NG 连在一起，当作一个辅音。

定义音节为一个辅音 + 一个元音 + 一个辅音。例如 CAR，KING 等等。
定义单词为由一个或多个音节串联得到的字符串。例如 KINGDOM 是由 KING + DOM 两个音节组成。

从 s 中删除零个或多个字母，然后重新排列剩余的字母，组成单词。
输出最长单词长度。
如果无法组成单词，输出 0。

Example

输入 ICPCJAKARTA
输出 9

输入 NGENG
输出 5

输入 YYY
输出 3

输入 DANGAN
输出 6

输入 AEIOUY
输出 0

Solution

首先统计每种字母的出现次数
计算元音数(a)、Y数(y)、辅音数(b)和NG组合数(ng)
考虑不同情况下能组成的最长单词：
- 如果NG组合充足，每个音节可以是5个字母（如NGENG）
- 如果普通辅音充足，每个音节是3个字母，可能额外使用NG
- 如果元音较多，需要根据辅音数量来限制
- 其他情况下尽可能组成3字符音节
时间复杂度:O(n),空间复杂度O(1)

void solve()
{
    string s;
    cin >> s;
    int n = s.length();
    vi count(26,0);
    for (auto e:s) {
        count[e-'A']++;
    }
    int a = count['A'-'A']+count['E'-'A']+count['I'-'A']+count['O'-'A']+count['U'-'A'];
    int y = count['Y'-'A'];
    int b = s.length() - a - y;
    int ng = min(count['N'-'A'],count['G'-'A']);
    if ((a+y)*2<=ng) {
        cout << (a+y)*5 << endl;
    } else if ((a+y)*2 <= b - ng) {
        cout << (a+y)*3+ng << endl;
    } else if ((b+y)/2 <= a) {
        int res = (b+y)/2*3;
        if ((b+y)%2 > 0 && ng > 0) {
            res++;
        }
        cout << res << endl;
    } else {
        cout << n - max(n%3-ng,0) << endl;
    }
}

20250109

Problem

Choose Two and Eat One

输入 n(2≤n≤500) m(2≤m≤1e9) 和长为 n 的数组 a(1≤a[i]≤m-1)。

重复如下操作 n-1 次：
选择 a 中的两个数 x 和 y，得到 (pow(x,y)+pow(y,x))%m 分，然后从 a 中删除 x 或者 y。

输出总得分的最大值。

Example

输入

1 2	`4 10 4 2 3 2`

输出

输入

1 2	`20 100 29 31 68 20 83 66 23 84 69 96 41 61 83 37 52 71 18 55 40 8`

输出

Solution

看成有 n 个节点的完全图。

每次操作相当于选择一条边，并删掉一个节点。

由于选择的边，不会与已删除的点相连，所以选择的边不能构成环。

于是 n-1 次选边后，我们得到的是一棵生成树。

Kruskal/Prim 计算最大生成树即可，后者复杂度 O(n^2)。

struct Tuple {
    ll v, w, wt;
};
ll my_pow(ll x, ll n, ll mod) {
    ll res = 1;
    while(n > 0) {
        if (n % 2 > 0) {
            res = (1LL * res * x) % mod;
        }
        x = (1LL * x * x) % mod;
        n /= 2;
    }
    return res;
}
void solve()
{
    int n, m;
    cin >> n >> m;
    vll a(n);
    FOR(i, 0, n - 1) cin >> a[i];
    vector<Tuple> b;
    for (int i = 0; i < n; ++i) {  
        for (int j = i + 1; j < n; ++j) {  
            ll v = a[i];  
            ll w = a[j];  
            ll weight = (my_pow(v, w, m) + my_pow(w, v, m)) % m;  
            b.push_back({i, j, weight});  
        }  
    }
    sort(b.begin(), b.end(), [](Tuple &a, Tuple &b) {
        return a.wt > b.wt;
    });
    vector<ll> fa(n);  
    for (int i = 0; i < n; ++i) {  
        fa[i] = i;  
    }  

    function<ll(ll)> find = [&](ll x) {  
        if (fa[x] != x) {  
            fa[x] = find(fa[x]);  
        }  
        return fa[x];  
    };  

    ll sum = 0;  
    for (const auto &e : b) {  
        ll v = e.v, w = e.w, wt = e.wt;  
        ll fv = find(v), fw = find(w);  
        if (fv != fw) {  
            fa[fv] = fw;
            sum += wt;  
        }  
    }  

    cout << sum << endl;  
}

20250110

Problem

Takahashi is Slime

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

有 n 只史莱姆排成一行，从左到右第 i 只史莱姆的体积为 a[i]。
假设你是第 k 只史莱姆，每次操作，你可以吃掉左右相邻的体积严格小于你的一只史莱姆，并获得它的体积。把你可以达到的最大体积记为 f(k)。

输出 f(1),f(2),f(3),…,f(n)。

Example

输入

1 2	`6 4 13 2 3 2 6`

输出

1	`4 30 2 13 2 13`

输入

1 2	`12 22 25 61 10 21 37 2 14 5 8 6 24`

输出

1	`22 47 235 10 31 235 2 235 5 235 6 235`

Solution

从大到小思考。
a 中最大值的答案是多少？次大值的答案是多少？

设：
a[i] 左边最近 > a[i] 的数的下标为 left[i]，若不存在则为 -1。
a[i] 左边最近 >= a[i] 的数的下标为 leftGE[i]，若不存在则为 -1。
a[i] 右边最近 > a[i] 的数的下标为 right[i]，若不存在则为 n。
a[i] 右边最近 >= a[i] 的数的下标为 rightGE[i]，若不存在则为 n。

分类讨论：
如果 rightGE[i]-leftGE[i]=2，那么啥也做不了，ans[i] = a[i]。
否则，由于 a 中元素都是正数，在吃掉一个史莱姆后，我们的体积一定比初始体积大。
计算从 left[i]+1 到 right[i]-1 的子数组和 s。
如果 left[i] >= 0，且子数组和 s 比 a[i] 左边更大数的答案还要大，那么左边更大数能吃掉的数，a[i] 也可以吃掉，所以 ans[i] 就是左边更大数的答案，即 ans[i] = ans[left[i]]。
否则如果 right[i] < n，且子数组和 s 比 a[i] 右边更大数的答案还要大，那么右边更大数能吃掉的数，a[i] 也可以吃掉，所以 ans[i] 就是右边更大数的答案，即 ans[i] = ans[right[i]]。
其他情况，ans[i] = s。

记得开 LL。

void solve()
{
    int n;
    cin >> n;
    vi a(n), sum(n+1), leftGE(n), right(n);
    vi st = {-1};
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum[i+1] = sum[i] + a[i];
        while (st.size() > 1 && a[st.back()] < a[i]) {
            right[st.back()] = i;
            st.pop_back();
        }
        leftGE[i] = st.back();
        st.push_back(i);
    }
    for (int i : st) {
        if (i != -1) right[i] = n;
    }
    vi rightGE(n);
    vi left(n);
    st = {n};
    for (int i = n - 1; i >= 0; i--) {
        while (st.size() > 1 && a[st.back()] < a[i]) {
            left[st.back()] = i;
            st.pop_back();
        }
        rightGE[i] = st.back();
        st.push_back(i);
    }
    for (int i : st) {
        if (i != n) left[i] = -1;
    }
    vi id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int i, int j) {
        return a[i] > a[j];
    });
    vi ans(n);
    for (int i : id) {
        if (rightGE[i] - leftGE[i] == 2) {
            ans[i] = a[i];
            continue;
        }
        int l = left[i], r = right[i];
        int s = sum[r] - sum[l + 1];
        if (l >= 0 && s > a[l]) {
            ans[i] = ans[l];
        } else if (r < n && s > a[r]) {
            ans[i] = ans[r];
        } else {
            ans[i] = s;
        }
    }
    for (int v : ans) cout << v << ' ';
    cout << '\n';
}

20250113

Problem

All Pairs Segments

输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤1e5，q 之和 ≤1e5。
每组数据输入 n(2≤n≤2e5) q(1≤q≤1e5) 和长为 n 的严格递增数组 a(1≤a[i]≤1e9)。

对于每个满足 i<j 的 (i,j)，画一条线段（闭区间）[ai,aj]。一共有 n*(n-1)/2 条线段。
然后输入 q 个询问，每个询问输入 k(1≤k≤1e18)，输出有多少个整数恰好在 k 条线段中。

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

Example

输入

3
2 2
101 200
2 1
6 15
1 2 3 5 6 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
5 8
254618033 265675151 461318786 557391198 848083778
6 9 15 10 6 9 4 4294967300

输出

1
2
3

0 100
0 0 0 0 2 0 0 0 3 0 2 0 0 0 0
291716045 0 0 0 291716045 0 301749698 0

Solution

直接预处理所有答案，即在回答询问之前，预处理 mp，其中 mp[k] 表示恰好在 k 条线段中的整数个数。

分类讨论。

对于不在 a 中的整数 x，如果 a[i-1]<x<a[i]，那么线段的左端点有 i 种选择，右端点有 n-i 种选择，所以一共有 i*(n-1) 条线段包含 x。

此外满足 a[i-1]<x<a[i] 的 x 有 a[i]-a[i-1]-1 个，那么 mp[i*(n-1)] += a[i]-a[i-1]-1。

对于在 a 中的整数 x，如果 x=a[i]，那么左端点有 i+1 种选择，右端点有 n-i 种选择，减去左右端点重合的线段（不符合题目要求），

所以一共有 (i+1)(n-1)-1 条线段包含 a[i]，那么 mp[(i+1)(n-i)-1] += 1。

最后对于每个询问，输出 mp[k]。

void solve()
{
    int n,q,pre;
    cin >> n >> q >> pre;
    vector<int> a(n);
    mii mp;
    mp[n-1] = 1;
    for (int i = 1; i < n; i++) {
        cin >> a[i];
        mp[i*(n-i)] += a[i] - pre - 1;
        mp[(i+1)*(n-i)-1]++;
        pre = a[i];
    }
    int k;
    for (int i = 0; i < q; i++) {
        cin >> k;
        cout << mp[k] << " ";
    }
    cout << endl;
}

20250114

Problem

Find B

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

对于每个询问，你需要构造一个和 b 一样长的数组 c，要求：

sum(c) = sum(b)。
所有 c[i] 都不等于 b[i]。
所有 c[i] 都是正数。

能否构造？输出 YES 或 NO。

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

Example

输入

输出

YES
NO
YES
NO

Solution

如果 b[i] = 1，那么必须增大，至少增大 1。
如果 b[i] > 1，那么为了弥补 b[i]=1 的增大，我们需要知道这些数最多能减小多少，也就是 b[i]-1 之和。

所以统计子数组内的 b[i]=1 的个数，以及 b[i]-1 的元素和，如果前者 <= 后者，那么输出 YES，否则输出 NO。
注意特判 L=R 的情况，只有一个数必然是 NO。

计算子数组和用前缀和。

void solve()
{
    int n,m;
    cin >> n >> m;
    vector<int> a(n);
    vector<int> sum(n+1,0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] == 1) {
            sum[i+1] = sum[i]-1;
        } else {
            sum[i+1] = sum[i] + a[i] - 1;
        }
    }
    int l,r;
    for (int i = 0; i < m; i++) {
        cin >> l >> r;
        if (l < r && sum[l-1] <= sum[r]) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

20250115

Problem

Road Blocked

输入 n(2≤n≤300) m(0≤m≤n*(n-1)/2) q(1≤q≤2e5)，表示一个 n 点 m 边的无向图。保证图中无自环和重边。
然后输入 m 条边，每条边输入 x y w(1≤w≤1e9)，表示一条边权为 w 的无向边连接 x 和 y。节点编号从 1 开始。

然后输入 q 个询问，格式如下：
“1 i”：删掉输入的第 i(1≤i≤m) 条边。保证这条边没被删除。
“2 x y”：输出从 x 到 y 的最短距离。如果无法到达，输出 -1。

保证第一种询问不超过 300 个。

Example

输入

输出

1
2
3

10
11
-1

输入

输出

1
2
3

-1
-1
-1

Solution

倒序处理查询，删边变成加边

struct Edge {
    int v,w, wt;
};
struct Query {
    int v,w;
};
void addEdge (vector<vector<int>>& g, int v, int w, int wt, int n) {
    for (int i = 0; i < n; ++i) {  
        for (int j = 0; j < n; ++j) {  
            g[i][j] = min(g[i][j], min(g[i][v] + wt + g[w][j], g[i][w] + wt + g[v][j]));  
        }  
    }
}
void solve()
{
    int n,m,q;
    cin>>n>>m>>q;
    vector<vector<int>> g(n, vector<int>(n, INF));
    for (int i = 0; i < n; ++i) {
        g[i][i] = 0;
    } 
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].v >> edges[i].w >> edges[i].wt;
        edges[i].v--;
        edges[i].w--;
        g[edges[i].v][edges[i].w] = edges[i].wt;
        g[edges[i].w][edges[i].v] = edges[i].wt;
    }
    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        int op;
        cin >> op >> queries[i].v;
        queries[i].v--;
        if (op == 2) {
            cin >> queries[i].w;
            queries[i].w--;
        } else {
            Edge e = edges[queries[i].v];
            g[e.v][e.w] = INF;
            g[e.w][e.v] = INF;
        }
    }

    for (int k = 0; k < n; ++k) {  
        for (int i = 0; i < n; ++i) {  
            for (int j = 0; j < n; ++j) {  
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);  
            }  
        }  
    }
    vi ans;
    for (int i = q - 1; i >= 0; i--) {
        Query q = queries[i];
        if (q.w == 0) {
            Edge e = edges[q.v];
            addEdge(g, e.v, e.w, e.wt, n);
        } else {
            int dist = g[q.v][q.w];
            if (dist == INF) {
                dist = -1;
            }
            ans.push_back(dist);
        }
    }
    for (int i = ans.size() - 1; i >= 0; --i) {  
        cout << ans[i] << "\n";  
    }
}

20250116

Problem

Buildings 2

输入 n(2≤n≤2e5) q(1≤q≤2e5) 和长为 n 的数组 a(1≤a[i]≤n)，所有元素互不相同，下标从 1 开始。
然后输入 q 个询问，每个询问输入两个数 L 和 R (1≤L≤R≤n)。

有 n 栋建筑物，第 i 栋建筑物的高度是 a[i]。
如果下标在 [i+1,j-1] 中的建筑物高度都 <= a[j]，那么在 i 能看到 j (i < j)。
对于每个询问，输出：在 L 和 R 都能看到的、下标在 [R+1,n] 中的建筑物的数量。

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

Example

输入

输出

1
2
3

2
0
1

输入

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

输出

Solution

离线，把询问按照左端点分组。

从右到左遍历 a，如果当前 a[i] 比右边的数 x 大，那么 x 在后续遍历中必然无法被看见。这启发我们用单调栈解决。
单调栈保存的是下标。由于我们是倒着遍历的，所以栈是底大顶小的。
在单调栈上二分下标 > r 的下标个数，即为能看到的建筑物的个数。

小技巧：为方便调用库函数，可以在单调栈中保存下标的相反数。

void solve()
{
    int n,q;
    cin >> n >> q;
    vi a(n);
    cnv(a);
    vector<vector<pair<int, int>>> ls(n);
    for (int i = 0; i < q; i++) {
        int l,r;
        cin >> l >> r;
        ls[l].push_back({r-1,i});
    }
    vi ans(q),st;
    for (int i = n - 1; i > 0; i--) {
        int v = a[i];
        while (!st.empty() && v > a[-st.back()]) {
            st.pop_back();
        }
        st.pb(-i);
        for (auto& p : ls[i]) {
            ans[p.second] = lower_bound(st.begin(), st.end(), -p.first) - st.begin();
        }
    }
    for (auto v : ans) {
        cout << v << endl;
    }
}

20250117

Problem

Not Argmax

输入 n(1≤n≤500) m(1≤m≤1e5)。
你需要构造一个 1~n 的排列 P。
然后输入 m 个约束，每个约束输入 L R X (1≤L≤X≤R≤n)，表示 P[L],P[L+1],…,P[R] 中的最大值不能是 P[X]。
输出有多少个符合要求的排列 P，模 998244353。

Example

输入

1
2
3

3 2
1 3 2
1 2 1

输出

输入

1 2	`5 1 1 1 1`

输出

输入

输出

输入

输出

1	`921467228`

Solution

如果 x 可以是区间 [L,R] 中的最大值的下标，那么把最大值放置在下标 x 上，问题变成：

从 R-L 个非最大值中，选 x-L 个数分到区间 [L,x-1] 中的方案数（其余数分到区间 [x+1,R]）。
区间 [L,x-1] 的排列数。
区间 [x+1,R] 的排列数。
三者互相独立，根据乘法原理相乘。

这样就有子问题了，于是定义 f[L] [R] 表示区间 [L,R] 的排列数。
枚举可以是区间 [L,R] 的最大值的下标 x，我们有
f[L] [R] = sum(C(R-L,x-L) f[L] [x-1] f[x+1] [R] for x in valid[L,R])。

怎么计算哪些 x 可以是最大值的下标？
把输入按照右端点分组。
在枚举 R 的过程中，把左端点 >= L 的 x 标记为「不能是最大值」。
为什么可以这样做？如果 x 不能是 [l,r] 中的最大值的下标，那么对于任意包含 [l,r] 的更大的区间 [L,R]，x 也不能是 [L,R] 中的最大值的下标。

初始值 f[i] [i-1] = 1。
答案为 f[1] [n]。

const int mx = 500;
int F[mx], invF[mx];
vector<vector<pair<int, int>>> ban;

int pow_mod(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return res;
}
int C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return 1LL * F[n] * invF[k] % mod * invF[n - k] % mod;
}
void solve()
{
    F[0] = 1;
    for (int i = 1; i < mx; i++) {
        F[i] = 1LL * F[i - 1] * i % mod;
    }
    invF[mx - 1] = pow_mod(F[mx - 1], mod - 2);
    for (int i = mx - 2; i >= 0; i--) {
        invF[i] = 1LL * invF[i + 1] * (i + 1) % mod;
    }
    int n,m;
    cin >> n >> m;
    ban.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int l, r, x;
        cin >> l >> r >> x;
        ban[r].push_back({l, x});
    }
    vector<vector<int>> f(n + 2, vi(n + 1));
    f[n + 1][n] = 1;
    // DP process
    for (int l = n; l >= 1; l--) {
        vector<bool> b(n + 1, false);
        f[l][l - 1] = 1;
        
        for (int r = l; r <= n; r++) {
            // Mark banned values
            for (auto& p : ban[r]) {
                if (p.first >= l) {
                    b[p.second] = true;
                }
            }
            
            // Calculate f[l][r]
            for (int x = l; x <= r; x++) {
                if (!b[x]) {
                    f[l][r] = (f[l][r] + 1LL * C(r - l, x - l) * f[l][x - 1] % mod * f[x + 1][r]) % mod;
                }
            }
        }
    }

    cout << f[1][n] << endl;
}

20250120

Problem

XXXXX

输入 T(≤5) 表示 T 组数据。
每组数据输入 n(1≤n≤1e5) x(1≤x≤1e4) 和长为 n 的数组 a(0≤a[i]≤1e4)。

输出 a 的最长连续子数组的长度，满足子数组的元素和不是 x 的倍数。
如果没有这样的子数组，输出 -1。

Example

输入

输出

1
2
3

2
3
-1

Solution

1.如果sum(a)不是x的倍数，输出n

2.否则删除一段和为x的倍数的子数组再删除一个数，便是答案

3.如果全是x的倍数，输出-1

void solve()
{
    int n,x,v;
    cin >> n >> x;
    int s = 0,l = -1, r = -1;
    for (int i = 0; i < n; i++) {
        cin >> v;
        s += v;
        if (v % x != 0) {
            if (l < 0) {
                l = i;
            }
            r = i;
        }
    }
    if (s % x != 0) {
        cout << n << endl;
        return;
    } else if (l < 0) {
        cout << -1 << endl;
        return;
    } else {
        cout << max(n-l-1,r) << endl;
    }
}

20250121

Problem

Max × Sum

输入 T(≤2e5) 表示 T 组数据。所有数据的 n 之和 ≤2e5。
每组数据输入 n k(1≤k≤n≤2e5)，长为 n 的数组 a(1≤a[i]≤1e6)，长为 n 的数组 b(1≤b[i]≤1e6)。

你需要从 n 个下标中选择恰好 k 个下标，组成集合 S。
输出 max(a[i] for i in S) * sum(b[i] for i in S) 的最小值。

Example

输入

3
3 2
3 7 6
9 2 4
5 3
6 4 1 5 9
8 6 5 1 7
10 6
61 95 61 57 69 49 46 47 14 43
39 79 48 92 90 76 30 16 30 94

输出

1
2
3

42
60
14579

Solution

假设 a[i] 是最大的，那么我们需要在所有 <= a[i] 的对应的 b[j] 中，选择最小的 k 个数。

把 a 和 b 绑在一起，按照 a 从小到大排序。
然后遍历 a，用最大堆维护最小的 k 个 b[i]。

void solve()
{
    int n, k;
    cin >> n >> k;
    
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) cin >> a[i].first;
    for (int i = 0; i < n; i++) cin >> a[i].second;
    
    // Sort by x coordinate
    sort(a);
     
    int ans = INF;
    int bsum = 0;
    priority_queue<int> pq;
    for (int i = 0; i < n; i++)
    {
        int c = a[i].first, b = a[i].second;
        if (pq.size() == (k - 1))
        {
            ans = min(ans, c * (bsum + b));
        }
        pq.push(b);
        bsum += b;
        // maintain bsum
        if (pq.size() > (k - 1))
        {
            bsum -= pq.top(); // smallest (k-1)
            pq.pop();
        }
    }
    cout << ans << endl;
}

20250122

Problem

Max/Min

输入 n(2≤n≤2e5) 和长为 n 的数组 a(1≤a[i]≤1e6)。下标从 1 开始。

定义 f(i,j) = floor(max(a[i],a[j]) / min(a[i],a[j]))。

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

Example

输入

1
2

3
3 1 4

输出

输入

1 2	`6 2 7 1 8 2 8`

输出

输入

1 2	`12 3 31 314 3141 31415 314159 2 27 271 2718 27182 271828`

输出

Solution

本质上是从 a 中选两个数来计算，所以 a 中元素顺序不影响答案。

（调和级数）枚举数字 i 以及 i 的倍数 j，那么 [j,j+i-1] 范围内的数，除以 i 下取整都等于 j/i。这些数可以合在一起计算。
为了快速知道范围中的元素个数，可以先统计每个元素的出现次数 cnt，然后计算 cnt 的前缀和。

注意所有等于 i 的数，对答案的正确贡献是 C(cnt[i], 2)，但按照上面的算法会错误地把 cnt[i]^2 加进去，
所以要额外减去 cnt[i]^2 - C(cnt[i], 2) = cnt[i]*(cnt[i]+1)/2。

void solve()
{
    int n, v, ans=0;
    const int mx = 1e6;
    vi s(mx+1);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> v;
        s[v]++;
    }
    for (int i = 2; i <= mx; i++) {
        s[i] += s[i-1];
    }
    for (int i = 1; i <= mx; i++) {
        int c = s[i] - s[i-1];
        if (c == 0) {
            continue;
        }
        for (int j = i; j <= mx; j+=i) {
            ans += j/i *(s[min(j+i-1,mx)]-s[j-1])*c;
        }
        ans -= c*(c+1)/2;
    }
    cout << ans << endl;
}

20250123

Problem

1122 Subsequence

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

输出 a 的子序列 b 的最长长度，满足：

b 的长度是偶数。
b[0]=b[1], b[2]=b[3], … 即两个两个一组，每组中的元素都相同。
b 中的每种数字恰好在 b 中出现两次。

注：子序列不一定连续。

Example

输入

1 2	`7 1 3 3 1 2 2 1`

输出

输入

1
2

1
20

输出

Solution

状态设计题。

定义 f[i] 表示 b 中元素恰好组成集合 i 的情况下，b 的最后一个元素在 a 中的下标的最小值。
枚举不在集合 i 中的 j，在 a 中下标 f[i] 右边寻找两个最近的元素 j，用第二个 j 的下标更新 f[i|1<<j] 的最小值。

初始值 f[0]=-1, f[i]=inf。
最后答案为：对于不等于 inf 的 f[i]，计算 i 的二进制 1 的个数的最大值 * 2。

const int inf = 0x7f7f7f7f;
int dp[(1<<20)+5];
int a[N];
int to[N][25];
int n,ans;
void init(){
    memset(dp,0x7f,sizeof(dp));
    int trans[25];
    memset(trans,0x7f,sizeof(trans));
    for(int i=n;i>=0;i--){
        for(int j=1;j<=20;j++)
            to[i][j] = trans[j];
        trans[a[i]] = i;
    }
    return;
}
int after_two(int x,int t){
    if(x == inf || to[x][t] == inf)
        return inf;
    return to[to[x][t]][t];
}
int record_num(int x){
    int cnt = 0;
    while(x){
        cnt += (x&1);
        x >>= 1;
    }
    return cnt;
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    init();
    dp[0] = 0;
    for(int k=1;k<(1<<20);k++){
        for(int i=1;i<=20;i++){
            if(!(k & (1<<(i-1))))
                continue;
            int k0 = k - (1<<(i-1));
            if(dp[k0] == inf)
                continue;
            if(after_two(dp[k0],i) == inf)
                continue;
            dp[k] = min(dp[k],after_two(dp[k0],i));
        }
        if(dp[k] != inf)
            ans = max(ans,record_num(k));
    }
    cout << (ans<<1) << endl;
}

20250124

Problem

Distributing Integers

输入 n(2≤n≤2e5) 和一棵无向树的 n-1 条边，节点编号从 1 到 n。

定义 f(i) 为如下过程的方案数：
首先，在节点 i 写下数字 1。
然后，选择一个与写下数字节点相邻的节点（没有写过数字），写下数字 2。
继续，重复上述过程，依次写下数字 3,4,…,n。

输出 f(1),f(2),…,f(n)。

Example

输入

1
2
3

3
1 2
1 3

输出

1
2
3

2
1
1

输入

1
2

2
1 2

输出

1
2

1
1

输入

输出

输入

输出

Solution

f(1) 怎么算？
写下所有数字后，如果 DFS 遍历这棵树，按顺序记录遍历到的数字，会得到一个 1~n 的排列，总共有 n! 种，其中肯定有不合法的。
比如，这个排列肯定要以 1 开头，所有不以 1 开头的排列都是不合法的。以 1 开头的排列个数是 (n-1)!，相当于把 n! 除以 n。
同理，对于每棵子树 v 而言（对应着 1~n 排列中的一个子序列），不以 v 的标记数字开头的排列都是不合法的，同样要把方案数除以 size[v]，即子树 v 的大小。
所以 f(1) = n! / (size[1] size[2] … * size[n])。

对于其他 f(i)，我们可以在 f(1) 的基础上，用换根 DP 快速计算上式的分母。
从节点 x 换到节点 y，先除以 size[y]，对于不在子树 y 中的节点，会形成一棵 y 的子树，所以要乘以 (n-size[y])。

由于上述过程有除法，需要用逆元（费马小定理）计算。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 5;

vector<int> adj[MAXN];
ll fact[MAXN], inv_fact[MAXN];
ll dp[MAXN];
int sz[MAXN];
int n;
vector<ll> ans;

ll pow_mod(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    inv_fact[MAXN - 1] = pow_mod(fact[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 0; i--) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    }
}

void dfs(int u, int parent) {
    sz[u] = 1;
    dp[u] = 1;
    vector<int> children;
    ll sum_s = 0;
    for (int v : adj[u]) {
        if (v == parent) continue;
        children.push_back(v);
        dfs(v, u);
        sz[u] += sz[v];
        sum_s += sz[v];
        dp[u] = dp[u] * dp[v] % MOD;
    }
    ll comb = fact[sum_s];
    for (int v : children) {
        comb = comb * inv_fact[sz[v]] % MOD;
    }
    dp[u] = dp[u] * comb % MOD;
}

void reroot(int u, int parent) {
    ans[u - 1] = dp[u];
    vector<int> children;
    for (int v : adj[u]) {
        if (v != parent) {
            children.push_back(v);
        }
    }
    int original_sz_u = sz[u];
    ll original_dp_u = dp[u];
    for (int v : children) {
        int original_sz_v = sz[v];
        ll original_dp_v = dp[v];
        int s_v = original_sz_v;
        int sum_s = original_sz_u - 1;
        int sum_s_new = sum_s - s_v;
        ll numerator = original_dp_u * pow_mod(dp[v], MOD - 2) % MOD;
        numerator = numerator * fact[sum_s_new] % MOD;
        numerator = numerator * fact[s_v] % MOD;
        numerator = numerator * inv_fact[sum_s] % MOD;
        ll dp_parent = numerator % MOD;
        int s_parent = n - original_sz_v;
        ll product_dp = 1;
        ll product_sz_fact = 1;
        ll sum_s_new_v = 0;
        for (int child : adj[v]) {
            if (child == u) continue;
            if (child == parent) {
                product_dp = product_dp * dp_parent % MOD;
                product_sz_fact = product_sz_fact * fact[s_parent] % MOD;
                sum_s_new_v += s_parent;
            } else {
                product_dp = product_dp * dp[child] % MOD;
                product_sz_fact = product_sz_fact * fact[sz[child]] % MOD;
                sum_s_new_v += sz[child];
            }
        }
        sum_s_new_v += s_parent;
        product_dp = product_dp * dp_parent % MOD;
        product_sz_fact = product_sz_fact * fact[s_parent] % MOD;
        ll comb_v = fact[sum_s_new_v] * pow_mod(product_sz_fact, MOD - 2) % MOD;
        ll new_dp_v = product_dp * comb_v % MOD;
        sz[v] = n;
        dp[v] = new_dp_v;
        reroot(v, u);
        sz[v] = original_sz_v;
        dp[v] = original_dp_v;
    }
}

int main() {
    precompute();
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    ans.resize(n);
    dfs(1, -1);
    reroot(1, -1);
    for (ll x : ans) {
        cout << x << '\n';
    }
    return 0;
}

20250127

Problem

Superultra’s Favorite Permutation

输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤2e5。
每组数据输入 n(2≤n≤2e5)。

构造一个 1~n 的排列，满足任意相邻两数之和都是合数。
如果无法构造，输出 -1。

Example

输入

1
2
3

2
3
8

输出

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

Solution

除了 2 以外的偶数都是合数。由于我们无法构造出 2，相邻元素之和只要是偶数，那么一定是合数。

奇数+奇数=偶数，偶数+偶数=偶数。
所以把奇数放在一起，把偶数放在一起。

唯一需要注意的是奇偶交界的位置，是奇数+偶数。
最小的奇合数是 9。
满足奇数+偶数=奇合数的最小数对是 5+4。

所以 n<5 直接输出 -1。
否则答案存在，按顺序输出以下内容：
1~n 中的除了 5 以外的奇数。
5 和 4。
1~n 中的除了 4 以外的偶数。

void solve()
{
    int n;
    cin >> n;
    if (n < 5) {
        cout << -1 << endl;
        return;
    }
    for (int i = 1; i <= n; i += 2) {
        if (i!=5)
            cout << i << " ";
    }
    cout << "5 4 ";
    for (int i = 2; i <= n; i += 2) {
        if (i != 4)
            cout << i << " ";
    }
    cout << endl;
}

20250128

Problem

LR-remainders

输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤2e5。
每组数据输入 n(1≤n≤2e5) mod(1≤mod≤1e4)，长为 n 的数组 a(1≤a[i]≤1e4)，长为 n 的字符串 s，只包含 L 和 R。

从左到右遍历 s，如果是 L，则去掉 a 最左边的元素，否则去掉 a 最右边的元素。
每次去掉元素【之前】，输出 a 中所有元素乘积模 m 的结果。

相似题目 P4588 [TJOI2018] 数学计算

Example

输入

4
4 6
3 1 4 2
LRRL
5 1
1 1 1 1 1
LLLLL
6 8
1 2 3 4 5 6
RLLLRR
1 10000
10000
R

输出

0 2 4 1
0 0 0 0 0
0 0 0 4 4 4
0

Solution

反向遍历操作，由删除变为添加，起始点可以根据L和R的个数判断

void solve()
{
    int n,m;
    cin >> n >> m;
    vi a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    string s;
    cin >> s;
    int cntL = 0;
    for (auto c : s) {
        if (c == 'L') {
            cntL++;
        }
    }
    int l = cntL - 1,r = cntL;
    int sum = 1;
    vi ans;
    for (int i = s.length()-1; i >= 0; i--) {
        if (s[i] == 'L') {
            sum = sum*a[l]%m;
            l--;
        } else {
            sum = sum*a[r]%m;
            r++;
        }
        ans.pb(sum%m);
    }
    for (int i = ans.size()-1; i >= 0; i--) {
        cout << ans[i] << " ";
    }
    cout << endl;
}

20250129

Problem

Virus Tree 2

输入 n(1≤n≤1e5) k(1≤k≤1e5) 和一棵无向树的 n-1 条边，节点编号从 1 到 n。

有 k 种颜色，你需要把每个节点染成 k 种颜色中的一个。
要求：对于相距为 1 或 2 的点对，颜色必须不同。

输出染色方案数，模 1e9+7。

Example

输入

输出

输入

输出

输入

输出

1	`271414432`

Solution

从特殊到一般，如果树是一条链，答案是多少？
从左到右思考：
第一个点可以染 k 种颜色；
第二个点颜色不能和前一个点相同，可以染 k-1 种颜色；
其余点不能和前两个点相同，可以染 k-2 种颜色。

对于一般树上的点 v，哪些点是在点 v 前面的距离点 v 至多为 2 的点？
v 的父节点，
v 的父节点的父节点，
v 左边的兄弟节点（即 v 的父节点的儿子）。
那么 v 可以染 (k - 上述节点个数) 种颜色。

void solve()
{
    int n,k,v,w;
    cin >> n >> k;
    vector<vector<int>> g(n+1);
    for (int i = 1; i < n; i++) {
        cin >> v >> w;
        g[v].push_back(w);
        g[w].push_back(v);
    }
    int ans = k;
    auto dfs = [&](int v, int fa, int dep,auto&& self) -> void {
        int c = 0;
        for (int w : g[v]) {
            if (w != fa) {
                ans = ans * (k - min(dep + 1, 2LL) - c) % mod;
                self(w, v, dep + 1, self);
                c++;
            }
        }
    };
    dfs(1, 0, 0, dfs);
    cout << ans << endl;
}

20250130

Problem

Rem of Sum is Num

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

输出 a 的非空连续子数组 b 的个数，满足 sum(b) % k = len(b)。

Example

输入

1 2	`5 4 1 4 2 3 5`

输出

输入

1 2	`8 4 4 2 4 2 4 2 4 2`

输出

输入

1 2	`10 7 14 15 92 65 35 89 79 32 38 46`

输出

Solution

由于 sum(b)%k < k，所以子数组的长度至多为 k-1。

考虑前缀和，我们有 (s[r] - s[l]) % k = r - l = (r - l) % k。
所以 s[r] - s[l] 和 r - l 模 k 同余。
移项得 ((s[r] - r) - (s[l] - l)) % k = 0。
哈希表统计 (s[i]-i)%k 的个数，用【枚举右维护左】解决。

注意子数组的长度至多为 k-1，所以还要滑窗（移除左端点元素）。

注：s[i]-i 等价于计算 a[i]-1 的前缀和。
注：由于本题保证 a[i] >= 1，所以无需考虑负数取模的问题。

void solve()
{
    int n,k,ans=0;
    cin >> n >> k;
    vi s(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] = (s[i] + s[i-1] - 1) % k;
    }
    mii cnt;
    for (int i = 0; i <= n; i++) {
        ans += cnt[s[i]];
        cnt[s[i]]++;
        if (i >= k-1) {
            cnt[s[i-k+1]]--;
        }
    }
    cout << ans << endl;
}

20250131

Problem

Camel Train

输入 T(≤1e5) 表示 T 组数据。所有数据的 n 之和 ≤2e5。
每组数据输入 n(1≤n≤2e5)。然后输入 n 行，每行输入三个数 ki(1≤ki≤n) li(1≤li≤1e9) ri(1≤ri≤1e9)。

有 n 只骆驼，你需要把这 n 只骆驼按照某种顺序，排成一行。
如果第 i 只骆驼在前 ki 个位置中，那么它的幸福值是 li，否则是 ri。
输出总幸福值的最大值。

本题简单版本：P2949 [USACO09OPEN] Work Scheduling G

Example

输入

输出

1
2
3

25
221
1354

Solution

初步分析

l > r 的骆驼放在 l < r 的骆驼的左边是更优的（可以用交换法证明）。
所以把 l > r 的骆驼分成一组，其余骆驼分成另一组，两组互相独立，分别计算。

下面只讨论 l > r 的情况。
我们可以先把所有 r 加起来，然后讨论 l-r 怎么选取。
如果没法把骆驼放在前 k 个中，那么幸福值只能是 r，这相当于不选 l-r。

方法一：反悔贪心（反悔堆）

按照 k 从小到大排序。
采取「捡到西瓜，丢掉芝麻」的反悔贪心策略：
先把 l-r 入堆（最小堆），如果入堆后发现堆的大小超过当前的 k，则弹出堆顶的「芝麻」。

void solve()
{
    int n,k,l,r;
    cin >> n;
    vector<vector<int>> a(n+1),b(n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> k >> l >> r;
        if (l > r) {
            ans += r;
            a[k].push_back(l-r);
        } else {
            ans += l;
            b[n-k].push_back(r-l);
        }
    }
    auto f = [&](vector<vector<int>>& a) {
        priority_queue<int, vector<int>, greater<>> pq;
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < a[i].size(); j++) {
                ans += a[i][j];
                pq.push(a[i][j]);
                if (pq.size() > i) {
                    int h = pq.top();
                    pq.pop();
                    ans -= h;
                }
            }
        }
    };
    f(a);
    f(b);
    cout << ans << endl;
}

方法二：有序集合

按照 l-r 从大到小排序。
最大的 l-r 肯定是要选的，为了能让其他 l-r 有位置放，最大的 l-r 放的位置越靠右越好，那就放在第 k 个位置。

一般地，用一个有序集合维护空位。
每次找到 <= k 的最大空位，放置骆驼，然后从有序集合中删除这个位置。
如果没有 <= k 的空位，就不放骆驼。

方法三：并查集

把方法二的有序集合改成用并查集维护。删除一个数就相当于把 i 指向 i-1。这样 find(i) 就是 <= i 的最大空位。

codeforces

#acm

茶-2025-01

https://www.polarishaw.top/2025/01/07/Tea202501/

作者

Polaris

发布于

2025年1月7日

许可协议

茶-2025-02 上一篇

CMU15445-lecture13 下一篇