A. D1T1 卡牌游戏
可以枚举一个 (p)，然后限制最小值 (geq p)，接着找到最小的 (q) 使得限制最大值 (leq q) 是合法的。
那么这个限制就相当于：
- 对于 (a_i < p)，必须要满足 (p leq b_i leq q)，记这类点数为 (c_1)。
- 对于 (a_i > q)，必须要满足 (p leq b_i leq q)，记这类点数为 (c_2)。
- (c_1+c_2 leq m)。
(p) 增加的时候，最优 (q) 必然是不下降的。双指针移动一下，注意实现。时间复杂度 (mathcal O(n log n)) 或 (mathcal O(n))。
#include <bits/stdc++.h>
using std::cerr;
template <class T>
inline void read(T &x) {
static char ch;
while (!isdigit(ch = getchar()));
x = ch - '0';
while (isdigit(ch = getchar()))
x = x * 10 + ch - '0';
}
template <class T>
inline void tense(T &x, const T &y) {
if (x > y) x = y;
}
template <class T>
inline void relax(T &x, const T &y) {
if (x < y) x = y;
}
const int MaxN = 1e6 + 5;
const int MaxM = 2e6 + 5;
const int INF = 0x3f3f3f3f;
int n, m;
int a[MaxN], b[MaxN];
int preMax[MaxN], preMin[MaxN];
int sufMax[MaxN], sufMin[MaxN];
int nV, val[MaxM];
int main() {
freopen("card.in", "r", stdin);
freopen("card.out", "w", stdout);
read(n), read(m);
for (int i = 1; i <= n; ++i) read(a[i]), val[++nV] = a[i];
for (int i = 1; i <= n; ++i) read(b[i]), val[++nV] = b[i];
std::sort(val + 1, val + nV + 1);
preMax[0] = sufMax[n + 1] = 0;
preMin[0] = sufMin[n + 1] = INF;
for (int i = 1; i <= n; ++i) {
a[i] = std::lower_bound(val + 1, val + nV + 1, a[i]) - val;
b[i] = std::lower_bound(val + 1, val + nV + 1, b[i]) - val;
relax(preMax[i] = preMax[i - 1], b[i]);
tense(preMin[i] = preMin[i - 1], b[i]);
}
for (int i = n; i >= 1; --i) {
relax(sufMax[i] = sufMax[i + 1], b[i]);
tense(sufMin[i] = sufMin[i + 1], b[i]);
}
int res = INF;
for (int l = 1, r = 0, c1 = 0, c2 = n; l <= nV; ++l) {
while (c1 < n && a[c1 + 1] < l) ++c1;
if (preMin[c1] < l || c1 > m) break;
while (
(c1 + c2 > m)
|| (preMax[c1] > r)
|| (sufMin[n - c2 + 1] < l || sufMax[n - c2 + 1] > r)
) {
++r;
while (c2 > 0 && a[n - c2 + 1] <= r) --c2;
}
tense(res, val[r] - val[l]);
}
printf("%d
", res);
return 0;
}
B. D1T2 矩阵游戏
思路一
首先，如果确定了第一行和第一列，那么整个矩阵就可以确定了。
一通观察+归纳证明，不难发现
[a_{i,j} = K_{i,j}+(-1)^{j+1}a_{i,1}+(-1)^{i+1}a_{1,j}+(-1)^{i+j+1}a_{1,1}
]
其中 (K_{i,j}) 是可以通过 (b) 矩阵唯一确定的一个常数。
不难发现，需要处理的就是 (a_{i,j} in [0,10^6]) 的限制，就相当于：
[K_{i,j}+(-1)^{j+1}a_{i,1}+(-1)^{i+1}a_{1,j}+(-1)^{i+j+1}a_{1,1} in [0,10^6]
]
这个形式对我们很有启发，两边同时乘上 ((-1)^{i+j+1})，尝试将每一项整理一下
[(-1)^{i+j+1}K_{i,j}+(-1)^{i}a_{i,1}+(-1)^{j}a_{1,j}+a_{1,1} \
in egin{cases}[0,10^6] & i+j+1 equiv 0 pmod 2 \ [-10^6,0] & i+j+1 equiv 1 pmod 2end{cases}
]
把 (a_{1,1}) 随便和 ((-1)^{i}a_{i,1}) 放到一起，这下就可以把 (i,j) 的变量分成两部分了。不难写成差分约束的形式：
[left((-1)^{i}a_{i,1}+a_{1,1}
ight)-(-1)^{j+1}a_{1,j} \
in egin{cases}[-K_{i,j},10^6-K_{i,j}] & i+j+1 equiv 0 pmod 2 \ [K_{i,j}-10^6,K_{i,j}] & i+j+1 equiv 1 pmod 2end{cases}
]
这下就可以做一个 (mathcal O(n+m)) 个点 (mathcal O(nm)) 条边的差分约束了。
时间复杂度 (mathcal O(T(n+m)nm))，SPFA 跑不满。
思路二
我看了看别人的题解，学到了一个明显更简单的思路。
将第一行、第一列都赋成 (0)，先得到一个满足矩阵 (b)，但是不一定满足范围的解，记为 (p)。
利用若干次以下两类操作，我们可以用矩阵 (p) 构造出任意一组满足矩阵 (b) 的解：
- 操作一：选择其中一行，依次将每个数 (+1,-1,+1,cdots)（权值记为 (+1)）或 (-1,+1,-1,cdots)（权值记为 (-1)）
- 操作二：选择其中一列，依次将每个数 (+1,-1,+1,cdots)（权值记为 (+1)）或 (-1,+1,-1,cdots)（权值记为 (-1)）
因为两种操作完全可以将第一行、第一列修改成任意情况，所以整个矩阵 (a) 的所有可能情况都可以达到。
记第 (i) 行进行的操作一总权值为 (c_i)，第 (j) 列进行的操作二总权值为 (d_i)。那么
[a_{i,j}=p_{i,j}+(-1)^{j+1} c_i+(-1)^{i+1} d_j
]
同「思路一」操作一下，就转化成差分约束了，这里就不赘述了。
#include <bits/stdc++.h>
#define foredge(u) for (int e = adj[u], v; v = to[e], e; e = nxt[e])
using std::cerr;
typedef long long s64;
template <class T>
inline void read(T &x) {
static char ch;
while (!isdigit(ch = getchar()));
x = ch - '0';
while (isdigit(ch = getchar()))
x = x * 10 + ch - '0';
}
template <class T>
inline void putint(T x) {
static char buf[15], *tail = buf;
if (!x) putchar('0');
else {
if (x < 0) x = ~x + 1, putchar('-');
for (; x; x /= 10) *++tail = x % 10 + '0';
for (; tail != buf; --tail) putchar(*tail);
}
}
template <class T>
inline bool tense(T &x, const T &y) {
return x > y ? x = y, true : false;
}
template <class T>
inline bool relax(T &x, const T &y) {
return x < y ? x = y, true : false;
}
const int MaxN = 3e2 + 5;
const int MaxV = 7e2 + 5;
const int MaxE = MaxN * MaxN * 2 + MaxV * 2;
int n, m, nV, lim = 1000000;
s64 b[MaxN][MaxN], dis[MaxV];
bool flgCir;
int ect, nxt[MaxE], to[MaxE], weight[MaxE];
int adj[MaxV];
inline void init() {
ect = 0;
for (int i = 1; i <= nV; ++i) adj[i] = 0;
}
inline void addEdge(int u, int v, int w) {
nxt[++ect] = adj[u];
adj[u] = ect;
to[ect] = v;
weight[ect] = w;
}
inline void addSeg(int u, int v, s64 l, s64 r) {
relax(l, -3LL * lim), tense(r, 3LL * lim);
if (l > r) flgCir = true;
addEdge(u, v, (int)r);
addEdge(v, u, -(int)l);
}
void SPFA() {
static int que[MaxV * MaxV], cnt[MaxV], qr;
static bool inq[MaxV];
for (int i = 1; i <= nV; ++i) {
cnt[i] = 0; //!!!
inq[i] = false;
dis[i] = 1LL << 60;
}
inq[nV] = true;
dis[que[qr = 1] = nV] = 0;
for (int i = 1; i <= qr; ++i) {
int u = que[i];
inq[u] = false;
foredge(u) if (tense(dis[v], dis[u] + weight[e])) {
if ((cnt[v] = cnt[u] + 1) >= nV) {
flgCir = true;
return;
}
if (!inq[v]) inq[que[++qr] = v] = true;
}
}
}
void work() {
init();
flgCir = false;
read(n), read(m), nV = n + m;
addSeg(nV, 1, 0, lim);
for (int i = 2; i <= n; ++i) {
if (i & 1)
addSeg(1, i, -lim, 0);
else
addSeg(1, i, 0, lim);
}
for (int i = 2; i <= m; ++i) {
int p = i + n - 1;
if (i & 1)
addSeg(nV, p, 0, lim);
else
addSeg(nV, p, -lim, 0);
}
for (int i = 2; i <= n; ++i)
for (int j = 2; j <= m; ++j) {
read(b[i][j]);
b[i][j] -= b[i - 1][j];
b[i][j] -= b[i][j - 1];
b[i][j] -= b[i - 1][j - 1];
if ((i + j + 1) & 1)
addSeg(j + n - 1, i, -lim + b[i][j], +b[i][j]);
else
addSeg(j + n - 1, i, -b[i][j], -b[i][j] + lim);
}
if (flgCir) return (void)(puts("NO"));
SPFA();
if (flgCir) return (void)(puts("NO"));
puts("YES");
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
int res =
b[i][j]
+ ((i + j + 1) & 1 ? -1 : 1) * dis[i]
+ ((i + j) & 1 ? -1 : 1) * dis[j + n - 1];
if (i == 1) {
res = (j & 1 ? 1 : -1) * dis[j == 1 ? 1 : j + n - 1];
} else if (j == 1) {
res = (i & 1 ? -1 : 1) * (dis[i] - dis[1]);
}
putint(res), putchar("
"[j == m]);
}
}
int main() {
freopen("matrix.in", "r", stdin);
freopen("matrix.out", "w", stdout);
int T;
read(T);
while (T--) work();
return 0;
}
#include <bits/stdc++.h>
#define foredge(u) for (int e = adj[u], v; v = to[e], e; e = nxt[e])
using std::cerr;
typedef long long s64;
template <class T>
inline void read(T &x) {
static char ch;
while (!isdigit(ch = getchar()));
x = ch - '0';
while (isdigit(ch = getchar()))
x = x * 10 + ch - '0';
}
template <class T>
inline void putint(T x) {
static char buf[15], *tail = buf;
if (!x) putchar('0');
else {
if (x < 0) x = ~x + 1, putchar('-');
for (; x; x /= 10) *++tail = x % 10 + '0';
for (; tail != buf; --tail) putchar(*tail);
}
}
template <class T>
inline bool tense(T &x, const T &y) {
return x > y ? x = y, true : false;
}
template <class T>
inline bool relax(T &x, const T &y) {
return x < y ? x = y, true : false;
}
const int MaxN = 3e2 + 5;
const int MaxV = 7e2 + 5;
const int MaxE = MaxN * MaxN * 2 + MaxV * 2;
const int INF = 0x3f3f3f3f;
int n, m, nV, lim = 1000000;
s64 b[MaxN][MaxN], dis[MaxV];
bool flgCir;
int ect, nxt[MaxE], to[MaxE], weight[MaxE];
int adj[MaxV];
int g[MaxV][MaxV];
inline void init() {
ect = 0;
for (int i = 1; i <= nV; ++i) adj[i] = 0;
for (int i = 1; i <= nV; ++i)
for (int j = 1; j <= nV; ++j) {
g[i][j] = INF;
}
}
inline void addEdge(int u, int v, int w) {
tense(g[u][v], w);
}
inline void addSeg(int u, int v, s64 l, s64 r) {
relax(l, -3LL * lim), tense(r, 3LL * lim);
if (l > r) flgCir = true;
addEdge(u, v, (int)r);
addEdge(v, u, -(int)l);
}
void SPFA() {
static int que[MaxV * MaxV], cnt[MaxV], qr;
static bool inq[MaxV];
for (int i = 1; i <= nV; ++i) {
cnt[i] = 0; //!!!
inq[i] = false;
dis[i] = 1LL << 60;
}
inq[nV] = true;
dis[que[qr = 1] = nV] = 0;
for (int i = 1; i <= qr; ++i) {
int u = que[i];
inq[u] = false;
for (int v = 1; v <= nV; ++v) if (tense(dis[v], dis[u] + g[u][v])) {
if ((cnt[v] = cnt[u] + 1) >= nV) {
flgCir = true;
return;
}
if (!inq[v]) inq[que[++qr] = v] = true;
}
}
}
void work() {
read(n), read(m), nV = n + m;
init();
flgCir = false;
addSeg(nV, 1, 0, lim);
for (int i = 2; i <= n; ++i) {
if (i & 1)
addSeg(1, i, -lim, 0);
else
addSeg(1, i, 0, lim);
}
for (int i = 2; i <= m; ++i) {
int p = i + n - 1;
if (i & 1)
addSeg(nV, p, 0, lim);
else
addSeg(nV, p, -lim, 0);
}
for (int i = 2; i <= n; ++i)
for (int j = 2; j <= m; ++j) {
read(b[i][j]);
b[i][j] -= b[i - 1][j];
b[i][j] -= b[i][j - 1];
b[i][j] -= b[i - 1][j - 1];
if ((i + j + 1) & 1)
addSeg(j + n - 1, i, -lim + b[i][j], +b[i][j]);
else
addSeg(j + n - 1, i, -b[i][j], -b[i][j] + lim);
}
if (flgCir) return (void)(puts("NO"));
SPFA();
if (flgCir) return (void)(puts("NO"));
puts("YES");
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
int res =
b[i][j]
+ ((i + j + 1) & 1 ? -1 : 1) * dis[i]
+ ((i + j) & 1 ? -1 : 1) * dis[j + n - 1];
if (i == 1) {
res = (j & 1 ? 1 : -1) * dis[j == 1 ? 1 : j + n - 1];
} else if (j == 1) {
res = (i & 1 ? -1 : 1) * (dis[i] - dis[1]);
}
putint(res), putchar("
"[j == m]);
}
}
int main() {
freopen("matrix.in", "r", stdin);
freopen("matrix.out", "w", stdout);
int T;
read(T);
while (T--) work();
return 0;
}
C. D1T3 图函数
首先不难得到一个结论：在计算 (f(u,G)) 的过程中，如果我们按顺序枚举到一个点 (v)，那么在 (v) 前面的点 (w) 如果没删掉，删掉 (w) 也不会改变我们的判断结果。
这是因为，我们在判断 (v) 是否会在 (f(u,G)) 中产生贡献的时候，实际上是判断 (u,v) 在当前的图上是否属于同一个强连通分量。而之前没有删掉的点 (w) 和 (u) 一定就不在一个强连通分量中，删掉它不影响我们的判断。
于是 (f(u,G)= sum_{v} [ ext{删掉 } 1 sim v-1 ext{ 的点后 } u,v ext{ 仍然连通}])。
记命题 (p(i,u,v)) 表示 (u,v) 之间存在一条路径，使得这条路径经过的点编号都 (geq i)。
显然使得 (p(i,u,v)) 成立的图一定是 (G_0sim G_m) 的一段前缀。如果能对于每个点对 ((u,v)) 找到最大的 (e)，使得 (p(v,u,v)land p(v,v,u)) 在 (G_0sim G_{e-1}) 都成立，那么就可以将其贡献到 (h(G_0)sim h(G_{e-1})) 中。
现在的问题就是如何找到这个 (e)，下面一一介绍。
思路一
注意到满足 (p(u,u,v)land p(u,v,u)) 这个条件的最大的 (e) 可以看成，在正图 (G) 和反图 (G^R) 上 (u) 经过 (geq u) 的点走到 (v) 的所有路径中，分别找到路径最小边权（边的编号）的最大值。
一个想法就是枚举起点 (u)，然后删去 (< u) 的点，以它为起点跑 Dijkstra。时间复杂度 (mathcal O(nmlog m))。
实际上限制只能经过编号 (geq u) 的点，可以通过 Floyd 枚举第一维来实现，用 Floyd 求解即可。时间复杂度 (mathcal O(n^3))。
code (O(nm log m))
#include <bits/stdc++.h>
#define foredge(u, G) for (int e = G.adj[u], v; v = G.to[e], e; e = G.nxt[e])
using std::min;
using std::cerr;
using std::pair;
using std::make_pair;
typedef std::vector<int> vi;
typedef std::pair<int, int> pii;
template <class T>
inline void read(T &x) {
static char ch;
while (!isdigit(ch = getchar()));
x = ch - '0';
while (isdigit(ch = getchar()))
x = x * 10 + ch - '0';
}
template <class T>
inline bool relax(T &x, const T &y) {
return x < y ? x = y, true : false;
}
const int INF = 0x3f3f3f3f;
const int MaxN = 1000 + 5;
const int MaxE = 4e5 + 5;
struct graph {
int ect, adj[MaxN];
int nxt[MaxE], to[MaxE], weight[MaxE];
inline void addEdge(int u, int v, int w) {
nxt[++ect] = adj[u];
adj[u] = ect;
to[ect] = v;
weight[ect] = w;
}
}G1, G2;
int n, m;
int ans[MaxE];
void Dijkstra(int st, int *dis, graph &G) {
static std::priority_queue<pii> heap;
static bool vis[MaxN];
for (int i = 1; i <= n; ++i) {
dis[i] = 0;
vis[i] = false;
}
while (!heap.empty()) heap.pop();
heap.push(make_pair(dis[st] = m + 1, st));
while (!heap.empty()) {
int u = heap.top().second;
heap.pop();
if (vis[u]) continue;
vis[u] = true;
foredge(u, G)
if (v >= st && !vis[v] && relax(dis[v], min(dis[u], G.weight[e])))
heap.push(make_pair(dis[v], v));
}
}
int main() {
freopen("graph.in", "r", stdin);
freopen("graph.out", "w", stdout);
read(n), read(m);
for (int i = 1; i <= m; ++i) {
int u, v;
read(u), read(v);
G1.addEdge(u, v, i);
G2.addEdge(v, u, i);
}
for (int st = 1; st <= n; ++st) {
static int dis1[MaxN], dis2[MaxN];
Dijkstra(st, dis1, G1);
Dijkstra(st, dis2, G2);
for (int i = st; i <= n; ++i)
++ans[min(dis1[i], dis2[i])];
}
for (int i = m; i >= 1; --i)
ans[i] += ans[i + 1];
for (int i = 1; i <= m + 1; ++i) {
printf("%d%c", ans[i], "
"[i == m + 1]);
}
return 0;
}
code (mathcal O(n^3))
#include <bits/stdc++.h>
#define foredge(u) for (halfEdge *e = adj[u]; e; e = e->next)
using std::min;
using std::cerr;
using std::pair;
using std::vector;
using std::make_pair;
typedef std::vector<int> vi;
typedef std::pair<int, int> pii;
template <class T>
inline void read(T &x) {
static char ch;
while (!isdigit(ch = getchar()));
x = ch - '0';
while (isdigit(ch = getchar()))
x = x * 10 + ch - '0';
}
template <class T>
inline void relax(T &x, const T &y) {
x < y ? x = y : 0;
}
const int INF = 0x3f3f3f3f;
const int MaxN = 1000 + 5;
const int MaxE = 4e5 + 5;
int n, m;
int ans[MaxE];
int f[MaxN][MaxN];
int main() {
freopen("graph.in", "r", stdin);
freopen("graph.out", "w", stdout);
read(n), read(m);
for (int i = 1; i <= m; ++i) {
int u, v;
read(u), read(v);
relax(f[u][v], i);
}
for (int k = n; k >= 1; --k) {
relax(f[k][k], m + 1);
for (int u = 1; u <= n; ++u) if (f[u][k])
for (int v = 1, lim = u > k ? k - 1 : n; v <= lim; ++v)
relax(f[u][v], min(f[u][k], f[k][v]));
for (int v = k; v <= n; ++v)
++ans[min(f[v][k], f[k][v])];
}
for (int i = m; i >= 1; --i)
ans[i] += ans[i + 1];
for (int i = 1; i <= m + 1; ++i) {
printf("%d%c", ans[i], "
"[i == m + 1]);
}
return 0;
}
思路二
反过来考虑，我们倒序加边，看看每个点对在加入哪条边的时候恰好连通。
假设 (f(u,v)) 表示在当前加入的边集中，(u) 能否通过 (geq u) 的点到达 (v)。
倒序枚举到边 ((x,y)) 的时候，再枚举点对的起点 (u(uleq y))：
- 如果 (f(u,x)=1) 且 (f(u,y)=0)
- 那么就从 (y) 点出发 DFS/BFS
- 将所有访问到的 (vgeq u) 且 (f(u,v)=0) 的点更新。
注意到在上述过程中，一个起点 (u) 中每个点 (v) 只会被访问至多一次，因此边也至多访问一次，时间复杂度就是 (mathcal O(nm+n^2))。
实际上，有些枚举是冗余的，因为在枚举过程中实际上用到的点对并不多：
- 对于枚举的边 ((x,y))，如果枚举的 (u) 满足 (f(u,x)=1) 且 (f(u,y)=0)，那么这样的 ((u,y)) 至多有 (mathcal O(n^2)) 对。
- 对于 DFS/BFS 过程中访问到的点 (v)，实际上在枚举的每个起点 (u) 中也只会至多访问一次，枚举出边的过程是冗余的。
用 bitset 的 _Find_first 和 _Find_next，我们就可以很好地解决冗余枚举的问题。只需要对每个点 (v) 多记一个 (g(v,u)=f(u,v)) 即可。
总的时间复杂度就可以优化到 (mathcal O(frac{n^3+nm}{omega}))，这个应该是比较正确的复杂度，实际效率也是这几种算法中最优的。
code (O(nm))
#include <bits/stdc++.h>
#define foredge(u) for (halfEdge *e = adj[u]; e; e = e->next)
using std::min;
using std::cerr;
using std::pair;
using std::make_pair;
typedef std::vector<int> vi;
typedef std::pair<int, int> pii;
template <class T>
inline void read(T &x) {
static char ch;
while (!isdigit(ch = getchar()));
x = ch - '0';
while (isdigit(ch = getchar()))
x = x * 10 + ch - '0';
}
template <class T>
inline bool relax(T &x, const T &y) {
return x < y ? x = y, true : false;
}
const int INF = 0x3f3f3f3f;
const int MaxN = 1000 + 5;
const int MaxE = 4e5 + 5;
struct edge {
int u, v;
}e1[MaxE], e2[MaxE];
struct halfEdge {
int v;
halfEdge *next;
}adjPool[MaxE], *adjTail = adjPool, *adj[MaxN];
int n, m;
int ans[MaxE];
inline void clear() {
adjTail = adjPool;
for (int i = 1; i <= n; ++i) {
adj[i] = NULL;
}
}
inline void addEdge(int u, int v) {
adjTail->v = v;
adjTail->next = adj[u];
adj[u] = adjTail++;
}
void bfs(int u, int *dis, int disval) {
static int que[MaxN], qr;
dis[que[qr = 1] = u] = disval;
for (int i = 1; i <= qr; ++i) {
int u = que[i];
foredge(u) if (!dis[e->v])
dis[que[++qr] = e->v] = disval;
}
}
void solve(int st, int *dis, edge *e) {
for (int i = 1; i <= n; ++i) {
dis[i] = 0;
}
clear();
dis[st] = m + 1;
for (int i = m; i >= 1; --i) {
int u = e[i].u, v = e[i].v;
if (u >= st && v >= st) {
if (!dis[u] && !dis[v])
addEdge(u, v);
else if (dis[u] && !dis[v])
bfs(v, dis, i);
}
}
}
int main() {
freopen("graph.in", "r", stdin);
freopen("graph.out", "w", stdout);
read(n), read(m);
for (int i = 1; i <= m; ++i) {
int u, v;
read(u), read(v);
e1[i] = (edge){u, v};
e2[i] = (edge){v, u};
}
for (int st = 1; st <= n; ++st) {
static int dis1[MaxN], dis2[MaxN];
solve(st, dis1, e1);
solve(st, dis2, e2);
for (int i = st; i <= n; ++i)
++ans[min(dis1[i], dis2[i])];
}
for (int i = m; i >= 1; --i)
ans[i] += ans[i + 1];
for (int i = 1; i <= m + 1; ++i) {
printf("%d%c", ans[i], "
"[i == m + 1]);
}
return 0;
}
code (mathcal O(frac{n^3+nm}{omega}))
#include <bits/stdc++.h>
#define foredge(u) for (halfEdge *e = adj[u]; e; e = e->next)
using std::min;
using std::cerr;
using std::pair;
using std::make_pair;
typedef std::vector<int> vi;
typedef std::pair<int, int> pii;
template <class T>
inline void read(T &x) {
static char ch;
while (!isdigit(ch = getchar()));
x = ch - '0';
while (isdigit(ch = getchar()))
x = x * 10 + ch - '0';
}
template <class T>
inline bool relax(T &x, const T &y) {
return x < y ? x = y, true : false;
}
const int INF = 0x3f3f3f3f;
const int MaxN = 1000 + 5;
const int MaxE = 4e5 + 5;
typedef std::bitset<MaxN> bst;
struct edge {
int u, v;
}e[2][MaxE];
int n, m;
int ans[MaxE];
int dis[2][MaxN][MaxN];
bst vis[MaxN], bel[MaxN], adj[MaxN];
void fillVis(int st, int src, int disVal, int opt) {
static int que[MaxN], qr;
vis[src][que[qr = 1] = st] = 1;
bel[st][src] = 1;
dis[opt][src][st] = disVal;
for (int i = 1; i <= qr; ++i) {
int u = que[i];
bst nxt = (~vis[src]) & adj[u];
for (int v = nxt._Find_next(src); v <= n; v = nxt._Find_next(v)) {
vis[src][que[++qr] = v] = 1;
bel[v][src] = 1;
dis[opt][src][v] = disVal;
}
}
}
void solve(int opt) {
for (int i = 1; i <= n; ++i) {
vis[i].reset();
bel[i].reset();
adj[i].reset();
bel[i][i] = vis[i][i] = 1;
dis[opt][i][i] = m + 1;
}
for (int ie = m; ie >= 1; --ie) {
int s = e[opt][ie].u;
int t = e[opt][ie].v;
adj[s][t] = 1;
bst st = bel[s] & (~bel[t]);
for (int u = st._Find_first(); u <= t; u = st._Find_next(u))
fillVis(t, u, ie, opt);
}
}
int main() {
freopen("graph.in", "r", stdin);
freopen("graph.out", "w", stdout);
read(n), read(m);
for (int i = 1; i <= m; ++i) {
int u, v;
read(u), read(v);
e[0][i] = (edge){u, v};
e[1][i] = (edge){v, u};
}
solve(0);
solve(1);
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j)
++ans[min(dis[0][i][j], dis[1][i][j])];
for (int i = m; i >= 1; --i)
ans[i] += ans[i + 1];
for (int i = 1; i <= m + 1; ++i) {
printf("%d%c", ans[i], "
"[i == m + 1]);
}
return 0;
}
D. D2T1 宝石
算法一
这个是我自己的思路。
首先注意题目的条件：「(P_1,P_2,cdots,P_c) 互不相等」。那么每个点就唯一对应排列中的一个编号，每个点的下一个和上一个匹配元素也很容易找到。
根据这一点，可以设计出一个寻找最长匹配子序列的思路。
首先，我们求出：
- (mathrm{par}_1(x)) 表示能在 (x) 的祖先中找到的，点权恰好等于 (x) 在排列中对应的下一个元素，且深度最深的点。
- (mathrm{par}_2(x)) 表示能在 (x) 的祖先中找到的，点权恰好等于 (x) 在排列中对应的上一个元素，且深度最深的点。
这样就得到了两棵新树，可以对两个 (mathrm{par}) 数组建立倍增数组。
然后对于询问的路径 (u o v)，将其拆解为 (u o mathrm{lca} o v)（显然，按照路径中访问的点的顺序依次匹配，肯定是能匹配先匹配更优）：
- 对于 (u o mathrm{lca}) 这一段，我们先找到深度最大的 (P_1) 的点 (x)，然后从 (x) 开始在 (mathrm{par}_1) 上倍增跳，跳到在原树中深度最小且 (geq mathrm{dep}_{mathrm{lca}}) 的点。
- 对于 (mathrm{lca} o v) 这一段，因为我们已经在前面一段找到了能匹配的最长前缀 (P_1sim P_{L_1})，所以可以二分这一段接着能匹配的长度 (L_2)。二分的判断只需要在 (mathrm{lca} o v) 这一段找到最深的 (P_{L_1+L_2})，然后在 (mathrm{par}_2) 上跳 (L_2-1) 步看看深度是否满足 (> mathrm{dep})
注意上面是把第二段的询问离线后 DFS，在 DFS 的时候用一个桶记录了路径上最后一个点权等于每个值的点。同时注意 LCA 必须只能属于其中一段，在另一端查询的时候要去掉 LCA。
因为有二分，所以时间复杂度就是 (mathcal O(n log n + qlog nlog m))。
code
#include <bits/stdc++.h>
using std::swap;
using std::cerr;
using std::vector;
typedef std::vector<int> vi;
template <class T>
inline void read(T &x) {
static char ch;
while (!isdigit(ch = getchar()));
x = ch - '0';
while (isdigit(ch = getchar()))
x = x * 10 + ch - '0';
}
template <class T>
inline void putint(T x) {
static char buf[15], *tail = buf;
if (!x) putchar('0');
else {
if (x < 0) putchar('-'), x = ~x + 1;
for (; x; x /= 10) *++tail = x % 10 + '0';
for (; tail != buf; --tail) putchar(*tail);
}
}
const int MaxN = 2e5 + 5;
const int MaxM = 5e4 + 5;
const int MaxE = MaxN << 1;
const int MaxLog = 18;
int dep[MaxN];
struct tree {
int anc[MaxN][MaxLog + 1];
inline void insert(int u, int fa) {
anc[u][0] = fa;
for (int i = 0; anc[u][i]; ++i)
anc[u][i + 1] = anc[anc[u][i]][i];
}
inline int jump(int x, int low) {
int res = 0;
for (int i = MaxLog; i >= 0; --i)
if (anc[x][i] && dep[anc[x][i]] >= low)
res |= 1 << i, x = anc[x][i];
return res + (dep[x] >= low);
}
inline int queryLCA(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int d = dep[u] - dep[v], i = 0; d; d >>= 1, ++i)
if (d & 1) {
u = anc[u][i];
}
if (u == v) return u;
for (int i = MaxLog; i >= 0; --i)
if (anc[u][i] != anc[v][i]) {
u = anc[u][i];
v = anc[v][i];
}
return anc[u][0];
}
}A, B, T;
struct request {
int d, lca, pos; // d: u->lca answer
request(){}
request(int a, int b, int c): d(a) ,lca(b), pos(c) {}
};
int n, m, Q;
int p[MaxN], idx[MaxN], c[MaxN];
vi adj[MaxN];
int lst[MaxN], src[MaxN];
vector<request> req[MaxN];
int ans[MaxN];
void dfsInit(int u, int pre) {
int tlst = lst[c[u]];
lst[c[u]] = u;
src[u] = lst[p[1]];
dep[u] = dep[pre] + 1;
A.insert(u, lst[p[idx[c[u]] + 1]]);
B.insert(u, lst[p[idx[c[u]] - 1]]);
for (int i = 0; i < (int)adj[u].size(); ++i) {
int v = adj[u][i];
if (v == pre) continue;
T.insert(v, u);
dfsInit(v, u);
}
lst[c[u]] = tlst;
}
void dfsSolve(int u, int pre) {
int tlst = lst[c[u]];
lst[c[u]] = u;
for (int i = 0; i < (int)adj[u].size(); ++i) {
int v = adj[u][i];
if (v == pre) continue;
dfsSolve(v, u);
}
for (int i = 0; i < (int)req[u].size(); ++i) {
request R = req[u][i];
int l = R.d + 1, r = m, mid, res = R.d;
int lim = dep[R.lca] + 1;
while (l <= r) {
mid = (l + r) >> 1;
if (B.jump(lst[p[mid]], lim) >= mid - R.d)
l = mid + 1, res = mid;
else
r = mid - 1;
}
ans[R.pos] = res;
}
lst[c[u]] = tlst;
}
int main() {
freopen("gem.in", "r", stdin);
freopen("gem.out", "w", stdout);
read(n), read(m)/*no use*/, read(m);
for (int i = 1; i <= m; ++i) {
read(p[i]);
idx[p[i]] = i;
}
for (int i = 1; i <= n; ++i) {
read(c[i]);
}
for (int i = 1; i < n; ++i) {
int u, v;
read(u), read(v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfsInit(1, 0);
read(Q);
for (int q = 1; q <= Q; ++q) {
int u, v;
read(u), read(v);
int lca = T.queryLCA(u, v);
ans[q] = A.jump(src[u], dep[lca]);
// cerr << u << ' ' << v << ':' << lca << ':' << ans[q] << '
';
if (lca != v) {
req[v].push_back(request(ans[q], lca, q));
}
}
dfsSolve(1, 0);
for (int q = 1; q <= Q; ++q) {
putint(ans[q]);
putchar('
');
}
return 0;
}
算法二
第二段的询问并不需要二分。可以将第一段已经得到的点放到 (mathrm{lca}) 的地方，离线 DFS 的时候用可撤销并查集维护。
这样总的时间复杂度就是 (mathcal O(n log n + Q log m)) 了。
算法三
算法一中的 (mathrm{lca}) 其实可以换一种角度看待。
用点分治处理所有路径询问，对于跨过某个分治中心 (G) 的询问，就将 (G) 看成算法一中的 (mathrm{lca}) 来处理。
这样的好处就是，可以直接算出到每个点 (u) 到 (G) 的路径上，在 (P) 中往前和往后分别能跳多少步，就不需要倍增了。
每个询问的第二段就像算法一那样二分，但是检查的时候也不需要倍增。
时间复杂度 (mathcal O(n log n + Qlog m))。
E. D2T2 滚榜
显然，最后排名的顺序就是滚榜顺序的倒序，所以我们只需要对滚榜顺序进行计数即可。
显然，在滚榜顺序确定的情况下，既然要求通过题数不下降且总和 (=m)，那么有一种最优构造就是依次取可能的最小值，多出来的放到最后一个滚榜的人身上。
那么判断一个排列是否合法，就相当于判断每个人都取最少题数的时候，总题数是否 (leq m)。
记原先的第一名为 (p_0)，滚榜顺序为排列 (p_1sim p_n)。显然我们有：
[b_i = max(b_{i-1},b_{i-1}+a_{p_{i-1}}-a_{p_i}+[p_i>p_{i-1}]) \
sum_{i=1}^n b_i = sum_{i=1}^n(n-i+1)cdot max(0, a_{p_{i-1}}-a_{p_i}+[p_i>p_{i-1}])
]
于是我们就可以设计一个状压 DP，设 (f(s,v,l)) 表示以下条件的方案数：
- 已经用了集合 (s) 中的元素作为排列的前 (|s|) 个元素
- 当前
[sum_{i=1}^{lvert s
vert}(n-i+1)cdot max(0, a_{p_{i-1}}-a_{p_i}+[p_i>p_{i-1}])=v
]
- 最后一个元素，即 (p_{|s|}=l)。
转移就再枚举一个 (x in [n]setminus S)，转移到
[fBig(scup {x}, v+(n-i+1)cdot max(0, a_{p_{i-1}}-a_{p_i}+[p_i>p_{i-1}]), xBig)
]
时间复杂度 (mathcal O(2^nn^2m))，卡卡常数可以过。
另：https://www.luogu.com.cn/blog/gyh20/solution-p7519
题解里面有另一种做法，大概是折半搜索。
code
#include <bits/stdc++.h>
using std::max;
using std::cerr;
using std::cout;
typedef long long s64;
template <class T>
inline void read(T &x) {
static char ch;
while (!isdigit(ch = getchar()));
x = ch - '0';
while (isdigit(ch = getchar()))
x = x * 10 + ch - '0';
}
const int MaxN = 15;
int n, m;
int a[MaxN], p[MaxN];
const int MaxS = 1 << 13 | 5;
const int MaxM = 510;
s64 f[MaxS][MaxM][MaxN];
int main() {
freopen("ranklist.in", "r", stdin);
freopen("ranklist.out", "w", stdout);
read(n), read(m);
a[0] = -1;
for (int i = 1; i <= n; ++i) {
read(a[i]);
if (a[i] > a[p[0]]) p[0] = i;
}
int all = (1 << n) - 1;
for (int i = 1; i <= n; ++i) {
int val = max(0, a[p[0]] - a[i] + (i > p[0])) * n;
if (val <= m) {
f[1 << (i - 1)][val][i] = 1;
}
}
for (int s = 1; s <= all; ++s) {
int cnt = 0, seq[MaxN], nS = 0;
for (int i = 1; i <= n; ++i)
if (s >> (i - 1) & 1)
++cnt;
else
seq[++nS] = i;
for (int v = 0; v <= m; ++v)
for (int lst = 1; lst <= n; ++lst)
if (f[s][v][lst]) {
int val = f[s][v][lst];
for (int j = 1; j <= nS; ++j) {
int i = seq[j];
int c = max(0, a[lst] - a[i] + (i > lst)) * (n - cnt);
if (v + c <= m)
f[s | (1 << (i - 1))][v + c][i] += val;
}
}
}
s64 res = 0;
for (int v = 0; v <= m; ++v)
for (int i = 1; i <= n; ++i)
res += f[all][v][i];
cout << res << '
';
return 0;
}
F. D2T3 支配
首先我们定义 (x operatorname{dom} y) 当且仅当 (1 o y) 的每条路径都经过了点 (x)。不难发现以下性质：
- (xoperatorname{dom} y,yoperatorname{dom} zimplies xoperatorname{dom} z)
- (xoperatorname{dom} y, yoperatorname{dom} ximplies x=y)
- (xoperatorname{dom} z, yoperatorname{dom} zimplies xoperatorname{dom} y operatorname{lor} yoperatorname{dom} x)
于是对于一个点 (x(x eq 1))，(D_x) 中的点可以根据它们之间的支配关系排成一条链。
我们总能找到唯一一个 (yin D_xsetminus{x})，使得 (forall zin D_xsetminus{x} , zoperatorname{dom} y)，这里的 (y) 就是 (D_xsetminus{x}) 中 (|D_y|) 最大的点。将 (y) 往 (x) 连边，我们就会连出一个 (n) 个点的图，每个点入度 (leq 1)，也不存在环，而 (1) 又支配所有点，因此一定是一棵有根外向树，我们就称之为支配树。
很容易发现，(D_x) 即这个支配树上 (x) 的祖先集合 (operatorname{anc}(x)) 并上自己，即 (D_x=operatorname{anc}(x)cup {x})。
那么首先建出原图的支配树，这里直接 (mathcal O(n(m+n))) 删去每个点后跑 DFS/BFS 求出受支配集 (D_x) 后建出来。
记 (mathrm{fa}_x) 表示 (x) 在支配树上的父亲。
那么加一条边后，显然 (D_x'subseteq D_x)，新的 (D_x') 就是原来 (x) 到根的路径上的一些点。所以如果 (D_x) 改变，那么只有可能是 (mathrm{fa}_x) 改变了或者 (D_{mathrm{fa}_x}) 改变了。
而如果 (mathrm{fa}_x) 改变了，(x) 子树中的所有点的 (D_x) 都会改变。我们只需要考虑每个点 (x) 的 (mathrm{fa}_x) 是否还支配 (x) 即可。
具体地，对于每个点 (x)，删去 (mathrm{fa}_x) 后从 (1) 开始 DFS/BFS，肯定会有 (1) 无法到达 (x)（因为 (mathrm{fa}_x operatorname{dom} x)）。此时，记删去 (mathrm{fa}_x) 后的图是 (G_{x})，我们将当前这张图点分成三类：
- 从 (1) 开始能够到达的点构成点集 (A_x)。
- 从 (y) 出发能够走到 (x) 的点构成点集 (B_x)。
- 其余点构成点集 (C_x)。
显然，一条连边 ((u,v)) 会使 (mathrm{fa}_x) 不再支配 (x)，当且仅当 (uin A_xland vin B_x)。
依次判断即可做到 (mathcal O(n(m+n)+Qn)) 的时间复杂度。
code
#include <bits/stdc++.h>
#define foredge(u) for (int e = adj[u], v; v = to[e], e; e = nxt[e])
using std::cerr;
using std::vector;
typedef vector<int> vi;
template <class T>
inline void read(T &x) {
static char ch;
while (!isdigit(ch = getchar()));
x = ch - '0';
while (isdigit(ch = getchar()))
x = x * 10 + ch - '0';
}
template <class T>
inline void putint(T x) {
static char buf[15], *tail = buf;
if (!x) putchar('0');
else {
if (x < 0) putchar('-'), x = ~x + 1;
for (; x; x /= 10) *++tail = x % 10 + '0';
for (; tail != buf; --tail) putchar(*tail);
}
}
const int MaxN = 3e3 + 5;
const int MaxE = MaxN << 2;
int n, m, Q;
int par[MaxN];
vi dom[MaxN], adj[MaxN], adjR[MaxN];
void bfs(int del) {
static int que[MaxN], qr;
static bool vis[MaxN];
for (int i = 1; i <= n; ++i) {
vis[i] = false;
}
if (del != 1) {
vis[que[qr = 1] = 1] = true;
for (int i = 1; i <= qr; ++i) {
int u = que[i];
for (int ei = 0; ei < (int)adj[u].size(); ++ei) {
int v = adj[u][ei];
if (!vis[v] && v != del) {
vis[que[++qr] = v] = true;
}
}
}
}
for (int i = 1; i <= n; ++i)
if (!vis[i]) dom[i].push_back(del);
}
int dfn[MaxN];
int tag[MaxN][MaxN];
void makeTag(int del, int st) {
if (del == 1) return;
static int que[MaxN], qr;
static bool vis[MaxN];
for (int i = 1; i <= n; ++i) vis[i] = false;
vis[que[qr = 1] = 1] = true;
for (int i = 1; i <= qr; ++i) {
int u = que[i];
tag[u][dfn[st]] = 1;
for (int ei = 0; ei < (int)adj[u].size(); ++ei) {
int v = adj[u][ei];
if (!vis[v] && v != del) {
vis[que[++qr] = v] = true;
}
}
}
for (int i = 1; i <= n; ++i) vis[i] = false;
vis[que[qr = 1] = st] = true;
for (int i = 1; i <= qr; ++i) {
int u = que[i];
tag[u][dfn[st]] = 2;
for (int ei = 0; ei < (int)adjR[u].size(); ++ei) {
int v = adjR[u][ei];
if (!vis[v] && v != del) {
vis[que[++qr] = v] = true;
}
}
}
}
vi adjT[MaxN];
int dfsClock, idx[MaxN], sze[MaxN];
void dfsInit(int u) {
idx[dfn[u] = ++dfsClock] = u;
for (int ei = 0; ei < (int)adjT[u].size(); ++ei) {
int v = adjT[u][ei];
dfsInit(v);
}
}
int main() {
freopen("dominator.in", "r", stdin);
freopen("dominator.out", "w", stdout);
read(n), read(m), read(Q);
for (int i = 1; i <= m; ++i) {
int u, v;
read(u), read(v);
adj[u].push_back(v);
adjR[v].push_back(u);
}
for (int i = 1; i <= n; ++i) {
bfs(i);
}
for (int u = 1; u <= n; ++u) {
for (int i = 0; i < (int)dom[u].size(); ++i) {
int v = dom[u][i];
if (dom[v].size() == dom[u].size() - 1) {
par[u] = v;
break;
}
}
if (u > 1) adjT[par[u]].push_back(u);
// cerr << u << ':' << par[u] << '
';
}
dfsInit(1);
for (int u = 2; u <= n; ++u) {
makeTag(par[u], u);
}
while (Q--) {
int x, y;
read(x), read(y);
static bool chg[MaxN];
int ans = 0;
for (int i = 2; i <= n; ++i) {
int u = idx[i];
chg[u] = chg[par[u]] | (tag[x][i] == 1 && tag[y][i] == 2);
ans += chg[u];
}
putint(ans), putchar('
');
}
return 0;
}
G. B卷 D1T1 数对
略。
H. B卷 D2T1 取模
先将 (a_1sim a_n) 全部排序。
假设当前的模数是 (a_k)，记 (b_i=a_i mod a_k)。
假设选出的两个数为 (i,j(i eq j,i eq k,j eq k))：
- 若 (b_i + b_j geq a_k)，这个时候我们只要找 (b_i,b_j) 最大的两个相加计算即可。
- 若 (b_i + b_j < a_k)，这个时候我们只要对于每个 (b_i)，找到最大的满足 (b_i + b_j < a_k) 的 (b_j) 即可，排序后用双指针扫描。
但是如果对于每个 (a_k) 都这么做的话，时间复杂度显然是 (mathcal O(n^2 log n)) 的。
但是我们只需要从大到小枚举 (a_k)，并且储存当前的最优答案 (mathrm{ans})，在 (a_k - 1 > mathrm{ans}) 的时候才去计算，否则就结束程序。
显然需要计算的是一段后缀。假设当前考虑到了 (a_k)，那么
[mathrm{ans} < a_k leq a_{k+1} leq cdots leq a_n
]
显然
[mathrm{ans} geq (a_i + a_{i+1}) mod a_{i+2}geq a_i + a_{i+1} - a_{i+2}(a_i<a_{i+2})
]
注意这个分析在相同的 (a_i) 不超过两个的时候才是成立的，否则时间复杂度就会可能是错的。
因此
[a_{i+2}-mathrm{ans} geq (a_i-mathrm{ans}) + (a_{i-1} - mathrm{ans})
]
注意到 (a_i - mathrm{ans} > 0)，因此 (a_i-mathrm{ans}=mathcal O(V)) 是斐波那契数列级别的增长（(V) 表示 (a) 的最大值），所以需要枚举的个数是 (mathcal O(log V)) 的。
因此时间复杂度为 (mathcal O(n log n log V))。
#include <bits/stdc++.h>
template <class T>
inline void read(T &x) {
static char ch;
while (!isdigit(ch = getchar()));
x = ch - '0';
while (isdigit(ch = getchar()))
x = x * 10 + ch - '0';
}
template <class T>
inline void relax(T &x, const T &y) {
if (x < y) x = y;
}
const int MaxN = 2e5 + 5;
int ans;
int n, a[MaxN];
void solve(int p, int del) {
static int b[MaxN], m;
m = 0;
for (int i = 1; i <= n; ++i) {
if (i != del) b[++m] = a[i] % p;
}
std::sort(b + 1, b + m + 1);
relax(ans, (b[m - 1] + b[m]) % p);
for (int i = 1, lst = m; i <= m; ++i) {
while (lst > i && b[lst] + b[i] >= p) --lst;
if (lst <= i) return;
relax(ans, b[i] + b[lst]);
}
}
int main() {
freopen("mod.in", "r", stdin);
freopen("mod.out", "w", stdout);
read(n);
for (int i = 1; i <= n; ++i) {
read(a[i]);
}
std::sort(a + 1, a + n + 1);
ans = 0;
for (int i = n; i >= 1; --i)
if (a[i] - 1 > ans && (i == 1 || a[i] != a[i - 1]))
solve(a[i], i);
std::cout << ans << '
';
return 0;
}