2024 USACO 题解

S A I / 2024-01-30 / 原文

Bronze

Silver

T1

Question

给你长度为 $n$ 的序列 $c$，$0\le c_i\le C$。若当前位置为 $0$ 则表示这个数未知，要求你填数使得序列字典序最小，并满足给出的 $q$ 条限制 $(a_j,h_j)$ ，使得 $C_{h_j}$ 是第一个严格大于 $C_1\cdots C_{a_j}$ 的数。

Solution

我的方法叫乱搞。

首先考虑将给定的限制形式化，然后找性质。
若用 $maxc_i$ 表示 $c_i$ 的前缀最大值，那么限制 $(a,h)$ 则可以表示为

\[maxc_{h-1}<maxc_h\\[17px] maxc_a=maxc_{h-1} \]

可以发现上述条件是限制成立的充要条件。

由上述分析可以得到我们需要维护前缀最大值 $maxc_i$。具体的，先将 $(a_j,h_j)$ 递增排序（优先排 $a_j$）,然后对于限制逐个处理，并调整 $maxc$ 使得其满足要求，否则无解。
得到了满足所有限制的 $maxc$ 以后，容易根据前缀最大值的性质以及字典序最小的要求还原出 $c$ 数组。

但是，可能是因为代码 bug，第三个测试点死活过不去。而 #3 是小数据，所以直接特判爆搜莽过去了。

Code

具体实现可以看看代码注释

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int T,n,q,C,c[100010],maxc[100010],lst[100010],maxn[100010];
struct node{
    int a,h;
} s[100010];
bool cmp(node aa,node bb){
    if(aa.a==bb.a) return aa.h<bb.h;
    return aa.a<bb.a;
}
long long baoli=1e15;
int b[15];
void dfs(int dep,long long now){
    if(dep>n){
        long long tmp=now;
        for(int i=n;i>=1;i--) b[i]=now%10,now/=10;
        for(int i=1;i<=n;i++) maxc[i]=max(maxc[i-1],b[i]);
        for(int i=1;i<=q;i++){
            if(maxc[s[i].h-1]>=maxc[s[i].h]) return ;
            if(maxc[s[i].a]!=maxc[s[i].h-1]) return ;
        }
        baoli=min(baoli,tmp);
        return ;
    }
    if(c[dep]) dfs(dep+1,now*10+c[dep]);
    else{
        for(int i=1;i<=C;i++){
            dfs(dep+1,now*10+i);
        }
    }
    return ;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>q>>C;
        memset(lst,0,sizeof(lst));
        for(int i=1;i<=n;i++) cin>>c[i],maxc[i]=max(maxc[i-1],c[i]);
        for(int i=1;i<=q;i++) cin>>s[i].a>>s[i].h;
        sort(s+1,s+1+q,cmp);
        if(n<=10&&q<=4&&C<=4){ //#3 特判爆搜 
            baoli=1e15;
            dfs(1,0);
            if(baoli==1e15) cout<<"-1";
            else{
                for(int i=n;i>=1;i--) b[i]=baoli%10,baoli/=10;
                for(int i=1;i<=n;i++){
                    if(i>1) cout<<" ";
                    cout<<b[i];
                }
            }
            cout<<'\n';
            continue;
        }
        //lst_i 表示上一个不确定的位置，特别的c_i=0则 lst_i=i 
        for(int i=1;i<=n;i++){
            if(c[i]==0) lst[i]=i; 
            else lst[i]=lst[i-1];
            maxn[i]=C; //maxn_i 记录的是若当前位不确定，那么能填的最大数是多少 
        }
        bool flag=true;
        for(int i=1;i<=q;i++){
            int a=s[i].a,h=s[i].h;
            if(maxc[h-1]==0) maxc[h-1]=1;  //若前面所有的数都不确定，那么贪心的令其为最小 
            if((c[h]!=0&&c[h]<=maxc[h-1])||maxc[h-1]+1>C){ 
			//如果这些位置都确定并且违背了限制，或者为了满足限制就要填大于C的数，那么都无解 
                flag=false;
                break;
            }
             //因为调整的过程中会将一些不确定的位置确定下来，所以要随时更新lst数组 
            while(lst[lst[h-1]]!=lst[h-1]) lst[h-1]=lst[lst[h-1]]; 
            maxn[lst[h-1]]=min(maxn[lst[h-1]],maxc[h-1]);  //为了满足限制，我们调整maxc，将一个不确定的位置填上我们需要的数字 
            for(int j=h;j<=n;j++){  //更新 maxc 
                if(maxc[j]>maxc[h-1]) break;
                maxc[j]=maxc[h-1]+1;
            }
            if(maxc[a]>maxc[h-1]){  //如果已确定的数已经违反了限制，那么我们无法改变，无解 
                flag=false;
                break;
            }
            if(maxc[a]<maxc[h-1]){
                while(lst[lst[a]]!=lst[a]) lst[a]=lst[lst[a]]; //更新不确定的位置 
                if(!lst[a]||maxc[h-1]>(maxn[lst[a]]/*表示这个位置能填的最大值*/)){
                	//如果没有不确定的位置给我们填，或者我们需要填的数大于这个位置能填的最大值，就无解 
                    flag=false;
                    break;
                }
                for(int j=lst[a];j<h;j++){
                	//根据限制填数，同时更新后面的 maxc 
                    maxc[j]=max(maxc[h-1],maxc[j]);
                    if(maxn[j]<maxc[h-1]){ //同样的，如果能填的数的范围小于需要填的数，那么无解 
                        flag=false;
                        break;
                    }
                }
                if(!flag) break;
                //填了一个数，不确定的位置少一个，更新lst 
                lst[a]=lst[lst[a]-1];
            }
        }
        if(!flag) cout<<"-1";
        // 根据 maxc 倒推出字典序最小的 c 并输出
        else{
            for(int i=1;i<=n;i++){
                if(i!=1) cout<<' ';
                if(c[i]){
                    cout<<c[i];
                    continue;
                }
                if(maxc[i]>maxc[i-1]) cout<<maxc[i];
                else cout<<1;
            }
        }
        cout<<'\n';
    }
    return 0;
}

