第四场¶
2022/07/28 周四
上周二的心态爆炸之后，
Rank Author Solved Penalty 1001 1002 1003 1004 1005 1006 1007 1008 1009 team1157 2 01:15:14 (-4) 00:29:17 00:45:57 总榜 726，大学榜 601，队内 11。照这个成绩根本进不了区域赛。
| Problem ID | Title | Ratio (Accepted / Submitted) |
|---|---|---|
| 1001 | Link with Bracket Sequence II | 29.43% |
| 1002 | Link with Running | 4.85% (199/4105) |
| 1003 | Magic | 49.78% (113/227) |
| 1004 | Link with Equilateral Triangle | 53.97% (1013/1877) |
| 1005 | Link with Level Editor II | 18.11% (132/729) |
| 1006 | BIT Subway | 37.86% (1059/2797) |
| 1007 | Climb Stairs | 26.47% (724/2735) |
| 1008 | Fight and upgrade | 4.55% (3/66) |
| 1009 | Fall with Full Star | 10.76% (38/353) |
| 1010 | Fall with Intersection | 4.57% (10/219) |
| 1011 | Link is as bear | 23.56% (524/2224) |
1001 Link with Bracket Sequence II¶
考场上挠着脑子想了半天一点思路都没有，vagrt 想到了一个数组的区间 DP，但实在想不到下一步了。括号序列问题需要强化。
区间 DP。
设 \(f_{i,j}\) 表示 \([i, j]\) 为合法序列且 \(i, j\) 上括号相匹配的方案数，\(g_{i, j}\) 表示 \([i, j]\) 区间形成一个合法括号序列的方案数。初始状态 \(g_{2k, 2k+1} = 1\)。
最外层枚举长度 \(len\)。
内层枚举左端点 \(l\)，可知右端点 \(r\)。
设 \(e\) 为使得 \(l, r\) 上括号相匹配的方案数，
一般地，
答案取 \(g_{1, n}\)。
时间复杂度 \(O(n^3)\)。
void solve() {
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
if (n & 1) {
puts("0");
return;
}
for (int i = 0; i <= n; i++) {
g[i + 1][i] = 1;
}
for (int len = 2; len <= n; len += 2) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
if (a[l] >= 0 && a[r] <= 0) {
int e;
if (a[l] == 0 && a[r] == 0) {
e = m;
} else if (a[l] == 0 || a[r] == 0) {
e = 1;
} else if (a[l] + a[r] == 0) {
e = 1;
} else {
e = 0;
}
f[l][r] = (ll)g[l + 1][r - 1] * e % mod;
}
for (int nl = l; nl <= r; nl += 2) {
g[l][r] = (g[l][r] + (ll)g[l][nl - 1] * f[nl][r]) % mod;
}
}
}
printf("%d\n", g[1][n]);
}1002 Link with Running¶
题意：小明在公园里跑步，公园有 \(n\) 个结点和 \(m\) 条有向边，从点 \(1\) 跑到点 \(n\)。跑过第 \(i\) 条边时，会消耗 \(e_i\) 点能量并得到 \(p_i\) 点健康。
小明打算在消耗最少能量 \(E\) 的前提下得到最多的健康 \(P\)。
赛场上 coder 写了一个 dijkstra，重写堆的比较函数，先出 \(e_i\) 小且 \(p_i\) 大的边，WA 了。
忘了是哪道题有 \(0\) 圈，我说 tarjan 缩点，vagrt 转手就拿出 tarjan 的板子。太强了。
还是得准备好封装性良好的板子。
在最短路图上跑最长路
- 可能有 \(0\) 圈，tarjan 缩点，变成 \(G_e\)。
- 先用 dijkstra 在 \(G_e\) 上跑出 \(e_i\) 的最短路，计算出 \(E\) 并获得新图 \(G_p\)
- 在 \(G_p\) 上跑最长路，得到 \(P\)。
#include <algorithm>
#include <cstdio>
#include <functional>
#include <queue>
#include <stack>
#include <vector>
#define MN 100000
using std::function;
using std::greater;
using std::max;
using std::min;
using std::priority_queue;
using std::queue;
using std::stack;
using std::swap;
using std::vector;
using ll = long long;
const ll INF = 1e18;
struct Edge {
int v, w1, w2;
};
namespace GetSpg {
ll dis[MN + 5];
vector<Edge> e[MN + 5];
void clear(int n) {
for (int i = 1; i <= n; i++) {
e[i].clear();
}
}
void addEdge(int u, int v, int w1, int w2) { e[u].push_back({v, w1, w2}); }
void dijkstra(int n, int S) {
using pii = std::pair<ll, int>;
priority_queue<pii, vector<pii>, greater<pii>> pq;
for (int i = 1; i <= n; i++) {
dis[i] = INF;
}
pq.push({dis[S] = 0, S});
while (!pq.empty()) {
int u = pq.top().second;
ll d = pq.top().first;
pq.pop();
if (d != dis[u])
continue;
for (Edge edge : e[u]) {
int v = edge.v;
int w = edge.w1;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
pq.push({dis[v], v});
}
}
}
}
void solve(int n, function<void(int, int, int, int)> addEdge) {
dijkstra(n, 1);
for (int u = 1; u <= n; u++) {
if (dis[u] == INF)
continue;
for (Edge edge : e[u]) {
if (dis[u] + edge.w1 == dis[edge.v]) {
addEdge(u, edge.v, edge.w1, edge.w2);
}
}
}
}
} // namespace GetSpg
namespace GetDag {
vector<Edge> e[MN + 5];
stack<int> s;
bool ins[MN + 5];
int low[MN + 5], dfn[MN + 5], scc[MN + 5];
int dfnCnt = 0, sccCnt = 0;
void clear(int n) {
for (int i = 1; i <= n; i++) {
e[i].clear();
ins[i] = false;
dfn[i] = low[i] = scc[i] = 0;
}
dfnCnt = 0;
sccCnt = 0;
while (!s.empty())
s.pop();
}
void addEdge(int u, int v, int w1, int w2) { e[u].push_back({v, w1, w2}); }
void tarjan(int u) {
dfn[u] = ++dfnCnt;
low[u] = dfn[u];
s.push(u);
ins[u] = true;
for (Edge edge : e[u]) {
int v = edge.v;
if (dfn[v]) {
if (ins[v]) {
low[u] = min(low[u], dfn[v]);
}
} else {
tarjan(v);
low[u] = min(low[u], low[v]);
}
}
if (low[u] == dfn[u]) {
int v;
++sccCnt;
do {
v = s.top();
s.pop();
ins[v] = false;
scc[v] = sccCnt;
} while (u != v);
}
}
void solve(int &n, function<void(int, int, int, int)> addEdge, bool isLoop[]) {
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
tarjan(i);
}
}
for (int u = 1; u <= n; u++) {
for (Edge edge : e[u]) {
int v = edge.v;
if (scc[u] == scc[v]) {
if (edge.w2 > 0) {
isLoop[scc[u]] = true;
}
} else {
addEdge(scc[u], scc[edge.v], edge.w1, edge.w2);
}
}
}
}
} // namespace GetDag
namespace GetLp {
int din[MN + 5];
bool isLoop[MN + 5];
vector<Edge> e[MN + 5];
struct Dis {
ll d;
Dis(ll d = 0) { this->d = d; }
Dis operator+(const Dis &that) const {
if (d == -INF || that.d == -INF)
return Dis(-INF);
if (d == INF || that.d == INF)
return Dis(INF);
return Dis(d + that.d);
}
bool operator<(const Dis &that) const { return this->d < that.d; }
};
Dis f[MN + 5];
void clear(int n) {
for (int i = 1; i <= n; i++) {
din[i] = 0;
isLoop[i] = false;
e[i].clear();
}
}
void addEdge(int u, int v, int w1, int w2) {
e[u].push_back({v, w1, w2});
din[v]++;
}
void solve(int n, int S) {
for (int i = 1; i <= n; i++) {
f[i] = -INF;
}
f[S] = 0;
queue<int> q;
for (int i = 1; i <= n; i++) {
if (din[i] == 0)
q.push(i);
}
while (!q.empty()) {
int u = q.front();
q.pop();
if (isLoop[u])
f[u] = f[u] + INF;
for (Edge edge : e[u]) {
int v = edge.v;
int w = edge.w2;
f[v] = max(f[v], f[u] + w);
if (--din[v] == 0) {
q.push(v);
}
}
}
}
} // namespace GetLp
void solve() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v, w1, w2;
scanf("%d%d%d%d", &u, &v, &w1, &w2);
GetSpg::addEdge(u, v, w1, w2);
}
GetSpg::solve(n, GetDag::addEdge);
GetDag::solve(n, GetLp::addEdge, GetLp::isLoop);
GetLp::solve(GetDag::sccCnt, GetDag::scc[1]);
printf("%lld %lld\n", GetSpg::dis[n], GetLp::f[GetDag::scc[n]].d);
GetSpg::clear(n);
GetDag::clear(n);
GetLp::clear(n);
}
int main() {
int T;
scanf("%d", &T);
while (T--)
solve();
}std 码量 234 行。好大的量啊。~估计能把我写吐，~但我不得不面对。
1003 Magic¶
赛场上第一次见题没看清往塔上放的是 magical ingredients，以为是直接向塔施法。直到给 vagrt 讲题意时才看明白。
好像读题就像看戏？看懂了觉得挺有意思，根本没思路回答问题。
数轴上 \(n\) 座魔法塔，编号 \(1, 2, \ldots, n\)，第 \(i\) 座塔至少需要 \(p_i\) 的 magic value。每座塔初始 magic value 为 \(0\)。Hongly 需要向塔添加 magic ingredients 来提高塔的 magic value。当一座塔增加 \(1\) 单位的 magic ingredient，附近半径为 \(k\) 的塔的 magic value 都会增加 \(1\)，\(k\) 为有效半径。假设 \(k=2\)，对第 \(i\) 座塔增加一点 magic ingredient，那么 \(i-1, i, i+1\) 的塔的 magic value 都会增加 \(1\)。
但是，有 \(q\) 条限制，在 \([L_i, R_i]\) 中的 magic ingredinents 总数不能超过 \(B_i\)。
问是否可行，若可行，最少几个 magic ingredients。
挠着头狂想 30 分钟一无所获。其实是走神了。
差分约束¶
差分约束系统 是一种特殊的 \(n\) 元一次不等式组，它包含 \(n\) 个变量 \(x_1,x_2,...,x_n\) 以及 \(m\) 个约束条件，每个约束条件是由两个其中的变量作差构成的，形如 \(x_i-x_j\leq c_k\)，其中 \(1 \leq i, j \leq n, i \neq j, 1 \leq k \leq m\) 并且 \(c_k\) 是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解 \(x_1=a_1,x_2=a_2,...,x_n=a_n\)，使得所有的约束条件得到满足，否则判断出无解。
差分约束系统中的每个约束条件 \(x_i-x_j\leq c_k\) 都可以变形成 \(x_i\leq x_j+c_k\)，这与单源最短路中的三角形不等式 \(dist[y]\leq dist[x]+z\) 非常相似。因此，我们可以把每个变量 \(x_i\) 看做图中的一个结点，对于每个约束条件 \(x_i-x_j\leq c_k\)，从结点 \(j\) 向结点 \(i\) 连一条长度为 \(c_k\) 的有向边。
注意到，如果 \(\{a_1,a_2,...,a_n\}\) 是该差分约束系统的一组解，那么对于任意的常数 \(d\)，\(\{a_1+d,a_2+d,...,a_n+d\}\) 显然也是该差分约束系统的一组解，因为这样做差后 \(d\) 刚好被消掉。
设 \(dist[0]=0\) 并向每一个点连一条权重为 \(0\) 边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则，\(x_i=dist[i]\) 为该差分约束系统的一组解。
一般使用 Bellman-Ford 或队列优化的 Bellman-Ford（俗称 SPFA，在某些随机图跑得很快）判断图中是否存在负环，最坏时间复杂度为 \(O(nm)\)。
回到本题¶
令 \(a[i]\) 为前 \(i\) 座魔法塔中加入的魔法原料之和。由于第 \(i\) 座塔的魔法值只与 \(k\) 内的魔法原料数量有关，则
对于魔法原料添加的限制 \((L_j, R_j, B_j)\)，可以表示为
由于每座魔法塔中原料数量非负，需要满足
即将原问题建模为一个差分约束问题，联立求解即可。哪有那么简单。
#include <bits/stdc++.h>
using namespace std;
const int maxne = 600001;
const int maxnn = 100001;
const long long int inf = 1e18;
int n, k;
int e, s, t, cnt;
int last[maxne], q[maxne], check[maxnn];
long long dis[maxnn];
bool is[maxnn], fuhuan;
struct line {
int to, next, v;
} l[maxne];
void add(int u, int v, int w) {
l[++cnt].to = v;
l[cnt].next = last[u];
last[u] = cnt;
l[cnt].v = w; /*printf("u:%d v:%d w:%d\n",u,v,w);*/
}
void spfa(int a, int maxnode) {
for (int i = 1; i <= maxnode; i++) {
dis[i] = inf;
check[i] = is[i] = 0;
}
dis[a] = 0;
is[a] = 1;
q[0] = a;
check[a]++;
fuhuan = 0;
int head = 0, tail = 1;
while (head != tail) {
int now = q[head++];
if (head == maxnode + 1)
head = 0;
for (int i = last[now]; i; i = l[i].next) {
if (dis[now] + l[i].v < dis[l[i].to] && dis[now] != inf) {
dis[l[i].to] = dis[now] + l[i].v;
if (!is[l[i].to]) {
is[l[i].to] = 1;
if (dis[l[i].to] < dis[q[head]]) {
head--;
if (head == -1)
head = n;
q[head] = l[i].to;
check[l[i].to]++;
if (check[l[i].to] == maxnode) {
fuhuan = 1;
return;
}
} else {
q[tail++] = l[i].to;
if (check[l[i].to] == maxnode) {
fuhuan = 1;
return;
}
if (tail == maxnode + 1)
tail = 0;
}
}
}
}
is[now] = 0;
}
}
void clear(int x) {
cnt = 0;
for (int i = 0; i <= x; i++) {
last[i] = q[i] = 0;
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int p, q;
scanf("%d%d", &n, &k);
// x[j]-x[i]>=k ==> x[i]-x[j]<=-k
for (int i = 1; i <= n; i++) {
scanf("%d", &p);
int st = (i - k >= 1) ? (i - k) : n + 1;
int ed = (i + k - 1 <= n) ? (i + k - 1) : n;
add(ed, st, -1 * p);
}
for (int i = 1; i <= n; i++)
add(i, (i - 1 == 0 ? n + 1 : i - 1), 0);
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
int x, y;
scanf("%d%d%d", &x, &y, &p);
add((x != 1) ? (x - 1) : n + 1, y, p);
}
spfa(n, n + 1);
int tmp = dis[n + 1];
printf("%d\n", fuhuan ? -1 : -1 * tmp);
clear(n + 2);
}
return 0;
}1004 Link with Equilateral Triangle¶
看到两分半就有人过题，我就想到输出一堆
No。正打算证明，vagrt 说写一个 DP，写了 30 分钟，过了。比完一看题解，傻了。
对于一个合法的解，应当满足不存在同时包含 \(0,1,2\) 的三角形，下面我们证明这样的三角形一定存在。
左下角必然是 \(1\)，右下角必然是 \(0\)，底边不能含有 \(2\)，则底边上必然有奇数条 \(1 \leftrightarrow 0\) 的边，这些边都属于一个小三角形。考虑其他的 \(0\leftrightarrow 1\) 边，由于不在两个斜边上的 \(0-1\) 边必然属于两个三角形。因此“所有三角形内 \(0-1\) 边的数量”的和必然为奇数。
但是，假设不存在 \(0, 1, 2\) 的三角形，则所有三角形都必然包含 \(0\) 条或 \(2\) 条的 \(0-1\) 边，产生了矛盾。
因此一定存在 \(0,1,2\) 的三角形。
这个故事告诉我们，别以为队友在忙活你就可以摸鱼了。你的更重要的任务是找出当前更优秀的解法。
1005 Link with Level Editor¶
看完题解突然就明白了，这个转移不就是矩阵乘法！！！
双指针（或者说队列）求解
发现矩阵并非全部可逆，难以进行删除操作，使用对顶栈的技巧规避掉删除操作即可。
说实在的我也没查到什么叫对顶栈，反正代码写得挺巧的。
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#define MN 5000
#define MM 20
using std::max;
using ll = long long;
const int INF = 1000000001;
namespace GTI { // 快读（略）
char gc(void); // get char
ll gti(void); // get int
int gts(char *s); // get string
int gtl(char *s); // get line
} // namespace GTI
using GTI::gti;
using GTI::gtl;
using GTI::gts;
int n, m, k;
// 矩阵的模板可以拿来用
struct Matrix {
int a[MM + 2][MM + 2];
Matrix(int x = 0) {
memset(a, 0, sizeof(a));
for (int i = 1; i <= m; i++) {
a[i][i] = x;
}
}
Matrix operator*(const Matrix &that) const {
Matrix ret;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 1; k <= m; k++) {
ret.a[i][j] = limit(ret.a[i][j] + (ll)this->a[i][k] * that.a[k][j]);
}
}
}
return ret;
}
// 控制 x 不要超过 INF
static int limit(ll x) {
if (x >= INF)
return INF;
else
return x;
}
};
Matrix d[MN + 5], b[MN + 5];
bool check(const Matrix &lhs, const Matrix &rhs) {
int ans = 0;
for (int i = 1; i <= m; i++) {
ans = Matrix::limit(ans + (ll)lhs.a[1][i] * rhs.a[i][m]);
}
return ans <= k;
}
void solve() {
n = gti();
m = gti();
k = gti();
for (int i = 1; i <= n; i++) {
int l = gti();
d[i] = 1;
while (l--) {
int u = gti();
int v = gti();
d[i].a[u][v] = 1;
}
}
int ans = 0;
Matrix csuf = 1; // 当前段的乘积
b[0].a[1][m] = INF;
for (int r = 1, l = 0, lim = 0; r <= n; r++) {
csuf = csuf * d[r];
while (!check(b[l], csuf)) {
l++; // 栈头弹出一个
if (l > lim) {
b[r] = d[r];
for (int i = r - 1; i > lim; i--) {
b[i] = d[i] * b[i + 1];
}
lim = r;
csuf = 1;
}
}
ans = max(ans, r - l + 1);
}
printf("%d\n", ans);
}
int main() {
int T = gti();
while (T--)
solve();
}1006 BIT Subway¶
签到题，难度让我想起天梯赛 Level 1。
有一个小坑是，要享受五折票价，需要购买原价共 225 元的票而不是 200 元，因为 \(100 + 0.8 \times 125 = 225\)。
1007 Climb Stairs¶
眼睁睁看着集训队内其他全部队伍过题而自己还在纠结怎么个贪心法。
这滋味难受极了。
题意：有一座 \(n\) 层的塔，\(1\) 到 \(n\) 层每层一个怪物，第 \(i\) 层的怪物的 HP 为 \(a_i\)。
主角从第 \(0\) 层以 \(a_0\) 的攻击力向上打，每次可以选择向上跳最多 \(k\) 层和向下跳最多 \(1\) 层。主角所在层数必须在 \(\{0, 1, 2,\ldots n\}\) 中。问能否将怪物打完。
由于题目要求必须把所有怪物打完，所以跳过的怪物还必须得走回去打败才行。我们要从当前位置 \(x\)，找到一个右端点 \(r\)，使得可以按照 \(r, r-1, r-2, \ldots, x+1\) 的顺序打败这一段的怪物。不难看出 \(r\) 更小的时候不会更劣。设以这种策略到达第 \(i\) 层时的能力值为 \(c_i\)。
不难看出吗？？场上我想了老半天（好吧可能是根本没仔细想。
主角攻击力的提升就相当于主角所在楼层以下怪物 HP 的下降，所以主角到 \(r\) 层，相当于楼下的怪物攻击力都降低 \(a_r\)。
直接从下到上枚举当前想要先到达的右端点（满足 \(x+k\le r\)），用线段树询问 \([l, r]\) 的 \(c_l - a_i\)（能否打得过），一旦能打过就扩展到 \(r\) 位置，将 \([l, r]\) 区间加 \(a_r\) 。找到最小的满足要求的 \(r\) 就可以继续更新位置。
更新位置后，相当于实际上完成了击杀 \(r, r-1, \ldots, l\) 的过程，所以将后面的区间加上相应的值。由于每个右端点只会被计算一次，所以时间复杂度是 \(O(n \log n)\)的。
1008 Fight and Upgrade¶
估计是防 AK 题
1009 Fall with Full Star¶
1010 Fall with Intersection¶
1011 Link is as Bear¶
当时在场听到有同学讨论线性基，翻开书查了一下，看到了线性基的内容但是不知道具体是什么意思。