牛客网暑期ACM多校训练营（第二场

B discount
对于每个i和f[i]，如果将其视为一条边f[i]->i,那么n个点那条边，那么它是多个基环树(一棵树加一条边则形成基环树)。这里我们需要断环为链。
考虑其中一颗基环树，如果我们将它的环中的一条边删掉的话，这里就变成了树，从而想到树形dp，状态也很容易想到dp[u][way] 代表u结点及其孩子的总的最小费用，且u按照way方式购买的，way=0,1,2分别表示，免费，第一种优惠和第二种优惠。设该树的根为root，指向root的结点为node，我们这样dp后，难以表示root和node之间的影响。所以我们再加一维，表示根节点选的方式。
如何转移呢，当way为1或2时，它的子节点可以随便选。而way=0时，它的子节点必须至少有一个结点选了2。
我们在断链的时候，可以添加一个虚点代表root，即将node指向root的边变成node指向n+1这个点来替代root，那么在进行dp，u=n+1时，它的方式必须和根一致，否则返回inf。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const long long inf=0x3f3f3f3f3f3f3f;
vector<int>G[maxn];
int pre[maxn];
int find(int a)
{
    return a==pre[a]?a:pre[a]=find(pre[a]);
}
vector<int>V;
int fa;
int p[maxn],d[maxn];
long long dp[maxn][4][4];
int n;
long long MIN[maxn];
long long dfs(int u,int way,int first)
{
    long long &ret=dp[u][way][first];
    if(ret!=-1)return ret;
    if(u==n+1)
    {
        if(way==first)return ret=0;
        return ret=inf;
    }
    long long cost=0;
    if(way==1)
        cost=p[u]-d[u];
    else if(way==2)
        cost=p[u];
    long long res=0;
    for(int i=0;i<G[u].size();i++)
    {
        long long mn=inf;
        for(int j=0;j<3;j++)
            mn=min(mn,dfs(G[u][i],j,first));
        MIN[G[u][i]]=mn;
        res+=mn;
    }
    if(way==0)
    {
        long long ans=inf;
        for(int i=0;i<G[u].size();i++)
            ans=min(ans,res-MIN[G[u][i]]+dp[G[u][i]][2][first]);
        res=ans;
    }
    return ret=res+cost;
}

int main()
{
    //cout<<inf<<endl;
    memset(dp,-1,sizeof(dp));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&p[i]),pre[i]=i;
    for(int i=1;i<=n;i++)scanf("%d",&d[i]);
    int u;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&u);
        G[u].push_back(i);
        int fu=find(u),fi=find(i);
        if(fu==fi)
            V.push_back(u);
        else
            pre[fi]=fu;
    }
    long long ans=0;
    for(int i=0;i<V.size();i++)
    {
        u=V[i];
        int v=find(u);
        for(int j=0;j<G[u].size();j++)
        {
            if(G[u][j]==v)
            {
                G[u][j]=n+1;
                break;
            }
        }
        //fa=u;
        long long mn=inf;
        for(int j=0;j<3;j++)
            mn=min(mn,dfs(v,j,j));
        //cout<<mn<<endl;
        ans+=mn;
    }
    printf("%lld\n",ans);
    return 0;
}

C message
做了那么多计算几何，这题还是没做出来，唉。。自己一开始想复杂了，觉得是对线段进行某种操作来减少一些冗余操作，但是想不出来。。
实际上我们首先联立方程组，解得x=−d−bc−a$x=-\frac{d-b}{c-a}$,那么原问题就转换成求在n个点中找到一个与(c,d)的最小斜率。
我们可以把点的x乘-1，那么就是求最大斜率了。
设询问的点为p,显然我们可以维护一个凸包Poly，那么当选择凸包中的下标为a这个点，我们求向量Poly[a]Poly[a+1]−→−−−−−−−−−−−−$\overrightarrow{Poly[a]Poly[a+1]}$ 和向量Poly[a]p−→−−−−$\overrightarrow{Poly[a]p}$ 的叉积时，我们会发现使斜率最大之后的点叉积值都会大于0，之前的点叉积值都会小于0.所以这里可以使用二分。

