2026夏组队训练赛第五场

C. Upside Down Dijkstra

图论
构造

cpp

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    
    int edge_id = 0;
    vector<int> ans(m + 1), deg(n + 1);
    vector<vector<pair<int, int>>> g(n + 1);
    map<pair<int, int>, int> mp;

    for (int i = 1; i <= m; i ++) {
        int u, v;
        cin >> u >> v;
        deg[u] ++;
        deg[v] ++;
        if (u > v) swap(u, v);
        mp[{u, v}] = 1;
        g[u].push_back({v, ++edge_id});
        g[v].push_back({u, edge_id});
    }

    queue<int> q;
    for (int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        q.push(x);
    }

    if (q.front() != 1) {
        cout << "impossible";
        return 0;
    }

    vector<int> lim(n + 1, 1e6), vis(n + 1);
    vector<pair<int, int>> pre(n + 1, {0, 0});
    q.pop();

    for (auto [v, id] : g[1]) {
        pre[v] = {1, id};
        deg[v] --;
    }

    vis[1] = 1;

    int cur = 1;


    while (!q.empty()) {
        while (deg[cur] == 0) cur = pre[cur].first;
        int u = q.front();

        int l = min(u, cur);
        int r = max(u, cur);
        if (mp[{l, r}] == 0) {
            cout << "impossible";
            return 0;
        }

        for (auto [v, id] : g[u]) if (!vis[v]) {
            pre[v] = {u, id};
        }
        auto [fa, id] = pre[u];
        
        ans[id] = lim[fa];
        lim[fa] --;
        vis[u] = 1;
        for (auto [v, _] : g[u]) deg[v] --;
        cur = u;
        q.pop();
    }

    for (int i = 1; i <= m; i ++) {
        if (ans[i] == 0) cout << 1 << ' ';
        else cout << ans[i] << ' ';
    }
}

D. Christmas Tree Un-decoration

树
树形 DP
线段树
树链剖分

cpp

#pragma optimize(2)
#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int N = 200010;
const LL ninf = LLONG_MIN >> 2;
vector<int> adj[N];
int dep[N], fa[N], cnt[N], son[N], dfn[N], rnk[N], top[N], t;
LL a[N], f[N], g[N];
int n, q, rr[N];

void dfs1(int x) {
    cnt[x] = 1;
    son[x] = g[x] = f[x] = 0;
    for (int &y : adj[x]) {
        if (y == fa[x]) continue;
        fa[y] = x;
        dep[y] = dep[x] + 1;
        dfs1(y);
        cnt[x] += cnt[y];
        if (cnt[y] > cnt[son[x]]) son[x] = y;
        f[x] += f[y];
    }
    f[x] = max(f[x], a[x]);
    for (int &y : adj[x]) {
        if (y == fa[x] || y == son[x]) continue;
        g[x] += f[y];
    }
}

void dfs2(int x, int tp) {
    dfn[x] = ++t;
    rnk[t] = x;
    top[x] = tp;
    if (son[x]) dfs2(son[x], tp);
    else rr[tp] = x;
    for (int &y : adj[x]) {
        if (y == son[x] || y == fa[x]) continue;
        dfs2(y, y);
    }
}

struct Info {
    LL g = 0, a = 0;
};

inline Info merge(const Info &a, const Info &b) {
    return Info{a.g + b.g, max(a.a, a.g + b.a)};
}

Info tr[N * 4];

void build(int u, int l, int r) {
    if (l == r) tr[u] = {g[rnk[l]], a[rnk[l]]};
    else {
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        tr[u] = merge(tr[u << 1], tr[u << 1 | 1]);
    }
}

void modify(int u, int l, int r, int p) {
    if (l == r) tr[u] = {g[rnk[l]], a[rnk[l]]};
    else {
        int mid = l + r >> 1;
        if (p <= mid) modify(u << 1, l, mid, p);
        else modify(u << 1 | 1, mid + 1, r, p);
        tr[u] = merge(tr[u << 1], tr[u << 1 | 1]);
    }
}

