Codeforces 876E：2-SAT 或者瞎搞-程序员宅基地

题意：给出N个字符串，每个字符用整数来代表，规定一个字符可以有大小写,设小写为1，大写为1‘，并且字典序表示为：1’<2'<3'<4'<1<2<3<4，现在要求你选出若干个字符变成大写（所有串中的这个字符都变成大写），使得N个字符串是按照字典序不降的。无解输出-1

题解：正解是2-SAT。。。。我要讲一个怪算法。。。

首先有一个不完整的思路是：正着扫一遍，要保证第i个字符串<第i+1个字符串，方法是，暴力搞掉最长公共前缀，然后拿到第一个不同的字符，必须让第i个串的那个字符小才行，如果不满足，就让那个字符变成大写的，如果变成大写了还不满足就是No。

但是这样有问题，后面有一些字符变成大写了之后，可能前边的字典序就保证不了了，那么显然另外一个不完整的思路就是：反着再扫一次。

但是这样还是有问题，于是我们发现了，问题其实是这样子：如果某次扫描，把某个字符变成了大写，那么之前的字典序可能会被破坏掉，那么我们至少需要再来一次扫描检查一次。

于是骚的算法来了：正着扫一次+反着扫一次，如果把某个字符变成了大写，就继续疯狂扫，如果没有，就可以书出答案了。

我他妈不知道怎么就AC了。。。

过几天把2-SAT的板子补出来ORZ。。。

Code：

#include<bits/stdc++.h>
using namespace std;
const int maxm = 2e5;
bool big[maxm];
int m,n;
int ch[maxm];
int l[maxm];
int pos[maxm];
int cnt=0;
bool small(int x_,int y_){
	if (big[x_]==big[y_]){
		return x_<=y_;
	}else{
		return big[x_];
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=0;i<n;i++){
		int len;
		scanf("%d",&len);
		l[i]=len;
		pos[i] =cnt;
		for (int j=0;j<len;j++){
			scanf("%d",ch+cnt+j);
		}
		cnt+=len;
	}
	pos[n]=cnt;
	while (true){
		bool flag = false;
		for (int i=0;i<n-1;i++){
		int p1=pos[i];
		int p2 = pos[i+1];
		int l1=l[i];
		int l2 = l[i+1];
		int mm = min(l1,l2);
		int del =0;
		while (del<mm&&ch[p1+del]==ch[p2+del]){
			del++;
		}
//		cout<<i<<" "<<del<<endl;
		if (del==mm&&del==l1)continue;
		if (del==mm&&del==l2){
			cout<<"No"<<endl;
			return 0;
		}
		if (small(ch[p1+del],ch[p2+del])){
			continue;
		}else{
			if (!big[ch[p1+del]])flag = true;
			big[ch[p1+del]] =true;
			if (small(ch[p1+del],ch[p2+del])){
				continue;
			}else{
				cout<<"No"<<endl;
				return 0;
			}
		}
	}
	for (int i=n-1;i>0;i--){
		int p2 = pos[i];
		int p1 = pos[i-1];
		int l2 = l[i];
		int l1 = l[i-1];
		int mm = min(l1,l2);
		int del =0;
		while (del<mm&&ch[p1+del]==ch[p2+del])del++;
//		cout<<"! "<<i<<" "<<del<<endl; 
		if (del==mm&&del==l1)continue;
		if (del==mm&&del==l2){
			cout<<"No"<<endl;
			return 0;
		}
		if (small(ch[p1+del],ch[p2+del])){
			continue;
		}else{
			if (!big[ch[p1+del]])flag = true;
			big[ch[p1+del]] = true;
			if (small(ch[p1+del],ch[p2+del])){
				continue;
			}else{
				cout<<"No"<<endl;
				return 0;
			}
		}
	}
	if (!flag)break;
	}
	printf("Yes\n");
	int cnt =0;
	for (int i=1;i<=m;i++){
		if (big[i])cnt++;
	}
	printf("%d\n",cnt);
	for (int i=1;i<=m;i++){
		if(big[i])printf("%d ",i);
	}
	return 0;
}

/*
5 5
3 1 2 3
4 1 2 4 4
3 1 3 4 
3 1 2 4
3 4 4 4

*/

本文链接：https://blog.csdn.net/calabash_boy/article/details/78255784

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

2017计算机专业方向,北京联合大学：2017年计算机专业新增无人驾驶与机器人技术研究方向...-程序员宅基地

1.2017年学校计划招收多少研究生？其中推免生计划为多少？权力：2017年研究生招生计划尚未下达，预计招收200人，其中推免生计划不超过招生计划总数的50%。2.2017年学校招生政策有什么新变化？是否有新增专业？权力：2017年北京联合大学招生政策没有太大变化，根据市场需求，结合学校李德毅院士的智能车团队建设及新成立的机器人学院需要，进行了招生专业方向的调整，计算机科学与技术专业新增了无人驾驶...

PCM音频文件播放-PC软件推荐+android代码_pcm格式播放软件-程序员宅基地

PCM音频文件播放PC工具推荐Audacity音频处理 PC端可以播放PCM的软件，亲测可用，并且作者很贴心了附上了可下载的FFMPEG库，按照步骤导入即可。但是我发现一个问题，我这边的PCM播放的时候，速率不对，我需要按照0.5X速播放才是正常，其他的一切正常，还能看到波形图。android代码Android pcm文件播放方法(AudioTrack)别的作者的，亲测可用。播放正常。下面是我本地的方法：public static void PlayPCM(String path) { _pcm格式播放软件

pip更新问题_pip update-程序员宅基地

1.常规命令python -m pip install --upgrade pip 2.多次尝试更新失败，用以下命令python -m pip install -U --force-reinstall pip_pip update

【中级】RHEL6.5下部署vsftpd实战全集-程序员宅基地

1.实验需求：1) 使用RPM包安装vsftpd服务2) 实现匿名用户访问，验证仅可以访问和下载，不可以上传3) 实现匿名用户可上传、下载、修改等完全权限（现实环境中这样的需求可能性很小）4) 实现把登陆的用户禁锢在自己的家目录中5) 实现限制某些用户的访问6) 实现虚拟用户的访问7) 实现针对不同...

Android-图片存入系统相册更新显示_android 插入图片更新相册-程序员宅基地

在开发android的过程中，我们避免不了可能会涉及到做一个自定义相册或则会去本地创建一个文件夹来存储我们需要的图片。拿相册来说，比如我们创建一个test的文件夹，拍完一张照片后存储到这个指定的test文件夹里，然后在相册里面显示出来，就像微信的效果一样。拍完即可立即显示。但是，在实际开发过程中我们保存完一张图片后并不能立即更新显示出来这个图片，需要我们重启手机才能在系统相册中显示出来。_android 插入图片更新相册

Springboot整合Dubbo-程序员宅基地

dubbo介绍Dubbo是阿里巴巴公司开源的一个高性能优秀的服务框架，使得应用可通过高性能的 RPC 实现服务的输出和输入功能，可以和 Spring框架无缝集成。RPC（Remote Procedure Call）—远程过程调用，它是一种通过网络从远程计算机程序上请求服务，而不需要了解底层网络技术的协议。RPC协议假定某些传输协议的存在，如TCP或UDP，为通信程序之间携带信息数据。在OSI..._"registryconfig.setclient(\"curator\");"