#include<bits/stdc++.h>
using namespace std;

const int maxn=5e4+5;
const double eps=1e-7;
int sgn(double x)
{
    if(fabs(x)<eps)return 0;
    if(x>0)return 1;
    return -1;
}
struct Point
{
    double x,y;
    int idx;
    Point(double x,double y,int idx=0):x(x),y(y),idx(idx){}
    Point(){}

    Point operator-(const Point &b)const
    {
        return Point(x-b.x,y-b.y);
    }
    double operator^(const Point &b)const
    {
        return x*b.y-y*b.x;
    }

}P[maxn*2];
double ans[maxn];
int n,m;

bool cmp(Point a,Point b)
{
    if(sgn(a.x-b.x)!=0)return sgn(a.x-b.x)<0;
    return sgn(a.y-b.y)<0;
}
Point Poly[maxn];

bool check(int num,int idx)
{
    if(((Poly[num+1]-Poly[num])^(P[idx]-Poly[num]))<=0)return 1;
    return 0;
}

int solve3(int tot,int idx)
{
    int l=1,r=tot-1;
    int ans=-1;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(check(mid,idx))
        {
            ans=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    if(ans==-1)ans=tot;
    return ans;

}

double getk(int x,int idx)
{
    return (Poly[x].y-P[idx].y)/(Poly[x].x-P[idx].x);
}

void solve2()
{
    int tot=0;
    for(int i=1;i<=n+m;i++)
    {
        if(P[i].idx)
        {
            if(tot==0)continue;
            int getx=solve3(tot,i);
            //if(getx==-1)continue;
            double tmp=getk(getx,i);
            if(sgn(ans[P[i].idx]-tmp)<0)
                ans[P[i].idx]=tmp;
        }
        else
        {
            //if(tot<=1){Poly[++tot]=P[i];continue;}
            while(tot-1>=1&&((P[i]-Poly[tot])^(Poly[tot]-Poly[tot-1]))>0)tot--;
            Poly[++tot]=P[i];
        }
    }
}

void solve()
{
    sort(P+1,P+1+n+m,cmp);
    solve2();
    reverse(P+1,P+1+n+m);
    solve2();
}

int main()
{
    scanf("%d",&n);
    double x,y;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf %lf",&x,&y);
        P[i]=Point(x,y);
    }

    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lf %lf",&x,&y);
        P[i+n]=Point(x,y,i);
    }
    for(int i=1;i<=n+m;i++)
        P[i].x=P[i].x*-1;
    solve();
    for(int i=1;i<=m;i++)
    {
        if(sgn(ans[i])<=0)puts("No cross");
        else printf("%.7f\n",ans[i]);
    }
    return 0;
}

D money
这题写的时候有点智障，没注意到它的范围，结果搞了好久才过了。。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn=1e5+10;
int n,num,A[maxn]; LL ans;
void solve()
{
    scanf("%d",&n); ans=num=0; int now=-1;
    for(int i=1;i<=n;++i)scanf("%d",&A[i]);
    for(int i=1;i<n;++i)
    {
        if(now!=-1 && A[i+1]<A[i])ans+=A[i]-now,now=-1,num++;
        if(now==-1 && A[i+1]>A[i])now=A[i],num++;
    }
    if(now!=-1)ans+=A[n]-now,num++;
    printf("%lld %d\n",ans,num);
}
int main()
{
    int T; scanf("%d",&T);
    for(int i=1;i<=T;++i)solve();
    return 0;
}