Info query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tr[u];
    else {
        int mid = l + r >> 1;
        Info res;
        if (ql <= mid) res = query(u << 1, l, mid, ql, qr);
        if (qr > mid) res = merge(res, query(u << 1 | 1, mid + 1, r, ql, qr));
        return res;
    }
}

LL query(int x) {
    Info res = query(1, 1, n, dfn[x], dfn[rr[top[x]]]);
    return max(res.a, res.g);
}

void modify(int x, LL v) {
    a[x] = v;
    while (x) {
        LL old = query(top[x]);
        modify(1, 1, n, dfn[x]);
        LL now = query(top[x]);
        g[fa[top[x]]] += now - old;
        x = fa[top[x]];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> q;
        
        for (int i = 1; i <= n; ++i) adj[i].clear();
        t = 0;

        for (int i = 2; i <= n; ++i) {
            int p;
            cin >> p;
            adj[p].emplace_back(i);
        }
        for (int i = 1; i <= n; ++i) cin >> a[i];

        dep[1] = 1;
        dfs1(1);
        dfs2(1, 1);

        build(1, 1, n);
        cout << f[1] << '\n';

        while (q--) {
            int x, y;
            cin >> x >> y;
            modify(x, y);
            cout << query(1) << '\n';
        }
    }
    return 0;
}

E. Parallel Sums

分块
贪心

cpp

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'

const int mod = 998244353;
const int INF = 1e18;
const int N = 2e5+5;

int mx[N],tmx[N];
int bel[N];
int vis[N],tvis[N];
pii stk[N];

void init() {}

void solve() {
    int n,m;
    cin>>n>>m;
    vi a(n);
    vi b(n-m+1);
    for(int i=0;i<n-m+1;i++){
        cin>>b[i];
    }
    int sum=b[0];
    for(int i=1;i<n-m+1;i++){
        a[i+m-1]=a[i-1]+b[i]-b[i-1];
    }
    for(int i=0,j=0;i<n;i++){
        bel[i]=j++;
        if(j==m)j=0;
    }
    int q;
    cin>>q;
    int B=max(1ll,(int)(n/sqrt(q)));
    int BC=(n+B-1)/B;
    vi ans(q);
    vpii qs(q);
    vvi q1(BC);
    for(int i=0;i<q;i++){
        int l,r;
        cin>>l>>r;
        l--,r--;
        qs[i]={l,r};
        if(r-l+1<m)ans[i]=-INF;
        else q1[l/B].pb(i);
    }

    for(int i=0;i<BC;i++){
        if(q1[i].empty())continue;
        sort(all(q1[i]),[&](int a,int b){
            return qs[a].s<qs[b].s;
        });
    }
    int tim=0;
    for(int i=0;i<BC;i++){
        if(q1[i].empty())continue;
        int nr=i+1;
        int br=min(n,(i+1)*B);
        int r=br;
        int sm=0;
        for(auto j:q1[i]){
            int l=qs[j].f;
            int rr=qs[j].s;
            if(rr<br){
                tim++;
                int cur=0;
                for(int k=l;k<=rr;k++){
                    int p=bel[k];
                    if(tvis[p]!=tim){
                        tvis[p]=tim;
                        tmx[p]=a[k];
                        cur+=a[k];
                    }else if(tmx[p]<a[k]){
                        cur+=a[k]-tmx[p];
                        tmx[p]=a[k];
                    }
                }
                int x=cur+sum;
                ans[j]=x/m+(x%m>0);
            }else{
                while(r<=rr){
                    int p=bel[r];
                    if(vis[p]!=nr){
                        vis[p]=nr;
                        mx[p]=a[r];
                        sm+=a[r];
                    }else if(mx[p]<a[r]){
                        sm+=a[r]-mx[p];
                        mx[p]=a[r];
                    }
                    r++;
                }
                int tmp=sm;
                int top=0;
                for(int k=l;k<br;k++){
                    int p=bel[k];
                    if(vis[p]!=nr){
                        stk[top++]={p,INF};
                        vis[p]=nr;
                        mx[p]=a[k];
                        sm+=a[k];
                    }else if(a[k]>mx[p]){
                        stk[top++]={p,mx[p]};
                        sm+=a[k]-mx[p];
                        mx[p]=a[k];
                    }
                }
                int x=sm+sum;
                ans[j]=x/m+(x%m>0);
                while(top){
                    top--;
                    int p=stk[top].f;
                    if(stk[top].s==INF){
                        vis[p]=0;
                    }else{
                        mx[p]=stk[top].s;
                    }
                }
                sm=tmp;
            }
        }
    }
    for(int i=0;i<q;i++){
        if(ans[i]==-INF){
            cout<<"unbounded"<<endl;
        }else{
            cout<<ans[i]<<endl;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

F. Minesweeper String

快速傅里叶变换
数论

cpp

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <complex>
using namespace std;
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
void pr(vector<int> a) {
    for (auto i : a)
        cout << i << ' ';
    cout << '\n';
}
const int mod = 998244353;
const int INF = 1e18;
const int N = 5e5 + 5;
vector<int> p[N];
void init() {
    for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j += i) {
            p[j].pb(i);
        }
    }
}
using ll = long long;

const int NTT_MOD = 998244353;
const int NTT_ROOT = 3;

int ntt_qpow(int a, int b) {
    int result = 1;
    while (b) {
        if (b & 1) result = 1LL * result * a % NTT_MOD;
        a = 1LL * a * a % NTT_MOD;
        b >>= 1;
    }
    return result;
}

void ntt(vector<int>& a, bool invert) {
    int n = a.size();

    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        while (j & bit) {
            j ^= bit;
            bit >>= 1;
        }
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        int root = ntt_qpow(NTT_ROOT, (NTT_MOD - 1) / len);
        if (invert) root = ntt_qpow(root, NTT_MOD - 2);

        for (int i = 0; i < n; i += len) {
            int w = 1;
            for (int j = 0; j < len / 2; j++) {
                int x = a[i + j];
                int y = 1LL * a[i + j + len / 2] * w % NTT_MOD;

                a[i + j] = x + y;
                if (a[i + j] >= NTT_MOD) a[i + j] -= NTT_MOD;

                a[i + j + len / 2] = x - y;
                if (a[i + j + len / 2] < 0) {
                    a[i + j + len / 2] += NTT_MOD;
                }
                w = 1LL * w * root % NTT_MOD;
            }
        }
    }

    if (invert) {
        int inv_n = ntt_qpow(n, NTT_MOD - 2);
        for (int& x : a) x = 1LL * x * inv_n % NTT_MOD;
    }
}

