# 第四场¶

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

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)

$$f_{i,j}$$ 表示 $$[i, j]$$ 为合法序列$$i, j$$ 上括号相匹配的方案数，$$g_{i, j}$$ 表示 $$[i, j]$$ 区间形成一个合法括号序列的方案数。初始状态 $$g_{2k, 2k+1} = 1$$

$$e$$ 为使得 $$l, r$$ 上括号相匹配的方案数，

$f_{i, j} = e \times g_{i+1, j-1}$

$g_{i, j} = \sum_{k=i, 2|k}^j g_{i, k}\times f_{k+1, j}$

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]);
}

1. 可能有 $$0$$ 圈，tarjan 缩点，变成 $$G_e$$
2. 先用 dijkstra 在 $$G_e$$ 上跑出 $$e_i$$ 的最短路，计算出 $$E$$ 并获得新图 $$G_p$$
3. $$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]) {
}
}
}
}

} // 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 {
}
}
}
}

} // 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);
}
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¶

### 差分约束¶

$$dist[0]=0$$ 并向每一个点连一条权重为 $$0$$ 边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则，$$x_i=dist[i]$$ 为该差分约束系统的一组解。

### 回到本题¶

$$a[i]$$ 为前 $$i$$ 座魔法塔中加入的魔法原料之和。由于第 $$i$$ 座塔的魔法值只与 $$k$$ 内的魔法原料数量有关，则

$a[\min(n, i+k-1)] - a[\max(0, i-k)] \ge p_i$

$a[R_j] - a[L_j-1] \le B_j$

$a[i] - a[i-1] \ge 0$

#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;
if (head == maxnode + 1)
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;
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;
}
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;
}

#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();
}