CF1083（div1）

题意：给定有点权，有边权的树，让你选择一条链（也可以是只有一个点），使得点权之和-边权最大。

思路：裸的树形DP，我们用dp[i]表示i的子树里某个点到i这条链的最大值，然后用次大值更新答案即可。

具体的，每个dp[i]初始化=a[i]; 对于i连出去的边-> (i,j)，用它来更新答案,max(ans,dp[i]+dp[j]-len[i,j]）；然后用它更新dp[i],max(dp[i],dp[i]-len[i,j])；

因为要的是最大值，肯定中途是大于等于0的，所以不会有中途油料耗尽的情况。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;
const int maxn=1000010;
int a[maxn],Laxt[maxn],Next[maxn],To[maxn],Len[maxn],cnt;
ll dp[maxn],ans;
void add(int u,int v,int c)
{
    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=c;
}
void dfs(int u,int f)
{
    dp[u]=a[u]; if(a[u]>ans) ans=a[u];
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i]; if(v==f) continue;
        dfs(v,u);
        ans=max(ans,dp[u]+dp[v]-Len[i]);
        dp[u]=max(dp[u],dp[v]-Len[i]+a[u]);
    }
}
int main()
{
    int N,u,v,c;
    scanf("%d",&N);
    rep(i,1,N) scanf("%d",&a[i]);
    rep(i,1,N-1){
        scanf("%d%d%d",&u,&v,&c);
        add(u,v,c); add(v,u,c);
    }
    dfs(1,0);
    printf("%lld
",ans);
    return 0;
}

View Code

B：B. The Fair Nut and Strings

题意：给定长度为N的由'a','b'组成的字符串S，T，满足S<=T，给出数字K，让你在[S,T]中找K个字符串，使得他们的value最大，value是指满足至少是K个字符串之一的前缀的字符串的个数。

思路：把'a'看成0，'b'看成1，那么[S,T]之间的个数num=T-S+1；我们先使K=min(K,num)。

题意转化一下：想象有深度为N的完全二叉树，左儿子是0，右儿子是1，分别把S和T划出来，由根到因子划成一条线，然后在这两条线之间找K条线，答案就是K条线路过的节点个数。显然第i层的贡献=min(K,2^i-边缘)，即除了最前面的线，和最后面的线，由上一层到下一层，节点数我们都可以*2；

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;
const int maxn=500010;
char a[maxn],b[maxn]; int N,K,x[maxn],y[maxn];
bool check()
{
    rep(i,1,N) x[i]=b[i]-a[i];
    for(int i=N;i>=1;i--){
        while(x[i]<0) x[i]+=2,x[i-1]-=1;
    }
    int tK=K;
    for(int i=N;i>=1;i--){
        if(!tK) break;
        y[i]=tK%2; tK/=2;
    }
    for(int i=1;i<=N;i++) {
        if(x[i]>y[i]) return true;
        if(x[i]<y[i]) return false;
    }
    return true;
}
void get()
{
    K=1; for(int i=N;i>=1;i--){
        if(x[i]) K+=(1LL<<(N-i));
    }
}
int main()
{
    int pos=0; ll ans=0; int tmp=1;
    scanf("%d%d",&N,&K);
    scanf("%s%s",a+1,b+1);
    if(!check()) get();
    rep(i,1,N){
         if(a[i]==b[i]) pos=i,ans++;
         else break;
    }
    rep(i,pos+1,N) {
        if(tmp<=K){
            tmp=tmp*2;
            if(a[i]=='b') tmp--;
            if(b[i]=='a') tmp--;
        }
        ans=ans+min(tmp,K);
    }
    printf("%lld
",ans);
    return 0;
}

View Code

E. The Fair Nut and Rectangles

（这个题太亏了，WA6，原因是没有用double！...不然这一次要上150分的....我的橙名啊

题意：给出N个左下角是原点的矩形，每个矩形有自己的val，保证矩形之间没有包含关系，让你选择一些矩形，使得他们的面积并-val之和最大。

思路：我们先给矩形排序，然后就是DP了，dp[i]=max(dp[j]+(y[i]-y[j])*x[i]-val[i]);

明显的斜率优化，但是注意维护队首时要超过long long，注意使用double！

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;
const int maxn=1000010;
struct in{
    ll x,y,val;
    bool friend operator <(in w,in v){
        return w.x<v.x;
    }
}s[maxn];
ll ans,dp[maxn],head,top,q[maxn];
ll DY(ll i)
{
    return dp[i];
}
ll getans(ll i,ll j){
    return dp[j]+(s[i].y-s[j].y)*s[i].x-s[i].val;
}
int main()
{
    int N; scanf("%d",&N);
    rep(i,1,N) scanf("%lld%lld%lld",&s[i].x,&s[i].y,&s[i].val);
    sort(s+1,s+N+1);
    for(ll i=N;i>=1;i--){
        while(head<top&&getans(i,q[head])<=getans(i,q[head+1])) head++;
        dp[i]=getans(i,q[head]); ans=max(ans,dp[i]);
        while(top>0&&1.0*(DY(i)-DY(q[top]))*(s[i].y-s[q[top-1]].y)>1.0*(DY(i)-DY(q[top-1]))*(s[i].y-s[q[top]].y)) top--;
        q[++top]=i;
    }
    printf("%lld
",max(ans,0LL));
    return 0;
}

View Code

（过了AB，涨了75分...E要是过了的话...

哭，菜死了