vector<int> ntt_mul(vector<int> a, vector<int> b) {
    if (a.empty() || b.empty()) return {};

    int size = a.size() + b.size() - 1;
    int n = 1;
    while (n < size) n <<= 1;

    a.resize(n);
    b.resize(n);

    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) {
        a[i] = 1LL * a[i] * b[i] % NTT_MOD;
    }
    ntt(a, true);

    a.resize(size);
    return a;
}

vi get(string &s, int n) {
    vi a(n), b(n);
    for (int i = 0; i < n; i++) {
        if (s[i] == '0')
            a[i] = 1;
        else
            b[n - 1 - i] = s[i] - '0';
    }
    // pr(a),pr(b);
    return ntt_mul(a, b);
}
void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vi res(n + 1);
    vi c = get(s, n);
    for (int i = 1; i < n; i++) res[i] += c[n - 1 + i] + c[n - 1 - i];
    int sum = 0;
    // pr(res);
    // pr(c);
    // reverse(all(s));
    vi cnt(n+1);
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            if (i != 0) {
                sum += s[i - 1] - '0';
                cnt[i]+=s[i-1]-'0';
            }
            if (i != n - 1) {
                sum += s[i + 1] - '0';
                cnt[i+1]+=s[i+1]-'0';
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(cnt[i]==0)continue;
        for(auto j:p[i]){
            res[j]-=cnt[i];
        }
    }
    for(int i=1;i<=n;i++)res[i]+=sum;
    sort(all(res));
    // pr(res);
    cout<<res[n-k+1]<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    init();
 
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
 
    return 0;
}

