USACO 2024 JAN Cu and Ag题解

未分类
2.5k 词

闲话

第一次打 USACO ，真是太刺激太好玩了，会弄就多弄点。

Bronze

T1

Question

给定一个 $n$ 个数的序列 $a$，定义一次操作为在序列中选定一个区间，若区间的某个数的个数大于区间长度的一半，那么就可以将这个区间全部变为这个数。问有哪些数可以经过若干次操作后使得整个序列都变成这个数。

Solution

考虑选一个长度不大于 $3$ 的区间，如果里面有至少两个数相同，那么另外一个数必然可以变得相同，于是这样一次次操作的扩张，序列就会变成同一个数。
于是我们就有了策略：如果一个数 $x$ 距离它两格以内还有一个 $x$ ，那么整个序列都能变成 $x$。

Code

代码有点细节，考场上稀里糊涂的调过了。

点击查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
int T,n,a[100010];
bitset<100010> v;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        v&=0;
        for(int i=1;i<=n;i++) cin>>a[i];
        if(n==2){
            if(a[1]==a[2]) cout<<a[1];
            else cout<<-1;
            cout<<"\n";
            continue;
        }
        for(int i=2;i<=n;i++){
            if(a[i-2]==a[i]||a[i-1]==a[i]) v[a[i]]=1;
        }
        if(v.count()==0) cout<<"-1";
        else{
            int i=1;
            while(!v[i]) i++;
            cout<<i;
            i++;
            for(;i<=n;i++) if(v[i]) cout<<' '<<i;
        }
        if(T) cout<<"\n";
    }
    return 0;
}

T2

Question

这真不好描述，自己去看题面吧。

Solution

因为能量不会减少，所以我们直接模拟即可（因为会越走越快），只需要判掉在几个位置循环跳的情况。

Code

点击查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,s,p[100010],a[100010];
unordered_map<int,bool> v[100010];
bool vis[100010];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        cin>>p[i]>>a[i];
    }
    int d=1,dir=1,ans=0;
    while(s>0&&s<=n){
        if(!p[s]) dir*=-1,d+=a[s];
        if(v[s][d*dir]==1) break;
        v[s][d*dir]=1;
        if(p[s]&&(!vis[s])&&d>=a[s]) ans++,vis[s]=1;
        s+=d*dir;
    }
    cout<<ans;
    return 0;
}

T3

Question

给出一个由整数构成的序列，定义一次操作为 「从倒数第 $L$ 位开始到序列末端，加上 / 减去一个以 $1$ 为首项 $L$ 为末项长度为 $L$ 的等差数列」，问最少几次操作可以使得序列全部变成 $0$。

Solution

因为是区间修改，我们考虑给序列差分，这样目标就变成了用最少的操作使差分数组变为 $0$，而在原序列上加上或减去一段等差数列其实就是在差分数组上加上或减去一段 $1$。这就转化为我们熟悉的区间加 $x$ 的差分问题了。具体的，再把差分数组再差分得到数组 $C$，这样 $L$ 操作就转为了在 $C_L\pm1$ 得单点修改问题，使得 $C$ 为 $0$ 最小操作数也显而易见就是 $\sum\limits_{i=1}^n |C_i|$。

Code

点击查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200010],b[200010];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i]-a[i-1];
    int ans=0;
    for(int i=1;i<=n;i++) ans+=abs(b[i]-b[i-1]);
    cout<<ans;
    return 0;
}

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_i$。具体的，先将 $(a_j,h_j)$ 递增排序（优先排 $a_j$）,然后对于限制逐个处理，并调整 $maxc$ 使得其满足要求，否则无解。
得到了满足所有限制的 $maxc$ 以后，容易根据前缀最大值的性质以及字典序最小的要求还原出 $c$ 数组。

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

Code

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

点击查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#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$ 节点无论何时都没有有效药水，则

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

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

最后 $f_1$ 即为答案。

其实这其中就蕴涵着官方题解中的那种贪心思想：对于每个叶子找到是其祖先且与它最近的药水配对，这样得到的答案是最优的。

Code

点击查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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;
}

T3

Question

给定 $n\in [1,10^4]$ 个数 $a_i\in [1,4\cdot 10^9]$，问对于所有满足要求的 $L$ 的和是多少。

  • $4\cdot L<=\min(a_i)$
  • 对于所有的 $a_i\bmod L$，最多只有三个不同的值。

Solution

第一条限制很容易，主要是第二条。

显然去重不会影响答案，所以先去个重。
有个简单的小结论，若 $a_i\equiv a_j\pmod L$ ，那么必然有 $L\mid a_i-a_j$。因此合法的 $L$ 只可能是序列中某一对同余的 $a_i,a_j$ 的差的因数。但是我们并不知道哪些 $a_i,a_j$ 会是同余的呀，那么就只好 $O(n^2)$ 枚举了吗？
我们利用鸽巢原理来优化，合法的 $L$ 只会产生 $3$ 种余数，因此前 $4$ 数个中必定有至少一对是同余的，因此我们只需要在前 $4$ 个中枚举即可保证每一个合法的 $L$ 都会被选到，并且大大优化了时间。
枚举出 $L$ 以后，就可以 $O(n)$ 的判断是否满足限制了。算法复杂度是 $O(6n\sqrt{V})$，$V$ 为 $a$ 的值域，显然卡不满。

建议还是有不懂的人可以去看看 USACO 的官方题解，讲得深入而详细——反正对我有很大帮助。

Code

点击查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,a[10010],minn=1e15,len;
set<int> s;
bool check(int x){
    set<int> ch;
    for(int i=1;i<=len;i++){
        ch.insert(a[i]%x);
        if(ch.size()>3) return false;
    }
    return true;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],minn=min(minn,a[i]);
    sort(a+1,a+1+n);
    len=unique(a+1,a+1+n)-a-1;
    if(len<=3){
        cout<<1ll*(minn/4)*(minn/4+1)/2;
        return 0;
    }
    for(int i=1;i<=4;i++){
        for(int j=i+1;j<=4;j++){
            int num=abs(a[j]-a[i]);
            for(int k=1;k*k<=num;k++){
                if(num%k!=0) continue;
                if(k*4>minn) break;
                if(check(k)) s.insert(k);
                if((num/k)*4<=minn&&check(num/k)) s.insert(num/k);
            }
        }
    }
    int ans=0;
    for(auto i:s) ans+=i;
    cout<<ans;
    return 0;
}