七海ノ心象素描

所有的为时已晚都是恰逢其时

Nanami^2 avatar

Author

Nanami^2

大一学生 | 不是很聪明的样子

Twitter GitHub
Telegram

我的频道

不定期推送灵感笔记

t.me/kisanami_blog
联系方式
QQ 群
1072614878
发送邮件

CF2193 Round 1076 (Div. 3)

个人题解

Nanami^2
Nanami^2 Even in the rain.
2026年01月27日
预计阅读 14 分钟
2980 字

打打 Div 3 找手感吧。

A

很简单不说了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N = 1005;
int T, n, x, s, sum, a[N];
void solve() {
    cin >> n >> s >> x;
    sum = 0;
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
        sum += a[i];
    }
    if(sum <= s && (s - sum) % x == 0) cout << "YES" << endl;
    else cout << "NO" << endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--) solve();
    return 0;
}

B

显然，如果 a1≠na_1 \neq n，那么把 nn 换到第一位一定是最大字典序。如果 a1=na_1 = n，那就看 a2a_2 是否等于 n−1n - 1，以此类推就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N = 2e5 + 5;
int T, n, a[N];
void solve() {
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    int now = n;
    int p = 0, t = 0;
    for(int i = 1;i <= n;i++) {
        if(a[i] != now) {
            p = i, t = now;
            break;
        } else now--;
    }
    if(!p) {
        for(int i = n;i;i--) cout << i << " ";
        cout << endl;
        return;
    }
    int s = 0;
    for(int i = p + 1;i <= n;i++) if(a[i] == t) {
        s = i;
        break;
    }
    // [p, s]
    for(int i = 1;i < p;i++) cout << a[i] << " ";
    for(int i = s;i >= p;i--) cout << a[i] << " ";
    for(int i = s + 1;i <= n;i++) cout << a[i] << " ";
    cout << endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--) solve();
    return 0;
}

C

不是很显然，难度也不高，好题。

手玩一下样例发现还是挺难刻画操作的，这时候不妨考虑一下贪心。以下操作都是追求最简，减去所有不会增大答案的冗余。

  1. 对下标 ii 使用操作 2，一定再对下标 i−1i - 1 使用操作 1 之前。

    证明：一个数对其他数的贡献只能是自己的值往左传递。如果需要这样做，显然是传递 max⁡{ai,bi}\max\{a_i, b_i\} 最优。

  2. aia_i 被它右边的数覆盖后，不可能再对下标 ii 使用操作 2。

    证明：如果使用了操作 22，此时一定有 bib_i 大于等于这个覆盖过来的值，于是不如不覆盖 aia_i，直接换上 bib_i 往左传递。

根据观察 1，我们发现答案等价于取 ci=max⁡{ai,bi}c_i = \max\{a_i, b_i\}，然后只用操作 1。

根据观察 2，我们发现一个 cic_i 会不断往前传递直到遇到第一个大于它的数。于是乎如果 ii 右边存在一个 cj>cic_j > c_i，最终一定是贡献 max⁡i<j{cj}\max_{i < j} \{c_j\}，否则贡献 cic_i。这不就是贡献出后缀 max⁡\max 吗？于是乎前缀和维护就好了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N = 2e5 + 5;
#define int long long
int T, n, q, a[N], b[N], c[N], s[N];
void solve() {
    cin >> n >> q;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++) {
        cin >> b[i];
        c[i] = max(a[i], b[i]);
    }
    c[n + 1] = -2e9;
    for(int i = n - 1;i >= 1;i--) {
        c[i] = max(c[i], c[i + 1]);
    }
    for(int i = 1;i <= n;i++) s[i] = s[i - 1] + c[i];
    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << " ";
    }
    cout << endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--) solve();
    return 0;
}

D

其实难度不如 C 题。

注意到答案一定是某个 aia_i。如果增大一点， ii 这把剑就废了；如果减小一点，答案又不如取 aia_i 时更大。

然后，排个序再枚举 aia_i，就能算出用剑的数量，然后二分查找能通关的数量即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N = 2e5 + 5;
int T, n, a[N], b[N];
ll sa[N], sb[N], ans;
ll calc(int x) {
    int k = upper_bound(sb + 1, sb + n + 1, n - (x - 1)) - sb - 1;
    return 1ll * k;
}
void solve() {
    cin >> n;
    ans = 0;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++) {
        cin >> b[i];
        sb[i] = sb[i - 1] + b[i];
    }
    sort(a + 1, a + n + 1);
    for(int i = 1;i <= n;i++) sa[i] = sa[i - 1] + a[i];
    for(int i = 1;i <= n;i++) {
        ll cnt = calc(i);
        // cout << "i = " << i << " cnt = " << cnt << endl;
        ans = max(ans, 1ll * a[i] * cnt);
    }
    cout << ans << endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--) solve();
    return 0;
}

