[Codeforces 908D]New Year and Arbitrary Arrangement

Link

Solution

首先,前导b对于ab子序列的个数不会产生影响,为了简化,强制第一个位置是a。
一个比较好用的想法是,任意一个合法解都以b为结尾,可以在最后一个b前面添加任意个a。
从第二个位置开始填,f[i][j]表示填了i个a,有j个ab子序列的概率。
i + j < n时,转移显然。
否则,就直接将在f[i][j]后面加任意个a和一个b产生的贡献累加到答案里,不再进行转移。因为如果将这部分f[i][j]加上一个a继续转移到f[i+1][j]中,就会与f[i][j]后面加任意个a和一个b重复。
f[i][j]后面加任意个a和一个b产生的贡献如下:

\begin{aligned}
&f[i][j]p_b\sum_{k=0}^{\infty}(i+j+k)p_a^k\\
=&f[i][j]p_b[\frac {i+j}{1-p_a}+\frac {p_a}{(1-p_a)^2}]
\end{aligned}

求出最后的答案还要乘上\sum_{i=0}^{\infty}p_b^i=\frac 1{1-p_b},因为在序列前方加上任意个b对概率是有影响的,因而对期望也有影响。

Code

#include <bits/stdc++.h>

const int P=1e9+7,XN=1e3+11;

int Add(int x,int const &y) {
    return (x+=y)>=P?x-P:x;
}

void AddBy(int &x,int const &y) {
    x=Add(x,y);
}

int Minus(int x,int const &y) {
    return (x-=y)<0?x+P:x;
}

int Mul(long long x,int const &y) {
    return x*y%P;
}

