USACO 22 DEC Ag 和 Au 组比赛记录

Ag 组

T1

题目描述

一棵树，点有点权，每次操作可以将选择两个相邻的点 u,v，并指定权值 w，让 u 权值减 w，v 权值加 w，求最少操作次数使得所有点的点权均相等，并构造方案。

解法

容易发现，点权和不变，可算出最终每个点应该得到的权值。如果一条边连接的两个连通块一边多余，一边不足，则这个边无论如何都要操作，而如果两边权值都恰好，则不用对这条边进行操作。构造方案随便选择一个点为根 dfs 两遍，第一遍从下往上操作多余的权值，第二遍从上往下补足不够的权值，容易证明正确性。时间复杂度 O(n)。

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
constexpr int N=2e5+5;using ll=long long;
struct edge{int to,nxt;}e[N<<1];
int head[N],cnt=0;
inline void add(int u,int v){e[++cnt]=(edge){v,head[u]};head[u]=cnt;}
ll siz[N],w[N];
inline void dfs1(int u,int fa)
{
    siz[u]=w[u];
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;if(v==fa)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
    }
}
struct op{int u,v;ll w;}a[N];int top=0;
inline void dfs2(int u,int fa)
{
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;if(v==fa)continue;
        dfs2(v,u);
    }
    if(siz[u]>0) a[++top]=(op){u,fa,siz[u]};
}
inline void dfs3(int u,int fa)
{
    if(siz[u]<0) a[++top]=(op){fa,u,-siz[u]};
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;if(v==fa)continue;
        dfs3(v,u);
    }
}
inline void work()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int n;cin>>n;ll s=0;
    for(int i=1;i<=n;i++)cin>>w[i],s+=w[i];
    s/=n;
    for(int i=1;i<=n;i++)w[i]-=s;
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        add(u,v),add(v,u);
    }
    dfs1(1,0);
    dfs2(1,0);
    dfs3(1,0);
    cout<<top<<"\n";
    for(int i=1;i<=top;i++) cout<<a[i].u<<" "<<a[i].v<<" "<<a[i].w<<"\n";
}
CPP

T2

题目描述

两个人博弈，有 个数，，从 开始依次操作，如果到结尾则从开头再来，对于每个数 A 先操作 B 后操作，操作者需选择一个不大于当前操作数的质数或者 ，并把操作数减去选择的数，当一个人操作前这个数就已经为 则这个人输。问胜者是谁？

解法

每个数都可以独立考虑。记 表示在操作前还剩 ，则当前操作者必胜还是必败（用 和 表示）。记集合 为素数集和 的并集，有转移 。边界 。根据 值可算出只有一个数的情况。考虑多个数的情况，显然对于多个数由结束最早的那个数的状态决定。对于在这个数必胜的人希望尽可能快的结束，而必败的人希望尽可能拖慢。记 表示在操作前还剩 ，则算上当前还需操作的次数。有转移 。边界 。比较 值的大小，由最小的决定状态。记 表示值域，朴素做法 。打表可知 。记 为小于等于 且与 模 同余的最大的素数或 的值。则打表可知 。线性筛素数可 计算。

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
constexpr int N=1e5+5,M=5e6+5,R=5e6;
bool vis[M];
int pri[M],tot=0;
inline void init(int n)
{
    pri[1]=1;tot++;
    for(int i=2;i<=n;i++)
    {
        if(vis[i]==false)pri[++tot]=i;
        for(int j=2;j<=tot&&i*pri[j]<=n;j++)
        {
            vis[i*pri[j]]=true;
            if(i%pri[j]==0) break;
        } 
    }
}
int mx[4],g[M];bool f[M];
int a[N];
inline void work()
{
    init(R);
    for(int i=1;i<=R;i++)
    {
        if(!vis[i]) g[i]=1,mx[i&3]=i;
        else if(i&1) g[i]=g[i-mx[i&3]]+1;
        else g[i]=i/2;
        f[i]=(i&3);
    }
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T;cin>>T;
    while(T--)
    {
        int n;cin>>n;int mn=1e9;
        for(int i=1;i<=n;i++) cin>>a[i],mn=min(mn,g[a[i]]/2+1);
        for(int i=1;i<=n;i++)
        {
            int d=g[a[i]]/2+1;
            if(d==mn) {cout<<"Farmer "<<(f[a[i]]?"John":"Nhoj")<<"\n";break;}
        }
    }
}
CPP

T3

题目描述

给定某序列 所有子区间的极差，还原整个序列，保证有解。

解法

