20181027

今天我又双叒叕打炸了，膜拜一下rk1 jarden巨佬滴博客
T1：【from new_dtoj 2503: HZ(666666) loves meat（meat）】
题目描述
HZ(666666)终于打开了密码箱，发现里面只是一堆风干的肉条，于是他打算喂狗。
HZ(666666)养了n条狗，有m根肉条，他想把肉条一根不留地分给狗，并使得每条狗至少有一条肉条可吃。狗总是很贪心，它们不希望看到有其他的狗有更多的肉条，否则就会不开心。一条狗的不开心程度可以表示为他的贪心程度和拥有比它更多肉条的狗的数量的乘积。现在HZ(666666)想知道一种分配方式使得狗们的不开心程度的和最小。
题解
szm神犇说这是extend integer division，快d她
首先我们知道，贪婪值越大，饼干会越多，所以我们先从大到小排序
令$f[i][j]$表示前i个人，分j个饼干，的最小不开心总和
若第i条狗的肉条>1，等价分配j−i个肉条给前i条狗，相对顺序不变，怨气总和不变
若第i个孩子只有一个饼干，那么枚举之前的多少孩子也获得一个饼干
所以可以得到dp式子

1. $f[i][j]=f[i][j-i]$
2. f[i][j]=f[k][j−(i−k)]+∑p=k+1ia[p]f[i][j]=f[k][j-(i-k)]+\sum_{p=k+1}^ia[p]f[i][j]=f[k][j−(i−k)]+∑p=k+1i​a[p]

输出方案的话，记录路径即可
效率O(n2m)O(n^2m)O(n2m)

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,s[55],f[55][5005],a[55];
struct O{int g,d;}p[55],r[55][5005],h,l;
bool C(O x,O y){return x.g>y.g;}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=0;i<=n;i++) for (int j=0;j<=m;j++) f[i][j]=1e9;
    f[0][0]=0;for (int i=1;i<=n;i++) scanf("%d",&p[i].g),p[i].d=i;
    sort(p+1,p+n+1,C);for (int i=1;i<=n;i++) s[i]=s[i-1]+p[i].g;
    for (int i=1;i<=n;i++)
        for (int j=i;j<=m;j++){
            f[i][j]=f[i][j-i];r[i][j]=(O){i,j-i};
            for (int k=0;k<i;k++){
                int t=f[k][j-i+k]+k*(s[i]-s[k]);
                if (t<f[i][j]) f[i][j]=t,r[i][j]=(O){k,j-i+k};
            }
        }
    printf("%d\n",f[n][m]);h=(O){n,m};
    while(h.g && h.d){
        l=r[h.g][h.d];
        if (l.g==h.g) for (int i=1;i<=l.g;i++) a[p[i].d]++;
        else for (int i=l.g+1;i<=h.g;i++) a[p[i].d]++;
        h=l;
    }
    for (int i=1;i<=n;i++) printf("%d%c",a[i],i<n?' ':'\n');
    return 0;
}

T2：【from new_dtoj 停不下来的团长奥尔加（rideon）】
题目描述
暂无
题解
考场想到了状态，但是转移式子推错了，然后炸了boom
我写的是设f[i]表示第二次经过这个点需要的步数
那么首先我们要从i-1走过来，所以先是f[i-1]+1
然后我们发现他跳回p[i]，然后因为这是一个类似前缀和的东西，所以我们应该加上一个f[i-1]-f[p[i]-1]
最后还要走一步，所以还要+1
所以f[i]=f[i-1]*2+f[p[i]-1]+2
注意特判p[i]=i的情况，即f[i]=2
效率$O(n)$

#include <cstdio>
const int N=1e6+5,P=1e9+7;
int n,p[N],f[N];
int main(){
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&p[i]);
    for (int i=1;i<=n;i++) f[i]=(2ll*f[i-1]+2-f[p[i]-1]+P)%P;
    return printf("%d\n",f[n]),0;
}

