CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!)

E. Tenzing and Triangle

题意

在网格图 $0\leq x,y,x+y< k$ 范围内有一些格点，每个点有点权。每次可以以 $x+y=k$ 为斜边，圈定一个等腰直角三角形，消除范围内的点的点权，代价为 $A$ 乘直角边长。也可以以某点点权为代价，消除该点。 问消除所有点的最小代价。

题解

我们用斜边表示选择的三角形，它们一定是不相交的。记 $f(l,r)$ 表示三角形 $l,r$ 覆盖的点权和减去 $A\times (r-l)$。那么，我们的任务是选择一些区间 $(l_i,r_i)$ 来最大化 $\sum f(l_i,r_i)$。

令 $dp_i$ 表示区间 $[1,i]$ 时 $\sum f(l_i,r_i)$ 的最大值。考虑转移：

• $i$ 没有被覆盖，$dp_i \leftarrow dp_{i-1}$
• $i$ 被 $[j+1,i]$ 覆盖，$dp_i \leftarrow dp_j +f(j+1,i)$

我们维护 $g_j=dp_j+f(j+1,i)$。从 $i-1$ 向 $i$ 转移时，$g$ 作如下修改：

• $g_0,g_1,\cdots,g_{i-1}$ 减去 $A$
• 对每个点 $(x,k-i)$，令 $g_0,g_1,...g_{x}$ 加上该点点权

用线段树维护。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int tr[4*maxn],tag[4*maxn],f[maxn];
vector<pair<int,int>> p[maxn];
void pushdown(int p)
{
    tr[p*2]+=tag[p],tr[p*2+1]+=tag[p];
    tag[p*2]+=tag[p],tag[p*2+1]+=tag[p];
    tag[p]=0;   
}
void update(int ul,int ur,int k,int l,int r,int p)
{
	if(ul<=l&&ur>=r)
    {
        tr[p]+=k,tag[p]+=k;
        return;
    }
    int m=l+((r-l)>>1);
    if(tag[p]&&l!=r) pushdown(p);
    if(ul<=m) update(ul,ur,k,l,m,p*2);
    if(ur>m) update(ul,ur,k,m+1,r,p*2+1);
    tr[p]=max(tr[p*2],tr[p*2+1]);
}
int query(int ql,int qr,int l,int r,int p)
{
    if(ql<=l&&qr>=r) return tr[p];
    int m=l+((r-l)>>1);
    if(tag[p]) pushdown(p);
    int sum=-0x80000000;
	if(ql<=m) sum=max(sum,query(ql,qr,l,m,p*2));
	if(qr>m) sum=max(sum,query(ql,qr,m+1,r,p*2+1));
	return sum;    
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k,A;cin>>n>>k>>A;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        int x,y,c;cin>>x>>y>>c;
        p[k-y].push_back({x,c});
        sum+=c;
    }
    for(int i=1;i<=k;i++)
    {
        update(0,i-1,-A,0,k,1);
        for(auto j:p[i])
        {
            int x=j.first,c=j.second;
            update(0,x,c,0,k,1);
        }
        f[i]=max(f[i-1],query(0,i-1,0,k,1));
        update(i,i,f[i],0,k,1);
    }
    cout<<sum-query(0,k,0,k,1)<<'\n';
    return 0;
}

F. Tenzing and Tree

题意

给定一棵树，点有黑白两种颜色。每条边的权值被定义为边两侧连通块黑点数量之差的绝对值。对于黑点数量为 $0\sim n$ ，要求最大化所有边权值之和。

题解

钦定 $root$ 为黑点的重心。那么权值之和为

$$\sum_{i\neq root} k-2\times size_i=(n-1)\times k-2\times \sum_{i\neq root}size_i$$

而每个点会对其所有祖先的子树大小作出贡献，所以贪心地令所有黑点深度尽可能小。

但如何保证令黑点深度尽可能小后原先钦定的根是黑点的重心呢？事实上，我们可以枚举所有点为根。对于它不是重心的情况，答案一定更差，所以不会影响最终结果。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=5005;
int n,cnt,dfn[maxn],dis[maxn],ans[maxn];
vector<int> g[maxn];
void bfs(int u)
{
    cnt=0;
    memset(dis,-1,sizeof(dis));
    queue<int> q;
    q.push(u),dis[u]=0,dfn[++cnt]=u;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(auto v:g[u])
        {
            if(dis[v]==-1)
            {
                q.push(v);
                dfn[++cnt]=v;
                dis[v]=dis[u]+1;             
            }
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        sum+=dis[dfn[i]];
        ans[i]=max(ans[i],(n-1)*i-sum*2);
    }

}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    for(int i=1;i<=n;i++) bfs(i);
    for(int i=0;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
    return 0;
}