[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;
}