Codeforces 每日一题

2026年9月7日 10 min

从周一开始,每天按难度递增解决 Codeforces 上的一道题

Array Replacement - Rating 1700

今天是 2026 年 8月 27 日,星期四,问题链接:Array Replacement。

此题考察方式比较隐晦,我们只能从操作方法入手,这其实是一个典型的交换差分,考虑一个三元组($a_{i-1}$, $a_i$, $a_{i+1}$),我们对它进行一次操作后,得到($a_i$, $a_{i - 1} - a_i + a_{i + 1}$, $a_{i + 1}$)。

我们思考什么情况下将 $a_i$ 替换为 $a_{i - 1}-a_i+a_{i + 1}$ 是优的。显然是在 $a_i < a_{i - 1}-a_i+a_{i + 1}$ 时进行替换。我们可以把这个式子移向变为 $a_i-a_{i + 1} < a_{i - 1}-a_i$,注意到与差分数组十分相似,于是考虑定义数组 $D$,满足 $D_i=a_{i-1}-a_{i}$。 我们观察一下,如果对 $a_i$ 进行操作时对 $D$ 数组的影响:

  • 对于 $D_{i}$ 来说,它会变成 $a_{i - 1} - (a_{i - 1} - a_i + a_{i + 1}) = a_{i} - a_{i + 1} = D_{i + 1}$。
  • 对于 $D_{i + 1}$ 来说,它会变成 $(a_{i - 1} - a_i + a_{i + 1}) - a_{i + 1} = a_{i - 1} - a_i = D_{i}$。

即一次操作,我们会交换 $D_i$ 和 $D_{i + 1}$,且只有两者奇偶性相同时才可交换。于是我们维护每段奇偶性相同的 $D$,在这段数组内按最大值排序,从头部每次减去最大的差分值来保证字典序最小即可。 代码如下:

cpp 30 行
// Retired?
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
void solve(){

    int n; cin >> n;

    vector<int> a(n + 1), d(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i], d[i] = a[i - 1] - a[i];

    int l = 2;
    while(l <= n){
        int r = l;
        while(r <= n && abs(d[l] % 2) == abs(d[r] % 2)) r++;
        sort(d.begin() + l, d.begin() + r);
        reverse(d.begin() + l, d.begin() + r);
        l = r;
    }   

    int x = a[1];
    cout << x << ' ';
    for(int i = 2; i <= n; i++) x -= d[i], cout << x << ' ';
    cout << '\n';

}
signed main(){
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t;cin>>t;while(t--)solve();
}

Robin Hood Archery - Rating 1900

今天是 2026 年 8月 28 日,星期五,问题链接:Robin Hood Archery。

首先考虑什么情况下 Sheriff 才不会输,由于 Robin Hood 总是先手出,那么在一大一小的情况下,他肯定选择拿大的,那么 Sheriff 不输的局面只有平局,因为他总是落后的,所以当两个数相等的局面,两者得到的分数才会相同,这样就不会输。

再看题意,题目的查询次数较大,因此需要频繁的在区间内进行统计和查询,且不具备实时性(即可以先乱序得出答案,再按问题顺序回答),因此我们考虑莫队,它可以使得我们在 $O(n \sqrt{n})$ 复杂度内进行区间内的修改查询。

我们维护一个变量 $res$,当区间内的数频均为偶数次时 $res=0$,具体代码如下:

cpp 57 行
// Retired?
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
int pos[N], a[N], cnt[N], mp[N];
struct node{
    int l, r, now;
    bool operator< (const node &w) const{
        return (pos[l] ^ pos[w.l]) ? pos[l] < pos[w.l] : ((pos[l] & 1) ? r < w.r : r > w.r);
    }
}p[N];
void solve(){

    int n, m; cin >> n >> m;

    int len = sqrt(n);
    for(int i = 1; i <= n; i++) cin >> a[i], pos[i] = i / len;

    for(int i = 1; i <= m; i++){
        int l, r; cin >> l >> r;
        p[i] = {l, r, i};
    }

    sort(p + 1, p + 1 + m);

    int res = 0;
    auto add = [&](int x) -> void{
        mp[a[x]]++;
        if(mp[a[x]] % 2 == 0) res--;
        else res++;
    }; 

    auto del = [&](int x) -> void{
        mp[a[x]]--;
        if(mp[a[x]] % 2 == 0) res--;
        else res++;
    };

    int l = 1, r = 0;
    vector<int> ans(m + 1);
    for(int i = 1; i <= m; i++){
        int id = p[i].now;
        while(l < p[i].l) del(l++);
        while(l > p[i].l) add(--l);
        while(r < p[i].r) add(++r);
        while(r > p[i].r) del(r--);
        ans[id] = res;
    }

    for(int i = 1; i <= m; i++) cout << (ans[i] ? "NO" : "YES") << '\n';
    for(int i = 1; i <= n; i++) mp[a[i]] = 0;

}
signed main(){
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t;cin>>t;while(t--)solve();
}

