【Codeforces 782D】Innokenty and a Football League

相关链接

题目传送门:http://codeforces.com/contest/782/problem/D

吐槽

为什么题面这么难懂啊?!
感觉出题人的英文比我好不到哪里去啊?!
差一点写成二分图了,还好室友嘈代码难写的时候多问了一句 _(:з」∠)_

解题报告

我们发现每个人只有两个状态
于是我们撸一发2-SAT就可以A辣!

Code

2-SAT判定有没有解是可以做到$O(m)$的,写个强连通就可以了
不过我这份代码是$O(m^2)$的啊!
为什么不会T?我的$m$是$O(n^2)$的啊

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000;
const int M = 5000009;

int n,que[N],cnt,head[N],to[M],nxt[M],mark[N];
char pat[2][100];
struct Data{
	char p[4];
	inline bool operator < (const Data &B) const {
		for (int i=0;i<3;i++) {
			if (p[i] < B.p[i]) return 1;
			else if (p[i] > B.p[i]) return 0;
		} return 0;
	}
	inline bool operator == (const Data &B) const {
		return !(*this < B) && !(B < *this);
	}
}c1[N],c2[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
}

inline int id(int w, int t) {
	return (w-1)*2 + t + 1;
}

bool DFS(int w) {
    if (mark[w]) return true;
    if (mark[w^1]) return false;
    mark[w] = 1; que[++cnt] = w;
     
    for (int i=head[w];i;i=nxt[i]) 
        if (!DFS(to[i])) return false;
    return true;
}
 
inline bool judge(){
    for (int i=2,lim=id(n,2);i<=lim;i+=2) if (!mark[i] && !mark[i+1]) {
        cnt = 0; if (DFS(i)) continue;
        for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
        cnt = 0; if (!DFS(i+1)) return false; 
    }
    return true;
}

int main() {
	n = read();
	for (int i=1;i<=n;i++) {
		scanf("%s%s",pat[0],pat[1]);
		Data a; a.p[3] = 0; a.p[0] = pat[0][0]; a.p[1] = pat[0][1]; a.p[2] = pat[0][2];
		Data b; b.p[3] = 0; b.p[0] = pat[0][0]; b.p[1] = pat[0][1]; b.p[2] = pat[1][0];
		c1[i] = a; c2[i] = b;
	}
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			if (i == j) continue; 
			if (c1[i] == c1[j]) Add_Edge(id(i, 2), id(j, 2));
			if (c1[i] == c1[j]) Add_Edge(id(i, 1), id(j, 2));
			if (c1[i] == c2[j]) Add_Edge(id(i, 1), id(j, 1));
			if (c2[i] == c1[j]) Add_Edge(id(i, 2), id(j, 2));
			if (c2[i] == c2[j]) Add_Edge(id(i, 2), id(j, 1));
		}
	}
	if (!judge()) puts("NO");
	else {
		puts("YES");
		for (int i=1;i<=n;i++) {
			if (mark[id(i, 1)]) printf("%s\n",c1[i].p);
			else printf("%s\n",c2[i].p);
		}
	} 
	return 0;
}

—————————— UPD 2017.3.27 ——————————
今天才知道输出一组可行解也是可以$O(m)$的
大概就是搞一发Tarjan,然后在拓扑图上按拓扑逆序染色

【算法笔记】2-SAT

好久没有见到这种清新脱俗的算法了!
刘汝佳的白书上面有这个东西,所以基础部分就自行翻阅啦!

唯一想说的是,有一种O(M)判定是否存在解的算法:
直接求一个SCC,然后看那两个点是否在同一个SCC里即可
当然这种算法也可以求出一组可行解,
但貌似刘汝佳的算法时间勉强够用了,所以就不管了吧( •̀ ω •́ )y

【BZOJ 1997】[Hnoi2010] Planar

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1997
数据生成器:http://paste.ubuntu.com/22273507/

这个题目在知道了是2-sat的情况下还是懵逼了好久QAQ
当时就想到这个图:一个正方形加上对角线.jpg(solidwork还没装,不想用word画图QAQ
发现他给的这个圆不能自交,于是每一条线就只有两种可能:
1.圆内
2.圆外
于是处理出相互干涉的线段,然后搞2-sat

最开始这么搞了,血RE
遂看题解,™有一个这个结论:
Theorem 1. If v ≥ 3 then e ≤ 3v − 6;
Theorem 2. If v ≥ 3 and there are no cycles of length 3, then e ≤ 2v − 4.
详细情况:https://en.wikipedia.org/wiki/Planar_graph
于是加特判,遂过

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<map>
using namespace std;

const int MAXN = 20000+9;
const int N = 200000;

int n,m,que[MAXN],L[MAXN],R[MAXN],T,nxt[N],to[N],head[MAXN],mark[MAXN],cnt;
vector<int> G[MAXN];
map<int,int> ins;

struct CMP{inline bool operator () (const int &A, const int &B) {return R[A] < R[B];}};
multiset<int,CMP>::iterator itr;
multiset<int,CMP> buf;


inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9'){c=getchar();}
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret;
}

inline void init(){
	n = read(); m = read(); T = 0;
	for (int i=1;i<=n;i++) G[i].clear();
	memset(head,0,sizeof(head));
	memset(mark,0,sizeof(mark));
}

#define Add_Edge(a,b) to[++T] = b,nxt[T]=head[a],head[a]=T
inline void AddEdge(int a, int b) {
	int ra=a*2+1, rb=b*2+1; a *= 2; b *= 2;
	Add_Edge(ra,b); Add_Edge(rb,a);
	Add_Edge(a,rb); Add_Edge(b,ra);
}