首先可以找出最大值和最小值的位置，即极差最大的情况下最短的子区间的两个端点。容易发现，可以指定任意一边为最小值。只需整体乘 即可构造出另一边为最小值的序列。钦定最小值为 。得知最小值位置后它左右两边的值必然大于它，可以知道这些位置的值。考虑往左右两边递推。此处仅介绍向左扩展。记 为区间 的极差。如果 则 与 和 与 的大小关系相同，否则不同，可根据此算出所有位置的值。注意相等的元素可能会干扰计算，需要将相同的元素合并起来。时间复杂度 。

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
constexpr int N=305;
int d[N][N],ans[N],lp[N],rp[N],bel[N],tot=0;
inline void get(int x,int y)
{
    int z=(x+y)>>1;
    int len1=abs(ans[z]-ans[y]),len2=d[lp[min(x,y)]][rp[max(x,y)]],len3=d[lp[min(x,z)]][rp[max(x,z)]];
    if(ans[z]>ans[y])
    {
        if(len2==len1+len3) ans[x]=ans[z]+len3;
        else ans[x]=ans[z]-len3;
    }
    else
    {
        if(len2==len1+len3) ans[x]=ans[z]-len3;
        else ans[x]=ans[z]+len3;
    }
}
int a[N];
inline bool check(int n)
{
    for(int i=1;i<=n;i++)
    {
        int mx=a[i],mn=a[i];
        for(int j=i+1;j<=n;j++) 
        {
            mx=max(a[j],mx),mn=min(a[j],mn);
            if(mx-mn!=d[i][j]) return false;
        }
    }
    return true;
}
inline void work()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int n,mx=0;cin>>n;
    for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)cin>>d[i][j],mx=max(mx,d[i][j]);
    int lenm=1e9,pm=0;
    for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)if(d[i][j]==mx)lenm=min(lenm,j-i+1);
    for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)if(j-i+1==lenm&&d[i][j]==mx)pm=i;
    tot=bel[1]=lp[1]=1;
    for(int i=2;i<=n;i++)if(d[i-1][i]==0) bel[i]=tot;else rp[tot]=i-1,bel[i]=++tot,lp[tot]=i;
    rp[tot]=n;
    pm=bel[pm];ans[pm]=1;
    if(pm!=1) ans[pm-1]=ans[pm]+d[lp[pm-1]][lp[pm]];
    if(pm!=tot) ans[pm+1]=ans[pm]+d[lp[pm]][lp[pm+1]];
    for(int i=pm-2;i>0;i--) get(i,i+2);
    for(int i=pm+2;i<=tot;i++) get(i,i-2);
    int num=0;
    for(int i=1;i<=tot;i++) for(int j=lp[i];j<=rp[i];j++) a[++num]=ans[i];
    for(int i=1;i<=n;i++) cout<<a[i]<<" \n"[i==n];
    cout.flush();
}
CPP

Au 组

T1

题目描述

个物品，可以拿两种货币混合支付。对于物品 ，需要 个货币 A， 个货币 相当于一个货币 A，它的价值为 ，求用 个货币 A 和 个货币 B 能买到商品的最大价值。

解法

以下默认值域与 同阶。首先，有个非常蠢的 的 DP。设 表示考虑前 个物品，使用 个 A 和 个 B 能买到商品的最大价值。转移的时候枚举物品支付的货币 A 的数量即可转移。考虑一个结论：至多有一个商品是混合支付的一定不劣。假如有两个物品同时混合支付，则将 较大的物品的 B 换到 较小的物品上支付则能省下一些 B 货币。结论得证。于是将物品按 排序，做一个前缀对 B 的背包，做一个后缀对 A 的背包，枚举混合支付的物品，根据背包的值算出最值，时间复杂度 。

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
constexpr int N=2005;
int f[N][N],g[N][N];
struct dat{int w,c,x;}a[N];
inline void work()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int n,wc,wx;cin>>n>>wc>>wx;
    for(int i=1;i<=n;i++)cin>>a[i].w>>a[i].c>>a[i].x;
    sort(a+1,a+n+1,[](const dat&x,const dat&y){return x.x<y.x;});
    for(int i=1;i<=n;i++) 
    {
        memcpy(f[i],f[i-1],sizeof(f[i-1]));
        for(int j=wx;j>=a[i].c*a[i].x;j--) f[i][j]=max(f[i-1][j],f[i-1][j-a[i].c*a[i].x]+a[i].w);
    }
    for(int i=n;i>0;i--) 
    {
        memcpy(g[i],g[i+1],sizeof(g[i+1]));
        for(int j=wc;j>=a[i].c;j--) g[i][j]=max(g[i+1][j],g[i+1][j-a[i].c]+a[i].w);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=a[i].c;j++)
        {
            int d1=wc-j,d2=wx-(a[i].c-j)*a[i].x;
            if(d1<0||d2<0) continue;
            ans=max(ans,a[i].w+f[i-1][d2]+g[i+1][d1]);
        }
        ans=max(ans,f[i-1][wx]+g[i+1][wc]);
    }
    cout<<ans<<endl;
}
CPP

T2

题目描述

有 个楼房，第 个的横坐标为 ，纵坐标为 ， 能看见 当且仅当这两点的连线上无其他楼房阻挡，有 个询问，每次会增加一个楼房的高度，问修改后有多少对楼房能互相看见。

解法