Stepan and Permutation - Rating 1100

今天是 2026 年 8月 31 日,星期一,问题链接:Stepan and Permutation。

我们可以根据交换条件得出可以随意交换的位置为分成组的,组内可以随便交换,组外不可交换。考虑通过并查集来分组,对于 $a_i$ 来说,它与 $a_{i + j * x}$ 和 $a_{i + j * y}$ 一组, 其中 $j \in {0,1,2...}$,那么我们在组内就可以直接排序,然后记录一下每一组所占的位置,按顺序安置。这样只需要检查最终结果是否为增序的排列即可。

代码如下:

cpp 53 行
// Retired?
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
void solve(){

    int n, x, y; cin >> n >> x >> y;
    
    vector<int> a(n + 1), p(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i], p[i] = i;

    function<int(int)> find = [&](int x) -> int{
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    };

    for(int i = 1; i <= n; i++){
        if(i + x <= n){
            if(find(a[i]) != find(a[i + x])){
                p[find(a[i + x])] = find(a[i]);
            }
        }
        if(i + y <= n){
            if(find(a[i]) != find(a[i + y])){
                p[find(a[i + y])] = find(a[i]);
            }
        }
    }

    vector<int> b(n + 1);
    vector<vector<int>> v(n + 1), pos(n + 1);
    for(int i = 1; i <= n; i++) v[find(a[i])].push_back(a[i]), pos[find(a[i])].push_back(i);
    for(int i = 1; i <= n; i++) sort(v[i].begin(), v[i].end());
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < v[i].size(); j++){
            b[pos[i][j]] = v[i][j];
        }
    }

    for(int i = 1; i <= n; i++){
        if(b[i] != i){
            cout << "NO" << '\n';
            return;
        } 
    }

    cout << "YES" << '\n';

}
signed main(){
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t;cin>>t;while(t--)solve();
}

Risky Tower - Rating 1400

今天是 2026 年 9 月 1 日,星期二,问题链接:Risky Tower。

首先考虑贪心策略:要摧毁第 $i$ 行,我们需要选取若干个木块使得总攻击力 $\geq v_i$,且每行最多选 $m$ 个木块。为了使操作次数最少,显然应优先选最大的木块。

考虑塔从上到下依次摧毁,摧毁第 $i$ 行时,第 $i$ 行及其下方(第 $i, i+1, \ldots, n$ 行)的所有木块都可以使用。因此,我们从第 $1$ 行开始枚举,每处理完一行就将该行的木块从可用集合中移除。

我们用一个计数器 $mp$ 统计所有木块的出现次数,并将所有不同的木块值存入数组 $que$ 后按降序排列。对于当前枚举的第 $i$ 行,我们从 $que$ 头部依次取最大的木块,将其值累加至 $sum$,直到 $sum \geq v_i$ 或已取满 $m$ 个。若当前最大值 $top$ 的剩余次数 $mp[top]$ 为 $0$,则跳过。处理完第 $i$ 行后,将该行所有木块的计数各减一。答案为所有行所需最小操作次数的最小值,且不超过 $m$。

代码如下:

cpp 48 行
// Retired?
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
void solve(){

    int n, m; cin >> n >> m;

    vector<int> v(n + 1);
    for(int i = 1; i <= n; i++) cin >> v[i];

    map<int, int> mp;
    vector<int> que;
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
            if(!mp.count(a[i][j])) que.push_back(a[i][j]);
            mp[a[i][j]]++;
        }
    }

    sort(que.begin(), que.end());
    reverse(que.begin(), que.end());

    int res = LLONG_MAX;
    for(int i = 1; i <= n; i++){
        int sum = 0, cnt = 0, pos = 0;
        while(sum < v[i] && cnt < m){
            int top = que[pos];
            while(mp[top] == 0) top = que[++pos];
            if(sum + top * mp[top] >= v[i]){
                int need = (v[i] - sum + top - 1) / top;
                sum += top * need, cnt += need;
            } else sum += top * mp[top], cnt += mp[top];
            pos++;
        }
        res = min(res, cnt);
        for(int j = 1; j <= m; j++) mp[a[i][j]]--;
    }

    cout << min(res, m) << '\n';

}
signed main(){
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t;cin>>t;while(t--)solve();
}

Prefix Equality - Rating 1800

今天是2026年9月2日星期三。题目链接:Prefix Equality。

这是一道有趣的题目。由于每次查询都涉及数组$a$中索引$1$到$i$以及$1$到$j$的元素,因此这些操作具有某种前缀般的性质。