int Pow(long long base,int v) {
    static long long res;
    for(res=1;v;v>>=1,(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

int Inverse(int x) {
    return Pow(x,P-2);
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,a,b;std::cin>>n>>a>>b;
    int pa=Mul(a,Inverse(a+b)),pb=Mul(b,Inverse(a+b));
    static int f[XN][XN];
    f[1][0]=pa;
    int c1=Inverse(Minus(1,pa)),c2=Mul(pa,Mul(c1,c1));
    int Ans=0;
    for(int i=1;i<=n;++i)
        for(int j=0;j<=n;++j) {
            if(i+j<n) {
                AddBy(f[i+1][j],Mul(pa,f[i][j]));
                AddBy(f[i][i+j],Mul(pb,f[i][j]));
            } else
                AddBy(Ans,Mul(Mul(pb,f[i][j]),((long long)(i+j)*c1+c2)%P));
        }
    Ans=Mul(Ans,Inverse(Minus(1,pb)));
    std::cout<<Ans<<'\n';
    return 0;
}

ICPC EC-Final 2018 I Misunderstood … Missing

Link

Solution

小数据爆搜,大数据三个贪心取max
DP的话,需要让2、3操作的贡献能够提前计算。
而2的贡献与后面攻击的下标和有关,3的贡献和后面攻击的次数有关,这样就有了状态。

Code

const int XN=1e2+11;

void Work() {
    static int a[XN],b[XN],c[XN];
    static long long f[2][XN][XN*XN];
    int n;fin>>n;
    for(int i=1;i<=n;++i)
        fin>>a[i]>>b[i]>>c[i];
    memset(f,0,sizeof(f));
    int cur=0;
    for(int i=1,sum=n*(n+1)/2-1;i<=n;sum-=++i,cur^=1)
        for(int j=0;j<=n-i;++j)
            for(int k=0;k<=sum;++k)
                f[cur][j][k]=Max(f[cur^1][j][k]+Max((long long)b[i]*(k-i*j),(long long)c[i]*j),f[cur^1][j+1][k+i]+a[i]);
    fout<<f[cur^1][0][0]<<'\n';
}

int main() {
    int T;fin>>T;
    while(T--)
        Work();
    return 0;
}

[EC-Final 2017H]Mr. Panda and Birthday Song

Link

Solution

两次dp,一次尽量符合要求,一次尽量不符合要求,即一次让连续的元音、辅音尽量长,一次让连续的辅音元音尽量短,判断判断就能转移出来了。

Code

const int XN=1e6+11,INF=0x1f1f1f1f;

int main() {
    int T;fin>>T;
    const char *Ans[]={"LIKE","SURPRISE","DISLIKE"};
    std::set<char> vowels({'a','e','i','o','u'});
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        static char s[XN];
        int x,y;
        fin>>(s+1)>>x>>y;//x vow y non-vow
        int n=strlen(s+1);
        static int f[XN][2];
        int type=0;
        for(int i=1;i<=n;++i) {
            f[i][0]=f[i][1]=-1;
            if(s[i]=='?') {
                if(~f[i-1][0])
                    f[i][1]=1;
                else
                    f[i][1]=f[i-1][1]+1;
                if(~f[i-1][1])
                    f[i][0]=1;
                else
                    f[i][0]=f[i-1][0]+1;
            } else if(vowels.count(s[i])) {
                if(~f[i-1][0])
                    f[i][1]=1;
                else
                    f[i][1]=f[i-1][1]+1;
            } else {
                if(~f[i-1][1])
                    f[i][0]=1;
                else
                    f[i][0]=f[i-1][0]+1;
            }
            if(f[i][0]==y)
                f[i][0]=-1;
            if(f[i][1]==x)
                f[i][1]=-1;
            if(f[i][0]==-1 && f[i][1]==-1) {
                type=2;
                break;
            }
        }
        if(type!=2) {
            for(int i=1;i<=n;++i) {
                f[i][0]=f[i][1]=-1;
                if(s[i]=='?') {
                    if(f[i-1][1]!=-1)
                        f[i][1]=f[i-1][1]+1;
                    else
                        f[i][1]=1;
                    if(f[i-1][0]!=-1)
                        f[i][0]=f[i-1][0]+1;
                    else
                        f[i][0]=1;
                } else if(vowels.count(s[i])) {
                    if(f[i-1][1]!=-1)
                        f[i][1]=f[i-1][1]+1;
                    else
                        f[i][1]=1;
                } else {
                    if(f[i-1][0]!=-1)
                        f[i][0]=f[i-1][0]+1;
                    else
                        f[i][0]=1;
                }
                if(f[i][0]==y || f[i][1]==x) {
                    type=1;
                    break;
                }
            }
        }
        puts(Ans[type]);
    }
    return 0;
}

[CF1088E]Ehab and a component choosing problem

Link

Solution

答案的值等于整棵树的点权最大联通块,可以用一次树形DP求出来。
接下来就求最多有多少个点权和等于所求答案的联通块。
有一个贪心是,凑出顶点深度更深的联通块一定不会比凑出顶点深度更浅的联通块更优。因此第二次DFS的时候如代码所示再DP一遍。

Code

const int XN=3e5+11;

std::vector<int> G[XN];
int a[XN];

long long f[XN],g[XN],res;

void DP(int pos,int fa) {
    f[pos]=a[pos];
    for(int u : G[pos]) if(u!=fa) {
        DP(u,pos);
        f[pos]+=std::max(f[u],0ll);
    }
}

int cnt=0;

void DFS(int pos,int fa) {
    g[pos]=a[pos];
    for(int u : G[pos]) if(u!=fa) {
        DFS(u,pos);
        g[pos]+=std::max(g[u],0ll);
    }
    if(g[pos]==res) {
        cnt++;
        g[pos]=0;
    }
}

int main() {
    int n;fin>>n;
    for(int i=1;i<=n;++i)
        fin>>a[i];
    for(int i=1;i<=n-1;++i) {
        int x,y;fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    DP(1,0);
    res=*std::max_element(f+1,f+1+n);
    DFS(1,0);
    fout<<res*cnt<<' '<<cnt<<'\n';
    return 0;
}

[CF1043E]Make It One

Link

Solution

将找最小值变成求是否可行,而求是否可行的方法又是容斥计数判断是否为0,这波操作666
f[i][j]表示选i个数字\gcdj的方案数目,答案就是最小的i使得f[i][1]\not=0
f[i][j]=\binom {i}{c[j]}-\sum_{k=2}f[i][j*k]c[j]表示所有数字中整除j的个数。

Code

const int XN=3e5+11,P=1e9+7;

int Add(int x,int const &y) {
    return (x+=y)>=P?x-P:x;
}

int Minus(int x,int const &y) {
    return (x-=y)<0?x+P:x;
}

int Mul(long long x,int const &y) {
    return x*y%P;
}

int Pow(long long base,int v) {
    long long res;
    for(res=1;v;(v>>=1),(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

int main() {
    static int f[8][XN],a[XN],fact[XN],ifact[XN],cnt[XN],c[XN];
    int n,m=0;fin>>n;

    fact[0]=1;
    for(int i=1;i<=n;++i)
        fact[i]=Mul(fact[i-1],i);
    ifact[n]=Pow(fact[n],P-2);
    for(int i=n-1;i>=0;--i)
        ifact[i]=Mul(ifact[i+1],i+1);

    auto C=[](int n,int m) { return n>=m?Mul(fact[n],Mul(ifact[n-m],ifact[m])):0; };

    for(int i=1;i<=n;++i) {
        fin>>a[i];
        f[1][a[i]]=1;
        Enlarge(m,a[i]);
        cnt[a[i]]++;
    }
    for(int i=1;i<=m;++i)
        for(int j=1;i*j<=m;++j)
            c[i]+=cnt[i*j];
    for(int i=2;i<=7;++i) {
        for(int j=m;j>=1;--j) {
            f[i][j]=C(c[j],i);//整除j的个数
            for(int k=2;k*j<=m;++k)
                f[i][j]=Minus(f[i][j],f[i][k*j]);
        }
    }
    int Ans=-1;
    for(int i=1;i<=7;++i)
        if(f[i][1]) {
            Ans=i;
            break;
        }
    fout<<Ans<<'\n';
    return 0;
}