loj2305 noi2017 游戏
程序员文章站
2022-04-09 08:54:19
思路
既然$x$的数量那么小,我们就可以先把每个$x$搜索一遍。
枚举x的时候不需要把$a,b,c$全枚举一遍,只要枚举其中的两个就可以枚举到当前 ......
思路
既然\(x\)的数量那么小,我们就可以先把每个\(x\)搜索一遍。
枚举x的时候不需要把\(a,b,c\)全枚举一遍,只要枚举其中的两个就可以枚举到当前位置选任何车的情况。
然后就变成了只有\('a','b','c'\)的序列。寻找满足题目要求的方案。
\(2-sat\)模型。
连边的时候注意一些技巧,否则\(if\)写到自闭。。
在\(uoj\)上会被卡掉\(3\)分。实在懒得去卡常了233
代码
/* * @author: wxyww * @date: 2019-04-29 09:08:01 * @last modified time: 2019-04-30 14:32:38 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int n = 100010; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } vector<int>e[n]; char a[n],tmp[n]; int n,d,m; int opp[n]; #define add(x,y) e[x].push_back(y) int val[n]; int tot,dfn[n],low[n],vis[n],sta[n],coljs,col[n],top; void tarjan(int u) { int k = e[u].size(); dfn[u] = low[u] = ++tot; sta[++top] = u;vis[u] = 1; for(int i = 0;i < k;++i) { int v = e[u][i]; if(!dfn[v]) { tarjan(v);low[u] = min(low[u],low[v]); } else if(vis[v]) low[u] = min(low[u],low[v]); } if(dfn[u] == low[u]) { ++coljs; do { int x = sta[top--]; col[x] = coljs; vis[x] = 0; }while(sta[top + 1] != u); } } int t1[n],t2[n]; char h1[n],h2[n]; int get_u(int x,char y) { if(a[x] == 'a') return y == 'b' ? x : x + n; return y == 'a' ? x : x + n; } #define ote(x) x > n ? x - n : x + n void solve() { memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low)); memset(col,0,sizeof(col)); coljs = 0,tot = 0;top = 0; for(int i = 1;i <= n + n;++i) e[i].clear(); for(int i = 1;i <= m;++i) { if(a[t1[i]] == h1[i] - 'a' + 'a') continue; int u = get_u(t1[i],h1[i]); if(a[t2[i]] == h2[i] - 'a' + 'a') { add(u,ote(u)); continue; } int v = get_u(t2[i],h2[i]); add(u,v);add(ote(v),ote(u)); } for(int i = 1;i <= n + n;++i) if(!dfn[i]) tarjan(i); for(int i = 1;i <= n;++i) if(col[i] == col[i + n]) return; for(int i = 1;i <= n;++i) { if(col[i] < col[i + n]) { if(a[i] == 'a') putchar('b'); else putchar('a'); } else { if(a[i] == 'c') putchar('b'); else putchar('c'); } } exit(0); } void dfs(int pos) { if(pos == n + 1) { solve(); return; } if(tmp[pos] != 'x') dfs(pos + 1); else { a[pos] = 'a'; dfs(pos + 1); a[pos] = 'b'; dfs(pos + 1); } } int main() { // freopen("2305/game3.in","r",stdin); n = read(),d = read(); scanf("%s",tmp + 1); memcpy(a + 1,tmp + 1,n); m = read(); for(int i = 1;i <= m;++i) { t1[i] = read();h1[i] = getchar();while(h1[i] != 'a' && h1[i] != 'b' && h1[i] != 'c') h1[i] = getchar(); t2[i] = read();h2[i] = getchar();while(h2[i] != 'a' && h2[i] != 'b' && h2[i] != 'c') h2[i] = getchar(); } dfs(1); puts("-1"); return 0; }
上一篇: C# WebForm 屏蔽输入框的验证