【Codeforces 804C】Ice cream coloring

相关链接

题目传送门:http://codeforces.com/contest/804/problem/C

解题报告

不难发现这货是个弦图
然后仔细想想,只要保证

在原图中,一个一个结点处理
所有处理过的结点组成一个连通块

就可以了

至于这样为什么是对的?
因为最小染色数很好确定,就是$\max(s_i)$
所以我们只需要求出染色方案数,所以只要染色随时是一个连通块就可以了

Code

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

const int N = 600009;

int n,m,ans,head[N],to[N],nxt[N],sz[N],col[N];
vector<int> vis[N],lst[N];
set<int> que[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 AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline void solve(int w, int f) {
	int cur = 1;
	for (int jj=0;jj<lst[w].size();jj++) {
		int j = lst[w][jj];
		if (!col[j]) {
			while (!que[w].empty() && cur == *que[w].begin()) {
				++cur;
				que[w].erase(que[w].begin());
			}
			col[j] = cur;
			for (int k=0;k<vis[j].size();k++) {
				que[vis[j][k]].insert(cur);
			}
		} 
	}
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			solve(to[i], w);
		}
	}
}

int main() {
	n = read(); m = read();
	ans = 1;
	for (int i=1;i<=n;i++) {
		sz[i] = read();
		ans = max(ans, sz[i]);
		for (int j=1,p;j<=sz[i];j++) {
			p = read();
			vis[p].push_back(i);
			lst[i].push_back(p);
		}
	}
	for (int i=1;i<n;i++) {
		AddEdge(read(), read());
	}
	solve(1, 1);
	cout<<ans<<endl;
	for (int i=1;i<=m;i++) {
		printf("%d ",col[i]? col[i]: 1);
	}
	return 0;
}

【BZOJ 3103】[ONTAK2010] Palindromic Equivalence

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3103
神犇题解:http://foreseeable97.logdown.com/posts/194507-herbicidalontak2010palindromic-equivalence

解题报告

这些字符串相关的计数题已经做过很多了吧?
这题显然就是给定$O(n)$个相等与不等的关系,让你求染色方案数
这样直接做好像是一个$NP$的问题?就是四色定理那个一般化后的问题

但这题有一个非常好的性质,如果我们把一个等价类看成点,不等关系看成边
那么每一个联通块都是一个完全图!也就是一个弦图!
弦图的染色方案数是可以使用完美消除序列在$O(n)$的时间复杂度内解决的
有因为这题是完全图,所以任意一个$1 \sim n$的排列都是完美消除序列
于是直接从$1 \to n$进行计算即可

至于这图是个弦图图的证明,想一想还是很简单的(虽然不怎么容易观察出来)
我们可以参考:http://foreseeable97.logdown.com/posts/194507-herbicidalontak2010palindromic-equivalence

Code

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

const int N = 2000009;
const int M = N << 1;
const int MOD = 1000000007;

char pat[N],s[N];
int n,ans=1,fa[N],rid[N],col[N];
int vis[N],head[N],nxt[M],to[M]; 
vector<pair<int,int> > e;

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

int find(int x) {
	return x == fa[x]? x: fa[x] = find(fa[x]);
}

inline void manacher() {
	for (int i=1,r=1,p=1,t;i<=n*2;i++) {
		t = min(r - i, rid[p - (i - p)]);
		while (s[i+t+1] == s[i-t-1]) t++, fa[find(i+t)] = find(fa[i-t]);
		if ((rid[i] = t) + i > r) r = t + i, p = i;
		e.push_back(make_pair(i - t - 1, i + t + 1));
	}
}

