Newnode

特派员业界良心

亚瑟王：

期望dp。。。$f[i][j]$表示第j轮到第i个的概率。。。dp一下就好。。。

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
 
const int N=233;
 
typedef double DB;
 
DB Ans,f[N][N],p[N],pw[N][N];
 
int n,t,d[N],r;
 
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&r);
        memset(f,0,sizeof f);
        Ans=0;
        f[0][r]=1;
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%d",p+i,d+i);
            pw[i][0]=1;
            for(int j=1;j<=r;j++)
                pw[i][j]=pw[i][j-1]*(1-p[i]);
            for(int j=r;j>=r-i&&j>=0;j--)
            {
                f[i][j]+=f[i-1][j]*pw[i][j];
                if(j+1)
                {
                    DB t=f[i-1][j+1]*(1-pw[i][j+1]);
                    f[i][j]+=t;
                    Ans+=d[i]*t;
                }
            }
        }
        printf("%.10lf\n",Ans);
    }
    return 0;
}

接水果：

特派员送温暖来辣。。。。。$O(n^{2}log n)$都能过。。。$smg$。。。

标算么。。整体二分，判断时一个盘子能接到的水果两端对应的dfs序其实是至多2个矩形。。。分情况讨论下，扫描线+树状数组还是很可写的。。。$O(nlog^{2}n)$跑的很快bzoj目前$rank1$(当然加了读入优化的黑科技辣)

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
 
namespace INPUT
{
    const int L=1<<15;
    char buf[L],*S,*T,ch;
     
    char Gc()
    {
        if(S==T)
        {
            T=(S=buf)+fread(buf,1,L,stdin);
            if(S==T)
                return EOF;
        }
        return *S++;
    }
     
    void get(int& x)
    {
        for(ch=Gc();ch<'0'||ch>'9';ch=Gc());
        x=ch^'0';
        for(ch=Gc();ch>='0'&&ch<='9';ch=Gc())
            x=x*10+(ch^'0');
    }
}
#define get INPUT::get
 
const int N=40005;
 
int n,p,q,e[N*2],next[N*2],G[N],dfn[N],end[N],S[N],Ans[N],dep[N],tot,Index,F[N][20],Num[N];
 
int Ancestor(int u,int k)
{
    for(int i=0;k;i++)
        if(k&(1<<i))
            u=F[u][i],
            k^=1<<i;
    return u;
}
 
struct Squ
{
    int x,y1,y2,flag,id;
     
    Squ(int _x=0,int _y1=0,int _y2=0,int _flag=0,int _id=0):x(_x),y1(_y1),y2(_y2),flag(_flag),id(_id){}
     
    friend bool operator<(const Squ& a,const Squ& b)
    {
        return a.x<b.x||(a.x==b.x&&a.flag>b.flag);
    }
}ALL[N][4],As[N*6];
 
struct Node
{
    int u,v,id,c;
     
    friend bool operator<(const Node& a,const Node& b)
    {
        return a.c<b.c;
    }
     
    void input(int i=0)
    {
        get(u);get(v);get(c);
        id=i;
        if(dfn[u]>dfn[v])
            swap(u,v);
    }
     
    void Make()
    {
        tot++;
        if(dfn[u]<=dfn[v]&&end[v]<=end[u])
        {
            int k=Ancestor(v,dep[v]-dep[u]-1);
            if(dfn[k]>1)
                ALL[tot][id++]=Squ(1,dfn[v],end[v],1,0),
                ALL[tot][id++]=Squ(dfn[k]-1,dfn[v],end[v],-1,0);
            if(end[k]<n)
                ALL[tot][id++]=Squ(dfn[v],end[k]+1,n,1,0),
                ALL[tot][id++]=Squ(end[v],end[k]+1,n,-1,0);
        }
        else
            ALL[tot][id++]=Squ(dfn[u],dfn[v],end[v],1,0),
            ALL[tot][id++]=Squ(end[u],dfn[v],end[v],-1,0);
    }
}pz[N],sg[N],_sg[N];
 
void adde(int u,int v)
{
    e[++tot]=v;next[tot]=G[u];G[u]=tot;
}
 
void dfs(int u,int p)
{
    dfn[u]=++Index;
    dep[u]=dep[p]+1;
    F[u][0]=p;
    for(int i=0;F[F[u][i]][i];i++)
        F[u][i+1]=F[F[u][i]][i];
    for(int i=G[u];i;i=next[i])
        if(e[i]!=p)
            dfs(e[i],u);
    end[u]=Index;
}
 
void add(int x,int k)
{
    for(;x<=n;x+=x&-x)
        S[x]+=k;
}
 
int sum(int x)
{
    int k=0;
    for(;x;x-=x&-x)
        k+=S[x];
    return k;
}
 