H. Reflect Sort

数学
数论

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    vector<ll> a(n + 1), sub(n + 1);
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 2; i <= n; i ++) sub[i] = abs(a[i] - a[i - 1]);
 
    ll g=0,mn=0;
    for(int i=2;i<=n;i++)g=gcd(g,(ll)abs(a[i]-a[i-1])*2);
    if(g==0){
        mn=a[1];
    }else{
        mn=(a[1]-1)%(g)+1;
    }
    for (int i = 2; i <= n; i ++) mn += sub[i];
    cout << mn;
}

J. Worldwide Playlist

数据结构
Ad Hoc

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;
typedef long long LL;

int a[N], rnk[N], b[N], rnkb[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i], rnk[a[i]] = i;
    for (int i = 1; i <= n; ++i) cin >> b[i], rnkb[b[i]] = i;
    LL res = 0;
    auto calc = [&](int i) {
        return (rnk[b[i]] - rnk[b[i - 1]] - 1 + n) % n;
    };
    for (int i = 1, cur = 0; i <= n; ++i) {
        res += calc(i);
    }
    while (q--) {
        cout << res << '\n';
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            int p1 = rnkb[a[x]], p2 = rnkb[a[y]];
            if (p1 > p2) swap(p1, p2);
            if (p1 + 1 == p2) {
                res -= calc(p1) + calc(p2);
                if (p2 != n) res -= calc(p2 + 1);
            } else {
                res -= calc(p1) + calc(p1 + 1) + calc(p2);
                if (p2 != n) res -= calc(p2 + 1);
            }
            swap(rnk[a[x]], rnk[a[y]]);
            swap(a[x], a[y]);
            if (p1 + 1 == p2) {
                res += calc(p1) + calc(p2);
                if (p2 != n) res += calc(p2 + 1);
            } else {
                res += calc(p1) + calc(p1 + 1) + calc(p2);
                if (p2 != n) res += calc(p2 + 1);
            }
        }
        else {
            int p1 = x, p2 = y;
            if (p1 > p2) swap(p1, p2);
            if (p1 + 1 == p2) {
                res -= calc(p1) + calc(p2);
                if (p2 != n) res -= calc(p2 + 1);
            } else {
                res -= calc(p1) + calc(p1 + 1) + calc(p2);
                if (p2 != n) res -= calc(p2 + 1);
            }
            swap(rnkb[b[x]], rnkb[b[y]]);
            swap(b[x], b[y]);
            if (p1 + 1 == p2) {
                res += calc(p1) + calc(p2);
                if (p2 != n) res += calc(p2 + 1);
            } else {
                res += calc(p1) + calc(p1 + 1) + calc(p2);
                if (p2 != n) res += calc(p2 + 1);
            }
        }
    }
    return 0;
}

K. Time Display Stickers

贪心
数学

cpp

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 2e5;
void init() {}
void solve() {
    int n;
    cin>>n;
    string s;
    cin>>s;
    vi cnt(10);
    for(int i=0;i<n;i++)cnt[s[i]-'0']++;
    int c0=cnt[0];
    int c1=cnt[1];
    int c5=accumulate(cnt.begin(),cnt.begin()+6,0ll);
    // cout<<c5<<endl;
    int ans=0;
    for(int i=1;i<=n/4;i++){
        if(c0+c1/2<i)break;
        if(c5-(max(i-c0,0ll)+i)<i)break;
        ans=i;
    }
    cout<<ans<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

其他没做的题

Compare Suffixes
Subtree Removal Game
Extra Transition
Growth Factor
Onion
Deformed Balance

2026夏组队训练赛第五场 ​

C. Upside Down Dijkstra ​

D. Christmas Tree Un-decoration ​

E. Parallel Sums ​

F. Minesweeper String ​

H. Reflect Sort ​

J. Worldwide Playlist ​

K. Time Display Stickers ​

2026夏组队训练赛第五场

C. Upside Down Dijkstra

D. Christmas Tree Un-decoration

E. Parallel Sums

F. Minesweeper String

H. Reflect Sort

J. Worldwide Playlist

K. Time Display Stickers