「CF568C」 New Language

一眼 \(\texttt{2-SAT}\) 。

然后不会了。

又看了一会儿，然后发现只要我们确定每个位置大于字典序的两种最小的字母是啥，然后按位贪心，这个问题就解决了。

吗？

然后你发现限制很多：

如果前几位都和题目所给的字符串一样，你需要判断接下来还能不能一样。

如果有一位不同，那么接下来的位你都不需要考虑字典序，只需要考虑是否可行即可。这可以通过把后面的字符都设为 a 来解决。

然后，想清楚还需要打一会，然后这题就没了。

注意用 \(\texttt{DFS}\) 求解 \(\texttt{2-SAT}\) 的清空问题。

/*---Author:HenryHuang---*/

/*---Never Settle---*/

#include<bits/stdc++.h>

#define add(a,b) e[a].emplace_back(b)

#define ano(x) (x>n?x-n:x+n)

using namespace std;

const int maxn=2e3+5;

char s[maxn],t[maxn];

vector<int> e[maxn];

int m0[maxn],m1[maxn];

int st[maxn],tp;

int b[maxn],n,m;

bool dfs(int u){

	if(b[ano(u)]) return 0;

	b[u]=1,st[++tp]=u;

	for(auto v:e[u])

		if(!b[v]&&!dfs(v)) return b[u]=0;

	return 1;

}

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	cin>>(s+1);int l=strlen(s+1);

	int t0=1e9,t1=1e9;

	m0[l+1]=m1[l+1]=1e9;

	for(int i=l;i;--i){

		if(s[i]=='V') t0=i;

		else t1=i;

		m0[i]=t0,m1[i]=t1;

	}

	cin>>n>>m;

	for(int i=1;i<=m;++i){

		int a,c;string b,d;

		cin>>a>>b>>c>>d;

		a=(a+n*(b[0]=='C')),c=(c+n*(d[0]=='C'));

		add(a,c),add(ano(c),ano(a));

	}

	cin>>(t+1);

	for(int i=1;i<=n;++i) t[i]-=96;

	int f=0;

	for(int i=1;i<=n;++i){

		tp=0;

		if(f) t[i]=1;

		pause:

		if(m0[t[i]]==1e9){

			if(m1[t[i]]==1e9||b[i]||!dfs(i+n)) cout<<"-1",exit(0);

		}

		else if(m1[t[i]]==1e9){

			if(b[i+n]||!dfs(i)) cout<<"-1",exit(0);

		}

		else if(!b[i]&&!b[i+n]){

			if(m0[t[i]]<m1[t[i]]){

				if(!dfs(i)){

					f=1;

					if(!dfs(i+n)) cout<<"-1",exit(0);

				}

			}

			else{

				if(!dfs(i+n)){

					f=1;

					if(!dfs(i)) cout<<"-1",exit(0);

				}

			}

		}

		else if(b[i]?m0[t[i]]>t[i]:m1[t[i]]>t[i]) f=1;

		if(!f){

			for(int j=i+1;j<=n;++j){

				if(b[j]){

					if(m0[t[j]]==1e9){

						++t[i],f=1;

						break;

					}

					if(m0[t[j]+1]!=1e9) break;

				}

				else if(b[j+n]){

					if(m1[t[j]]==1e9){

						++t[i],f=1;

						break;

					}

					if(m1[t[j]+1]!=1e9) break;

				}

				else if(m0[t[j]+1]!=1e9||m1[t[j]+1]!=1e9) break;

			}

			if(f){

				while(tp) b[st[tp--]]=0;

				goto pause;

			}

		}

	}

	for(int i=1;i<=n;++i) cout<<(char)(96+(b[i]?m0[t[i]]:m1[t[i]]));

	return 0;

}

巴特西

「CF568C」 New Language

「CF568C」 New Language

最新文章

热门文章