[ICPC 2018 Asia Yokohama Onsite D]Shortest Common Non-Subsequence

Link

Solution

正着DP,f[i][j]表示第一个字符串匹配到i第二个匹配到j的最短长度。DP完之后,考虑构造字典序最小的解。
(|s|+1,|t|+1)状态出发,沿着DP值递减的路径走,把路上经过的所有的点都标记上,表示从这个点有一条合法的最短路径。
求答案的时候,如果填0之后到达的状态是被标记的状态,且DP值增加了1,那么就填0。一个点在一条最短路上不代表这个点随便走都行。

Code

const int XN=4e3+5;

int main() {
//  freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    static char s[XN],t[XN];
    static int snext[XN][2],tnext[XN][2];
    std::cin>>(s+1)>>(t+1);
    int slen=strlen(s+1),tlen=strlen(t+1);
    snext[slen+1][0]=snext[slen+1][1]=slen+1;
    for(int i=slen;i>=0;--i)
        for(int c=0;c<2;++c)
            snext[i][c]=s[i+1]-'0'==c?i+1:snext[i+1][c];
    tnext[tlen+1][0]=tnext[tlen+1][1]=tlen+1;
    for(int i=tlen;i>=0;--i)
        for(int c=0;c<2;++c)
            tnext[i][c]=t[i+1]-'0'==c?i+1:tnext[i+1][c];
    static int f[XN][XN];
    memset(f,31,sizeof(f));
    f[0][0]=0;
    for(int i=0;i<=slen+1;++i)
        for(int j=0;j<=tlen+1;++j)
            if(i!=slen+1 || j!=tlen+1)
                for(int c=0;c<2;++c)
                    Reduce(f[snext[i][c]][tnext[j][c]],f[i][j]+1);  

//  std::cerr<<f[slen+1][tlen+1]<<'\n';

    static bool isValid[XN][XN];
    isValid[slen+1][tlen+1]=1;
    for(int i=slen+1;i>=0;--i)
        for(int j=tlen+1;j>=0;--j)
            if(i!=slen+1 || j!=tlen+1)
                for(int c=0;c<2;++c)
                    if(f[snext[i][c]][tnext[j][c]]==f[i][j]+1)
                        isValid[i][j]|=isValid[snext[i][c]][tnext[j][c]];

    for(int x=0,y=0;x!=slen+1 || y!=tlen+1;) {
        static int cc;
        assert(f[x][y]==cc++);

        for(int c=0;c<2;++c)
            if(isValid[snext[x][c]][tnext[y][c]] && f[snext[x][c]][tnext[y][c]]==f[x][y]+1) {
                std::cout<<c;
                x=snext[x][c];y=tnext[y][c];
                break;
            }
    }
    std::cout<<'\n';
    return 0;
}

[Codeforces 1137C]Museums Tour

Link

这WA的有点难受2333333333333333333333333
一张边权为1的图,从点1处出发,如果走到某个点p经过的路径长度\bmod d的值属于一个特定的集合S_p,那么p点就能对答案做出1的贡献。点可以重复经过,但只能做一次贡献。问所有点的贡献最大和是多少。

Solution

首先把强连通分量缩起来。考虑强连通分量内的点的答案如何计算。
从分量内任意一个点出发BFS,可以得到一个能到达的(p,l\bmod d)二元组集合。为了简单,可以假设到达连通分量内的出发点已经走过的距离,那么对于d种距离,可以得到d个集合。而这d个集合中,(p,l\mod d)二元组的相对关系是不变的,因此一次BFS就可以得到d个集合的元素。
对于这d个集合,求一下每个集合各自有多少个点能产生贡献,然后在后面的DP中,每个集合的所有的点的DP值就是集合中产生贡献的点+集合中二元组的原来DP值的最大值。
求出(p,l\bmod d)的DP值之后,用它去更新后继SCC中的点。最后,在所有二元组的DP值中取max。
注意!由于必须从1开始,所有的合法值都只能从(1,0)二元组来!其他的所有初始值都必须是不合法的极小值!

Code

const int XN=1e5+11;

std::vector<int> G[XN],C[XN],scc[XN],lc[XN];

int low[XN],dfn[XN],stack[XN],dft,cc,belong[XN],top;
bool instack[XN];
void DFS(int u){
    dfn[u]=low[u]=++dft;
    stack[++top]=u;instack[u]=1;
    for(auto v : G[u])
        if(!dfn[v]){
            DFS(v);
            low[u]=std::min(low[u],low[v]);
        }else if(instack[v]){
            low[u]=std::min(low[u],dfn[v]);
        }
    if(dfn[u]==low[u])
        for(++cc;;){
            int x=stack[top--];
            instack[x]=0;
            scc[cc].push_back(x);
            belong[x]=cc;
            if(x==u) break;
        }
}

int d;
std::string status[XN];
auto Level=[&](int cur,int t)->int {
    return ((t-cur)%d+d)%d;
};


