河北seo网站开发,返利网一类的网站怎么做,民宿网站建设,品牌网站建设费用要多少UVa12273/LA4958 Palindromic DNA 题目链接题意分析AC 代码 题目链接 本题是2010年icpc欧洲区域赛西南欧赛区的的E题
题意 DNA由四种核苷碱基A、G、T、C组成#xff0c;它们形成环状排序。当今能对DNA进行修改#xff08;但不能同时对相邻位置进行修改#xff09;#xff… UVa12273/LA4958 Palindromic DNA 题目链接题意分析AC 代码 题目链接 本题是2010年icpc欧洲区域赛西南欧赛区的的E题
题意 DNA由四种核苷碱基A、G、T、C组成它们形成环状排序。当今能对DNA进行修改但不能同时对相邻位置进行修改将某位置加/减1比如将C加1变成A、将C减1变成T。现给出一个DNA序列并从中选出若干子序列问能否将所有选出的子序列修改成回文形式。
分析 对每个子序列要满足回文形式则必然是原DNA序列某些位置最终要变成相同的这可以用并查集处理。然后考虑每个集合里面原始的不同碱基情况如果四种都有显然无法修改无解如果有三种或者有两种并且是相对碱基AT/GC则一定要把相对碱基都做修改如果有两种并且是相邻碱基则一定要修改一个并且另外一个不能修改如果只有一种则已经是回文形式无需修改。 由不能同时对相邻位置进行修改联想到2-SAT对于位置 i i i用结点 2 i 2i 2i表示修改、结点 2 i 1 2i1 2i1表示不修改下面考虑怎么添加子句构建有向边相邻位置添加子句 x i ∧ ¬ x i 1 x_i∧\neg x_{i1} xi∧¬xi1即连接 2 i → 2 i 3 2i\rightarrow2i3 2i→2i3、 2 i 2 → 2 i 1 2i2\rightarrow2i1 2i2→2i1两条有向边每个集合不同碱基有三种或者有两种并且是相对碱基AT/GC那么AT/GC是一定要修改的连接 2 i i → 2 i 2ii\rightarrow2i 2ii→2i即可每个集合不同碱基有两种并且是相邻碱基则一定要修改一个并且另外一个不能修改找到根 r r r当位置 i ≠ r i\ne r ir时需要建边位置 i i i和位置 r r r的碱基不同则添加两个子句 x i ∧ ¬ x r x_i∧\neg x_r xi∧¬xr和 ¬ x i ∧ x r \neg x_i∧x_r ¬xi∧xr相同则添加两个子句 x i ∧ x r x_i∧x_r xi∧xr和 ¬ x r ∧ ¬ x i \neg x_r∧\neg x_i ¬xr∧¬xi。 这里再说一下对于限定了部分结点取值的2-sat问题可以这样连边处理如果结点 i i i必须为真对应 2 i 2i 2i则连边 2 i i → 2 i 2ii\rightarrow2i 2ii→2i如果结点必须为假则连边 2 i → 2 i 1 2i\rightarrow2i1 2i→2i1。
AC 代码
#include iostream
using namespace std;#define w(c) cA ? 1 : (cG ? 2 : (cT ? 4 : 8))
#define M 20020
int g[M][M1], f[M1], h[M1], v[M1], c[M], s[M], sn[M], low[M], pre[M], cc, clk, n, p, t; char d[M1];int find(int x) {return x f[x] ? x : f[x] find(f[x]);
}void add_clause(int u, int v) {g[u][c[u]] v^1; g[v][c[v]] u^1;
}bool dfs(int u) {low[u] pre[u] clk; s[p] u;for (int i0, v; ic[u]; i) if (!pre[v g[u][i]]) {if (!dfs(v)) return false;low[u] min(low[u], low[v]);} else if (!sn[v]) low[u] min(low[u], pre[v]);if (low[u] pre[u]) {cc;while (true) {if (cc sn[s[--p]^1]) return false;sn[s[p]] cc;if (s[p] u) break;}}return true;
}bool solve() {cin d;for (int i0; in; i) f[i] i, h[i] 0;while (t--) {int l, h; char _; cin l _; h l 1;for (int i1; il; i) {cin v[i];if (i h) f[find(v[i])] find(v[l-i]);}}t n1;for (int u0; ut; u) c[u] pre[u] sn[u] cc p clk 0;for (int i0; in; i) h[find(i)] | w(d[i]);for (int i0; in; i) {int j f[i], v h[j];if (v 15) return false;if (i 0) add_clause((i-1) 1, i 1);if ((v5) 5) {if (d[i]A || d[i]T) ji1 | 1, g[j][c[j]] j^1;} else if ((v10) 10) {if (d[i]G || d[i]C) ji1 | 1, g[j][c[j]] j^1;} else if (i ! j (v3 || v6 || v9 || v12)) {bool e d[i] d[j];add_clause(i1, e ? j1 | 1 : j1); add_clause(i1 | 1, e ? j1 : j1 | 1);}}for (int u0; ut; u) if (!pre[u] !dfs(u)) return false;return true;
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);while (cin n t n) cout (solve() ? YES : NO) endl;return 0;
}