T3：【from new_dtoj 3996: Lesson5！（johnny）】
题目描述
暂无
题解
Johnny是我的英文名然鹅考场上对这题一点想法也没有
jarden：睡梦中想到的，G啊
楼上神犇写的博客，可神了
因为是DAG，所以我们可以跑两遍拓扑，求出从每个点出去和到每个点的最长路径$f[]$，$g[]$
然后我们先把$g[]$放到一棵权值线段树，然后每次按照拓扑序拿出一个x，把$g[x]$和$g[x]+f[y]+1$（y指向x，边权为1）取出来
这个时候我们可以发现这个操作相当于x被删除了，所以我们求出线段树里面的最大下标，如果这个值比ans小即为答案
（也可以用别的喜欢的数据结构，例如multiset或者堆）
效率$O(nlogn)$

#include <cstdio>
#include <cstring>
#include <string>
#define _(d) while(d(isdigit(c=getchar())))
#define Ls k<<1
#define Rs Ls|1
using namespace std;
inline int R(){int x;char c;_(!);x=(c^48);_()x=(x<<3)+(x<<1)+(c^48);return x;}
const int N=1e5+5,M=5e5+5;
int T,n,m,in[N],ot[N],f[N],g[N],q[N],c,h,ans,id,s[N*4],ax[N*4];
struct O{
    int t,head[N],V[M],nex[M];
    inline void add(int u,int v){
        V[++t]=v;nex[t]=head[u];head[u]=t;
    }
}e1,e2;
inline void update(int k,int l,int r,int x,int v){
    if (l==r){
        s[k]+=v;
        if (s[k]>0) ax[k]=l;
        else ax[k]=-1,s[k]=0;
        return;
    }
    int mid=l+r>>1;
    if (mid>=x) update(Ls,l,mid,x,v);
    else update(Rs,mid+1,r,x,v);
    ax[k]=max(ax[Ls],ax[Rs]);
}
int main(){
    for (T=R();T--;){
        n=R();m=R();e1.t=e2.t=0;ans=1e9;
        memset(s,0,sizeof s);memset(ax,0,sizeof ax);
        for (int i=1;i<=n;i++) e1.head[i]=e2.head[i]=in[i]=ot[i]=g[i]=f[i]=0;
        for (int x,y,i=1;i<=m;i++)
            x=R(),y=R(),e1.add(x,y),e2.add(y,x),in[y]++,ot[x]++;
        c=0;h=1;for (int i=1;i<=n;i++) if (!ot[i]) q[++c]=i;
        while(h<=c){
            for (int i=e2.head[q[h]];i;i=e2.nex[i]){
                if (g[e2.V[i]]<g[q[h]]+1) g[e2.V[i]]=g[q[h]]+1;
                ot[e2.V[i]]--;if (!ot[e2.V[i]]) q[++c]=e2.V[i];
            }
            h++;
        }
        c=0;h=1;for (int i=1;i<=n;i++) if (!in[i]) q[++c]=i;
        while(h<=c){
            for (int i=e1.head[q[h]];i;i=e1.nex[i]){
                if (f[e1.V[i]]<f[q[h]]+1) f[e1.V[i]]=f[q[h]]+1;
                in[e1.V[i]]--;if (!in[e1.V[i]]) q[++c]=e1.V[i];
            }
            h++;
        }
        for (int i=1;i<=n;i++) update(1,0,n,g[i],1);
        for (int i=1;i<=n;i++){
            update(1,0,n,g[q[i]],-1);
            for (int j=e2.head[q[i]];j;j=e2.nex[j]) update(1,0,n,g[q[i]]+1+f[e2.V[j]],-1);
            if (ans>ax[1] || ans==ax[1] && id>q[i]) ans=ax[1],id=q[i];
            for (int j=e1.head[q[i]];j;j=e1.nex[j]) update(1,0,n,f[q[i]]+1+g[e1.V[j]],1);
            update(1,0,n,f[q[i]],1);
        }
        printf("%d %d\n",id,ans);
    }
    return 0;
}