我们先以数组 $a$ 为例。

  • 对于数组 $a$ 中的特定位置 $i$,我们将数组 $b$ 中与集合 $\{a_1, \dots, a_i\}$ 匹配的最近和最远位置分别记为 $La$ 和 $Ra$。然后,我们维护两个集合 set_a 和 set_b,用于记录 $a$ 和 $b$ 前缀中的不同元素。

  • 如果 $a_i$ 不会对 set_a 产生影响,则初始化 $La_i = La_{i - 1}$ 和 $Ra_i = Ra_{i - 1}$。只要 $b_j$ 属于 set_a,我们就可以将 $j$ 递增,并将 $Ra_i$ 更新为 $j$。此外,当首次遇到 $b_j$ 时,应将 $j$ 记录为 $La_i$,因为 <$j$ 的集合无法包含集合 $\{a_1, \dots, a_i\}$ 中所需的所有元素。

因此我们可以计算 $La$、$Ra$、$Lb$ 和 $Rb$。如果 $x$ 和 $y$ 是一对正确的组合,则应满足 la[x] <= y && y <= ra[x] and lb[y] <= x && x <= rb[y]。时间复杂度为 $O(N \log N + Q)$。

代码如下:

cpp 42 行
// Retired?
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
signed main(){
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int n; cin >> n;

    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];

    auto work = [&](const vector<int>& A, const vector<int>& B) {
        vector<int> l(n + 1), r(n + 1);
        set<int> seA, seB;
        for(int i = 1, j = 1; i <= n; i++){
            if(seA.count(A[i])) l[i] = l[i - 1], r[i] = r[i - 1];
            else seA.insert(A[i]);
            while(j <= n && seA.count(B[j])){
                r[i] = j;
                if(!seB.count(B[j])) l[i] = j;
                seB.insert(B[j++]);
            }
        }
        return make_pair(l, r);
    };

    auto [la, ra] = work(a, b);
    auto [lb, rb] = work(b, a);

    int Q; cin >> Q;
    for(int i = 1; i <= Q; i++){
        int x, y; cin >> x >> y;
        if((la[x] <= y && y <= ra[x]) && (lb[y] <= x && x <= rb[y])){
            cout << "Yes" << '\n';
        } else cout << "No" << '\n';
    }

    return 0;
}

Sanae, Cross and Color - Rating 1900

今天是2026年9月3日星期四。题目链接:Sanae, Cross and Color。

什么情况下会增加有效的切割方案?如果一次坐标变换没有跨过任何一个点,那么各个点所属的颜色不变,所以每次有效的切割必须跨过至少一个点。

什么情况下能够使得四个象限都有点?我们首先固定竖线 x,考虑最左边的 x,我们的 $k_1$ 肯定要大于等于 x,这样 $k_1+0.5$ 之后,左边保底有一个点,同时,$k_1$ 要小于最右边的 x。

竖线固定后,考虑什么情况下会让四个象限都有点。

  1. 左上角:$k_2$ 小于最大的 y,设为 LmaxY
  2. 右上角:$k_2$ 小于最大的 y,设为 RmaxY
  3. 左下角:$k_2$ 大于等于最小的 y,设为 LminY
  4. 右下角:$k_2$ 大于等于最小的 y,设为 RminY 因此,对于一个合法的 x,我们的 y 必须满足 max{LminY,RminY} <= y <= min{LmaxY,RmaxY} - 1,只要 y 是一个真实存在的 y 值坐标且没出现过,那么这就是一种全新的方案。

接下来考虑怎么在 $O(n)$ 的复杂度内解决,对于不重复的 y 来说,我们预先处理一个前缀和 preY,preY[y] 表示小于等于 y 有几个,那么可以在 $O(1)$ 的复杂度内可以得到任意区间的合法 y,然后将 x 相同的点分到一组内,对于每一组,我们计算它的 $L\{min/max\}Y$ 和 $R\{min/max\}Y$,那么我们就可以将 x 按升序排列,然后 y 分为左和右,计算一组 x 时,先把这一组的 y 全部加到左边的一组。 代码如下:

