USACO2026 First Gold Solution English Version

__vector__ · 2026-01-14 12:22:37 · 个人记录

This is the English Version of the article.
Translated by doubao.com.
Chinese Version is here.

AKed and got into Platinum, just a quick record.

Almost got stuck on T1.

T1

• Contest time spent: 2 hours 20 minutes.
• Personal difficulty rating: Codeforces 2200.

Draw an edge from i to a_i, resulting in an inward functional graph (inward-based cycle forest).

For nodes with a party held, we care about how many nodes in its subtree will reach it, as well as its type.

For nodes without a party held, we care about how many nodes pass through it.

If processing operations in forward order, extremely complex data structures and case analysis are required. I spent over an hour writing this approach during the contest, then realized it would most likely be impossible to debug, so I abandoned this method.

Note that after a party is held at node i, the edge i \rightarrow a_i becomes effectively invalid; otherwise, it remains valid.

We then consider processing operations in reverse order, converting the problem to continuously modifying types and closing parties.

We use a Disjoint Set Union (DSU/Union-Find) to maintain the state.

If we encounter an operation that only modifies the type, we simply mark the new type of the node and update the total count for each type accordingly—this is straightforward.

If we encounter an operation that closes a party, we add an edge from node i to a_i, and accumulate the number of nodes passing through i to the root node of its set in the DSU.

::::info[Contest Code]

// oh shit prewritten code is not allowed in the USACO
// so I must write this template during the contest.
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define eb emplace_back
#define gc getchar()
#define pc putchar
#define mkpr make_pair
#define fi first
#define se second
#define pln pc('\n');
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}

template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
const int maxn=2e5+5;
int n,m;
int a[maxn];
int c[maxn],v[maxn];
int typ[maxn];
int cnt[maxn];// Number of remaining occurrences of the node after deletions
int prv[maxn];// Type of the affected node before each operation
int ans[4];
struct UF{
    int fa[maxn],siz[maxn];
    void init(){
        FOR(i,1,n)fa[i]=i,siz[i]=1;
    }
    int get(int x){
        return x==fa[x]?x:fa[x]=get(fa[x]);
    }
    int getval(int x){
        if(typ[x])return siz[x];
        return 0;
    }
    void merge(int u,int _fa){
        _fa=get(_fa);
        ans[typ[u]]-=getval(u);
        ans[typ[_fa]]-=getval(_fa);
        siz[_fa]+=siz[u];
        fa[u]=_fa;
        ans[typ[_fa]]+=getval(_fa);
    }
}uf;
void solve(int id_of_test){
    read(n);
    FOR(i,1,n){
        read(a[i]);
    }
    read(m);
    FOR(i,1,m){
        read(c[i]);
        prv[i]=typ[c[i]];
        char op=gc;
        while(!isalpha(op))op=gc;
        if(op=='C')v[i]=1;
        else if(op=='O')v[i]=2;
        else v[i]=3;
        typ[c[i]]=v[i];
        cnt[c[i]]++;
    }
    uf.init();
    FOR(i,1,n){
        if(typ[i]){
            ans[typ[i]]+=uf.getval(i);
        }
    }
    FOR(i,1,n){
        if(!typ[i]){
        //    printf("%d -> %d getval %d %d\n",i,a[i],uf.getval(i),uf.getval(a[i]));
            if(uf.get(a[i])!=i){
                uf.merge(i,a[i]);
            }
          //  printf("upd %d\n",uf.getval(a[i]));
        }
    }
    vector<tuple<int,int,int> > out;
    REP(i,m,1){
        out.eb(make_tuple(ans[1],ans[2],ans[3]));
        cnt[c[i]]--;
        if(cnt[c[i]]){
         //   printf("i = %d typ %d prv %d\n",i,typ[c[i]],prv[i]);
            ans[typ[c[i]]]-=uf.getval(c[i]);
            typ[c[i]]=prv[i];
            ans[typ[c[i]]]+=uf.getval(c[i]);
        }else{
            if(uf.get(a[c[i]])!=uf.get(c[i])){
                uf.merge(c[i],a[c[i]]);
            }else{
                ans[typ[c[i]]]-=uf.getval(c[i]);
            }
            typ[c[i]]=0;
        }
    }
    reverse(out.begin(),out.end());
    for(auto [a,b,c]:out){
        printf("%d %d %d\n",a,b,c);
    }
}
int main()
{
    int T;
    T=1;
    FOR(_,1,T){
        solve(_);
    }
    return 0;
}

