CF568C New Language

IOI2020集训队作业

集训队作业完成22/150祭

为什么祭?因为我认为比写我颓死了更好

这里写的没有洛谷上写的详细

输入一个划分方案,将 $\texttt{a} \sim \texttt{a} + l - 1$ 这 $l$ 个字符分成 $\texttt{V,C}$ 两个集合。
你需要构造一个长度为 $n$ 且满足 $m$ 个限制且不小于另一个长度为 $n$ 的字符串 $s$ 的最小字符串。
每一个限制为若字符串的第 $p_1$ 个位置上的字符 $\in t_1$ ，则第 $p_2$ 个位置上的字符 $\in t_2$ ,其中 $t_1,t_2$ 是集合V或者C
$l \le 26$ ， $n \le 200$ ， $m \le 4n(n-1)$ 。

做法:2-SAT

为什么呢?这个还是比较好看出来的,首先每个元素都属于一个集合,然后一共有两个集合,这个很二分图

但是给出的限制条件并没有那么简单是边的关系所以要2-SAT建图

建完2-SAT我们还要考虑字典序最小QAQ

然而2-SAT理论上线性啊?为啥n这么小?

显然我们只需要枚举一下放啥就好了/汗,然而枚举也不用枚举直接找大于他最小的就行

复杂度?O(nm),m是2-SAT,n是枚举,常数至少也是??要注意没有给出集合的字符不能用的!

code:

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

const int MAXN = 207, L = 33, MAXM = 3e5;
int n, m, k, a[L], b[L][2], vis[MAXN << 1];
char s[MAXN];
int home[MAXM], nxt[MAXM], to[MAXM], ccnt;

inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

bool dfs(int x) {
	if(vis[x > n ? x - n : x + n])return 0;
	//如果已经有环了的话
    //就是i+n为1,i为1
    //这个dfs只需要找有没有接
	vis[x] = 1;
	for(int i = home[x]; i; i = nxt[i]) {
		int v = to[i];
		if(!vis[v] && !dfs(v))return 0;
	}
	return 1;
}

inline bool pd(int C) {
	for(int i = 1; i <= n << 1; ++i)vis[i] = 0;
	for(int i = 1; i <= C; ++i) {
		if(!dfs(i + a[s[i] - 'a' + 1]*n))return 0;
        //把每个点dfs一下,如果有1,说明这个分发不合理
	}
	for(int i = C + 1; i <= n; ++i) {
		if(vis[i])s[i] = b[1][0] + 'a' - 1;
		else if(vis[i + n])s[i] = b[1][1] + 'a' - 1;
		else {
			int x = min(b[1][0], b[1][1]), y = max(b[1][0], b[1][1]);
			if(dfs(i + a[x]*n))s[i] = x + 'a' - 1;
			else if(dfs(i + a[y]*n))s[i] = y + 'a' - 1;
            //这个dfs....判断一下有没有能合法的分配?
			else return 0;
		}
	}
	return 1;
}


map<char, int> p;
int main() {
	scanf("%s", s + 1);
	k = strlen(s + 1);
	p['V'] = 0, p['C'] = 1;//真,假
	b[k + 1][0] = b[k + 1][1] = k + 1;
	for(int i = k, t[2] = {k + 1, k + 1}; i; i--) {
		t[a[i] = p[s[i]]] = i;
		b[i][0] = t[0];
		b[i][1] = t[1];
        //把每个字符变成他应该的样子
        //就是分到哪个集合
        //同时我们处理出了上一个另一个集合的字符的位置
	}
	scanf("%d%d", &n, &m);
	for(int i = 1, x, y, s1, t1, s2, t2; i <= m; ++i) {
		scanf("%d", &x);
		scanf("%s", s + 1);
		y = strlen(s + 1);
		s1 = x + p[s[y]] * n;
		s2 = s1 > n ? s1 - n : s1 + n;
		scanf("%d", &x);
		scanf("%s", s + 1);
		y = strlen(s + 1 );
		t1 = x + p[s[y]] * n;
        //这里是建边,如果是s1就是选择分到集合1,否则是分到集合2
        //s1可推出t1,t2可推出s2

		t2 = t1 > n ? t1 - n : t1 + n;
		ct(s1, t1);
		ct(t2, s2);

	}
	scanf("%s", s + 1);
	n = strlen(s + 1);
	//	printf("%s?\n", s + 1);
	if(pd(n))return printf("%s\n", s + 1), 0;
	else if(b[1][0] == k + 1 || b[1][1] == k + 1)return puts("-1"), 0;
    //如果第一个字符他都没有对应集合
    //也就无解了
	for(int i = n; i; --i) {
		int c = s[i] - 'a' + 2, x = min(b[c][0], b[c][1]), y = max(b[c][0], b[c][1]);
        //b是上一个的!
		if(x != k + 1) {
			s[i] = x + 'a' - 1;
			if(pd(i))return printf("%s\n", s + 1), 0;
		}
		if(y != k + 1) {
			s[i] = y + 'a' - 1;
            //如果填上一个的话
			if(pd(i))return printf("%s\n", s + 1), 0;
		}
	}
	puts("-1");
	return 0;
}

不太会

夏晓光(loveJY)的博客

CF566C Logistical Questions