Codeforces 876E National Property

题意：n个字符串，m个字符，有大写小写，大写小于小写，输入的字符串都是小写，可以把一个字符全部改成大写，使者n个字符串满足字典序是升序的，问能否达到，如果可以需要改哪几个字符，不需要任意解即可无需最小

题解：只对相邻的两个字符串进行考虑，找到第一个不相同的位置，如果s[i][j]<s[i+1][j]，如果把s[i+1][j]改了，那s[i][j]也一定要改；如果s[i][j]>s[i+1][j]，则s[i][j]一定大写， s[i+1][j]一定小写

这就是一个2-SAT问题，而且很裸，可以参考点击打开链接

转载点击打开链接

代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#define N 200005
using namespace std;
typedef long long ll;
vector<int>a[N],ans,v[N];
int len[N],b[N];
int d[N],low[N],sk[N],top=0,scc[N],sccnum=0,in[N],time=0;
void dfs(int p)
{
    d[p]=low[p]=time++;
    sk[++top]=p;
    in[p]++;
    for(int i=0;i<v[p].size();i++){
        int to=v[p][i];
        if(!d[to]){
            dfs(to);
            low[p]=min(low[p],low[to]);
        }
        else if(in[to])low[p]=min(low[p],d[to]);
    }
    if(d[p]==low[p]){
        sccnum++;
        while(1){
            int x=sk[top--];
            scc[x]=sccnum;
            in[x]--;
            if(x==p)break;
        }
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d",&len[i]);
        for(int j=0;j<len[i];j++){
            int x;
            scanf("%d",&x);
            a[i].push_back(x);
        }
    }
    int f=1;
    for(int i=0;i<n-1;i++){
        int j=0;
        while(j<len[i]&&j<len[i+1]&&a[i][j]==a[i+1][j])j++;
        if(j==len[i])continue;
        if(j==len[i+1]){
            f=0;
            break;
        }
        int x=a[i][j]*2,y=a[i+1][j]*2;
        if(x>y){
            v[x].push_back(x+1);
            v[y+1].push_back(y);
        }
        else {
            v[y+1].push_back(x+1);
            v[x].push_back(y);
        }
    }
    for(int i=2;i<=m*2+1;i++)
        if(!d[i])dfs(i);
    for(int i=2;i<=m*2+1;i++){
        if(scc[i]==scc[i^1]){
            f=0;
            break;
        }
        b[i>>1]=scc[i]<scc[i^1]?i:i+1;
    }
    if(f){
        printf("Yes\n");
        for(int i=1;i<=m;i++)
            if(b[i]==i*2+1)ans.push_back(i);
        printf("%d\n",ans.size());
        for(int i=0;i<ans.size();i++)
            printf("%d ",ans[i]);
        printf("\n");
    }
    else printf("No\n");
    return 0;
}