E

一开始搞了个直接贪心的策略，傻乎乎写完后发现死掉了。枚举 ii，贪心选大因子并不正确，比如 {3,4,6,…}\{3, 4, 6, \ldots\} 凑 1212，显然选 66 后就玩完了。

然后，这个做法其实有巨大的冗余，我们能发现这个是有子问题结构的，如果 j∣ij \mid i，那么凑成 ii 就要求得到凑 jj 的最小个数以及因子 i/ji / j 存在。然后尝试 DP 一下。

设 fif_i 为凑成 ii 的最小个数，有

fi=min⁡j∣i and i/j∈{a}{fj+1}f_i = \min_{j \mid i \text{ and } i / j \in \{a\}} \Big\{ f_j + 1\Big\}

这个显然就很对了，复杂度 O(nn)O(n \sqrt{n})

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N = 3e5 + 5;
int T, n, a[N], c[N], f[N];
void solve() {
    cin >> n;
    for(int i = 0;i <= n;i++) c[i] = 0, f[i] = 1e9;
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
        f[a[i]] = 1;
        ++c[a[i]];
    }
    for(int i = 1;i <= n;i++) {
        for(int j = 2;j * j <= i;j++) if(i % j == 0) {
            if(c[j]) f[i] = min(f[i], f[i / j] + 1);
            if(c[i / j]) f[i] = min(f[i], f[j] + 1);
        }
    }
    for(int i = 1;i <= n;i++) {
        if(f[i] != 1e9) cout << f[i] << " ";
        else cout << "-1 ";
    }
    cout << endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--) solve();
    return 0;
}

F

场上没调出来也是一大遗憾啊。

不能往上走，于是乎必须一层一层送货。自然而然想到按照横坐标相同分分类。先把横坐标统统离散化掉，设有 mm 个。

然后考虑 DP 一下。设 f(i,j)f(i,j) 为处理完前 ii 行，最后一个送货地点是 jj 的最小代价。

f(i,j)=min⁡k{f(i−1,k)+S(k,j)}+dis(i−1,i)f(i, j) = \min_{k} \Big\{ f(i - 1, k) + S(k, j)\Big\} + dis(i - 1, i)

其中 S(k,j)S(k, j) 为从第 ii 行坐标 kk 开始送货，最后一个送到 jj 的最小代价。然后因为这东西情况太多我没讨论全，遗憾立场。

其实就是，设下面一行的纵坐标范围是 [L,R][L,R] 吧。如果 k∈[L,R]k \in [L,R]，那最有解其实是 2(R−L+1)−∣j−k∣2 (R - L + 1) - |j - k|，于是乎你发现绝对值可以拆开，前面的是定值。但是当下面一行只有一个元素的时候这个式子就死了而你著需要朴素地拆开绝对值即可。

而且我跟个弱智一样看到这个就高潮了想用线段树优化结果忘了你只要枚举一下上一行的点就行因为总量是 O(n)O(n) 的并且用两棵线段树维护后也是有一车细节哎呀妈呀我也是服了为什么每次都会遇到这种情况但不得不说纯粹是因为我欠 CF 大跌教育了。