void solve(int l,int r,int ql,int qr)
{
    if(l==r)
    {
        for(int i=ql;i<=qr;i++)
            Ans[sg[i].id]=pz[l].c;
        return;
    }
    int Mid=l+r>>1,x1=ql,x2=qr;
    tot=0;
    for(int i=l;i<=Mid;i++)
        for(int k=0;k<pz[i].id;k++)
            As[++tot]=ALL[i][k];
    for(int i=ql;i<=qr;i++)
        As[++tot]=Squ(dfn[sg[i].u],dfn[sg[i].v],dfn[sg[i].v],0,i);
    sort(As+1,As+tot+1);
    for(int i=1;i<=tot;i++)
        if(As[i].flag)
            add(As[i].y1,As[i].flag),add(As[i].y2+1,-As[i].flag);
        else
            Num[As[i].id]=sum(As[i].y1);
    for(int i=1;i<=tot;i++)
        if(As[i].flag)
            add(As[i].y1,-As[i].flag),add(As[i].y2+1,As[i].flag);
    for(int i=ql;i<=qr;i++)
        if(Num[i]>=sg[i].c)
            _sg[x1++]=sg[i];
        else
            sg[i].c-=Num[i],
            _sg[x2--]=sg[i];
    for(int i=ql;i<=qr;i++)
        sg[i]=_sg[i];
    solve(l,Mid,ql,x1-1);
    solve(Mid+1,r,x1,qr);
}
 
int main()
{
    get(n);get(p);get(q);
    for(int i=1,u,v;i<n;i++)
        get(u),get(v),
        adde(u,v),adde(v,u);
    dfs(1,0);
    tot=0;
    for(int i=1;i<=p;i++)
        pz[i].input();
    for(int i=1;i<=q;i++)
        sg[i].input(i);
    sort(pz+1,pz+p+1);
    for(int i=1;i<=p;i++)
        pz[i].Make();
    solve(1,p,1,q);
    for(int i=1;i<=q;i++)
        printf("%d\n",Ans[i]);
    return 0;
}

菜肴制作：

贪心，倒过来考虑，让i必须后于j取，然后搞个堆topsort一下就行，每次取能取的最大编号的辣个。。。

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
 
const int N=100005;
 
priority_queue<int> Q;
 
int d[N],e[N],next[N],tot,G[N],Ans[N],Now,n,m,t;
 
void adde(int u,int v)
{
    e[++tot]=v;next[tot]=G[u];G[u]=tot;
}
 
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(G,0,(n+5)*sizeof(d[1]));
        memset(d,0,(n+5)*sizeof(d[1]));
        tot=Now=0;
        for(int i=1,u,v;i<=m;i++)
            scanf("%d%d",&u,&v),
            adde(v,u),d[u]++;
        for(int i=1;i<=n;i++)
            if(!d[i])
                Q.push(i);
        while(!Q.empty())
        {
            int u=Q.top();
            Q.pop();
            Ans[++Now]=u;
            for(int i=G[u];i;i=next[i])
            {
                d[e[i]]--;
                if(!d[e[i]])
                    Q.push(e[i]);
            }
        }
        if(Now==n)
            for(int i=n;i;i--)
                printf("%d ",Ans[i]);
        else
            printf("Impossible!");
        puts("");
    }
    return 0;
}

落忆枫音：

如果只是个DAG的话就是所有入度(除了1号)的积，如果有一个环，答案要减去这个环出现的情况之和，显然环上的点选择的入边一定是环上的边，而环之外的任意，就是所有环之外的点的入度的积，也就是所有入度的积/环上点入度的积，记忆化搜索一下就好了。

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
 
typedef long long LL;
 
const int N=300005,Mod=1e9+7;
 
LL f[N],Ans;
 
int n,m,x,y,d[N],e[N],next[N],G[N],tot;
 
inline void adde(int u,int v)
{
    e[++tot]=v;next[tot]=G[u];G[u]=tot;
}
 
LL Pow(LL x,LL y)
{
    LL k=1;
    while(y)
    {
        if(y&1)
            k=k*x%Mod;
        x=x*x%Mod;
        y>>=1;
    }
    return k;
}
 
LL dp(int u)
{
    if(f[u]!=-1)
        return f[u];
    if(u==x)
        return Ans*Pow(d[x],Mod-2)%Mod;
    f[u]=0;
    for(int i=G[u];i;i=next[i])
        f[u]=(f[u]+dp(e[i]))%Mod;
    return f[u]=f[u]*Pow(d[u],Mod-2)%Mod;
}
 
