2024 USACO計算機競賽真題解析（完整版）

題解分析：

有q對(x,y)的輸入，每對表示前1~x個數右邊第一個比它們大的數必須在下標為y的位置，這句話還有一個隱藏含義就是第x+1到第y-1個數必須比前1~x個數的最大值要小，即第y個數比前y-1個數都要大(代碼中稱為前綴最大值)。

用一個前綴和數組pre_max[i]表示前i個數中的最大值，則a[y]至少為pre_max[y-1]+1。

現在從左往右遍歷a[N]，分類討論每一個a[i]的情況：

1.a[i]==0且位置i是前綴最大值，令a[i]=pre_max[y-1]+1

2.a[i]==0 且不是前綴最大值，根據貪心思路令a[i]=1 （字典序最?。?/span>

3.a[i]不為0，是第x+1到第y-1個數的其中一個，但是比前x個數要大，破壞了前綴最大值的要求，此時需要把之前的某個能改的值提高為a[i]

對全部a[N]修改完畢后，再重新for循環(huán)掃描一遍看看新的a[N]有沒有沖突，有沖突輸出-1

注意事項：這題有T個測試，每個輸出最后不能帶空格

代碼：

//Q x y 的限制等價于是y是前綴最大值，x+1~y-1內的元素不能是前綴最大值
//貪心，對于不是前綴最大值的填1，是前綴最大值的填前綴max再+1
//注意有時候需要反悔，由于當前值是前綴最大值但是題目要求它不能是，只能把之前的值改大
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int a[N],sum[N],f[N],b[N];
int main(){
    int T;
    cin>>T;
    while (T--){
        int n,m,c;
        cin>>n>>m>>c;
        for (int i=1;i<=n;i++) cin>>a[i];
        for (int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            f[y]=1; //f代表是前綴最大值
            sum[x+1]++; sum[y]--; //前綴和看哪些不是前綴最大值
        }
        for (int i=1;i<=n;i++) sum[i]+=sum[i-1];
        int mx=1;
        int pre=0;
        for (int i=1;i<=n;i++){
            if (a[i]==0){
                if (f[i]) a[i]=mx+1; //前綴max
                else a[i]=1; //不是前綴max
                if (sum[i]==0) pre=i; //記錄能修改的位置
            }
            if (sum[i]>0&&a[i]>mx){
                a[pre]=a[i];
            }
            mx=max(mx,a[i]); //最大值
        }
        bool tt=1;
        for (int i=1;i<=n;i++) { //判斷是否合法
          b[i]=max(b[i-1],a[i]);
          if (a[i]>c) tt=0;
          if (b[i-1]<a[i]&&sum[i]>0) tt=0;
          if (b[i-1]>=a[i]&&f[i]) tt=0;
        }
        if (!tt){
            cout<<-1<<endl;
        } else {
            for (int i=1;i<n;i++) cout<<a[i]<<" ";
            cout<<a[n]<<endl;
        }
        for (int i=1;i<=n+10;i++) sum[i]=0,f[i]=0;
    }
    return 0;
}

題解分析：

以房間1為根節(jié)點的樹。每次traversal相當于從根出發(fā)，沿著父子關系一直走，一個traversal的終點一定是一個葉節(jié)點，因此最小的traversal數必定為葉節(jié)點數量，可以用dfs得到，假設這個數量是k。

可以用樹上DP來記錄每個節(jié)點的子樹擁有的葉節(jié)點數量，狀態(tài)轉移方程為dp[fa] += dp[child],則dp[1]就是整棵樹擁有的葉節(jié)點數量

此時來看題目對potion的描述，每次traversal會在一個節(jié)點生成一個potion，下一次traversal前消失，而我們只會有k個(即dp[1]個)traversal。

因此實際上只需要考慮前k個potion。而由于potion是依靠traversal獲取的，因此potion和traversal,也就是葉節(jié)點，是一對一綁定的。

假設我們目前在某個節(jié)點p，從點p出發(fā)獲得的potion數量不會超過點p的子樹擁有的葉節(jié)點數量。我們再用一個樹上DP，potion[p]表示點p的子樹擁有的potion數量，狀態(tài)轉移方程為potion[fa] += potion[child]。統(tǒng)計完畢后再令potion[p] = min(potion[p], dp[p])。

最終potion[1]就是本題答案。

代碼：

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int> G[N];
int a[N],f[N],dp[N];
void dfs(int x,int y){ //dp[x]代表每個點往下葉子個數
    for (auto v:G[x])
      if (v!=y){
            dfs(v,x);
            dp[x]+=dp[v];
      }
    if (!dp[x]) dp[x]=1;
}
void dfs2(int x,int y){//f[x]代表每個點往下葉子個數和到達點個數的min
    int ans=0;
    for (auto v:G[x])
      if (v!=y){
            dfs2(v,x);
            f[x]+=f[v];
      }
    f[x]=min(f[x],dp[x]);
}
int main(){
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);  
    }
    dfs(1,0);
    for (int i=1;i<=dp[1];i++) f[a[i]]++; //只有前葉子個數個是有用的
    dfs2(1,0);
    cout<<f[1]<<endl;
    return 0;
}

題解分析：

抽屜原理+同余性質

題目等價于N個數除以L最多只有3個不同的余數，根據抽屜原理，任意選擇4個不同的數 ，必定至少有兩個數a[i]和a[j]除以L的余數相同(即模L同余)。由同余的基本性質可知abs(a[i]-a[j])必定能被L整除。

因此本題只需要從a[N]中任選4個不同的數，枚舉它們的兩兩差值(一共有 = 6 種)，對這6個數，枚舉它們的所有因子fac，進行檢驗（看看a[1]到a[N]除以fac是不是最多只有3個余數），符合要求則令ans+=fac。

代碼：

//抽屜原理 4個數里一定有一個相同種類的 L一定是a[i]-a[j]的因數
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;
int a[N],f[N],n;
int sum=0;
void check(int x){ //檢驗x是否合法
    vector<int> v;
    for (int i=1;i<=n;i++){
        int t=a[i]%x;
        bool pp=0;
        for (auto p:v){
            if (p==t) pp=1;
        }
        if (!pp) v.push_back(t);
        if (v.size()>3) break;
    }
    if (v.size()<=3) sum+=x;    
}
signed main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    n=unique(a+1,a+n+1)-a-1;
    //排序去重
    if (n<=3){
        //3個數任意答案都合法
        int x=a[1]/4;
        cout<<(x+1)*x/2<<endl;
        return 0;
    }
    int ans=1e10,now=1;
    for (int i=1;i<=n-3;i++) {
        if (a[i+3]-a[i]<ans){
            now=i;
            ans=a[i+3]-a[i];
        }
    }
    //找到最小差值 隨便找其實也是對的
    vector<int> v;
    map<int,bool> M;
    v.push_back(a[now+1]-a[now]);
    v.push_back(a[now+2]-a[now]);
    v.push_back(a[now+3]-a[now]);
    v.push_back(a[now+2]-a[now+1]);
    v.push_back(a[now+3]-a[now+1]);
    v.push_back(a[now+3]-a[now+2]);
    for (auto vv:v){ //標記因數
        if (vv>0){
            for (int j=1;j*j<=vv;j++)
            if (vv%j==0)
            {
                M[j]=1;
                M[vv/j]=1;
            }
        }
    }
    for (auto v:M){
        if (v.first*4<=a[1]){
            check(v.first);
        }
    }
    cout<<sum<<endl;
    return 0;
}