B. Tairitsu
首先很容易想到一个加边后 DAG 上 DP 的做法。这个做法是 (O(n^2)) 的，考虑如何优化。
DAG 上 DP 的本质是一种刷表法，如果我们换成填表法会不会好一些呢？
设 (f(i)) 表示以 (i) 结尾的最长合法子序列的长度，(O(n^2)) 转移的时候相当于是这个位置可以从前面所有合法位置转移过来，如果出现一大串重复字符会变得非常慢。
注意到一个性质，两个相同的字符，后一个的答案一定不比前一个的答案更劣。这个东西很显然，因为后一个字符也可以继承前一个字符之前的那一串，而且这两个之间夹着的地方有可能对答案有贡献。
所以我们直接从该字符最后一次出现的地方转移就好了。
const int MAXN = 5e5 + 10;
int n, m;
std::string ss;
std::vector<std::string> vs;
namespace Task80 {
std::vector<int> G[MAXN];
std::vector<int> idx[27];
int ind[MAXN];
void addEdge(int u, int v) {
G[u].push_back(v); ++ind[v];
}
int dp[MAXN];
void DP() {
std::queue<int> q;
for (int i = 1; i <= n; ++i) if (!ind[i]) { q.push(i); dp[i] = 1; }
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto v : G[u]) {
dp[v] = std::max(dp[v], dp[u] + 1);
--ind[v];
if (!ind[v]) q.push(v);
}
}
}
void _main() {
for (int i = 1; i <= n; ++i) {
idx[ss[i - 1] - 'a'].push_back(i);
}
for (auto vv : vs) {
for (auto u : idx[vv[0] - 'a']) {
for (auto v : idx[vv[1] - 'a']) {
if (v > u) addEdge(u, v);
}
}
}
DP();
cout << *std::max_element(dp + 1, dp + 1 + n) << endl;
}
}
namespace TaskAC {
int dp[MAXN];
int last[27];
std::vector<int> G[27];
void _main() {
for (auto sx : vs) {
G[sx[1] - 'a'].push_back(sx[0] - 'a');
}
rep (i, 1, n) {
dp[i] = 1;
for (auto v : G[ss[i - 1] - 'a']) {
dp[i] = std::max(dp[i], dp[last[v]] + 1);
}
last[ss[i - 1] - 'a'] = i;
}
cout << *std::max_element(dp + 1, dp + 1 + n) << endl;
}
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
cin >> ss;
rep (i, 1, m) {
std::string sx; cin >> sx; vs.push_back(sx);
}
TaskAC::_main();
return 0;
}
C. Guiding Star
很容易想到考虑加入一个点给答案造成的增量，接下来就是去快速维护以某点为中心的一个菱形上的点的个数。
这个东西直接维护很难，但是我们可以把它拆成四条线段，分别属于四条对角线，相当于是在对角线上做区间查询。
使用树状数组维护所有对角线即可。
const int MAXN = 1e5 + 10;
const int MAXL = 2e3 + 10;
int n, k;
namespace Task40 {
std::pair<int, int> nodes[MAXN];
void _main() {
int ans = 0;
for (int cas = 1; cas <= n; ++cas) {
int x = read(); int y = read();
rep (i, 1, cas - 1) {
ans += (std::abs(nodes[i].fi - x) + std::abs(nodes[i].se - y) == k);
}
nodes[cas] = {x, y};
printf("%d
", ans);
}
}
}
namespace TaskAC {
static const int MAXX = MAXL + MAXL;
struct BIT {
static const int UP = MAXX - 20;
lli seq[MAXX];
#define lb(x) (x & (-x))
void mod(int x) { for (; x <= UP; x += lb(x)) ++seq[x]; }
lli qry(int x) {
lli r = 0; for (; x; x -= lb(x)) r += seq[x]; return r;
}
lli qrg(int x, int y) { return qry(y) - qry(x - 1); }
} bp[MAXX << 1], bm[MAXX << 1];
// bp[a] : a = x + y
// bm[a] : a = x - y + offset
// b[][i]: x = 0 to x = i
void _main() {
lli ans = 0;
for (int cas = 1; cas <= n; ++cas) {
int x = read(); int y = read();
// upper right segment
ans += bp[x + y + k].qrg(x, x + k);
// lower right segment
ans += bm[(x + k - y) + MAXX].qrg(x, x + k);
// lower left segment
if (x + y > k) ans += bp[x + y - k].qrg(std::max(1, x - k), x);
// upper left segment
ans += bm[(x - k - y) + MAXX].qrg(std::max(1, x - k), x);
ans -= bp[x + y + k].qrg(x, x); // (x, y + k)
if (x - k >= 1 && x + y > k) ans -= bp[x + y - k].qrg(x - k, x - k); // (x - k, y) if exist
ans -= bm[(x + k - y) + MAXX].qrg(x + k, x + k); // (x + k, y)
if (x + y > k) ans -= bp[x + y - k].qrg(x, x); // (x, y - k) whatever it exists or not
bp[x + y].mod(x); bm[x - y + MAXX].mod(x);
printf("%lld
", ans);
}
}
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
n = read(); k = read();
TaskAC::_main();
return 0;
}
E. Vicious Labyrinth
建反图，跑从 n 到 1 的最短路，遇到陷阱点就把路径长乘 2.
const int MAXN = 5e5 + 10;
const int MAXS = 20 + 5;
int n, m, s;
int sps[MAXS]; bool issps[MAXN];
struct E {
int v; lli w;
bool operator < (const E &th) const { return w > th.w; }
}; std::vector<E> G[MAXN];
lli dist[MAXN];
void sp(int st) {
static bool vis[MAXN];
for (int i = 1; i <= n; ++i) {
dist[i] = (1ll << 60);
vis[i] = 0;
}
std::priority_queue<E> q;
q.push({st, dist[st] = 0});
while (!q.empty()) {
int u = q.top().v; q.pop();
if (vis[u]) continue;
vis[u] = true;
forall (G[u], i) {
int v = G[u][i].v; lli w = G[u][i].w;
lli nxt = dist[u] + w;
if (issps[v]) nxt *= 2;
if (dist[v] > nxt) {
dist[v] = nxt;
q.push({v, dist[v]});
}
}
}
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
n = read(); m = read(); s = read();
rep (i, 1, s) {
sps[i] = read();
issps[sps[i]] = true;
}
rep (i, 1, m) {
int u = read(); int v = read(); lli w = read();
G[v].push_back({u, w});
}
sp(n);
printf("%lld
", dist[1]);
return 0;
}