Codeforces Round #541 (Div. 2)D&E

总结

ABC都还好，F题很水，STLlist的splice方法+并查集就足够了

D Gourmet choice

个人觉得这其实就是拓扑排序的特殊情况，但是看了rank1的代码，惊呆了，竟然还可以这样，先介绍码量比较大的，用拓扑，然后介绍rank1的暴力代码

一般方法(类似拓扑排序)

1. 先并查集，然后将点进行映射
2. A>B 则在连一条A->B的有向边,现在只有大于和小于的关系,是有向无环图，就可以直接暴力确定每一个点的最小值, A>B 则在连一条A->B的有向边
   复杂度O(N)

const int maxn = 2000+10;

int F[maxn]
int Find(int x){
    return x == F[x]?x:F[x]= Find(F[x]);
}

void end(){
    puts("No");
    exit(0);
}

char ar[maxn][maxn];// 存关系
int ans[maxn],cnt,vis[maxn],X[maxn];
bool G[maxn][maxn]; // A>B 则在连一条A->B的有向边
int dfs(int u){
    vis[u] = -1;
    ans[u] = 1;
    for(int i = 0;i < cnt; ++i){
        if(G[u][i])
            {
                if(vis[i] == -1)  end();
                if(!vis[i]) dfs(i);
                ans[u] = max(ans[u],ans[i]+1);
            }
    }
    vis[u] = 1;
    return ans[u];
}
int main(void)
{
    int n,m;
    cin>>n>>m;
    for(int i = 1;i <= n+m; ++i)
        F[i] = i;
    for(int i = 1;i <= n; ++i){
        cin>>(ar[i]+1);
        for(int j = 1;j <= m; ++j)
            if(ar[i][j] == '=')
            {
                int xx = Find(i);
                int yy = Find(j+n);
                if(xx == yy)
                    continue;
                F[xx] = yy;
            }
    }
    for(int i = 1;i <= n+m; ++i)
            if(i == F[i]) X[i] = cnt++;
   
    for(int i = 1;i <= n; ++i){
        for(int j = 1;j <= m; ++j){
            int x = X[Find(i)];
            int y = X[Find(j+n)];
            if(ar[i][j] == '=') continue;
            if(ar[i][j] == '>')
                G[x][y] = true;
            else
                G[y][x] = true;
        }
    }
    for(int i = 0;i < cnt; ++i){
        if(!vis[i])
            dfs(i);
    }
    puts("Yes");
    for(int i = 1;i <= n; ++i)
        printf("%d ",ans[X[Find(i)]]);
    cout<<endl;
    for(int i = n+1;i <= m+n;++i)
        printf("%d ",ans[X[Find(i)]]);
   return 0;
}

暴力搜索dp

这种思路就是不断用节点去更新比他大的节点值，用有权图表示A和B的关系，如果A== B 这在A-B连接一条边权为0的边，如果A<B 则连一条A->B 的边，这个时候更新A的时候就要更新B，如果更新A，就更新所有比A大的所有点，复杂度O(N^2)
参考代码

E - String Multiplication

s1s2 = s2+s1[0]+s2+s1[1]+…s2
如果s2 是一个由单个字符c组成的字符串，那么如果在s1 中有连续x个c,那么s1s2 之后会出现一个长度为c*s2+c+s2 长度且全为c的子串
如果s2 不是由单个字符组成，那么 s2+s1[0] + s2 必然不可能是全由一个字符组成，所以我们只需要统计s2的左和右就行了

const int maxn = 1e5+10;
int f[maxn][30];
inline void chmax(int &a,int b){
    a<b?a=b:1;
}
inline int idx(char c){
    return c -'a';
}
int main(void)
{
    int n;
    cin>>n;
    string s;
    int ans = 0;
    rep(i,1,n+1){
        cin>>s;
        int l = s.length();
        int r[30] = {},x[30] = {};
        rep(j,0,l){
            int c = idx(s[j]);
            if(j&&s[j] ==s[j-1]) x[c]++;
            else x[c] = 1;
            chmax(r[c],x[c]);
        }
        rep(j,0,26){
            f[i][j] = r[j];
            int t1 = 0,t2 = l-1;
            while(t1 < l&&s[t1] == j+'a') t1++;
            while(t2 >= 0&&s[t2] == j+'a') t2--;
            if(t1 == l)
                chmax(f[i][j],f[i-1][j]*l+l+f[i-1][j]);// 如果s是由单个字符组成的
            else if(f[i-1][j])
                chmax(f[i][j],t1+l-t2);//如果s不是由单个字符组成的
            if(i == n)
                chmax(ans,f[i][j]);// 只在最后一次更新ans
        }
    }
    cout<<ans<<endl;

   return 0;
}