cpp 47 行
// Retired?
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
void solve(){

    int n; cin >> n;

    vector<vector<int>> xtoy(n + 1);
    vector<pair<int, int>> point(n + 1);
    vector<int> cnty(n + 1), cntx(n + 1);
    for(int i = 1; i <= n; i++){
        int x, y; cin >> x >> y;
        point[i] = {x, y}, xtoy[x].push_back(y); 
        cnty[y]++, cntx[x]++;
    }

    vector<int> prey(n + 1), difx;
    for(int i = 1; i <= n; i++){
        prey[i] = prey[i - 1] + (cnty[i] != 0);
        if(cntx[i]) difx.push_back(i);
    }
    
    int m = difx.size();
    vector<int> Lminy(m, n + 1), Rminy(m, n + 1), Lmaxy(m), Rmaxy(m);
    for(int i = 0, j = m - 1; i < m; i++, j--){
        if(i != 0){
            Lminy[i] = Lminy[i - 1], Lmaxy[i] = Lmaxy[i - 1];
            Rminy[j] = Rminy[j + 1], Rmaxy[j] = Rmaxy[j + 1];
        }
        for(auto y : xtoy[difx[i]]) Lminy[i] = min(Lminy[i], y), Lmaxy[i] = max(Lmaxy[i], y);
        for(auto y : xtoy[difx[j]]) Rminy[j] = min(Rminy[j], y), Rmaxy[j] = max(Rmaxy[j], y);
    }   

    int res = 0;
    for(int i = 0; i < m - 1; i++){
        if(min(Lmaxy[i], Rmaxy[i + 1]) - 1 < max(Lminy[i], Rminy[i + 1])) continue;
        res += prey[min(Lmaxy[i], Rmaxy[i + 1]) - 1] - prey[max(Lminy[i], Rminy[i + 1]) - 1];
    }

    cout << res << '\n';

}
signed main(){
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t;cin>>t;while(t--)solve();
}

Fence Divercity - Rating 2300

今天是 2026 年 9 月 4 日,星期五。题目链接:Fence Divercity。

通读题意后,我们得到以下约束条件:

  1. 被切除的部分必须是连通的,且必须严格从顶部向下切,每块木板切除后剩余的高度必须为正数($h \ge 1$)。
  2. 只有相邻的木板才能作为一个连通块一起被切除。

由于方案数较多,我们考虑使用动态规划(DP)。接下来计算在第 $i$ 列有多少种切除方案。设 dp[i] 为仅切除第 $i$ 列并延伸至第 $i + 1$ 列的合法方案数。分为以下几种情况:

  • 情况 1:仅切除第 $i$ 列,忽略第 $i - 1$ 列和第 $i + 1$ 列。在这种情况下,有 $h_i - 1$ 种切法。
  • 情况 2:仅考虑第 $i$ 列和第 $i - 1$ 列。在这种情况下,若 $h_i > h_{i - 1}$,切除的高度不能高于 $h_{i - 1}$,因此合法方案数为 $h_{i - 1} - 1$;当 $h_i < h_{i - 1}$ 时,合法方案数为 $h_i - 1$。所以根据乘法原理,总合法方案数为 $(\min(h_i, h_{i-1}) - 1) \times \text{dp}[i - 1]$。
  • 情况 3:仅考虑第 $i$ 列和第 $i + 1$ 列。从第 $i$ 列开始一段新的切除并延伸至第 $i + 1$ 列。因此合法方案数为 $\min(h_i, h_{i + 1}) - 1$。
  • 情况 4:同时考虑第 $i - 1$ 列、第 $i$ 列和第 $i + 1$ 列。合法方案数为 $(\min(\{h_{i-1}, h_i, h_{i+1}\}) - 1) \times \text{dp}[i - 1]$。

因此,我们递推维护 dp 数组,并累加记录最终答案 res。最终答案由情况 1 和情况 2 构成。

代码如下:

cpp 25 行
// Retired?
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
signed main(){
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int n; cin >> n;

    vector<int> h(n + 2);
    for(int i = 1; i <= n; i++) cin >> h[i];

    int res = 0;
    vector<int> dp(n + 1);
    for(int i = 1; i <= n; i++){
        dp[i] = ((min({h[i - 1], h[i], h[i + 1]}) - 1) * dp[i - 1] + min(h[i], h[i + 1]) - 1) % mod;
        res += (h[i] - 1 + (min(h[i - 1], h[i]) - 1) * dp[i - 1]) % mod;
        res %= mod;
    }

    cout << res << '\n';

    return 0;
}

RemovevomeR - Rating 1000

今天是2026年9月7日星期一。题目链接:RemovevomeR

这道题很简单。如果出现多个相同的字符连续出现,我们可以通过 $size - 1$ 次操作将其简化为一个字符。

因此,在第 1 步之后,情况变为 s_new = $xyxyxyxyxy...$。需要注意的是,$xyx$ 可以变为 $x$,而 $xyxy$ 可以变为 $x$ 或 $y$。因此,如果 s_new 的大小 > 3,我们可以将其大小缩减为 1。但如果 s_new 是 $xy$,我们就无法对其进行任何操作。

代码如下:

cpp 27 行
// Retired?
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
void solve(){

    int n; cin >> n;
    string s; cin >> s;
    s = " " + s;

    string news = "";
    for(int i = 1; i <= n; i++){
        int j = i + 1;
        news.push_back(s[i]);
        while(j <= n && s[i] == s[j]) j++;
        i = j - 1;
    }

    if(news.size() >= 3) cout << 1 << '\n';
    else cout << news.size() << '\n';


}
signed main(){
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t;cin>>t;while(t--)solve();
}

评论