G transform
计算某个区间放到一个地方去需要的价值实际上只要维护两个前缀和就行了，关键是要把区间定下来。
所以我们第一步可以2分答案，然后枚举左端点，利用前缀和可以计算出右端点。
第二步则需要算出需要将这一段运到哪里最划算，也就是mid。
第三步这一段实际上总的个数可能比我们需要的多，假设该区间为[L,R],那么我们首先计算[L+1,R-1]这一段到mid的值，少的部分我们以X[L]和X[R]到X[mid]谁比较近来作为优先级来计算。
第四步看用的钱有没有超过T，没超过就return 1(这一步博主的代码不太一样，但道理差不多)，否则继续往下走。
要完成这四步可能要预先要计算一些公式，就留给读者啦。

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
struct node
{
    int x,y;
    node(){}
    node(int x,int y):x(x),y(y){}
}P[maxn];
int n;
long long T;
long long sum[maxn];
long long themax;
long long sum2[maxn];
long long Cost(int L,int R,int mid)
{
    if(L>R)return 0;
    long long Right=2LL*(sum2[R]-sum2[mid-1])-2LL*(sum[R]-sum[mid-1])*P[mid].x;
    long long Left=2LL*(sum[mid-1]-sum[L-1])*P[mid].x-2LL*(sum2[mid-1]-sum2[L-1]);
    return Left+Right;

}

long long buy(int L,int R,int mid,long long have)
{
    int first=L,second=R;
    if(P[mid].x-P[L].x>P[R].x-P[mid].x)
        swap(first,second);
    long long res=0;
    if(have>=2LL*abs(P[mid].x-P[first].x)*P[first].y)
    {
        have-=2LL*abs(P[mid].x-P[first].x)*P[first].y;
        res=P[first].y;
        res+=have/(2LL*abs(P[mid].x-P[second].x));
        return res;
    }
    return have/(2LL*abs(P[mid].x-P[first].x));
}

long long f(int mid,int L,int R)
{
    return 2LL*P[mid].x*(2LL*sum[mid-1]-sum[L-1]-sum[R])+2LL*(sum2[R]-sum2[L-1]-2LL*sum2[mid-1]);
}

