26.11.8 比赛记录

更新于 2026年11月12日约 3 分钟阅读

T1 疯狂钻石

蓝色数组在数轴上把红色数字分分隔开,假如蓝色数字去重后有 xx 个数,就会形成 x+1x+1 个间隔。处在同一个间隔里的红色数字是可以一起选的,求每个间隔的红色数字的最大数量即可。

T2 绯红之王

定义 DP 数组,fi,jf_{i,j} 表示处理了第一叠的前 ii 张和第二叠的前 jj 张的最优情况。这个最优情况是一个 pair,如果两个情况的处理批数不同,批数小的更优,否则剩余容量大的更优。转移方程就是从第一叠取和第二叠取,两种情况里选最优的。DP 可以用滚动数组,比较两种情况的优劣用 pair 自带的比较即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
const int N=5005;
int n,m,k,w,a[N],b[N];
pii dp[N];
pii add(pii x,int y){
    if(!x.first||x.second+y>w)x.first++,x.second=y;
    else x.second+=y;
    return x;
}
signed main(){
    cin>>n>>m>>w>>k;
    for(int i=1;i<=n;i++)cin>>a[n-i+1];
    for(int i=1;i<=m;i++)cin>>b[m-i+1];
    for(int i=1;i<=m;i++)dp[i]=add(dp[i-1],b[i]);
    for(int i=1;i<=n;i++){
        dp[0]=add(dp[0],a[i]);
        for(int j=1;j<=m;j++)
            dp[j]=min(add(dp[j],a[i]),add(dp[j-1],b[j]));
    }
    cout<<dp[m].first*k;
    return 0;
}

T3 紫色隐者

赛时想到正解了,最终没 AC(因为 SPJ 比较难测大样例,码完后直接去写下一题了)。

可以发现这题的问题可以拆分成很多子问题。假如你有一棵以 uu 为根的树,还有很多子树。你可以把一些子树的编号设置成比 uu 小的,另一些子树的编号设置成比 uu 大的。这样所有子树就被划分成了两部分。如何划分最优呢?显然两部分 siz 之差最小是最优的。这可以使用背包 DP 计算。然后对于每个子树递归下去求解即可。注意 11 和 nn 这两个点要忽略。总时间复杂度 O(n2)O(n^2)。

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int n,fa[N],dp[N],siz[N],ans[N],sizz[N],cnt[N];
bool b[N],choose[N][N];
vector<int>g[N];
void dfs(int u){
    sizz[u]=1,cnt[u]=(u!=1&&u!=n);
    for(int v:g[u])dfs(v),sizz[u]+=sizz[v],cnt[u]+=cnt[v];
}
void bag(int u,int n,int m){
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            dp[j]=choose[i][j]=0;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=1;j--)
            if(j>=cnt[g[u][i-1]]&&dp[j]<dp[j-cnt[g[u][i-1]]]+cnt[g[u][i-1]])
                dp[j]=dp[j-cnt[g[u][i-1]]]+cnt[g[u][i-1]],choose[i][j]=1;
    for(int i=n,j=m;i>=1;i--)
        if(choose[i][j])b[g[u][i-1]]=1,j-=cnt[g[u][i-1]];
}
void dfs1(int u,int l,int r){
    if(!siz[u]){
        ans[u]=l;
        return;
    }
    int sum=l;
    for(int v:g[u])
        if(b[v])dfs1(v,sum,sum+sizz[v]-1),sum+=sizz[v];
    ans[u]=sum++;
    for(int v:g[u])
        if(!b[v])dfs1(v,sum,sum+sizz[v]-1),sum+=sizz[v];
}
int main(){
    cin>>n;
    for(int i=2;i<=n;i++)cin>>fa[i],g[fa[i]].push_back(i);
    for(int i=1;i<=n;i++)siz[i]=g[i].size();
    dfs(1);
    for(int i=1;i<=n;i++){
        if(siz[i]<=1)continue;
        int sum=0;
        for(int v:g[i])sum+=cnt[v];
        bag(i,siz[i],sum/2);
    }
    dfs1(1,1,n);
    for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
    return 0;
}

T4 公路之星

首先把所有 R 边转换成反向的 B 边。我们可以发现一个性质:如果有两条边指向同一个点,例如 u1→vu_1\to v,u2→vu_2\to v,我们就可以把 u1,u2u_1,u_2 这两个点视作互相可达的点,因为 u1→v→u2u_1\to v\to u_2 和 u2→v→u1u_2\to v\to u_1 都是合法的路径且 C=0C=0。既然这样,我们可以把 u1,u2u_1,u_2 合成一个等效节点 uu。对于所有拥有两条及以上入边的点进行此操作,不断合成,直到无法操作。最终,如果 s,ts,t 处于同一个等效节点中,就是互相可达的。对于不断合并的操作,我们可以使用并查集实现,因为节点的可达性具有自反性、传递性、对称性(这三个性质具体来讲,就是 xx 可达 xx,xx 可达 yy 且 yy 可达 zz 能推出 xx 可达 zz,xx 可达 yy 能推出 yy 可达 xx)。我们可以使用链表记录每个节点有哪些入边,这样可以 O(1)O(1) 合并。总时间复杂度 O((N+M+Q)α(n))O((N+M+Q)\alpha(n))。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,u[N],v[N],t;
int cnt[N],hd[N],tl[N],nx[N];//链表储存每个节点的入边
int fa[N],siz[N];
queue<int>q;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return;
    if(siz[x]<siz[y])swap(x,y);
    fa[y]=x;
    siz[x]+=siz[y];
    if(cnt[x])nx[tl[x]]=hd[y];
    else hd[x]=hd[y];
    if(cnt[y])tl[x]=tl[y];
    cnt[x]+=cnt[y];
    hd[y]=tl[y]=cnt[y]=0;
    if(cnt[x]>=2)q.push(x);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(int i=0;i<N;i++)
        fa[i]=i,siz[i]=1;
    for(int i=1;i<=m;i++){
        char d;
        cin>>u[i]>>v[i]>>d;
        if(d=='R')swap(u[i],v[i]);
        if(cnt[v[i]]++==0)hd[v[i]]=tl[v[i]]=i;
        else nx[tl[v[i]]]=i,tl[v[i]]=i;
    }
    for(int i=1;i<=n;i++)
        if(cnt[i]>=2)q.push(i);
    while(q.size()){
        int x=q.front();
        q.pop();
        while(cnt[x]>=2){
            int e=hd[x];
            hd[x]=nx[hd[x]];
            cnt[x]--;
            merge(u[e],u[hd[x]]);
            x=find(x);
        }
    }
    cin>>t;
    while(t--){
        int s,t;
        cin>>s>>t;
        cout<<(find(s)==find(t))<<'\n';
    }
    return 0;
}

Vector Log · 算法竞赛学习笔记

Built with Nuxt UI & Nuxt MDC