Beavermuncher-0xFF

https://cn.vjudge.net/problem/CodeForces-80E

利用巧妙的树形递归

对于一个非叶子节点u来说，设 $sz[u]$ 是到达1次某个节点能吃掉的最大数量，应该挑出最大的 $sz[v]$ ,（v是u的子节点）。之后如果u节点还有剩余的海狸（说明还能继续吃子树上的），那么对子节点扫一遍，看看是否有剩余的。

对于叶子节点，或是只有1个的海狸节点，不可能继续往下走，直接令它的sz等于1然后返回

坑1：n=1的时候ans=0

坑2：数据范围爆int

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define maxn (100000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("input.txt","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int head[maxn],to[maxn<<1],pre[maxn<<1],tot;
int n,s;
int num[maxn];
ll sz[maxn];
int buf[maxn];
void adde(int u,int v){to[++tot]=v,pre[tot]=head[u],head[u]=tot;}
bool cmp(int a,int b){
    return sz[a]>sz[b];
}
void dfs(int u,int fa)
{
    if(u!=s)num[u]--,sz[u]=1;
    if(num[u]==0)return;
    bool f=1;
    for(int i=head[u];i;i=pre[i])
    {
        int v=to[i];if(v==fa)continue;
        dfs(v,u);f=0;
    }
    if(f){sz[u]=1;return;}
    int pb=0;
    for(int i=head[u];i;i=pre[i])
    {
        int v=to[i];if(v==fa)continue;
        buf[pb++]=v;//see(u),see(v),NL;
    }
    //see(sz[u]),NL;
    sort(buf,buf+pb,cmp);
    for(int i=0;i<pb;i++)
    {
        int v=buf[i];
        if(num[u])sz[u]+=sz[v]+1,num[u]--;
        else break;
        //see(sz[u]),NL;
    }
    for(int i=0;i<pb;i++)
    {
        int v=buf[i];
        if(num[u])
        {
            if(num[v])
                sz[u]+=1LL*min(num[u],num[v])*2,
                num[u]-=min(num[u],num[v]);
        }
        else break;
    }
}
int main()
{
    RD1(n);for(int i=1;i<=n;i++)RD1(num[i]);
    for(int i=1;i<n;i++){int u,v;RD2(u,v);adde(u,v),adde(v,u);}RD1(s);
    if(n==1)printf("0");
    else 
    {
        dfs(s,0);cout<<sz[s];
    }
    return 0;
}

OpenStreetMap

https://cn.vjudge.net/problem/CodeForces-1195E

经典的单调队列问题，先按第一维单调队列，保存在c中，再按第二维单调队列，保存在c2中。

注意，c如果重复使用，千万要主要更新的先后顺序。因为这个debug好久，后来索性开了c2

$c[i][j]$ 表示以i,j为长a宽b的矩形中的最小值

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define maxn (3000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("input.txt","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll mp[maxn][maxn];
ll c[maxn][maxn];
ll c2[maxn][maxn];
ll n,m,a,b,g,x,y,z;
int main()
{
    RDL2(n,m),RDL2(a,b),RDL1(g),RDL3(x,y,z);
    for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)
        mp[i][j]=g,g=(g*x+y)%z;
    for(ll i=1;i<=n;i++)
    {
        deque<ll>Q;
        for(ll j=1;j<=m;j++)
        {
            while(!Q.empty()&&mp[i][Q.back()]>=mp[i][j])Q.pop_back();
            //see(i),see(j),see(mp[i][Q.front()]),NL;
            Q.push_back(j);
            c[i][j]=mp[i][Q.front()];
            while(!Q.empty()&&Q.front()<=j-b+1)Q.pop_front();
        }
    }
//for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)printf("%d ",c[i][j]);printf("\n");}
    ll ans=0;
    for(ll j=1;j<=m;j++)
    {
        deque<ll>Q;
        for(ll i=1;i<=n;i++)
        {
            //see(i),see(j),NL;for(deque<ll>::iterator it=Q.begin();it!=Q.end();it++)see(*it);NL;
            while(!Q.empty()&&c[Q.back()][j]>=c[i][j])    Q.pop_back();
            Q.push_back(i);
            c2[i][j]=c[Q.front()][j];
            if(i>=a&&j>=b)ans+=c2[i][j];
            while(!Q.empty()&&Q.front()<=i-a+1)Q.pop_front();
        }
    }
//for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)printf("%d ",c2[i][j]);printf("\n");}
    cout<<ans;
    return 0;
}

Build String

https://cn.vjudge.net/problem/CodeForces-237E

网络流，建立源点(0)和汇点(n+26+1)，中间第一层是字符串，n个节点（27~26+n），第二层字母，26个节点(1~26)

源点到各字符串的cap是a_i，字符串到字母的cap是每个字母的个数，字母到汇点（目标字符串）的cap是目标字符串每种字母的个数

字符串到字母的有费用，其余为0

代码参考https://blog.csdn.net/qq_29963431/article/details/51264329

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxn (1000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
char buf[maxn];
int c1[30];
int c2[200][30];
int lim[maxn];
int s,t;
int tot,head[maxn],pre[maxn<<4],to[maxn<<4],
cap[maxn<<4],flow[maxn<<4],cost[maxn<<4];
void adde(int u,int v,int cp,int spt)
{
    to[tot]=v,pre[tot]=head[u],head[u]=tot,
    cap[tot]=cp,cost[tot]=spt,flow[tot]=0,
    tot++;
}
int dis[maxn];
bool in[maxn];
int last[maxn];
bool bfs()
{
    INF(dis),CLR(in),NEG(last);
    queue<int>Q;Q.push(s);
    dis[s]=0;
    in[s]=1;
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();in[u]=0;
        for(int i=head[u];~i;i=pre[i])
        {
            int v=to[i];
            int c=cost[i];
            int cp=cap[i];
            int f=flow[i];
            if(dis[u]+c<dis[v]&&f<cp)
            {
                dis[v]=dis[u]+c,
                last[v]=i;
                if(!in[v])
                {
                    in[v]=1;Q.push(v); 
                }
            }
        }
    }
    return last[t]!=-1;
}
void mfmc(int &cst,int &flw)
{
    flw=cst=0;
    while(bfs())
    {
        int Min=inf;
        for(int i=last[t];~i;i=last[to[i^1]])
            Min=min(Min,cap[i]-flow[i]);
        for(int i=last[t];~i;i=last[to[i^1]])
            flow[i]+=Min,
            flow[i^1]-=Min,
            cst+=Min*cost[i];
        flw+=Min;
    }
}
int main()
{
    scanf("%s",buf);
    int n;RD1(n);
    s=0,t=26+n+1;
    NEG(head);
    int sum=strlen(buf);
    for(int i=0;i<sum;i++)c1[buf[i]-'a'+1]++;
    for(int i=1;i<=26;i++)if(c1[i])adde(i,t,c1[i],0),adde(t,i,0,0);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",buf);RD1(lim[i]);
        for(int j=0;buf[j];j++)c2[i][buf[j]-'a'+1]++;
        adde(s,i+26,lim[i],0),adde(i+26,s,0,0);
    }
    for(int i=1;i<=26;i++)
    {
        if(!c1[i])continue;
        for(int j=1;j<=n;j++)
        {
            if(!c2[j][i])continue;
            adde(j+26,i,c2[j][i],j),adde(i,j+26,0,-j);
        }
    }
    int cst,flw;mfmc(cst,flw);
    if(flw!=sum)printf("-1");
    else printf("%d",cst);
    return 0;
}

2019.8.2

Beavermuncher-0xFF

OpenStreetMap

Build String