bool check(long long num)
{
    int mid=1;
    int idx=1;
    for(int i=1;i<=n;i++)
    {
        while(idx<=n&&sum[idx]-sum[i-1]<num)idx++;
        if(idx>n)break;
        if(mid<i)mid=i;
        while(mid+1<=idx&&f(mid+1,i,idx)<f(mid,i,idx))mid++;
        long long cost=Cost(i+1,idx-1,mid);
        if(cost>T)continue;
        long long have=T-cost;

        long long maxleft=sum[idx]-sum[i-1]-num;
        long long canbuy=buy(i,idx,mid,have);
        if(P[i].y+P[idx].y-canbuy<=maxleft)return 1;
    }
    return 0;
}
void solve()
{
    long long l=themax,r=6e9;
    long long ans;
    while(l<=r)
    {
        long long mid=(l+r)/2;
        if(check(mid))
        {
            ans=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    printf("%lld\n",ans);
}

int main()
{

    scanf("%d %lld",&n,&T);
    for(int i=1;i<=n;i++)
        scanf("%d",&P[i].x);
    for(int i=1;i<=n;i++)
        scanf("%d",&P[i].y),sum[i]=sum[i-1]+P[i].y,themax=max(themax,1LL*P[i].y),sum2[i]=sum2[i-1]+(1LL*P[i].x*P[i].y);
    solve();
}

H travel
依然是树形dp。
设dp[u][j][k]为当前u结点下面有j条链，有k条链与u相连。
那么j最大为4，因为两条与u相连的实际上是一条。k显然最大为2。
递推式子很显然，但需要注意方向。在dfs完一个子节点v时，我们需要更新u的dp值，虽然是由j小的来推j大的，但我们需要保证在递推时不能重复计算v的情况。所以j递推的顺序为从大到小。

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e5+5;
const long long inf=0x3f3f3f3f3f3f;
long long dp[maxn][5][3];
int a[maxn];
vector<int>G[maxn];
void dfs(int u,int pre)
{
    dp[u][1][1]=a[u];
    dp[u][0][0]=0;
    for(int v:G[u])if(v!=pre)
    {
        dfs(v,u);
        for(int j=4;j>=0;j--)
        {
            for(int k=j-1;k>=0;k--)
            {
                dp[u][j][2]=max(dp[u][j][2],dp[v][j-k][1]+dp[u][k][1]);
                dp[u][j][2]=max(dp[u][j][2],dp[u][k][2]+max(dp[v][j-k][0],dp[v][j-k][1]));
                dp[u][j][2]=max(dp[u][j][2],dp[u][k][2]+dp[v][j-k+1][2]);
                dp[u][j][1]=max(dp[u][j][1],dp[v][j-k][1]+dp[u][k][0]+a[u]);
                dp[u][j][1]=max(dp[u][j][1],dp[u][k][1]+max(dp[v][j-k][0],dp[v][j-k][1]));
                dp[u][j][1]=max(dp[u][j][1],dp[u][k][1]+dp[v][j-k+1][2]);
                dp[u][j][0]=max(dp[u][j][0],dp[u][k][0]+max(dp[v][j-k][0],dp[v][j-k][1]));
                dp[u][j][0]=max(dp[u][j][0],dp[u][k][0]+dp[v][j-k+1][2]);
            }
        }
    }
}
int main()
{
    //cout<<inf<<endl;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=4;j++)
        for(int k=0;k<3;k++)dp[i][j][k]=-inf;
    int u,v;
    for(int i=1;i<n;i++)
    {
        scanf("%d %d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    printf("%lld\n",max({dp[1][3][0],dp[1][3][1],dp[1][4][2]}));
}

大家注意代码，在递推的过程中实际上有很多不符合实际情况的式子，实际上由于初始值赋为了-inf，那么在求max的过程中他们是不会对正确状态产生影响的。
我觉得这样挺巧妙的，以前写代码感觉有种洁癖，总想保证每步都写对，没有冗余步骤。虽然这种写法虽然让我感觉不舒服，但是还是有借鉴意义的。
J farm
对于一个点来说，它死了以为着它至少被不同于他的类型的农药操作过。所以我们一开始可以维护区间被操作的次数，对于某种颜色的结点同时计算，删掉与该颜色相同的操作，那么一个结点的值大于0，就说明它被其他颜色的操作了。
这里要用到的方法就是矩阵的区间修改和单点询问了，二维树状数组就可以办到。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
const int maxn=1e6+5;
#define lowbit(x) x&-x
vector<int>bit[maxn];
int n,m,T;
inline void add(int x,int y,int z)
{
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=m;j+=lowbit(j))
        bit[i][j]+=z;
}
inline void update(int x1,int y1,int x2,int y2,int z)
{
    add(x1,y1,z);add(x2+1,y2+1,z);
    add(x1,y2+1,-z);add(x2+1,y1,-z);
}
inline int query(int x,int y)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i))
        for(int j=y;j;j-=lowbit(j))
        res+=bit[i][j];
    return res;
}
vector<pii>P[maxn];
struct node
{
    int x1,y1,x2,y2;
    node(int _x1,int _y1,int _x2,int _y2):x1(_x1),y1(_y1),x2(_x2),y2(_y2){}
    node(){}
};
vector<node>V[maxn];
int main()
{

    scanf("%d %d %d",&n,&m,&T);
    for(int i=1;i<=n;i++)bit[i].resize(m+1);
    int tp;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
    {
        scanf("%d",&tp);
        P[tp].push_back({i,j});
    }
    int x1,y1,x2,y2,k;
    for(int i=1;i<=T;i++)
    {
        scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&k);
        V[k].push_back(node(x1,y1,x2,y2));
        update(x1,y1,x2,y2,1);
    }
    int ans=0;
    for(int i=1;i<=n*m;i++)if(P[i].size())
    {
        for(int j=0;j<V[i].size();j++)
        {
            node tmp=V[i][j];
            update(tmp.x1,tmp.y1,tmp.x2,tmp.y2,-1);
        }
        for(int j=0;j<P[i].size();j++)
        {
            if(query(P[i][j].first,P[i][j].second)>0)ans++;
        }
        for(int j=0;j<V[i].size();j++)
        {
            node tmp=V[i][j];
            update(tmp.x1,tmp.y1,tmp.x2,tmp.y2,1);
        }
    }
    printf("%d\n",ans);
    return 0;
}

题目终于补完了，好开心！