inline void AddEdge(int u, int v) {
	static int E = 1; 
	if (u == v || !(u & 1) || !(v & 1)) return;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

int main() {
	scanf("%s",pat+1); n = strlen(pat+1); 
	s[0] = '#'; s[n*2] = '@';
	for (int i=1;i<=n;i++) s[i*2-1] = pat[i], s[i*2] = '*';
	for (int i=1;i<=n*2;i++) fa[i] = i;
	manacher();
	for (int i=0;i<e.size();i++) AddEdge(find(e[i].first), find(e[i].second));
	for (int i=1,cnt;cnt=26,i<=n*2;i+=2) {
		if (find(i) != i) continue; col[i] = 1;
		for (int j=head[i];j;j=nxt[j]) {
			if (col[to[j]] && vis[to[j]] < i) 
				--cnt, vis[to[j]] = i;
		}  
		if (cnt <= 0) ans = 0; 
		else ans = (LL)ans * cnt % MOD;
	}
	cout<<ans;
	return 0;
}

—————————— UPD 2017.4.26 ——————————
今天我们机房讨论了一下,这货是个弦图,不一定是一个完全图

【BZOJ NOI十连测】KMP

题目传送门:http://begin.lydsy.com/JudgeOnline/problem.php?id=3026
离线版题目:http://paste.ubuntu.com/18022623/
数据生成器:http://paste.ubuntu.com/18021204/
大样例答案:http://paste.ubuntu.com/18022708/
大样例:http://paste.ubuntu.com/18022662/

这是一道很好玩的题目!本来以为是字符串处理题目,结果最后是图论QAQ
很明显,nxt[]实际上是给出了一些字符的等于或不等关系。
如果我们把不等关系用边来表示,那么这货就是一个弦图。
证明的话,也很简单:因为所连的边一定是一条fail链上拓展出来的,所以每一次连边,一定会向所有可能建立关系的点连边
这样的话,不仅仅是一个弦图?还是一个完全图?
然后用完美消除序列倒着求方案数乘一乘就好。(参见本博客的文章《弦图的计数问题》)

更进一步,kmp的构造顺序就是反的完美消除序列。
这个的证明建立在上文提到的“一定会向所有可能建立关系的点连边”,即每一次如果加入了点,那么这个点是一个单纯点
所以直接按照数组顺序乘就可以了QAQ

弦图染色代码:

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define LL long long
using namespace std;

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

const int MAXN = 200000+9;
const LL MOD = 1000000000+7;

int n,c,cnt,fail[MAXN],p[MAXN],Ord[MAXN];
int T,nxt[MAXN],head[MAXN],to[MAXN];
int tot,mx,used[MAXN],pos[MAXN],ord[MAXN];
queue<int> que[MAXN];

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

inline void MCS(){
	tot = 0; mx = 0;
	for (int i=1;i<=n;i++)
		que[0].push(i);
		
	while (tot < n){
		while (!que[mx].empty()&&used[que[mx].front()]) 
			que[mx].pop();
		if (que[mx].empty()) mx--;
		else {
			int w = que[mx].front(); que[mx].pop();
			ord[++tot] = w; used[w] = 1;
			for (int i=head[w];i;i=nxt[i]) if (!used[to[i]]) 
				que[++pos[to[i]]].push(to[i]), 
				mx = max(mx, pos[to[i]]);
		}
	}
}

int main(){
	n = read(); c = read();
	for (int i=2;i<=n;i++) fail[i] = read();
	
	p[1] = cnt = 1;
	for (int i=1,j;i<n;i++){
		if (fail[i+1]) p[i+1]=p[fail[i+1]];
		else {
			int j = fail[i]; p[i+1]=++cnt;
			while (j) {
				if (Ord[p[j+1]] < i+1 ) 
					AddEdge(p[j+1],p[i+1]), Ord[p[j+1]]=i+1; 
				j=fail[j];
			}
			if (Ord[p[j+1]] < i+1 ) 
				AddEdge(p[j+1],p[i+1]), Ord[p[j+1]]=i+1; 
		}
	}
	
	MCS();
	
	LL vout = 1;
	memset(used,0,sizeof(used));
	for (int j=1,i=ord[j],sum;j<=cnt;i=ord[++j]){
		sum = 0; 
		for (int k=head[i];k;k=nxt[k])
			if (used[to[k]]) sum++;
		sum = c-sum; used[i] = 1;
		vout = (vout*(LL)sum)%MOD;
	}
	printf("%lld\n",vout);
	
	return 0;
}

%%% YJQ 的利用kmp特殊性质的神代码:

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const LL MOD = 1000000000+7;
const int MAXN = 200000+9;
int n,m,fail[MAXN],go[MAXN];

int main(){
	cin>>n>>m;
	for (int i=2;i<=n;i++)
		scanf("%d",&fail[i]);
	go[0]=1; int ans=m;
	for (int i=1;i<n;i++){
		if (fail[i+1]) go[i] = go[fail[i]];
		else go[i] = go[fail[i]]+1,
		ans = 1LL*ans*(m-go[fail[i]])%MOD;
	}
	printf("%d\n",ans);
	return 0;
}