USACO 2021 Jan 总结

发表于 更新于 分类于 阅读次数： Valine： 本文字数： 3.5k 阅读时长 ≈ 3 分钟

这次是我第一次打 USACO qaq

于是参加了铜组和银组（铜组 AK 提前晋级）。

USACO 2021 Jan

Bronze

铜组的题都很水啦。。

T1

直接模拟。将 Farmer John 听到的字符串扫一遍，如果有相邻的两个字母在牛版字母表中逆序，就重新开一个新的字母歌。

1
2
3
4
5
6
7
8
9
10
11
12
//s 为牛的字母表，t 为 FJ 听到的字符串
rep(i,0,25) {
    to[s[i]-'a']=i;
}
int l=strlen(t+1);
int ans=1,now=-1;
rep(i,1,l) {
    if(to[t[i]-'a']<=now) {
        now=to[t[i]-'a'];
        ++ans;
    } else now=to[t[i]-'a'];
}

T2

先统计奇数和偶数的个数。

由于题目要求一奇一偶交替，于是我们可以先把奇数和偶数中个数最少的那个先用完。

然后只剩下一堆奇数或者一堆偶数了。

如果剩下一堆偶数，那么可以把这堆偶数搓成一团放在下一个。答案 +1+1。

如果剩下一堆奇数，由于题目要保证所有的牛都划分完，所以我们分奇数个数mod  3\mod 3 的三种情况讨论即可。具体见代码：

1
2
3
4
5
6
7
8
int ans=min(ji,ou);
ji-=ans,ou-=ans;
if(ou) printf("%d\n",ans*2+1);
else {
    if(ji%3==0) printf("%d\n",ans*2+(ji/3)*2);
    else if(ji%3==2) printf("%d\n",ans*2+(ji/3)*2+1);
    else printf("%d\n",ans*2+((ji-2)/3)*2+1);
}

T3

考虑乘法原理。

我们把牛从高到低考虑，因为如果先考虑低牛的话，低牛可能会占用高牛的必须位置，但是先考虑高牛就不会影响到低牛的方案数。

然后就是裸的乘法原理了。对于每头牛，将答案乘以这头牛的方案数即可。别忘了乘完之后下一头牛的方案数要 −1-1，因为这头牛占用了下一头牛的一个可能情况（只是可能情况，而不是必须位置）。

1
2
3
4
5
6
7
8
9
sort(a+1,a+n+1);
sort(b+1,b+n+1);
int ans=1,now=0;
per(i,n,1) {
    int id=lower_bound(b+1,b+n+1,a[i])-b;
    id=n-id+1; // 有多少个牛棚塞得下这头牛
    ans*=id-now; // -now 是因为更高的牛一定占用了其中的 now 个牛棚
    ++now; // 下一头牛方案数 -1
}

Silver

这次银组还是比较有含金量的。

T1

我们先模拟一轮，看每头牛分别能到哪里，对每头牛开一个 set。

模拟完一轮之后，我们可以找到这个序列中所有的环。

然后将这些环中的 set 合并即可。

一个节省代码量的小 trick：将两个 set 合并可以这么写：

1
a.insert(b.begin(),b.end()); // 意为将 b 合并进 a

核心代码：

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
void dfs(int u,int k,bool first) {
    if(!first&&u==k) return ;
    vis[u]=1;
    s[k].insert(s[u].begin(),s[u].end());
    dfs(cow[u],k,0);
}
void dfs2(int u,int k,bool first) {
    if(!first&&u==k) return ;
    ans[u]=s[k].size();
    dfs2(cow[u],k,0);
}
int main() {
    scanf("%d%d",&n,&k);
    rep(i,1,n) cow[i]=i,s[i].insert(i);
    rep(i,1,k) {
        int a,b;
        scanf("%d%d",&a,&b);
        swap(cow[a],cow[b]);
        s[cow[b]].insert(b);
        s[cow[a]].insert(a);
    }
    rep(i,1,n) if(!vis[i]) {
        dfs(i,i,1);
        dfs2(i,i,1);
    }
    rep(i,1,n) printf("%d\n",ans[i]);
    return 0;
}

T2

我们可以先 dp 求出前缀的答案和后缀的答案。

具体可以开一个桶，转移的时候分两种情况讨论即可。

然后对一个挖掉的区间 [l,r][l,r]，答案就是 prel−1+sufr+1pre_{l-1}+suf_{r+1}。

详见代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
rep(i,1,n) {
    if(s[i]>s[i-1]) f[i]=f[i-1]+1,vis[s[i]-'A']=1;
    else {
        f[i]=f[i-1]+(!vis[s[i]-'A']);
        per(j,s[i-1]-'A',s[i]-'A'+1) vis[j]=0;
        vis[s[i]-'A']=1;
    }
}
rep(i,0,25) vis[i]=0;
per(i,n,1) {
    if(s[i]>s[i+1]) g[i]=g[i+1]+1,vis[s[i]-'A']=1;
    else {
        g[i]=g[i+1]+(!vis[s[i]-'A']);
        per(j,s[i+1]-'A',s[i]-'A'+1) vis[j]=0;
        vis[s[i]-'A']=1;
    }
}
rep(i,1,q) {
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%d\n",f[l-1]+g[r+1]);
}

T3

只会一半分的 N≤10N\le 10 做法qwq

具体来说就是，我们确定了一行一列之后，其它的格子都可以直接确定。

那么爆搜这一行一列即可。

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
void dfs(int x,int y) {
    int qwq=0;
    if(x==1&&y==n+1) {
        rep(i,2,n) rep(j,2,n) {
            int tmp=now[i-1][j-1]+now[i][j-1]+now[i-1][j];
            if(!tmp||tmp==3) {anss-=qwq;return;}
            else if(tmp==1) anss+=a[i][j],now[i][j]=1,qwq+=a[i][j];
            else now[i][j]=0;
        }
        ans=max(ans,anss);
        anss-=qwq;
        return ;
    }
    if(x==n+1&&y==1) x=1,y=2;
    if(y==1) {
        now[x][y]=1;
        anss+=a[x][y];
        dfs(x+1,y);
        now[x][y]=0;
        anss-=a[x][y];
        dfs(x+1,y);
    } else {
        now[x][y]=1;
        anss+=a[x][y];
        dfs(x,y+1);
        now[x][y]=0;
        anss-=a[x][y];
        dfs(x,y+1);
    }
}

int main() {
    scanf("%d",&n);
    rep(i,1,n) rep(j,1,n) scanf("%d",&a[i][j]);
    dfs(1,1);
    printf("%d\n",ans);
    return 0;
}

总结

Bronze 没啥好说的，轻松 AK。

Silver C 没想出来正解，不过估计能上 Gold 了。