前天晚上打得一场，没想到神仙特别多，把我这个卡在 D 题的小 sb 直接区分出来了，害。
D – Shortest and Longest LIS
这题在考场上卡了很久，直接送掉了前 500 的资格。我们可以预处理出所有连续上升的段，然后对于 LIS 最小的情况，我们只需要强行把后方的上升段的最大值强行设置为小与上一段的最小值。这样做就可以解决第一个问题。第二个问题我们只需要反转串和答案即可。
// D.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 200;
int T, n, ans1[MAX_N];
char str[MAX_N];
bool vis_in[MAX_N], vis_out[MAX_N];
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%s", &n, str + 1);
for (int rd = 0; rd <= 1; rd++)
{
memset(vis_in, 0, sizeof(vis_in)), memset(vis_out, 0, sizeof(vis_out));
for (int i = 1, last_ptr = -1; i <= n; i++)
{
if (str[i] == '<' && last_ptr == -1)
last_ptr = i;
else if ((str[i] == '>' || i == n) && last_ptr != -1)
vis_in[last_ptr] = true, vis_out[i] = true, last_ptr = -1;
}
stack<int> ans, tmp;
for (int i = n, flag = 0; i >= 1; i--)
{
if (vis_in[i])
{
ans.push(i);
while (!tmp.empty())
ans.push(tmp.top()), tmp.pop();
flag = 0;
}
else if (vis_out[i])
flag = 1, tmp.push(i);
else if (flag)
tmp.push(i);
else
ans.push(i);
}
for (int i = n; i >= 1; i--)
ans1[ans.top()] = i, ans.pop();
if (rd == 1)
reverse(ans1 + 1, ans1 + 1 + n);
for (int i = 1; i <= n; i++)
printf("%d ", ans1[i]);
puts("");
reverse(str + 1, str + n);
for (int i = 1; i <= n - 1; i++)
if (str[i] == '>')
str[i] = '<';
else
str[i] = '>';
// printf("%s\n", str + 1);
}
}
return 0;
}
E – 1-Trees and Queries
真的就 nm 傻逼题？
对于 \(x, y, a, b, k\)，我们可以讨论多种情况，然后判断奇偶性即可。
// E.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200;
int head[MAX_N], current, n, q, dep[MAX_N], fa[20][MAX_N];
struct edge
{
int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
edges[current].to = dst, edges[current].nxt = head[src];
head[src] = current++;
}
void dfs(int u)
{
dep[u] = dep[fa[0][u]] + 1;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa[0][u])
fa[0][edges[i].to] = u, dfs(edges[i].to);
}
int getLCA(int x, int y)
{
if (dep[x] < dep[y])
swap(x, y);
for (int i = 19; i >= 0; i--)
if (dep[fa[i][x]] >= dep[y])
x = fa[i][x];
if (x == y)
return x;
for (int i = 19; i >= 0; i--)
if (fa[i][x] != fa[i][y])
x = fa[i][x], y = fa[i][y];
return fa[0][x];
}
int getDist(int x, int y) { return dep[x] + dep[y] - (dep[getLCA(x, y)] << 1); }
int main()
{
memset(head, -1, sizeof(head));
scanf("%d", &n);
for (int i = 1, u, v; i <= n - 1; i++)
scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
dfs(1), scanf("%d", &q);
for (int i = 1; i <= 19; i++)
for (int j = 1; j <= n; j++)
fa[i][j] = fa[i - 1][fa[i - 1][j]];
while (q--)
{
int x, y, a, b, k;
scanf("%d%d%d%d%d", &x, &y, &a, &b, &k);
int org = getDist(a, b);
int loop = min(getDist(a, x) + getDist(y, b), getDist(a, y) + getDist(x, b)) + 1;
int loop_1 = getDist(x, y) + getDist(a, x) + getDist(b, x) + 1;
int loop_2 = getDist(x, y) + getDist(a, y) + getDist(b, y) + 1;
int ans = 2e9;
if ((org % 2) == (k % 2))
ans = org;
if ((loop % 2) == (k % 2))
ans = min(ans, loop);
if ((loop_1 % 2) == (k % 2))
ans = min(ans, loop_1);
if ((loop_2 % 2) == (k % 2))
ans = min(ans, loop_2);
puts(ans <= k ? "YES" : "NO");
}
return 0;
}
F – Animal Observation
这题也贼 sb。我们每行每列做 \(dp[i][j]\)，然后用线段树维护上一行的 DP 值，并每次线段 \((i, j), (i, j + k – 1)\)进行移动时，将前后两个位置的值放入线段树，消掉或加上其贡献即可。
// F2.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e4 + 200;
int log2_arr[MAX_N], n, m, k, mp[55][MAX_N], dp[55][MAX_N], pre[55][MAX_N];
int nodes[MAX_N << 2], tag[MAX_N << 2];
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)
void pushdown(int p)
{
if (tag[p] != 0)
{
nodes[lson] += tag[p], nodes[rson] += tag[p];
tag[lson] += tag[p], tag[rson] += tag[p];
tag[p] = 0;
}
}
void pushup(int p) { nodes[p] = max(nodes[lson], nodes[rson]); }
void build(int l, int r, int p, int *src)
{
tag[p] = 0;
if (l == r)
return (void)(nodes[p] = src[l], tag[p] = 0);
build(l, mid, lson, src), build(mid + 1, r, rson, src);
pushup(p);
}
void update(int ql, int qr, int l, int r, int p, int val)
{
if (ql <= l && r <= qr)
return (void)(nodes[p] += val, tag[p] += val);
pushdown(p);
if (ql <= mid)
update(ql, qr, l, mid, lson, val);
if (mid < qr)
update(ql, qr, mid + 1, r, rson, val);
pushup(p);
}
int query(int ql, int qr, int l, int r, int p)
{
if (ql <= l && r <= qr)
return nodes[p];
pushdown(p);
int ret = -2e9;
if (ql <= mid)
ret = max(ret, query(ql, qr, l, mid, lson));
if (mid < qr)
ret = max(ret, query(ql, qr, mid + 1, r, rson));
return ret;
}
#undef mid
#undef rson
#undef lson
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &mp[i][j]), pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + mp[i][j];
for (int i = 1; i <= m; i++)
pre[n + 1][i] = pre[n][i];
for (int i = 1; i <= n; i++)
{
build(1, m - k + 1, 1, dp[i - 1]);
for (int j = 1; j <= k; j++)
update(max(1, j - k + 1), j, 1, m - k + 1, 1, -mp[i][j]);
for (int j = 1; j <= m - k + 1; j++)
{
// the interval is [j, min(j + k - 1, m)]
int rig = j + k - 1, block = pre[i + 1][rig] - pre[i + 1][j - 1] - pre[i - 1][rig] + pre[i - 1][j - 1];
dp[i][j] = block + (i == 1 ? 0 : nodes[1]);
update(max(1, j - k + 1), j, 1, m - k + 1, 1, mp[i][j]);
if (rig != m)
update(max(1, rig - k + 2), min(rig + 1, m - k + 1), 1, m - k + 1, 1, -mp[i][rig + 1]);
}
}
int ans = 0;
for (int i = 1; i + k - 1 <= m; i++)
ans = max(ans, dp[n][i]);
printf("%d\n", ans);
return 0;
}
妈的，为啥会被 D 题给卡啊，日了狗。