(2-sat)
时间复杂度
$O(2^{d}*(n+m))$
好像这题题解比较少,我来写一发
首先考虑,如果无x存在的情况,我们是不是直接就转化成了一个2-sat模板的题.
建边思想:
每个场地,我们当前只剩下了两种车可用,设都不可用C车,均只为A,B。
给一个条件为1 A 2 B,
1A选了必须选2B,逆否命题,选了!2B(即为2A)必须选!1A(1B).
注意存在一种情况给一个条件为1 A 2 C,这组条件让1 A不能选,
则2-SAT问题中只选一个点,可!x向x连一条边,即举例中的1号点只能为B,1A->1B,就保证了我们再有解选
择的时候,1B拓扑序再1A之后,一定选1B.
那么跑图就行了.
若存在x,注意x的数量很小(<=8),那么我们分情况枚举x,
1.把x变成A场地
2.把x变成B场地
3.把x变成C场地
再每次跑2-sat即可
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize(3, "Ofast", "inline")
#define fir(i, a, b) for (int i = a; i <= b; i++)
const int maxn = 3e5 + 10;
char s[maxn];
int n, d, m;
bool flag[maxn];
struct node
{
int x, y;
char ch0, ch1;
} b[maxn];
namespace suodian
{
vector<int> g[maxn];
int sta[maxn], top = 0, cnt = 0;
int dfn[maxn], low[maxn];
bool use[maxn];
int siz[maxn];
int scc_cnt = 0;
int id[maxn];
int d[maxn];
void dfs(int u)
{
dfn[u] = low[u] = ++cnt;
sta[++top] = u;
use[u] = true;
for (auto v : g[u])
{
if (!dfn[v])
{
dfs(v);
low[u] = min(low[u], low[v]);
}
else if (use[v])
low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u])
{
++scc_cnt;
int v;
do
{
v = sta[top--];
id[v] = scc_cnt;
use[v] = false;
siz[scc_cnt]++;
} while (v != u);
}
}
void init()
{
fir(i, 1, 3 * n)
{
sta[i] = 0, top = 0, cnt = 0;
dfn[i] = low[i] = 0;
use[i] = false;
siz[i] = 0;
scc_cnt = 0;
id[i] = 0;
d[i] = 0;
g[i].clear();
}
}
void tarjan()
{
fir(i, 1, 3 * n) if (flag[i] && !dfn[i]) dfs(i);
}
bool solve()
{
init();
fir(i, 1, m)
{
int x = b[i].x, y = b[i].y;
char ch0 = b[i].ch0, ch1 = b[i].ch1;
int lastx = x, lasty = y;
x += (ch0 - 'A') * n, y += (ch1 - 'A') * n;
int tx, ty;
fir(j, 0, 2)
{
int num = lastx + j * n;
if (flag[num] && num != x)
{
tx = num;
break;
}
}
fir(j, 0, 2)
{
int num = lasty + j * n;
if (flag[num] && num != y)
{
ty = num;
break;
}
}
// cout<<x<<' '<<y<<' '<<tx<<' '<<ty<<endl;
if (!flag[y])
g[x].push_back(tx);
else
{
if (flag[x])
{
g[x].push_back(y);
g[ty].push_back(tx);
}
}
}
/* fir(i,1,3*n)
{
cout<<i<<':';
for(auto it:g[i])cout<<it<<' ';
puts("");
} */
tarjan();
string str = "";
fir(i, 1, n)
{
vector<pair<int, int>> val;
fir(j, 0, 2) if (flag[i + j * n])
val.push_back({id[i + j * n], j});
if (val[0].first == val[1].first)
return false;
// cout << i << ':' << char(val[0].second + 'A') << val[0].first << ' ' << char(val[1].second + 'A') << val[1].first << endl;
sort(val.begin(), val.end());
str += 'A' + val[0].second;
}
// cout<<str.size()<<endl;
cout << str << endl;
return true;
}
} // namespace suodian
vector<int> idx;
bool curdfs(int cnt)
{
if (cnt == d)
{
if (suodian::solve())
return true;
return false;
}
for (int i = 0; i <= 2; i++)
{
int num = idx[cnt] + i * n;
flag[num] = false;
//cout<<idx[cnt]<<':';
if (curdfs(cnt + 1))
{
// puts("true");
return true;
}
// puts("false");
flag[num] = true;
}
return false;
}
int main()
{
cin >> n >> d;
scanf("%s", s + 1);
memset(flag, true, sizeof(flag));
fir(i, 1, n) if (s[i] != 'x')
flag[i + (s[i] - 'a') * n] = false;
else idx.push_back(i);
cin >> m;
fir(i, 1, m)
scanf("%d %c %d %c", &b[i].x, &b[i].ch0, &b[i].y, &b[i].ch1);
if (!curdfs(0))
puts("-1");
}