int main()
{
    scanf("%d%d%d%d",&n,&m,&x,&y);
    for(int i=1,x,y;i<=m;i++)
        scanf("%d%d",&x,&y),
        adde(x,y),d[y]++;
    d[y]++;
    Ans=1;
    for(int i=2;i<=n;i++)
        Ans=Ans*d[i]%Mod;
    if(y!=1)
        memset(f,-1,sizeof(f)),
        Ans=(Ans+Mod-dp(y))%Mod;
    cout<<Ans<<endl;
    return 0;
}

开店：

也是陈老师的题。。。特派员大法吼。。。

显然的可持久化动态树分治，用点分治就好，一个分治结构最多有3个子结构，把这个三叉树可持久化就好辣

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
 
typedef long long LL;
 
const int N=300005;
 
struct Lzz
{
    int u,k;
}hsh[N];
 
inline bool operator<(const Lzz& a,const Lzz& b)
{
    return a.k<b.k;
}
 
LL Ans;
 
int n,Q,A,tot,e[N*2],next[N*2],G[N],Len[N*2],sz[N],fa[N][25],po[N][25],vis[N],q[N],pre[N],head,tail,rt[N];
 
bool Can[N];
 
struct Wlp
{
    int sz,son[3],Ssz[3];
    LL All_dis,Sdis[3];
}T[5000000];
 
inline void adde(int u,int v,int l)
{
    e[++tot]=v;next[tot]=G[u];Len[tot]=l;G[u]=tot;
    e[++tot]=u;next[tot]=G[v];Len[tot]=l;G[v]=tot;
}
 
namespace LZZ
{
    int Min[N][22],lg2[N],dis[N],Index,pos[N];
     
    void dfs(int u,int p)
    {
        Min[++Index][0]=dis[u];
        pos[u]=Index;
        for(int i=G[u];i;i=next[i])
            if(p!=e[i])
                dis[e[i]]=dis[u]+Len[i],
                dfs(e[i],u),
                Min[++Index][0]=dis[u];
    }
     
    void main()
    {
        dfs(1,0);
        for(int i=2;i<=Index;i++)
            lg2[i]=lg2[i>>1]+1;
        for(int i=1;(1<<i)<=Index;i++)
            for(int j=1;j+(1<<i)-1<=Index;j++)
                Min[j][i]=min(Min[j][i-1],Min[j+(1<<i-1)][i-1]);
    }
     
    inline int dist(int u,int v)
    {
        int x=pos[u],y=pos[v],l;
        if(x>y)
            swap(x,y);
        l=lg2[y-x+1];
        return dis[u]+dis[v]-2*min(Min[x][l],Min[y-(1<<l)+1][l]);
    }
}
 
inline int bfs(int u)
{
    q[head=tail=1]=u;
    pre[u]=0;
    while(head<=tail)
    {
        int u=q[head++];
        Can[u]=sz[u]=1;
        for(int i=G[u];i;i=next[i])
            if(!vis[e[i]]&&e[i]!=pre[u])
                q[++tail]=e[i],
                pre[e[i]]=u;
    }
    for(int i=tail;i>=1;i--)
    {
        int u=q[i];
        sz[pre[u]]+=sz[u];
        if(sz[u]*2>tail)
            Can[pre[u]]=0;
        if(Can[u]&&sz[u]*2>=tail)
            return u;
    }
}
 
inline void OrzLzz(int u,int p,int num)
{
    u=bfs(u);
    vis[u]=1;
    int i=1;
    if(p)
    {
        for(;fa[p][i]!=-1;i++)
            fa[u][i]=fa[p][i],
            po[u][i]=po[p][i];
        fa[u][i]=num;
        po[u][i]=p;
        i++;
    }
    fa[u][i]=-1;
    po[u][i]=u;
    num=0;
    for(int i=G[u];i;i=next[i])
        if(!vis[e[i]])
            OrzLzz(e[i],u,num++);
}
 
inline void Change(int &x,int u,int k)
{
    int y=x,t=fa[u][k],d=LZZ::dist(u,po[u][k]);
    x=++tot;
    T[x]=T[y];
    T[x].sz++;
    T[x].All_dis+=d;
    if(t!=-1)
        T[x].Sdis[t]+=d,
        T[x].Ssz[t]++,
        Change(T[x].son[t],u,k+1);
}
 
inline LL Ask(int x,int u,int k)
{
    if(!x)
        return 0;
    int t=fa[u][k],d=LZZ::dist(u,po[u][k]);
    return t!=-1?(d*(LL)(T[x].sz-T[x].Ssz[t])+T[x].All_dis-T[x].Sdis[t]+Ask(T[x].son[t],u,k+1)):T[x].All_dis;
}
 
inline int get(int time)
{
    int l=1,r=n+1,Mid,pos=0;
    while(l<=r)
        if(hsh[Mid=l+r>>1].k<=time)
            pos=Mid,l=Mid+1;
        else
            r=Mid-1;
    return pos;
}
 