给出丑陋的代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N = 2e5 + 5;
int T, n, Ax, Ay, Bx, By;
PII a[N];
int mx, my, hx[N], hy[N];
vector<int> p[N];
void lsh() {
    sort(hx + 1, hx + mx + 1);
    mx = unique(hx + 1, hx + mx + 1) - (hx + 1);
    sort(hy + 1, hy + my + 1);
    my = unique(hy + 1, hy + my + 1) - (hy + 1);


    Ax = lower_bound(hx + 1, hx + mx + 1, Ax) - hx;
    Bx = lower_bound(hx + 1, hx + mx + 1, Bx) - hx;
    Ay = lower_bound(hy + 1, hy + my + 1, Ay) - hy;
    By = lower_bound(hy + 1, hy + my + 1, By) - hy;
    p[Ax].pb(Ay);
    p[Bx].pb(By);


    for(int i = 1;i <= n;i++) {
        a[i].fi = lower_bound(hx + 1, hx + mx + 1, a[i].fi) - hx;
        a[i].se = lower_bound(hy + 1, hy + my + 1, a[i].se) - hy;
        p[a[i].fi].pb(a[i].se);
    }
    for(int i = 1;i <= mx;i++) {
        sort(p[i].begin(), p[i].end());


    }
}
struct SEG {
    ll t[N << 2];
    void pushup(int x) { t[x] = min(t[x << 1], t[x << 1 | 1]); }
    void build(int x = 1, int l = 1, int r = my) {
        if(l == r) {
            t[x] = 2e18;
            return;
        }
        int mid = (l + r) >> 1;
        build(x << 1, l, mid);
        build(x << 1 | 1, mid + 1, r);
        pushup(x);
    }
    void modify(int p, ll d, int x = 1, int l = 1, int r = my) {
        if(l == r) {
            t[x] = d;
            return;
        }
        int mid = (l + r) >> 1;
        if(p <= mid) modify(p, d, x << 1, l, mid);
        else modify(p, d, x << 1 | 1, mid + 1, r);
        pushup(x);
    }
    ll query(int L, int R, int x = 1, int l = 1, int r = my) {
        if(L > R) return 2e18;
        if(L <= l && r <= R) {
            return t[x];
        }
        int mid = (l + r) >> 1;
        ll res = 2e18;
        if(L <= mid) res = min(res, query(L, R, x << 1, l ,mid));
        if(R > mid) res = min(res, query(L, R, x << 1 | 1, mid + 1, r));
        return res;
    }
} seg[2];
int calc(int x, int y, int xx, int yy) {
    return abs(x - xx) + abs(y - yy);
}
void solve() {
    cin >> n >> Ax >> Ay >> Bx >> By;
    mx = my = 0;
    hx[++mx] = Ax;
    hx[++mx] = Bx;
    hy[++my] = Ay;
    hy[++my] = By;
    for(int i = 1;i <= n;i++) {
        p[i].clear();
        cin >> a[i].fi;
        hx[++mx] = a[i].fi;
    }
    p[n + 1].clear();
    p[n + 2].clear();
    for(int i = 1;i <= n;i++) {
        cin >> a[i].se;
        hy[++my] = a[i].se;
    }
    lsh();


    seg[0].build();
    seg[1].build();
    seg[0].modify(p[1][0], 0 + hy[Ay]);


    seg[1].modify(p[1][0], 0 - hy[Ay]);
    ll ans = 2e18;


    for(int i = 2;i <= mx;i++) {
        vector<pair<int, ll> > vec;
        ll len = hy[p[i].back()] - hy[p[i][0]], t = hx[i] - hx[i - 1];
        for(auto j : p[i]) {
            ll f0 = 2e18;
            ll f1 = 2e18;
            if(p[i].size() == 1) {
                f0 = seg[1].query(1, j) + hy[j] + t;
                f1 = seg[0].query(j, my) - hy[j] + t;
            } else {
                f0 = seg[0].query(p[i][0], j) + 2ll * len - hy[j] + t;
                f0 = min(f0, seg[1].query(1, p[i][0] - 1) + hy[j] + t + 2 * (hy[p[i].back()] - hy[j]));
                f1 = seg[1].query(j, p[i].back()) + 2ll * len + hy[j] + t;
                f1 = min(f1, seg[0].query(p[i].back() + 1, my) - hy[j] + t + 2 * (hy[j] - hy[p[i][0]]));
            }
            ll f = min(f0, f1);


            vec.pb({j, f});


            if(i == mx) ans = min(ans, f);
        }
        for(auto j : p[i - 1]) {
            seg[0].modify(j, 2e18);
            seg[1].modify(j, 2e18);
        }
        for(auto [j, f] : vec) {
            seg[0].modify(j, f + hy[j]);
            seg[1].modify(j, f - hy[j]);
        }
    }




    cout << ans << endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T--) solve();
    return 0;
}

G

H

觉得这篇文章怎么样？

点个赞，让更多人看到！

分享这篇文章

知识因分享而增值

Twitter Telegram 微博 QQ Facebook LinkedIn

分类

Codeforces
比赛

标签

构造
DP
线段树
贪心
数论

版权声明：本文作者为 Nanami^2，首发于nanami7.top。

遵循 CC BY-NC-SA 4.0 许可协议。转载请注明出处！

评论区

本评论区由 EveSunMaple 自主开发