Mr. Liang play Card Game (区间 DP)
题意
给出一组长度为 $n$ 的卡牌，每张牌有一个类型 $t$，同时初始等级为 1。类型为 $t$ 的卡牌初始价值为 $w_t$。同时给定 $p$，你可以执行以下两种操作：
- 对相邻的两张同类型 $t$ 且同等级 $r$ 的卡牌进行合并，获得一张类型为 $t$ 的等级为 $r+1$ 的卡牌。
- 打出一张类型为 $t$ 且等级为 $r$ 的卡牌，获得价值 $ p^{(r-1)} \cdot w_t $。
等级限制最高为 $r$，问最终能获得的最大价值。
思路
任选相邻元素合并很明显是区间DP的特征。要求同类型同等级合并，那么这里dp数组就得带上某个区间的类型和等级的信息，考虑到一个区间内如果都是同类型的$1$级牌，那么利益最大的合并方式可以唯一确定，那么等级的信息可以用剩下的牌数代替。设 $ dp[l][r][t][c] $ 为区间 $[l,r]$ 中将其他牌打出，剩下 $c$ 张类型为 $t$ 的牌的最大价值，那么可以得到转移方程：
$$ \begin{cases}dp[l][r][t][c_1+c_2]=\max_{k}(dp[l][k][t_1][c_1]+dp[k][r][t_2][c_2]) & \left(t_1=t_2\right) \\ dp[l][r][t_1][c_1]=\max_{k}(dp[l][k][t_1][c_1]+dp[k][r][t_2][c_2]+sum[t_2][c_2]) & \left(t_1 \ne t_2\right) \\ dp[l][r][t_2][c_2]=\max_{k}(dp[l][k][t_1][c_1]+dp[k][r][t_2][c_2]+sum[t_1][c_1]) & \left(t_1 \ne t_2\right) \end{cases} $$其中 $sum[t][c]$ 为$c$ 张类型为 $t$ 的牌可以打出的最大价值。最终答案为 $ \max_{t,c}(dp[0][n][t][c] + sum[t][c]) $。
需要注意特判 $p=1$ 时不需要合并任何牌，直接一张一张打出去就可以了。
Code
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define orep(i, l, r) for(auto i = (l); i < (r); ++i)
#define NL std::cout << '\n'
using lnt = long long;
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
int n, m, r, p; std::cin >> n >> m >> r >> p;
r = std::min(r, std::__lg(n)+1);
std::vector<lnt> v(n); for (auto &x : v) { std::cin >> x; --x; }
std::vector<lnt> w(m); for (auto &x : w) { std::cin >> x; }
if (p == 1) {
std::cout << std::accumulate(all(v), 0ll, [&](lnt s, int x) { return s+w[x];});
continue;
}
int maxN = n+1;
const lnt inf = 2e18;
std::vector dp(maxN, std::vector(maxN, std::vector(m, std::vector(maxN, -inf))));
std::vector csum(m, std::vector(maxN, 0));
std::vector val(m, std::vector(maxN, 0ll));
for (int i = 0; i < m; ++i) {
val[i][1] = w[i];
for (int x0 = 2; x0 < maxN; ++x0) {
lnt x = x0; lnt o = 1;
for (int k = 0; x; ++k, x >>= 1, o *= p) {
if (k == r-1) { val[i][x0] += x*o*w[i]; break; }
if (x & 1) {
val[i][x0] += o*w[i];
}
}
}
}
for (int i = 0; i < n; ++i) {
dp[i][i+1][v[i]][1] = 0;
for (int t0 = 0; t0 < m; ++t0) {
csum[t0][i] = (i ? csum[t0][i-1] : 0) + (v[i] == t0);
}
}
for (int len = 2; len <= n; ++len) {
for (int i = 0; i < n; ++i) { int j = i+len; if (j > n) { break; }
for (int k = i+1; k < j; ++k) {
for (int t1 = 0; t1 < m; ++t1) {
for (int c1 = 1; c1 <= csum[t1][k-1] - (i ? csum[t1][i-1] : 0); ++c1) {
if (dp[i][k][t1][c1] < -2e17) continue;
for (int t2 = 0; t2 < m; ++t2) {
for (int c2 = 1; c2 <= csum[t2][j-1] - (k ? csum[t2][k-1] : 0); ++c2) {
lnt s = dp[i][k][t1][c1] + dp[k][j][t2][c2];
if (t1 == t2) {
dp[i][j][t1][c1+c2] = std::max(dp[i][j][t1][c1+c2], s);
} else {
dp[i][j][t1][c1] = std::max(dp[i][j][t1][c1], s+val[t2][c2]);
dp[i][j][t2][c2] = std::max(dp[i][j][t2][c2], s+val[t1][c1]);
}
}
}
}
}
}
}
}
lnt ret = 0;
for (int t0 = 0; t0 < m; ++t0) {
for (int c0 = 1; c0 <= n; ++c0){
ret = std::max(ret, dp[0][n][t0][c0] + val[t0][c0]);
}
}
std::cout << ret; NL;
}
return 0;
}Cyclically Isomorphic (字符串最小表示)
题意
给出包含 $n$ 个字符串的集合 $S$，给出 $q$ 次询问，每次问 $S_a$ 是否能通过若干次循环位移得到 $S_b$ (或相反)。
思路
求出每个字符串的最小表示并哈希放进数组里，然后判断 $S_a$ 和 $S_b$ 的哈希值是否相同即可。
Code
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define orep(i, l, r) for(auto i = (l); i < (r); ++i)
#define NL std::cout << '\n'
using lnt = long long;
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
const auto minStr = [](const std::string &s) {
int k = 0, i = 0, j = 1, n = s.size();
while (k < n && i < n && j < n) {
if (s[(i + k) % n] == s[(j + k) % n]) {
k++;
} else {
s[(i + k) % n] > s[(j + k) % n] ? i = i + k + 1 : j = j + k + 1;
if (i == j) i++;
k = 0;
}
}
i = std::min(i, j);
return s.substr(i)+s.substr(0, i);
};
const auto hash = [](const std::string &s) {
lnt h1 = 0, h2 = 0;
const int mo1 = 100000007, mo2 = 999999751;
const lnt b1 = 996491788296388807, b2 = 996491788296388619;
for (const auto &x : s) {
h1 = (h1*b1 + x) % mo1;
h2 = (h2*b2 + x) % mo2;
}
return std::make_pair(h1, h2);
};
int t;
std::cin >> t;
while (t--) {
int n, m; std::cin >> n >> m;
std::vector<std::pair<lnt, lnt>> h(n);
for (int i = 0; i < n; ++i) {
std::string s; std::cin >> s;
h[i] = hash(minStr(s));
}
int q; std::cin >> q;
while (q--) {
int a, b; std::cin >> a >> b;
std::cout << (h[a-1] == h[b-1] ? "Yes" : "No"); NL;
}
}
return 0;
}Easy problem I (线段树)
题意
给你一个长度为 $n$ 的序列$A$，$q$ 次询问。
- 操作1： 给定 $l,r,x$，对于$i \in [l,r]$，$ A_i := |A_i - x|$。
- 操作2： 给定 $l,r$，求$\sum_{i=l}^rA_i$。
保证操作1的$x$单调递增。
思路
由于$x$的单调递增性，可以发现假设序列$A$中的某个元素$A_i$被赋值多次，我们将其操作的绝对值去掉，其被赋值的操作序列必然是前半部分为 $A_i-x$，后半部分 $x-A_i$。
将该序列中所有元素分为两类，类型1为大于 $x$ 的数，类型2为小于 $x$ 的数。我们设所有数初始类型为类型1，且可以发现一个数最多只会从类型1转换到类型2一次，而类型2的数永远不会转换为类型1。
用线段树维护区间信息。在执行对类型1的区间减操作时，需要考虑是否区间内是否有数会坠落至类型2，也即是否存在 $A_i < x$，所以需要维护区间最小值。若存在，将对应数的区间最小值改为 $+\infty$ (避免被多次转为类型2)，同时将区间上类型1的数量改为 $0$，类型2的数量改为 $1$。类型2的操作相当于$-1 * A_i + x$，用可处理乘法和加法的线段树维护一下就可以了。最后统计区间上类型1的和与类型2的和即可。
Code
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define orep(i, l, r) for(auto i = (l); i < (r); ++i)
#define NL std::cout << '\n'
using lnt = long long;
lnt inf = 2e18;
struct Node {
int c1, c2;
lnt s1, s2, mi, tg1, tg2, mul;
};
struct SegTree {
std::vector<Node> t;
int n;
void apply(int p, lnt tg1, lnt tg2, lnt mul) {
t[p].mul *= mul;
t[p].tg2 *= mul;
t[p].s2 *= mul;
t[p].tg2 += tg2;
t[p].s2 += tg2 * t[p].c2;
t[p].tg1 += tg1;
t[p].s1 += tg1 * t[p].c1;
t[p].mi += tg1;
}
void pushdn(int p) {
const auto &v = t[p];
apply(p * 2, t[p].tg1, t[p].tg2, t[p].mul);
apply(p * 2 + 1, t[p].tg1, t[p].tg2, t[p].mul);
t[p].tg1 = t[p].tg2 = 0;
t[p].mul = 1;
}
static Node merge(const Node a, const Node b) {
return {
a.c1 + b.c1, a.c2 + b.c2,
a.s1 + b.s1, a.s2 + b.s2,
std::min(a.mi, b.mi), 0, 0, 1
};
}
void pushup(int p) {
t[p] = merge(t[p * 2], t[p * 2 | 1]);
}
void mod1(lnt val, int l, int r, int cl, int cr, int p) {
if (l <= cl && cr <= r) {
if (t[p].mi >= val) {
apply(p, -val, 0, 1);
return;
}
if (cl == cr - 1) {
t[p].s1 = t[p].c1 = 0;
t[p].c2 = 1;
t[p].s2 = val - t[p].mi;
t[p].mi = inf;
return;
}
}
pushdn(p);
int mid = cl + ((cr - cl) >> 1);
if (l < mid) { mod1(val, l, r, cl, mid, p * 2); }
if (r > mid) { mod1(val, l, r, mid, cr, p * 2 + 1); }
pushup(p);
}
void mod2(lnt val, int l, int r, int cl, int cr, int p) {
if (l <= cl && cr <= r) {
apply(p, 0, val, -1);
return;
}
pushdn(p);
int mid = cl + ((cr - cl) >> 1);
if (l < mid) { mod2(val, l, r, cl, mid, p * 2); }
if (r > mid) { mod2(val, l, r, mid, cr, p * 2 + 1); }
pushup(p);
}
Node qry(int l, int r, int cl, int cr, int p) {
if (l <= cl && cr <= r) {
return t[p];
}
pushdn(p);
int mid = cl + ((cr - cl) >> 1);
Node ret = {0, 0, 0, 0, inf, 0, 0};
if (l < mid) { ret = merge(ret, qry(l, r, cl, mid, p * 2)); }
if (r > mid) { ret = merge(ret, qry(l, r, mid, cr, p * 2 + 1)); }
return ret;
}
explicit SegTree(const std::vector<int> &v) {
n = v.size();
t.assign(n * 4, {});
auto build = [&](const auto &f, int l, int r, int p) {
if (l == r - 1) {
t[p] = {1, 0, v[l], 0, v[l], 0, 0, 1};
return;
}
const int mid = l + ((r - l) >> 1);
f(f, l, mid, p * 2);
f(f, mid, r, p * 2 + 1);
pushup(p);
};
build(build, 0, n, 1);
}
};
signed main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t;
std::cin >> t;
while (t--) {
int n, q;
std::cin >> n >> q;
std::vector<int> v(n);
for (auto &x : v) { std::cin >> x; }
SegTree seg(v);
while (q--) {
int e, l, r;
std::cin >> e >> l >> r;
--l;
if (e == 1) {
lnt x;
std::cin >> x;
seg.mod2(x, l, r, 0, n, 1);
seg.mod1(x, l, r, 0, n, 1);
} else {
auto nd = seg.qry(l, r, 0, n, 1);
std::cout << nd.s1 + nd.s2;
NL;
}
}
}
return 0;
}