void Get(int& x)
{
    static char ch;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    x=ch^48;
    for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())
        x=x*10+(ch^48);
}
 
int main()
{
    Get(n);Get(Q);Get(A);
    for(int i=1;i<=n;i++)
        Get(hsh[i].k),
        hsh[i].u=i;
    for(int i=1,a,b,c;i<n;i++)
        Get(a),Get(b),Get(c),
        adde(a,b,c);
    LZZ::main();
    OrzLzz(1,0,0);
    tot=0;
    sort(hsh+1,hsh+n+1);
    hsh[n+1].k=A;
    for(int i=1;i<=n;i++)
        rt[i]=rt[i-1],
        Change(rt[i],hsh[i].u,1);
    while(Q--)
    {
        int u,a,b,l,r;
        Get(u);Get(a);Get(b);
        l=min((a+Ans)%A,(b+Ans)%A);
        r=max((a+Ans)%A,(b+Ans)%A);
        int rl=get(l-1),rr=get(r);
        Ans=Ask(rt[rr],u,1)-Ask(rt[rl],u,1);
        printf("%lld\n",Ans);
    }
    return 0;
}

实验比较：

首先把相同的缩点，如果$x<y$就连边$<x,y>$，由于题目中的限制，可以保证这是棵树(要增加一个新点使得它比其他点都小，这样可以把森林变成树)。

然后是树形dp，$f[i][j]$表示以$x$为根的子树有$y$种不同取值的时候的答案。

$考虑合并子树yjc,cjy。如果yjc有i个值，cjy有j个值，合并成k个值的方案数为$$f[yjc][i]*f[cjy][j]*\binom{k}{i}\binom{i}{i+j-k}$,类似背包搞一搞就好了。。。注意特判无解情况

#include<algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
 
typedef long long LL;
 
const int Mod=1000000007,N=105;
 
LL f[N][N],C[N*2][N*2];
 
int n,m,U[N],V[N],FLAG[N],fa[N],sz[N],d[N],e[10*N],next[10*N],G[N],tot,vis[N],Tag;
 
void adde(int u,int v)
{
    e[++tot]=v;
    next[tot]=G[u];
    G[u]=tot;
    d[v]++;
}
 
int getfa(int t)
{
    return t==fa[t]?t:fa[t]=getfa(fa[t]);
}
 
void Calc()
{
    C[0][0]=1;
    for(int i=1;i<=200;i++)
        for(int j=0;j<=i;j++)
            C[i][j]=j?(C[i-1][j]+C[i-1][j-1])%Mod:1;
}
 
void Union(LL F[],LL f2[],int n,int m)
{
    static LL f1[N]={};
    for(int i=1;i<=n;i++)
        f1[i]=F[i],F[i]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=max(i,j);k<=i+j;k++)
                F[k]=(F[k]+f1[i]*f2[j]%Mod*C[k][i]%Mod*C[i][i+j-k]%Mod)%Mod;
}
 
void Tree_Dp(int u)
{
    if(G[u])
    {
        Tree_Dp(e[G[u]]);
        sz[u]=sz[e[G[u]]];
        for(int i=1;i<=sz[u];i++)
            f[u][i]=f[e[G[u]]][i];
        for(int i=next[G[u]];i;i=next[i])
            Tree_Dp(e[i]),
            Union(f[u],f[e[i]],sz[u],sz[e[i]]),
            sz[u]+=sz[e[i]];
        sz[u]++;
        for(int i=sz[u];i;i--)
            f[u][i]=f[u][i-1];
    }
    else
        f[u][sz[u]=1]=1;
}
 
void check(int u)
{
    vis[u]=Tag;
    for(int i=G[u];i;i=next[i])
        if(!vis[e[i]])
            check(e[i]);
        else if(vis[e[i]]==Tag)
            cout<<0,
            exit(0);
}
 
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        char c[10];
        scanf("%d%s%d",U+i,c,V+i);
        if(c[0]=='<')
            FLAG[i]=1;
        else
            fa[getfa(U[i])]=getfa(V[i]);
    }
    for(int i=1;i<=m;i++)
        if(FLAG[i])
            adde(getfa(U[i]),getfa(V[i]));
    for(int i=1;i<=n;i++)
        if(getfa(i)==i&&!vis[i])
            Tag++,check(i);
    for(int i=1;i<=n;i++)
        if(d[i]==0&&getfa(i)==i)
            adde(n+1,i);
    Calc();
    Tree_Dp(n+1);
    LL Ans=0;
    for(int i=1;i<=sz[n+1];i++)
        Ans=(Ans+f[n+1][i])%Mod;
    cout<<Ans<<endl;
    return 0;
}