std::vector<int> T[XN];
void BFS(int c) {
    static bool ud[XN][55];
    std::queue<std::pair<int,int>> Q;
    Q.push({scc[c].front(),0});
    ud[Q.front().first][0]=1;
    while(!Q.empty()) {
        int pos,t;std::tie(pos,t)=Q.front();
        Q.pop();
        for(auto u : G[pos])
            if(belong[u]==c && !ud[u][(t+1)%d]) {
                ud[u][(t+1)%d]=1;
                Q.push({u,(t+1)%d});
            }
    }
    for(auto u : scc[c]) {
        for(int t=0;t<d;++t)
            if(ud[u][t])
                T[u].push_back(t);
    }
    lc[c].resize(d);
    for(int t=0;t<d;++t) {
        lc[c][t]=0;
        for(auto u : scc[c])
            for(int ut=0;ut<d;++ut)
                if(ud[u][ut] && status[u][(t+ut)%d]=='1') {
                    lc[c][t]++;
                    break;
                }
    }
}

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,m;std::cin>>n>>m>>d;
    for(int i=1;i<=m;++i) {
        int x,y;std::cin>>x>>y;
        G[x].push_back(y);
    }
    for(int i=1;i<=n;++i) {
        std::cin>>status[i];
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            DFS(i);
    for(int i=1;i<=n;++i)
        for(auto u : G[i])
            if(belong[u]!=belong[i])
                C[belong[i]].push_back(belong[u]);
    static int f[XN][55],deg[XN];
    for(int i=1;i<=cc;++i) {
        BFS(i);
        std::sort(C[i].begin(),C[i].end());
        C[i].erase(std::unique(C[i].begin(),C[i].end()),C[i].end());
        for(int u : C[i])
            deg[u]++;
    }
    for(int i=1;i<=n;++i)
        for(int t=0;t<d;++t)
            f[i][t]=-1e9;
    f[1][0]=0;
    std::queue<int> Q;
    for(int i=1;i<=cc;++i)
        if(!deg[i])
            Q.push(i);
    while(!Q.empty()) {
        int pos=Q.front();Q.pop();
        std::vector<int> lf(d,-1e9);//写成0最后没过!
        for(auto u : scc[pos])
            for(int t=0;t<d;++t)
                for(auto ut : T[u])
                    Enlarge(lf[Level(ut,t)],f[u][t]+lc[pos][Level(ut,t)]);
        for(auto u : scc[pos])
            for(int t=0;t<d;++t)
                for(auto ut : T[u])
                    Enlarge(f[u][t],lf[Level(ut,t)]);
        for(auto u : scc[pos])
            for(int t=0;t<d;++t)
                for(auto v : G[u]) {
                    if(belong[v]==belong[u])
                        assert(!Enlarge(f[v][(t+1)%d],f[u][t]));
                    Enlarge(f[v][(t+1)%d],f[u][t]);
                }
        for(auto u : C[pos])
            if(--deg[u]==0)
                Q.push(u);
    }
    for(int i=1;i<=cc;++i)
        assert(deg[i]==0);

    int Ans=0;
    for(int i=1;i<=n;++i)
        for(int t=0;t<d;++t)
            Enlarge(Ans,f[i][t]);
    std::cout<<Ans<<'\n';
    return 0;
}

[ICPC 2018 Nanjing Onsite B]Tournament

Link

Solution

首先需要知道,用一个stadium覆盖n个位置,肯定建在中间的那个上。
普通的DP,f[i][j]表示前i个放了j个stadium,将前i个都覆盖了的最小代价,然后f[i][j]=\min (f[k][j-1]+cost(k+1,i))。这个cost就是用一个stadium覆盖[k+1,i]的最小代价。虽然这样没有保证被不同的stadium覆盖的地点一定是被离它最近的那个覆盖,但是考虑到最小的答案一定是那样的情况,所以这样DP正确性没有问题。
接着就wqs二分+决策单调性。。会了就是模板了。。
各种决策单调性还要好好学一学……

Code

const int XN=3e5+11;

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    static int a[XN];
    static long long sum[XN];
    int n,m;std::cin>>n>>m;
    for(int i=1;i<=n;++i) {
        std::cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }

    auto DP=[&](long long C)->std::pair<long long,int> {
        static std::pair<long long,int> f[XN];
        auto Cost=[&](int l,int r) {//建站覆盖[l,r]
            int mid=(l+r)/2;
            return sum[r]-2*sum[mid-1]+sum[l-1]+(long long)a[mid]*(2*mid-l-r-1);
        };

        auto Calc=[&](int j,int i)->std::pair<long long,int> {
            return std::make_pair(f[j].first+Cost(j+1,i)+C,f[j].second+1);
        };

        auto Boundary=[&](int k1,int k2)->int {//k2 better than k1 if p>=x
            int L=k2+1,R=n+1;
            while(L!=R) {
                int M=(L+R)/2;
                if(M!=n+1 && Calc(k1,M)<=Calc(k2,M))
                    L=M+1;
                else
                    R=M;
            }
            return L;
        };

        static std::pair<int,int> Q[XN];
        static int head,tail;
        Q[(tail=head=0)++]={0,0};
        for(int i=1;i<=n;++i) {
            while(tail-head>=2 && Calc(Q[head].first,i)>=Calc(Q[head+1].first,i))
                head++;
            f[i]=Calc(Q[head].first,i);
            while(tail-head>=2 && (Q[tail-1].second==n+1 || Calc(Q[tail-1].first,Q[tail-1].second)>=Calc(i,Q[tail-1].second)))
                tail--;
            Q[tail]={i,Boundary(Q[tail-1].first,i)};
            tail++;
        }
        return f[n];
    };

    long long L=0,R=sum[n];
    while(L!=R) {
        long long M=(L+R)/2;
        if(DP(M).second<=m)
            R=M;
        else
            L=M+1;
    }

    long long Ans=DP(L).first-L*m;
    std::cout<<Ans<<'\n';
    return 0;
}

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