以下认为 同阶。容易发现，对于 来说，它向后能看到的楼房斜率单调不降。有非常蠢的 的做法。当然你可以用 P4198 楼房重建的方式做到 ，如果会 Seg Beats 等科技则可做到 。考虑到楼房只会增高。对于每个 维护一个 set 存储以 开始向后能看到的楼房集合。对于 修改时重构 对应的楼房集合，对于 前面每个楼房 ，在 中按照斜率二分，删除会被新的 挡住的楼房，每次最多往 set 中新插入 个元素，故总复杂度为 ，但是奇慢无比。

Code

std::set 真的难用。

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
constexpr int N=2005;constexpr double eps=1e-10;
struct dat{int id;double lp;dat(){};dat(int x,double y):id(x),lp(y){}};
inline bool operator<(const dat&x,const dat&y){return x.lp<y.lp||(x.lp==y.lp&&x.id<y.id);}
set<dat>s[N];
int a[N],n;int ans=0;
inline double calc(int x,int y){return 1.0*(a[y]-a[x])/(y-x);}
inline void build(int x)
{
    ans-=s[x].size();
    s[x].clear();
    double mx=-1e10;
    for(int i=x+1;i<=n;i++)
    {
        double now=calc(x,i);
        if(now>=mx-eps) mx=now,s[x].emplace(i,now);
    }
    ans+=s[x].size();
}
inline void update(int x,int y)
{
    double ns=calc(x,y);
    auto lp=s[x].lower_bound(dat(y,ns));
    if(lp!=s[x].end()&&lp->id<y)return; 
    auto rp=lp;
    while(lp!=s[x].begin())
    {
        lp=prev(lp);
        if(lp->id>=y)ans--;
        else break;
    }
    if(lp->id<y) lp=next(lp);
    s[x].erase(lp,rp);
    s[x].emplace(y,ns);
    ++ans;
}
inline void work()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int q;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)build(i);
    cin>>q;
    while(q--)
    {
        int x,y;cin>>x>>y;a[x]+=y;
        build(x);
        for(int i=1;i<x;i++)update(i,x);
        ans=0;
        for(int i=1;i<=n;i++) ans+=s[i].size();
        cout<<ans<<"\n";
    }
}
CPP

T3

题目描述

一个 个点 条边的无向图，你需要选出一个联通子图，仅保留两个端点都在这个联通子图内的边，你需要最大化你选出的点的个数和所有点度数最小值的乘积。图无重边自环。

解法

枚举最小度数，则仅可能的保留更多的点。将度数不合法的点从原图上删去，然后可能造成原图多出来一些不合法的点，继续删除，直到图合法为止，选点最多的联通块即可。容易发现，最小度数最大为 ，因为图无重边自环，一个联通子图度数至少为 说明至少有 个点。时间复杂度 。考虑一个不那么暴力的做法。我们发现每次删点在上一次枚举的基础上删除即可。使用一个堆维护最小度数。倒着根据删边顺序用并查集维护最大联通块。时间复杂度 。

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
constexpr int N=2e5+5;
struct dat{int u,w;};
bool operator<(const dat&x,const dat&y){return x.w>y.w;};
priority_queue<dat>q;
struct edge{int to,nxt,w;}e[N<<1];
int head[N],cnt=0,deg[N];
inline void add(int u,int v,int w){e[++cnt]=(edge){v,head[u],w};head[u]=cnt;++deg[v];}
bool vis[N];
struct et{int u,v;}a[N];
int pos[N],ord[N];
namespace dsu
{
    int fa[N],siz[N],mx=1;
    inline void init(int n){for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;}
    inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    inline void merge(int x,int y){x=find(x),y=find(y);if(x==y)return;fa[y]=x;siz[x]+=siz[y];mx=max(siz[x],mx);}
}
inline void work()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        add(u,v,i),add(v,u,i);
        a[i]=(et){u,v};
    }
    for(int i=1;i<=n;i++)q.push((dat){i,deg[i]});
    int tot=0;
    for(int i=1;i<=n;i++)
    {
        if(tot==m)pos[i]=m;
        while(tot!=m&&q.top().w<i)
        {
            int u=q.top().u;q.pop();
            if(vis[u])continue;
            vis[u]=true;
            for(int j=head[u];j;j=e[j].nxt)
            {
                int v=e[j].to;
                if(vis[v])continue;
                ord[++tot]=e[j].w;
                deg[v]--;
                q.push((dat){v,deg[v]});
            }
        }
        pos[i]=tot;
    }
    dsu::init(n);int ans=0;
    for(int i=n,j=m;i>0;i--)
    {
        while(j>pos[i])dsu::merge(a[ord[j]].u,a[ord[j]].v),j--;
        if(dsu::mx>=i) ans=max(ans,dsu::mx*i);
    }
    cout<<ans<<endl;
}
CPP
比赛记录
#DP #线段树 #堆 #平衡树 #构造 #贪心 #并查集
USACO 22 DEC Ag 和 Au 组比赛记录
https://www.llingy.top/posts/2860623136/
作者
llingy
发布于
2022年12月28日
许可协议