inline void build_map(){
	buf.clear();
	for (int i=1;i<=n;i++) {
		while (buf.size() && R[*(buf.begin())] <= i) buf.erase(buf.begin());
		for (int j=0,sz=G[i].size();j<sz;j++) 
			for (itr=buf.begin();itr!=buf.end() && R[*itr] < R[G[i][j]];itr++) 
				AddEdge(G[i][j],*itr);
		for (int j=0,sz=G[i].size();j<sz;j++) buf.insert(G[i][j]);
	}
}

bool DFS(int w) {
	if (mark[w]) return true;
	if (mark[w^1]) return false;
	mark[w] = 1; que[++cnt] = w;
	
	for (int i=head[w];i;i=nxt[i]) 
		if (!DFS(to[i])) return false;
	return true;
}

inline bool judge(){
	for (int i=2;i<=m*2+1;i+=2) if (!mark[i] && !mark[i+1]) {
		cnt = 0; if (DFS(i)) continue;
		for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
		cnt = 0; if (!DFS(i+1)) return false; 
	}
	return true;
}

int main(){
	int TT = read(); while (TT--) { init();
		for (int i=1;i<=m;i++) L[i] = read(), R[i] = read();
		for (int i=1;i<=n;i++) que[i] = read(), ins[que[i]] = i;
		for (int i=1;i<=m;i++) {
			L[i] = ins[L[i]]; R[i] = ins[R[i]];
			if (L[i] > R[i]) swap(L[i], R[i]);
			G[L[i]].push_back(i);
		}
		if (m > 3*n-6) printf("NO\n");
		else {
			build_map();
			if (judge()) printf("YES\n");
			else printf("NO\n");
		}
	} 
	return 0;
}

【BZOJ 2199】[Usaco2011 Jan] 奶牛议会

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2199
离线版题目:http://paste.ubuntu.com/22149982/

仍然是2-sat
一开始觉得这货,拓扑关系上的父亲对该决策有影响
遂wa
后来想一想,貌似父亲那过来的条件只是充分的,不是必要的
于是O(n^2)暴力验证,ac

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 8000+9;

int T,nxt[MAXN],to[MAXN],head[MAXN],mark[MAXN];
int que[MAXN],cnt,vout[MAXN],n,m;

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9'){c=getchar();}
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret;
}

inline void AddEdge(int u, int v){
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

inline bool DFS(int w){
	if (mark[w^1]) return false;
	else if (mark[w]) return true;
	mark[w] = 1; que[++cnt] = w;
	
	for (int i=head[w];i;i=nxt[i]) 
		if (!DFS(to[i])) return false;
	return true;
}

inline bool Get_Ans(){
	for (int i=2;i<=n*2+1;i+=2) if (!mark[i] && !mark[i+1]) {
		cnt = 0; if (DFS(i)) vout[i/2] = 1;
		for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
		cnt = 0; if (DFS(i+1)) vout[i/2] += 2;
		for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
		if (!vout[i/2]) return false;
	}
	return true;
}

int main(){
	n = read(); m = read();
	for (int i=1,a,b,ra,rb;i<=m;i++) { char tmp; 
		a = ra = read()*2; scanf("%c",&tmp);
		if (tmp == 'Y') ra++; else a++;
		b = rb = read()*2; scanf("%c",&tmp);
		if (tmp == 'Y') rb++; else b++;
		AddEdge(ra,b); AddEdge(rb,a);
	} 
	if (!Get_Ans()) printf("IMPOSSIBLE");
	else for (int i=1;i<=n;i++) {
		if (vout[i] == 3) printf("?");
		else if (vout[i] == 1) printf("Y");
		else printf("N");
	}
	return 0;
} 

【BZOJ 1823】[JSOI2010] 满汉全席

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1823
数据生成器:http://paste.ubuntu.com/22127360/

2-sat的裸题
如果一个评委是喜欢h1 && m3
那么为了满足该评委一定有:m1 -> m3 或 h3 -> h1
™读入那里写挫了,wa了一上午QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 2000+9;

int T,nxt[MAXN],to[MAXN],head[MAXN],n,m,mark[MAXN],que[MAXN],cnt;
char pat[10];

inline char Get(){
	char c=getchar();
	while (c != 'm' && c != 'h') c=getchar();
	return c;
}

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret;
}

inline void AddEdge(int a, int b){
	to[++T] = b; nxt[T] = head[a]; head[a] = T;
}

inline void init(){
	scanf("%d%d",&n,&m); T = 0;
	memset(head,0,sizeof(head));
	memset(mark,0,sizeof(mark));
}

bool DFS(int w){
	if (mark[w^1]) return false;
	if (mark[w]) return true;
	mark[w] = 1; que[++cnt] = w;
	
	for (int i=head[w];i;i=nxt[i]) 
		if (!DFS(to[i])) return false;
	return true;
}

inline bool judge(){
	for (int i=1*2;i<=n*2+1;i+=2) if (!mark[i] && !mark[i+1]) { 
		cnt = 0; if (DFS(i)) continue;
		else {
			for (int j=1;j<=cnt;j++) mark[que[j]] = 0; 
			cnt = 0; if (!DFS(i+1)) return false;
		}
	}
	return true;
}

int main(){
	int TT; scanf("%d",&TT);
	while (TT--) {
		init();
		for (int i=1,a,b,ra,rb;i<=m;i++) {
			pat[1] = Get(); a = ra = read()*2;
			pat[4] = Get(); b = rb = read()*2;
			if (pat[1] == 'm') a++; else ra++;
			if (pat[4] == 'm') b++; else rb++;
			AddEdge(ra,b);
			AddEdge(rb,a);
		}
		if (judge()) printf("GOOD\n");
		else printf("BAD\n");
	}
	return 0;
}