T1001 超维攻坚(HDU 7469)
三维凸包，不会。
T1002 黑白边游戏(HDU 7470)
显然这道题没有一个固定的最优策略，所以只能 \(\text{dp}\) 决策。
可以倒着做，设 \(f_{i, S}\) 表示从后往前进行了第 \(i \sim m\) 轮，第 \(i\) 轮结束后（在原始意义下是开始前）黑边集合为 \(S\)，双方使用最优策略时先手与后手的分差，\(g_{S, a, b}\) 表示黑边集合为 \(S\)，一条黑边/白边长度分别为 \(a, b\) 时，可以获得的收益（就是两两最短路之和）。
转移考虑枚举 \(T\)，需要满足 \(S\) 可翻转一条边的颜色到达 \(T\)，那么 \(f_{i, S} = \max \{ g_{a_i, b_i, T} - f_{i + 1, T} \}\)。注意到 \(S\) 是 \(O(2^{\frac{n(n - 1)}{2}})\) 的，无法接受。
注意到这题点与点之间是不区分的，我们可以将本质不同的图全部搜出来，建立状态自动机，在自动机上跑上述 \(\text{dp}\)（只需将 \(S\) 换成自动机上的结点即可），我们猜测自动机上的结点不会太多，实际上，在 \(n = 8\) 时只有 \(12346\) 个结点。
现在考虑如何建出自动机，也就是找出所有本质不同的图（现在我们默认删掉所有白边，那么我们只考虑有边和无边），并在恰好相差一条边的图之间连边。
对于一张图 \(G\)，我们钦定它的最小表示为，对于所有结点，计算它的度数 \(d\)，和所有邻居度数组成的可重集 \(d'\)，对于所有点按二元组 \((d, d')\) 从小到大排序，然后按照 \((d, d')\) 划分等价类，对于同一个等价类中的点，我们直接阶乘枚举全排列，最后考虑重标号后的邻接矩阵，我们取字典序最小的邻接矩阵作为图的最小表示。然后我们认为两张图 \(G_0, G_1\) 同构，当且仅当他们的最小表示相等。
知道如何判断图的同构后，我们对于所有图按照 \(|E|\) 分层，容易发现只有相邻层之间有连边，所以考虑从当前层 \(|E| = e\) 转移到下一层 \(|E| = e + 1\)，枚举当前层的一张图，在它上面任加一条边，然后判断一下这张新图是否已经有了即可。
复杂度可能不太好分析，但是我们有自动机上点数最大为 \(12346\)，转移数最大为 \(172844\)。
Code
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_set>
#include <chrono>
#include <array>
using namespace std;
using uLL = unsigned long long;
uLL Get_time () {
return chrono::steady_clock::now().time_since_epoch().count();
}
namespace State_automaton {
int n;
struct G {
struct State {
uLL es;
bool Get (int i, int j) {
return ((es >> (i << 3)) >> j) & 1;
}
void Add (int i, int j) {
es |= (1ull << (((i << 3) | j)));
es |= (1ull << (((j << 3) | i)));
}
State () : es(0) {}
State (uLL _es) : es(_es) {}
void Rebuild () {
vector<int> deg(n);
vector<uLL> cdeg(n);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (Get(i, j)) ++deg[i], ++deg[j];
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (Get(i, j)) {
cdeg[i] += 1ull << (deg[j] * 3);
}
}
}
auto cmp = [&](int i, int j) -> bool {
return deg[i] < deg[j] || deg[i] == deg[j] && cdeg[i] < cdeg[j];
};
vector<int> p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), cmp);
vector<int> rk(n);
rk[0] = 0;
for (int i = 1; i < n; ++i) {
rk[p[i]] = rk[p[i - 1]] + cmp(p[i - 1], p[i]);
}
int tot = rk[p[n - 1]] + 1;
vector<vector<int>> vec(tot);
for (int i = 0; i < n; ++i) {
vec[rk[i]].push_back(i);
}
uLL mi = -1;
auto Dfs = [&](auto &self, int x) -> void {
if (x == tot) {
vector<int> per;
for (int i = 0; i < tot; ++i) {
for (auto j : vec[i]) {
per.push_back(j);
}
}
uLL news = 0;
for (int i = n - 1; ~i; --i) {
for (int j = n - 1; j > i; --j) {
if (Get(per[i], per[j])) {
news |= (1ull << (((i << 3) | j)));
news |= (1ull << (((j << 3) | i)));
}
}
}
mi = min(mi, news);
return;
}
sort(vec[x].begin(), vec[x].end());
do {
self(self, x + 1);
} while (next_permutation(vec[x].begin(), vec[x].end()));
};
Dfs(Dfs, 0);
es = mi;
}
};
int tot;
vector<unordered_set<int>> e;
vector<State> s;
vector<array<array<int, 5>, 5>> g;
int New_Node (State a) {
e.push_back(unordered_set<int>());
s.push_back(a);
g.push_back({});
vector<vector<int>> dis(n, vector<int>(n));
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
g.back()[i][j] = 0;
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
dis[x][y] = (x == y ? 0 : (a.Get(x, y) ? i + 1 : j + 1));
}
}
for (int z = 0; z < n; ++z) {
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
dis[x][y] = min(dis[x][y], dis[x][z] + dis[z][y]);
}
}
}
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
g.back()[i][j] += dis[x][y];
}
}
}
}
return tot++;
}
void Add_edge (int u, int v) {
e[u].insert(v);
e[v].insert(u);
}
void Init () {
vector<pair<State, int>> now{{State(), New_Node(State())}};
for (int k = 1; k <= n * (n - 1) / 2; ++k) {
map<uLL, int> p;
for (auto i : now) {
State s = i.first;
int id = i.second;
for (int x = 0; x < n; ++x) {
for (int y = x + 1; y < n; ++y) {
if (!s.Get(x, y)) {
State t = s;
t.Add(x, y);
t.Rebuild();
auto it = p.find(t.es);
if (it != p.end()) {
Add_edge(id, it->second);
}
else {
it = p.insert({t.es, New_Node(t)}).first;
Add_edge(id, it->second);
}
}
}
}
}
now.clear();
for (auto i : p) {
now.push_back(pair<State, int>({State({i.first}), i.second}));
}
}
}
} g[7];
void Init () {
for (int i = 0; i < 7; ++i) {
n = i + 2, g[i].Init();
}
}
}
const int M = 305, S = 12346;
const int Inf = 1e9;
int n, m;
int f[M][S];
int a[M], b[M];
int main () {
cin.tie(0)->sync_with_stdio(0);
uLL st0 = Get_time();
State_automaton::Init();
int T;
cin >> T;
while (T--) {
cin >> n >> m;
auto &mg = State_automaton::g[n - 2];
for (int i = 1; i <= m; ++i) {
cin >> a[i] >> b[i];
--a[i], --b[i];
}
for (int i = 0; i < mg.tot; ++i) {
f[m + 1][i] = 0;
}
for (int i = m; i; --i) {
for (int s = 0; s < mg.tot; ++s) {
f[i][s] = -Inf;
for (auto t : mg.e[s]) {
f[i][s] = max(f[i][s], mg.g[t][a[i]][b[i]] - f[i + 1][t]);
}
}
}
cout << f[1][mg.tot - 1] << '\n';
}
uLL ed0 = Get_time();
// cerr << "Time0 = " << (ed0 - st0) / int(1e6) << '\n';
return 0;
}
T1003 最优 K 子段(HDU 7471)
首先可以二分，转化成判断是否存在不相交的 \(k\) 个长度为质数的子段，满足这 \(k\) 段的和都 \(\ge x\)。
考虑贪心，每次我们在合法的子段中选一个最靠左的肯定不劣。所以从左往右扫一遍，相当于每次将 \(r \gets r + 1\)，你需要判断是否存在 \(l \in [minl, r]\) 使得子段 \([l, r]\) 合法。有 \(minl\) 的限制是因为不能和之前的子段重合。
做前缀和 \(s_i = \sum\limits_{k = 1}^{i} a_k\)，那么一个子段中所有数的和可以表示为 \(s_r - s_{l - 1}\)，容易发现如果没有子段长度为质数的限制是好做的，因为我们固定右端点 \(r\) 后，必定会选使得 \(s_{l - 1}\) 最小的 \(l\)。但加入质数的限制后这样可能会使 \([l, r]\) 的长度不为质数，所以只记一个决策点肯定是不行的。
考虑用 \(\text{set}\) 按照 \(s_{l - 1}\) 从小到大维护所有决策点 \(l\)，查询一个 \(r\) 时在 \(\text{set}\) 上暴力跳，由于素数密度，期望跳 \(O(\log n)\) 次就可以跳到一个质数。注意这个 \(\log\) 是素数密度，而不是 \(s\) 的单调栈期望长度，后者是假的。
时间复杂度 \(O(n \log n \log V)\)。
Code
#include <iostream>
#include <vector>
#include <set>
using namespace std;
using Pii = pair<int, int>;
const int N = 2e5 + 5;
const int Inf = 1e9;
int n, k;
int a[N], pre[N];
bool is_prime[N];
vector<int> prime;
bool check (int x) {
set<Pii> s;
int cnt = 0;
for (int i = 1; i <= n; ++i) {
int maxv = [&]() -> int {
for (auto j : s) {
if (is_prime[i - j.second]) {
return pre[i] - j.first;
}
}
return -Inf;
}();
s.insert({pre[i - 1], i - 1});
if (maxv >= x) {
++cnt;
s.clear();
}
}
return cnt >= k;
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
fill(is_prime + 2, is_prime + N, 1);
for (int i = 2; i < N; ++i) {
if (is_prime[i]) {
for (int j = i * 2; j < N; j += i) {
is_prime[j] = 0;
}
}
}
int T;
cin >> T;
while (T--) {
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i], pre[i] = pre[i - 1] + a[i];
}
const int low = -2e3, hig = 2e8;
int ansl = low, ansr = hig;
while (ansl <= ansr) {
int ansm = (ansl + ansr) >> 1;
if (check(ansm)) {
ansl = ansm + 1;
}
else {
ansr = ansm - 1;
}
}
if (ansr == low - 1) {
cout << "impossible" << '\n';
}
else {
cout << ansr << '\n';
}
}
return 0;
}
T1004 分组(HDU 7472)
考虑把四个集合分成两部分，每部分两个集合，分别算一个答案，然后用一些优化技巧拼起来，大概相当于 Meet in the middle。
设 \(f_{S, v}\) 表示我们划分出一个部分 \(S\)，是否能在内部选出一个异或和为 \(v\) 的集合，直接转移即可。
枚举 \(L \cup R = [1, n]\)，表示划分的两个部分，对于部分 \(L\)，通过 \(f\) 数组可以知道是否可以进一步划分出两个集合，使它们的异或和分别为 \(A, B\)，对于 \(R\) 类似，有许多 \(C, D\) 可供选择，直接这样暴力做是 \(O(2^{n + 2m})\) 的。
不妨钦定 \(w_A \ge w_B, w_C \ge w_D\)，这样一种方案的代价就是 \(\max(w_A, w_C) - \min(w_B, w_D)\)，枚举 \(A\) 并分类讨论：
- 对于 \(w_A \ge w_C\)，答案为 \(w_A - \min(w_B, w_D)\) 显然我们只需知道最大的 \(w_D\)，设 \(s_i\) 表示 \(w_C = i\) 时的最大 \(w_D\)，我们所查询的相当于 \(s\) 的一段前缀 \(\max\)。
- 对于 \(w_A < w_C\) 类似。
我们可以对 \(w\) 排序，然后前缀优化一下即可。
时间复杂度 \(O(2^{n + m})\)。
Code
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
const int N = 18, NS = (1 << N);
const int M = 10, MS = (1 << M);
const int Inf = 1e9;
int n, m;
int a[N], w[MS], p[MS], rk[MS];
int s[MS], pres[MS], t[MS], pret[MS];
bitset<MS> f[NS];
int main () {
cin.tie(0)->sync_with_stdio(0);
int T;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < (1 << m); ++i) {
cin >> w[i], p[i] = i;
}
sort(p, p + (1 << m), [&](int i, int j) -> bool {
return w[i] < w[j];
});
for (int i = 0; i < (1 << m); ++i) {
rk[p[i]] = i;
}
for (int s = 0; s < (1 << n); ++s) {
f[s].reset();
}
f[0][0] = 1;
for (int s = 1; s < (1 << n); ++s) {
int x = -1;
for (int i = 0; i < n; ++i) {
if ((s >> i) & 1) {
x = i;
break;
}
}
int t = s ^ (1 << x);
for (int i = 0; i < (1 << m); ++i) {
if (f[t][i]) {
f[s][i] = 1, f[s][i ^ a[x]] = 1;
}
}
}
int ans = Inf;
for (int L = 0; L < (1 << n); L += 2) {
int R = ((1 << n) - 1) ^ L, Ls = 0, Rs = 0;
for (int i = 0; i < n; ++i) {
((L >> i) & 1 ? Ls : Rs) ^= a[i];
}
fill(s, s + (1 << m), -1);
fill(t, t + (1 << m), -1);
fill(pres, pres + (1 << m), -1);
fill(pret, pret + (1 << m), -1);
for (int wa = 0; wa < (1 << m); ++wa) {
if (!f[L][wa]) continue;
int wb = Ls ^ wa;
if (rk[wb] > rk[wa]) continue;
s[rk[wa]] = max(s[rk[wa]], rk[wb]);
}
for (int wc = 0; wc < (1 << m); ++wc) {
if (!f[R][wc]) continue;
int wd = Rs ^ wc;
if (rk[wd] > rk[wc]) continue;
t[rk[wc]] = max(t[rk[wc]], rk[wd]);
}
pres[0] = s[0], pret[0] = t[0];
for (int i = 1; i < (1 << m); ++i) {
pres[i] = max(s[i], pres[i - 1]);
pret[i] = max(t[i], pret[i - 1]);
}
for (int i = 0; i < (1 << m); ++i) {
if (s[i] != -1 && pret[i] != -1) {
ans = min(ans, w[p[i]] - w[p[min(s[i], pret[i])]]);
}
if (t[i] != -1 && pres[i] != -1) {
ans = min(ans, w[p[i]] - w[p[min(t[i], pres[i])]]);
}
}
}
cout << ans << '\n';
}
return 0;
}
T1005 多层血条(HDU 7473)
注意到只有在 \([hp - m + 1, hp]\) 范围内的生命值是有用的，其余都会被覆盖掉，暴力处理这一段即可。
Code
#include <iostream>
#include <cassert>
using namespace std;
int main () {
// freopen("1005.in", "r", stdin);
// freopen("1005.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, m, hp, dmg;
cin >> n >> m >> hp >> dmg;
cout << '+' << string(m, '-') << '+' << '\n';
string ans = string(m, ' ');
for (int i = max(1, hp - m + 1); i <= hp; ++i) {
int pos = (i - 1) % m;
char &res = ans[pos];
int cur = (i - 1) / m + 1;
char ch = 'A' + ((cur - 1) % 5);
res = (i >= hp - dmg + 1 ? '.' : ch);
}
assert(int(ans.size()) == m);
for (int i = 1; i <= n; ++i) {
cout << '|' << ans << '|' << '\n';
}
cout << '+' << string(m, '-') << '+' << '\n';
}
return 0;
}
T1006 延时操控(HDU 7474)
首先延时移动显然不好做，考虑将敌方的操作提前 \(k\) 回合，不影响答案，相当于我们要在 \(m - k\) 回合打败敌方，然后接着随机游走 \(k\) 步，我们将这两部分分开计算。
注意到敌方会和己方在同一个方向移动，除非它受到了伤害。由于它受到的伤害不超过 \(hp\)，所以它与己方相对位置的变化量（较初始的相对位置而言）不超过 \(hp\)，所以设 \(f_{i, x_1, y_1, tx, ty, d}\) 表示经过 \(i\) 个回合，我方位于 \((x_1, y_1)\)，我方与敌方相对位置变化量为 \(tx, ty\)，敌方受到了 \(d\) 点伤害的操作序列数。
设 \(g_{x_1, y_1, k}\) 表示从 \((x_1, y_1)\) 开始游走 \(k\) 步且不能碰到障碍的方案数，计算答案 \(f, g\) 拼一下即可。
时间复杂度 \(O(mn^2hp^3)\)。
Code
#include <iostream>
#include <cstring>
using namespace std;
const int N = 53;
const int Mod = 1e9 + 7;
const int Dx[4] = {0, 0, 1, -1};
const int Dy[4] = {1, -1, 0, 0};
int n, m, t, hp, px, py, ex, ey, dx, dy;
char s[N][N];
int f[N][N][N][11][11][6], g[N][N][N];
int main () {
cin.tie(0)->sync_with_stdio(0);
int T;
cin >> T;
while (T--) {
cin >> n >> m >> t >> hp, m -= t;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> s[i][j];
if (s[i][j] == 'P')
px = i, py = j;
if (s[i][j] == 'E')
ex = i, ey = j;
}
}
for (int i = 0; i <= n + 1; ++i) {
for (int j = 0; j <= n + 1; ++j) {
if (!i || !j || i == n + 1 || j == n + 1)
s[i][j] = '#';
}
}
dx = px - ex, dy = py - ey;
fill(f[0][0][0][0][0], f[m][n][n][hp * 2 + 1][hp * 2 + 1] + hp + 1, 0);
f[0][px][py][hp][hp][0] = 1;
for (int i = 1; i <= m; ++i) {
for (int x1 = 1; x1 <= n; ++x1) {
for (int y1 = 1; y1 <= n; ++y1) {
for (int d = 0; d < hp; ++d) {
for (int tx = -d + hp; tx <= d + hp; ++tx) {
for (int ty = -d + hp; ty <= d + hp; ++ty) {
int x2 = x1 - dx - (tx - hp), y2 = y1 - dy - (ty - hp);
if (x2 <= 0 || x2 > n || y2 <= 0 || y2 > n) continue;
int lstv = f[i - 1][x1][y1][tx][ty][d];
if (!lstv) continue;
for (int k = 0; k < 4; ++k) {
int _x1 = x1 + Dx[k];
int _y1 = y1 + Dy[k];
if (s[_x1][_y1] == '#') continue;
int _x2 = x2 + Dx[k];
int _y2 = y2 + Dy[k];
int _d = d;
if (s[_x2][_y2] == '#')
_x2 = x2, _y2 = y2, ++_d;
int _tx = (_x1 - _x2) - dx + hp, _ty = (_y1 - _y2) - dy + hp;
f[i][_x1][_y1][_tx][_ty][_d] = (f[i][_x1][_y1][_tx][_ty][_d] + lstv) % Mod;
}
}
}
}
}
}
}
memset(g, 0, sizeof(g));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (s[i][j] != '#')
g[i][j][0] = 1;
}
}
for (int k = 1; k <= t; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int d = 0; d < 4; ++d) {
int x = i + Dx[d];
int y = j + Dy[d];
if (s[x][y] != '#')
g[i][j][k] = (g[i][j][k] + g[x][y][k - 1]) % Mod;
}
}
}
}
int ans = 0;
for (int i = 1; i <= m; ++i) {
for (int x1 = 1; x1 <= n; ++x1) {
for (int y1 = 1; y1 <= n; ++y1) {
for (int tx = 0; tx <= hp * 2; ++tx) {
for (int ty = 0; ty <= hp * 2; ++ty) {
ans = (ans + 1ll * f[i][x1][y1][tx][ty][hp] * g[x1][y1][t]) % Mod;
}
}
}
}
}
cout << ans << '\n';
}
return 0;
}
T1007 序列更新(HDU 7475)
考虑对于每个位置独立算答案。每个位置暴力做 \(\sqrt n\) 次操作，做完这些操作后期望只有 \(O(\sqrt n)\) 种数字大于当前最大值，算这些数字最早什么时候对这个位置有贡献即可。
时间复杂度 \(O(n \sqrt n)\)。
Code
#include <iostream>
#include <numeric>
#include <algorithm>
#include <cmath>
using namespace std;
using LL = long long;
const int N = 2.5e5 + 5;
int n, m;
int a[N], b[N], ok[N], fs[N], p[N];
LL ans[N];
int main () {
// freopen("1007.in", "r", stdin);
// freopen("1007.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
cin >> b[i];
}
iota(p + 1, p + n + 1, 1);
auto cmp = [&](int i, int j) -> bool {
return b[i] < b[j];
};
sort(p + 1, p + n + 1, cmp);
fill(fs, fs + n, n + 1);
for (int i = 1; i <= m; ++i) {
cin >> ok[i], fs[ok[i]] = min(fs[ok[i]], i);
}
fill(ans, ans + m + 1, 0);
auto add = [&](int l, int r, int x) -> void {
ans[l] += x, ans[r + 1] -= x;
};
int d = min(int(sqrt(n)), m);
for (int i = 1; i <= n; ++i) {
int now = a[i];
for (int j = 1; j <= d; ++j) {
now = max(now, b[(i + ok[j] - 1) % n + 1]);
add(j, j, now);
}
auto cmp = [&](int i, int j) -> bool {
return b[i] < j;
};
int low = lower_bound(p + 1, p + n + 1, now, cmp) - p, ed = n;
for (int j = n; j >= low; --j) {
int id = p[j];
int abl = max(d + 1, fs[(id - i + n) % n]);
if (abl <= ed) {
add(abl, ed, b[id]);
ed = abl - 1;
}
}
add(d + 1, ed, now);
}
for (int i = 1; i <= m; ++i) {
ans[i] += ans[i - 1];
cout << ans[i] << '\n';
}
}
return 0;
}
T1008 魔法卡牌(HDU 7476)
不会。
T1009 昵称检索(HDU 7477)
对于每一个昵称算包含它的最短前缀 \([1, x]\)，对于每一个日期算包含它的最短后缀 \([y, n]\)，一对昵称-日期会产生 \(1\) 的贡献当且仅当 \(x < y\)，做一个前缀和即可快速计算。
时间复杂度 \(O(n + m + \sum |name|)\)。
Code
#include <iostream>
using namespace std;
const int N = 1e6 + 5;
int n, m;
int la[N][10], nx[N][26], suf[N];
string s;
int main () {
// freopen("1009.in", "r", stdin);
// freopen("1009.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T;
cin >> T;
while (T--) {
cin >> m >> n >> s, s = " " + s;
for (int i = 1; i <= n; ++i) {
copy(la[i - 1], la[i - 1] + 10, la[i]);
if (s[i] >= '0' && s[i] <= '9') {
la[i][s[i] - '0'] = i;
}
}
const int days[12] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
auto get_string = [&](int x) -> string {
return to_string(x / 10) + to_string(x % 10);
};
fill(suf, suf + n + 2, 0);
for (int month = 1; month <= 12; ++month) {
for (int day = 1; day <= days[month - 1]; ++day) {
string goal = get_string(month) + get_string(day);
int pos = n + 1;
for (int i = 3; pos && ~i; --i) {
int x = goal[i] - '0';
pos = la[pos - 1][x];
}
++suf[pos];
}
}
for (int i = n; i; --i) {
suf[i] += suf[i + 1];
}
fill(nx[n + 1], nx[n + 1] + 26, n + 1);
for (int i = n; i; --i) {
copy(nx[i + 1], nx[i + 1] + 26, nx[i]);
if (s[i] >= 'a' && s[i] <= 'z') {
nx[i][s[i] - 'a'] = i;
}
}
int ans = 0;
for (string s; m--; ) {
cin >> s;
int pos = 0;
for (auto c : s) {
int x = c - 'a';
pos = nx[pos + 1][x];
if (pos >= n) break;
}
if (pos + 1 <= n) ans += suf[pos + 1];
}
cout << ans << '\n';
}
return 0;
}
T1010 矩阵的周期(HDU 7478)
不会。
T1011 找环(HDU 7479)
不会。
T1012 寻找宝藏(HDU 7480)
设 \(f_i\) 表示从 \((0, 0)\) 走到第 \(i\) 个宝藏的位置，能获得的最大收益，\(g_i\) 表示从 \((n + 1, n + 1)\) 走到第 \(i\) 个宝箱的位置，能获得的最大收益，这个都容易用树状数组优化求出。
考虑一个禁区矩形 \([x_1, x_2] \times [y_1, y_2]\)，答案有可能是来自以下四种情况：
-
选一个坐标为 \([1, x_1) \times (y_2, n]\) 的点 \(A\)，答案为 \(f_A + g_A - v_A\)。
-
选一个坐标为 \((x_2, n] \times [1, y_1)\) 的点 \(A\)，答案为 \(f_A + g_A - v_A\)。
-
选一个坐标为 \([1, x_1) \times [1, y_2]\) 的点 \(A\)，再选一个坐标为 \([x_1, n] \times (y_2, n]\) 的点 \(B\)，答案为 \(f_A + g_B\)。
-
选一个坐标为 \([1, x_2] \times [1, y_1)\) 的点 \(A\)，再选一个坐标为 \((x_2, n] \times [y_1, n]\) 的点 \(B\)，答案为 \(f_A + g_B\)。
注意到后两种情况 \(A\) 和 \(B\) 的选取是独立的，所以还是相当于二位数点问题，扫描线 + 树状数组即可。
时间复杂度 \(O(n \log n)\)。
Code
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
const int N = 3e5 + 5;
int n, m;
int p[N], v[N];
LL f[N], g[N], c[N], ans[N], sum1[N], sum2[N];
int x1[N], x2[N], y1[N], y2[N];
vector<int> vx1[N], vx2[N];
void Insert (int x, LL y) {
for (; x <= n; x += (x & -x)) {
c[x] = max(c[x], y);
}
}
LL Query (int x) {
LL res = 0;
for (; x; x -= (x & -x)) {
res = max(res, c[x]);
}
return res;
}
int main () {
cin.tie(0)->sync_with_stdio(0);
int T;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> p[i] >> v[i];
}
fill(c, c + n + 1, 0);
for (int i = 1; i <= n; ++i) {
f[i] = Query(p[i]) + v[i];
Insert(p[i], f[i]);
}
fill(c, c + n + 1, 0);
for (int i = n; i; --i) {
g[i] = Query(n - p[i] + 1) + v[i];
Insert(n - p[i] + 1, g[i]);
}
fill(vx1 + 1, vx1 + n + 1, vector<int>());
fill(vx2 + 1, vx2 + n + 1, vector<int>());
for (int i = 1; i <= m; ++i) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
vx1[x1[i]].push_back(i);
vx2[x2[i]].push_back(i);
}
fill(ans + 1, ans + m + 1, 0);
fill(sum1 + 1, sum1 + m + 1, 0);
fill(sum2 + 1, sum2 + m + 1, 0);
fill(c, c + n + 1, 0);
for (int i = 1; i <= n; ++i) {
for (auto j : vx1[i]) {
ans[j] = max(ans[j], Query(n - y2[j]));
}
Insert(n - p[i] + 1, f[i] + g[i] - v[i]);
}
fill(c, c + n + 1, 0);
for (int i = n; i; --i) {
for (auto j : vx2[i]) {
ans[j] = max(ans[j], Query(y1[j] - 1));
}
Insert(p[i], f[i] + g[i] - v[i]);
}
fill(c, c + n + 1, 0);
for (int i = 1; i <= n; ++i) {
for (auto j : vx1[i]) {
sum1[j] += Query(y2[j]);
}
Insert(p[i], f[i]);
}
fill(c, c + n + 1, 0);
for (int i = n; i; --i) {
Insert(n - p[i] + 1, g[i]);
for (auto j : vx1[i]) {
sum1[j] += Query(n - y2[j]);
}
}
fill(c, c + n + 1, 0);
for (int i = 1; i <= n; ++i) {
Insert(p[i], f[i]);
for (auto j : vx2[i]) {
sum2[j] += Query(y1[j] - 1);
}
}
fill(c, c + n + 1, 0);
for (int i = n; i; --i) {
for (auto j : vx2[i]) {
sum2[j] += Query(n - y1[j] + 1);
}
Insert(n - p[i] + 1, g[i]);
}
for (int i = 1; i <= m; ++i) {
cout << max(ans[i], max(sum1[i], sum2[i])) << '\n';
}
}
return 0;
}