几何 100pts
赛时打的 $ DP $ 没有用 bitset 优化过了，也是放过了暴力；
考虑设状态 $ f_{i, j, k} $ 表示考虑到第 $ i $ 位，到第 $ j $ 位 $ x $ 和第 $ k $ 位 $ y $ 可不可取，直接转移即可；
时间复杂度：$ \Theta(|s||x||y|) $，应该是过不了的；
点击查看暴力
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int t;
char s[500005], x[55], y[55];
int sl, xl, yl;
bool f[2][52][52];
int main() {freopen("geometry.in", "r", stdin);freopen("geometry.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> t;while(t--) {cin >> (s + 1);cin >> (x + 1);cin >> (y + 1);memset(f, false, sizeof(f));sl = strlen(s + 1);xl = strlen(x + 1);yl = strlen(y + 1);f[0][xl][0] = true;f[0][0][yl] = true;for (int i = 1; i <= sl; i++) {memset(f[i & 1], false, sizeof(f[i & 1]));for (int j = 0; j <= xl; j++) {for (int k = 0; k <= yl; k++) {if (s[i] == x[j]) {if (j - 1 == 0) {f[i & 1][j][k] |= f[(i - 1) & 1][xl][k];f[i & 1][j][k] |= f[(i - 1) & 1][0][k];} else {f[i & 1][j][k] |= f[(i - 1) & 1][j - 1][k];}}if (s[i] == y[k]) {if (k - 1 == 0) {f[i & 1][j][k] |= f[(i - 1) & 1][j][0];f[i & 1][j][k] |= f[(i - 1) & 1][j][yl];} else {f[i & 1][j][k] |= f[(i - 1) & 1][j][k - 1];}}}}}if (f[sl & 1][xl][yl] || f[sl & 1][xl][0] || f[sl & 1][0][yl]) {cout << "Yes" << '\n';} else {cout << "No" << '\n';}}return 0;
}
根据我们以前的经验，我们可以将答案与状态后两维中的一位互换，所以设 $ f_{i, j} = k $ 表示考虑前 $ i $ 位，到第 $ j $ 位 $ x $ 时所有合法的 $ y $ 的状态，这时我们就可以用 bitset 来存储 $ f $ 数组，进而转移；
转移其实就是循环移位和按位与和按位或的操作；
时间复杂度：$ \Theta(\frac{|s||x||y|}{w}) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>
using namespace std;
int t;
char s[500005], x[55], y[55];
int sl, xl, yl;
bitset<55> f[2][52];
bitset<55> g[500005];
bitset<55> Y(bitset<55> x) {int y = x[yl];bitset<55> bit = (x << 1);if (y) bit[1] = 1;return bit;
}
int main() {freopen("geometry.in", "r", stdin);freopen("geometry.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> t;while(t--) {cin >> (s + 1);cin >> (x + 1);cin >> (y + 1);memset(f, 0, sizeof(f));memset(g, 0, sizeof(g));sl = strlen(s + 1);xl = strlen(x + 1);yl = strlen(y + 1);for (int i = 1; i <= sl; i++) {for (int j = 1; j <= yl; j++) {if (s[i] == y[j]) g[i][j] = 1;}}f[0][0][0] = 1;for (int i = 1; i <= sl; i++) {memset(f[i & 1], 0, sizeof(f[i & 1]));for (int j = 0; j <= xl; j++) {if (s[i] == x[j]) {f[i & 1][j] |= f[(i - 1) & 1][j - 1];if (j - 1 == 0) f[i & 1][j] |= f[(i - 1) & 1][xl];}bitset<55> b = Y(f[(i - 1) & 1][j]);b &= g[i];f[i & 1][j] |= b;}}if (f[sl & 1][xl][yl] || f[sl & 1][xl][0] || f[sl & 1][0][yl]) {cout << "Yes" << '\n';} else {cout << "No" << '\n';}}return 0;
}
分析 0pts
$ DP $，。。。
点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
long long a, b;
long long f[500005][2][2], w[2][2];
struct sss{int t, ne;
}e[2000005];
int h[2000005], cnt;
void add(int u, int v) {e[++cnt].t = v;e[cnt].ne = h[u];h[u] = cnt;
}
void dfs(int x, int fa) {f[x][0][0] = 0;for (int i = h[x]; i; i = e[i].ne) {int u = e[i].t;if (u == fa) continue;dfs(u, x);for (int j = 0; j <= 1; j++) {for (int k = 0; k <= 1; k++) {w[j][k] = f[x][j][k];f[x][j][k] = 0x3f3f3f3f3f3f3f3f;}}for (int j = 0; j <= 1; j++) {for (int k = 0; k <= 1; k++) {for (int uj = 0; uj <= 1; uj++) {for (int uk = 0; uk <= 1; uk++) {f[x][j][k | uj | uk] = min(f[x][j][k | uj | uk], w[j][k] + f[u][uj][uk] + a);long long now = 0;if (j && uj) {now = -b;} else if (!j && !uj) {now = b;}f[x][j ^ 1][k | (uj ^ 1) | uk] = min(f[x][j ^ 1][k | (uj ^ 1) | uk], w[j][k] + f[u][uj][uk] + now);}}}}}
}
int main() {freopen("analyse.in", "r", stdin);freopen("analyse.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;cin >> a >> b;a = min(a, b);int x, y;for (int i = 1; i <= n - 1; i++) {cin >> x >> y;add(x, y);add(y, x);}memset(f, 0x3f, sizeof(f));dfs(1, 0);cout << min({f[1][0][0], f[1][0][1] - b, f[1][1][0] - b, f[1][1][1] - b});return 0;
}