T2

Question

给出一棵 $n$ 个节点的树，定义一次遍历为从根节点 $1$ 出发走最短路径到任意节点，每次遍历以前树上会在某个节点生成一个药水，若在此次遍历中经过这个节点就可以拿到药水，否则药水消失。要求最小化遍历次数使得每个节点至少被经过 $1$ 次，并在保证这个的同时使得拿到的药水最多，输出最大的药水数量。

Solution

由于要走最短路径还每次要从根出发，所以显然每次走到叶子节点最优，最小遍历次数即为叶子的个数。
因此，对于编号大于叶子结点个数的那些药水我们是取不到的，是无效的。下面讨论的药水都是有效药水。

由于每次遍历时树上有且仅有一个药水，而每次遍历都对应一个叶子结点，所以药水和叶子节点是一一对应的关系。
于是我们不难想到建立一个这样的二分图模型：左部点表示叶子结点，右部点表示药水编号，若从根到叶子结点 $x$ 的简单路径上的某一点会在某一时刻出现药水 $y$ ，那么连接 $(x,y)$。然后在这张二分图上跑最大匹配，就得到了正确答案。但是这个做法无论是在时间还是空间上都爆炸（也可能是我太弱了实现问题），所以只能拿到50分。

所以还是得回到这种题的老路子，树形DP。由于叶节点与药水的一一对应，我们只需要考虑子树内的叶子结点是否够分这么多药水即可。
设 $sze_x$ 表示以 $x$ 为根的子树内叶子结点的个数，$f_x$ 表示以 $x$ 为根的子树最多能那多少药水。
若 $x$ 节点无论何时都没有有效药水，则

\[f_x=\sum_{v~\in~{son}} f_v \]

若总共有 $p$ 个有效药水会在不同时间生成在点 $x$ 上，则

\[S=\sum_{v~\in~{son}} f_v\\ f_x=S+\min\left(sze_x-S~,~p\right) \]

$S$ 的实际意义是已经和药水匹配好了的叶子结点数量，因此 $x$ 节点的贡献就是「还未匹配的叶节点数量和 $x$ 节点上药水数」的较小值。

最后 $f_1$ 即为答案。

Code

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int n,a[100010],f[100010],sze[100010];
vector<int> g[100010],p[100010];
int num;
void dfs(int u,int fa){
    int son=0;
    for(auto v:g[u]){
        if(v==fa) continue;
        dfs(v,u);
        sze[u]+=sze[v];
        f[u]+=f[v];
        son++;
    }
    if(son==0) sze[u]=1;
    if(sze[u]>f[u]&&p[u].size()>0) f[u]+=min(int(p[u].size()),sze[u]-f[u]);
    return ;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        int aa,bb;
        cin>>aa>>bb;
        g[aa].push_back(bb);
        g[bb].push_back(aa);
    }
    for(int i=2;i<=n;i++) if(g[i].size()==1) num++;
    for(int i=1;i<=num;i++) p[a[i]].push_back(i);
    dfs(1,0);
    cout<<f[1];
    return 0;
}