::::

T2

• Contest time spent: 1 hour 10 minutes
• Personal difficulty rating: Codeforces 2100
• Similar problem with the same approach (trick) solved before

If merging non-adjacent elements is allowed, the optimal merging strategy is to merge the two smallest elements each time—this is a classic problem.

Note that any sequence satisfying the following condition can achieve the minimum cost:

• It can be obtained by "enumerating each element of a in ascending order and placing it at either the leftmost or rightmost position of the sequence".

All other sequences cannot achieve the minimum cost, which can be verified by referring to the merging process.

However, the number of valid sequences is on the order of O(2^n), making brute-force enumeration infeasible.

We consider the minimum cost to transform the original sequence into any valid solution (still converted to inversion count).

Now we distribute the total number of inversions to each larger element—that is, calculate how many inversions each element contributes as the larger element, then sum them up.

If an element x is placed to the left of the minimum value, it means it must be placed before all elements smaller than it. In this case, the number of inversions generated equals the number of elements smaller than x to its left.

If an element x is placed to the right of the minimum value, it means it must be placed after all elements smaller than x. In this case, the number of inversions generated equals the number of elements smaller than x to its right.

Each element can now independently decide to be placed either to the left or right of the minimum value (whichever yields a smaller contribution), and we sum these minimum contributions to get the final result.

::::info[Contest Code]

// oh shit prewritten code is not allowed in the USACO
// so I must write this template during the contest.
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define eb emplace_back
#define gc getchar()
#define pc putchar
#define mkpr make_pair
#define fi first
#define se second
#define pln pc('\n');
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}

template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
const int maxn=5e5+5;
int n;
int a[maxn];
vi pos[maxn];
struct BIT{
    int lowbit(int x){
        return x&-x;
    }
    int val[maxn];
    void add(int pos,int _v){
        for(;pos<=n;pos+=lowbit(pos)){
            val[pos]+=_v;
        }
    }
    int qsum(int pos){
        int res=0;
        for(;pos;pos-=lowbit(pos)){
            res+=val[pos];
        }
        return res;
    }
    int qsum(int l,int r){
        return qsum(r)-qsum(l-1);
    }
    void clear(){
        FOR(i,1,n)val[i]=0;
    }
}bit;
ll lfsmall[maxn],rgsmall[maxn];
void solve(int id_of_test){
    read(n);
    vi disc;
    FOR(i,1,n){
        read(a[i]);
        disc.eb(a[i]);
    }
    sort(disc.begin(),disc.end());
    disc.erase(unique(disc.begin(),disc.end()),disc.end());
    FOR(i,1,n){
        a[i]=lower_bound(disc.begin(),disc.end(),a[i])-disc.begin()+1;
    }
    bit.clear();
    FOR(i,1,n){
        lfsmall[i]=bit.qsum(a[i]-1);
        bit.add(a[i],1);
    }
    bit.clear();
    REP(i,n,1){
        rgsmall[i]=bit.qsum(a[i]-1);
        bit.add(a[i],1);
    }
    ll ans=0;
    FOR(i,1,n){
        ans+=min(lfsmall[i],rgsmall[i]);
    }
    printf("%lld\n",ans);
}
int main()
{
    int T;
    read(T);
    FOR(_,1,T){
        solve(_);
    }
    return 0;
}

::::

T3

• Contest time spent: 10 minutes.
• Personal difficulty rating: Codeforces 1400
• Exists as a previous problem but I forgot which one—definitely solved it before anyway.