USACO 22 DEC Ag 和 Au 组比赛记录

Ag 组

T1

题目描述

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

解法

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

Code

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";
}

T2

题目描述

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

解法

每个数都可以独立考虑。记 $f_i$ 表示在操作前还剩 $i$，则当前操作者必胜还是必败（用 $1$ 和 $0$ 表示）。记集合 $P$ 为素数集和 $\{1\}$ 的并集，有转移 $f_i=1-\prod\limits_{j\in P,j\le i}f_{i-j}$。边界 $f_0=0$。根据 $f$ 值可算出只有一个数的情况。考虑多个数的情况，显然对于多个数由结束最早的那个数的状态决定。对于在这个数必胜的人希望尽可能快的结束，而必败的人希望尽可能拖慢。记 $g_i$ 表示在操作前还剩 $i$，则算上当前还需操作的次数。有转移 $g_i=\begin{cases}\min_{j\in P,j\le i,f_{i-j}=0}\{g_{i-j}\}+1&f_i=1\\ \max_{j\in P,j\le i}\{g_{i-j}\}+1&f_i=0\\ \end{cases}$。边界 $g_0=0$。比较 $g$ 值的大小，由最小的决定状态。记 $v$ 表示值域，朴素做法 $O(v^2+n)$。打表可知 $f_i=[i \bmod 4\ne 0]$。记 $t(x)$ 为小于等于 $x$ 且与 $x$ 模 $4$ 同余的最大的素数或 $1$ 的值。则打表可知 $g_i=\begin{cases}0.5i&i \bmod 2=0\\ g_{i-t(i)}+1& i\bmod 2=1\end{cases}$。线性筛素数可 $O(v+n)$ 计算。

Code

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;}
        }
    }
}

T3

题目描述

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

解法

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

Code

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();
}

Au 组

T1

题目描述

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

解法

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

Code

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;
}

T2

题目描述

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

解法

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

Code

std::set 真的难用。

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";
    }
}

T3

题目描述

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

解法

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

Code

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;
}