2020牛客暑期多校训练营(第二场)

Tsukkomi

这场的难度感觉是我目前最需要的 qwq


Problem D. Duration

Description

给定同一天的两个时刻,求这两个时刻相差的秒数。
时刻以 HH:MM:SS (00HH23, 00MM,SS59)\left(00\leq\mathrm{HH}\leq23,\ 00\leq\mathrm{MM,SS}\leq59\right) 的形式给出。

Solution

签到题。

时间复杂度:O(1)\mathcal O\left(1\right) .

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int h1, m1, s1, h2, m2, s2;

void solve(void);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d:%d:%d%d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
printf("%d\n", abs((h2 - h1) * 3600 + (m2 - m1) * 60 + s2 - s1));
}

Problem F. Fake Maxpooling

Description

给定一个 n×mn\times m (1n,m5×103)\left(1\leq n,m\leq5\times10^3\right) 的矩阵 AA ,其中 Ai,j=lcm(i,j)A_{i,j}=\operatorname{lcm}\left(i,j\right) .
给定 kk (1kmin(n,m))\left(1\leq k\leq\min\left(n,m\right)\right) ,求

i=1nk+1j=1mk+1maxixi+k1, jyj+k1Ax,y\sum_{i=1}^{n-k+1}\sum_{j=1}^{m-k+1}\max_{i\leq x\leq i+k-1,\ j\leq y\leq j+k-1}A_{x,y}

Solution

先预处理出矩阵 AA ,这部分的时间复杂度为 O(nmlogmax(n,m))\mathcal O\left(nm\log\max\left(n,m\right)\right) .
这里容易 常数过大 ,求 lcm\operatorname{lcm} 时可以对 gcd\gcd 加个 记忆化 进行优化。
更好的办法是求 lcm(a,b)\operatorname{lcm}\left(a,b\right) 的时处理所有的 lcm(ka,kb)\operatorname{lcm}\left(ka,kb\right) ,将 logmax(n,m)\log\max\left(n,m\right) 优化掉。
之后再用 单调队列递推 求出所有 k×kk\times k 的子矩阵的最大元素,求和即可。

时间复杂度:O(nm)\mathcal O\left(nm\right) .

Code

单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 5e3 + 5;
int n, m, k;
int a[N][N];
deque<pii> q;
ll ans;

void solve(void);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
for (int j = 1, u; j <= m; j++) {
if (a[i][j]) continue;
u = min(n / i, m / j);
for (int k = 1; k <= u; k++) a[k * i][k * j] = k * i * j;
}
for (int i = 1; i <= n; i++) {
while (!q.empty()) q.pop_back();
for (int j = 1; j <= m; j++) {
if (!q.empty() && q.front().first <= j - k) q.pop_front();
while (!q.empty() && q.back().second <= a[i][j]) q.pop_back();
q.emplace_back(j, a[i][j]);
if (j >= k) a[i][j - k + 1] = q.front().second;
}
}
for (int j = 1; j <= m - k + 1; j++) {
while (!q.empty()) q.pop_back();
for (int i = 1; i <= n; i++) {
if (!q.empty() && q.front().first <= i - k) q.pop_front();
while (!q.empty() && q.back().second <= a[i][j]) q.pop_back();
q.emplace_back(i, a[i][j]);
if (i >= k) ans += q.front().second;
}
}
printf("%lld\n", ans);
}

递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 5e3 + 5;
int n, m, k;
int a[N][N];
ll ans;

void solve(void);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
for (int j = 1, u; j <= m; j++) {
if (a[i][j]) continue;
u = min(n / i, m / j);
for (int k = 1; k <= u; k++) a[k * i][k * j] = k * i * j;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j < k; j++)
a[i][k] = a[i][j] > a[i][k] ? a[i][j] : a[i][k];
for (int j = k; j <= m; j++) {
if (k > 1) {
a[i][j] = a[i][j - 1] > a[i][j] ? a[i][j - 1] : a[i][j];
a[i][j] = a[i - 1][j] > a[i][j] ? a[i - 1][j] : a[i][j];
}
if (i >= k) ans += a[i][j];
}
}
printf("%lld\n", ans);
}

Problem C. Cover the Tree

Description

给定一棵 nn (1n2×105)\left(1\leq n\leq2\times10^5\right) 个点的无根树,树边以 (u,v)\left(u,v\right) 的形式给出。
求最少需要多少条链才能覆盖树上的所有边,并输出一种方案。
一条边被覆盖当且仅当在某条链上,一条链用两个链端表示。

Solution

构造题

链若覆盖所有的边,则必定 覆盖所有的点
设选定了某个点 rr 作为根结点后有 kk 个叶子结点,第 ii 个叶子结点为 aia_i .
一条链至多覆盖两个叶子结点,故链数的下界为 k2\left\lceil\frac k2\right\rceil .
显然答案可以这样达到下界:

  • 2k2\nmid k ,选择链 (r,ak)\left(r,a_k\right) 后即可视为只有 k1k-1 个叶子结点。
  • 2k2\mid k ,将叶子结点两两配对作为链的链端。
    保证 rr 的每棵子树都有叶子结点和 另一棵子树 的叶子结点配对。

有一种特殊情况即 rr 的度为 11 时,则:

  • 选择链 (r,ak)\left(r,a_k\right) ,找到 rr 的第一个度大于 11 的子孙结点 rr' .
  • 考虑以 rr' 为根的子树中剩下的 k1k-1 个叶子结点即可。

最简单的做法即,一开始就选择一个度大于 11 的点为 rr .
假定 rr 的度大于 112k2\mid k ,只需考虑叶子结点的配对问题。
一使链数最少的可行方案即:

  • 将叶子结点按 DFS 序排序。
  • i[1,k2]\forall i\in\left[1,\frac k2\right] ,令 aia_iai+k2a_{i+\frac k2} 配对即可。

时间复杂度:O(n)\mathcal O\left(n\right) .

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
int n;
int edg = 1, head[N], to[N << 1], nxt[N << 1];
int r, k, d[N], le[N];

void solve(void);
void add_edge(int u, int v);
void dfs(int u, int f = 0);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d", &n);
for (int i = 1, u, v; i < n; i++)
scanf("%d%d", &u, &v), add_edge(u, v), d[u]++, d[v]++;
for (int i = 1; i <= n && !r; i++) r = d[i] > 1 ? i : r;
dfs(r), printf("%d\n", (k + 1) / 2);
for (int i = 1; i <= k / 2; i++) printf("%d %d\n", le[i], le[i + k / 2]);
if (k & 1) printf("%d %d\n", r, le[k]);
}

inline void add_edge(int u, int v) {
to[++edg] = v, nxt[edg] = head[u], head[u] = edg;
to[++edg] = u, nxt[edg] = head[v], head[v] = edg;
}

void dfs(int u, int f) {
if (d[u] == 1) return le[++k] = u, void();
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (v ^ f) dfs(v, u);
}
}

Problem B. Boundary

Description

给定二维平面上的 nn (1n2×103)\left(1\leq n\leq2\times10^3\right) 个点。
每个点以 (x,y)\left(x,y\right) (0x,y104)\left(0\leq\left|x\right|,\left|y\right|\leq10^4\right) 的形式给出,不为原点 OO 且两两互异。
存在一个过原点 OO 的圆使得圆上的给定点最多,求该圆上的给定点数量。

Solution

Solution 1

std 解法。

考虑过点 OO 且圆上给定点数量最多的一个圆。
该圆上必定有一给定点 PP 满足弧 OPOP 上无其他给定点。
枚举这个点 PP ,再枚举弧 OPOP 某一侧的其他所有的给定点 AA .
设在弧 OPOP 的某一侧最多有 kPk_P 个给定点和 O,PO,P 共圆。
同弧所对的圆周角相等 可知 圆周角 OAP\angle OAP众数kPk_P ,答案即 maxkP\max k_P .

时间复杂度:O(n2logn)\mathcal O\left(n^2\log n\right) .

Solution 2

枚举不共线的两相异点,它们和原点共圆。
圆心 并借助 map排序 统计出现次数。
显然 出现次数最多 的圆心对应的圆上给定点数量最多。
假定枚举的两个相异点是 无序的 ,设出现次数最多的圆心为 pp .
pp 的出现次数为 kk ,对应的圆上有 xx 个给定点。
x(x1)2=k\frac{x\left(x-1\right)}2=k ,故 x=2kx=\left\lceil\sqrt{2k}\right\rceil .

时间复杂度:O(n2logn)\mathcal O\left(n^2\log n\right) .

Code

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
typedef double db;

const int N = 2e3 + 5;
const db eps = 1e-12;
int n, x[N], y[N];
vector<db> ag;
int ans = 1;

void solve(void);
int cross(int xa, int ya, int xb, int yb);
db get_agcir(int xp, int yp, int xa, int ya);
db dis(int xa, int ya, int xb = 0, int yb = 0);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", x + i, y + i);
for (int i = 1; i <= n; i++) {
ag.clear();
for (int j = 1; j <= n; j++) {
if (cross(x[i], y[i], x[j], y[j]) >= 0) continue;
ag.push_back(get_agcir(x[i], y[i], x[j], y[j]));
}
sort(ag.begin(), ag.end());
for (int l = 0, r; l < ag.size(); l = r) {
for (r = l; fabs(ag[l] - ag[r]) < eps && r < ag.size();) r++;
ans = max(ans, r - l + 1);
}
}
printf("%d\n", ans);
}

inline int cross(int xa, int ya, int xb, int yb) { return xa * yb - xb * ya; }

inline db get_agcir(int xp, int yp, int xa, int ya) {
db a = dis(xa, ya), b = dis(xp, yp, xa, ya), c = dis(xp, yp);
return (a * a + b * b - c * c) / (2 * a * b);
}

inline db dis(int xa, int ya, int xb, int yb) {
return sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
}

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
typedef double db;
typedef pair<db, db> pdd;

const int N = 2e3 + 5;
const db eps = 1e-6;
int n, x[N], y[N];
int ct = 1, k;
vector<pdd> pt;

void solve(void);
pdd get_cen(int xa, int ya, int xb, int yb);
bool equ(const pdd &a, const pdd &b);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", x + i, y + i);
for (int i = 1; i < n; i++)
for (int j = i + 1; j <= n; j++) {
if (x[j] * y[i] == x[i] * y[j]) continue;
pt.push_back(get_cen(x[i], y[i], x[j], y[j]));
}
sort(pt.begin(), pt.end());
for (int i = 1; i < pt.size(); i++)
ct = equ(pt[i], pt[i - 1]) ? ct + 1 : 1, k = max(k, ct);
printf("%d\n", (int) sqrt(k << 1) + 1);
}

inline pdd get_cen(int xa, int ya, int xb, int yb) {
int d = (xb * ya - xa * yb) << 1;
db x = xb * xb * 1ll * ya - xa * xa * 1ll * yb + ya * yb * 1ll * (yb - ya);
db y = xa * yb * 1ll * yb - xb * ya * 1ll * ya + xa * xb * 1ll * (xb - xa);
return make_pair(x / d, y / -d);
}

inline bool equ(const pdd &a, const pdd &b) {
return fabs(a.first - b.first) < eps && fabs(a.second - b.second) < eps;
}

Problem J. Just Shuffle

Description

给定一个 1n1\sim n (1n105)\left(1\leq n\leq10^5\right) 的排列 AA 和一个大素数 kk (108k109)\left(10^8\leq k\leq10^9\right) .
求一个 1n1\sim n 的置换 PP ,使得序列 {1,2,,n}\left\{1,2,\dots,n\right\} 经过 kkPP 置换后恰为 AA .

Solution

AA 为一个置换并表示为 不相杂轮换之积 ,设 A=i=1mfiA=\prod\limits_{i=1}^mf_i .
fi\left|f_i\right|fif_i ,则 fi<k, gcd(fx,k)=1\left|f_i\right|<k,\ {\gcd}\left(\left|f_x\right|,k\right)=1 .
故模 fi\left|f_i\right| 意义下 ri=inv(k)r_i=\operatorname{inv}\left(k\right) 存在,显然令 P=i=1mfiriP=\prod\limits_{i=1}^mf_i^{r_i} 即可。

时间复杂度:O(n)\mathcal O\left(n\right) .

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, k, a[N];
bool vis[N];
int f[N], p[N];

void solve(void);
int inv(int a, int p);
int exgcd(int a, int b, int &x, int &y);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 1, ct; i <= n; i++) {
if (vis[i]) continue;
vis[i] = true, ct = 1, f[0] = i;
for (int j = a[i]; j != i; j = a[j]) vis[j] = true, f[ct++] = j;
int r = inv(k, ct);
for (int j = 0; j < ct; j++) p[f[j]] = f[(j + r) % ct];
}
for (int i = 1; i <= n; i++) printf("%d%c", p[i], " \n"[i == n]);
}

inline int inv(int a, int p) {
int x, y, g = exgcd(a, p, x, y);
return p /= g, (x % p + p) % p;
}

int exgcd(int a, int b, int &x, int &y) {
if (!b) return (x = 1, y = 0), a;
int g = exgcd(b, a % b, y, x);
return y -= a / b * x, g;
}

Problem A. All with Pairs

Description

对于字符串 ss ,记 prei(s)pre_i\left(s\right) 为长度为 ii 的前缀,sufi(s)suf_i\left(s\right) 为长度为 ii 的后缀。
定义

f(s,t)=max{kk[1,min(s,t)], prek(s)=sufk(t)}f\left(s,t\right)= \max\left\{k\big|k\in\left[1,\min\left(\left|s\right|,\left|t\right|\right)\right],\ pre_k\left(s\right)=suf_k\left(t\right)\right\}

特别的,当满足 prek(s)=sufk(t)pre_k\left(s\right)=suf_k\left(t\right)kk 不存在时 f(s,t)=0f\left(s,t\right)=0 .
给定 nn (1n105)\left(1\leq n\leq10^5\right) 个仅由小写字母构成的字符串。
ii 个字符串为 sis_i (1si,i=1nsi106)\left(1\leq\left|s_i\right|,\sum\limits_{i=1}^n\left|s_i\right|\leq10^6\right) .

ans=(i=1nj=1nf(si,sj)2)mod998244353ans=\left(\sum_{i=1}^n\sum_{j=1}^nf\left(s_i,s_j\right)^2\right)\bmod998244353

Solution

gi,j=k=1n[f(si,sk)=j]g_{i,j}=\sum_{k=1}^n\left[f\left(s_i,s_k\right)=j\right]

ans=i=1nj=1nf(si,sj)2=i=1nj=1sigi,jj2ans=\sum_{i=1}^n\sum_{j=1}^nf\left(s_i,s_j\right)^2=\sum_{i=1}^n\sum_{j=1}^{\left|s_i\right|}g_{i,j}\cdot j^2

直接求 gg 比较困难。
引入辅助量,记

cnti,j=k=1n[prej(si)=sufj(sk)]cnt_{i,j}=\sum_{k=1}^n\left[pre_j\left(s_i\right)=suf_j\left(s_k\right)\right]

考虑 KMP ,记 nextjinext^i_jsis_i 对应的 Next 数组的第 jj 位。
显然有

gi,j=cnti,jj<ksi, nextki=jcnti,kg_{i,j}=cnt_{i,j}-\sum\limits_{j<k\leq\left|s_i\right|,\ next^i_k=j}cnt_{i,k}

对于 cntcnt ,利用 Hash 统计即可。

时间复杂度:O(i=1nsi)\mathcal O\left(\sum\limits_{i=1}^n\left|s_i\right|\right) .

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int p = 998244353;
const int m = (1 << 7) - 1;
int n;
char s[M];
ull pw[M];
vector<int> nxt[N];
vector<ull> hsh[N];
unordered_map<ull, int> mp;
int ans, g[M];

void solve(void);
void get_nxt(int x, int n, char *s);
void get_hsh(int x, int n, char *s);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d", &n), pw[0] = 1;
for (int i = 1; i < M; i++) pw[i] = pw[i - 1] * m;
for (int i = 1, ls; i <= n; i++) {
scanf("%s", s + 1), ls = strlen(s + 1);
nxt[i].resize(ls + 1), get_nxt(i, ls, s);
hsh[i].resize(ls + 1), get_hsh(i, ls, s);
for (int j = 0; j < ls; j++) mp[hsh[i][ls] - hsh[i][j] * pw[ls - j]]++;
}
for (int i = 1; i <= n; i++) {
int len = nxt[i].size() - 1;
for (int j = 1; j <= len; j++)
g[j] = mp[hsh[i][j]], g[nxt[i][j]] -= g[j];
for (int j = 1; j <= len; j++)
ans = (ans + g[j] * 1ll * j % p * j % p) % p;
}
printf("%d\n", ans);
}

void get_nxt(int x, int n, char *s) {
for (int i = 2, p = 0; i <= n; i++) {
while (p && s[p + 1] != s[i]) p = nxt[x][p];
nxt[x][i] = s[p + 1] == s[i] ? ++p : p;
}
}

void get_hsh(int x, int n, char *s) {
for (int i = 1; i <= n; i++) hsh[x][i] = hsh[x][i - 1] * m + s[i] - 'a' + 1;
}

Problem E. Exclusive OR

Description

给定长度为 nn (1n2×105)\left(1\leq n\leq2\times10^5\right) 的序列 AA (0Ai<218)\left(0\leq A_i<2^{18}\right) .
i=1,2,,ni=1,2,\dots,n ,求

ansi=max1a1,a2,,ainj=1iAajans_i=\max_{1\leq a_1,a_2,\dots,a_i\leq n}\bigoplus_{j=1}^iA_{a_j}

Solution

显然当 i>2i>2ansiansi2ans_i\geq ans_{i-2} .
以下证明当 i>19i>19 时,ansi=ansi2ans_i=ans_{i-2} .
注意到 Ai<218A_i<2^{18} ,则:

  • i<19i<19 时从 AA重复 选元素不会使 ansians_i 变大。
  • 必定 k[1,18]\exists k\in\left[1,18\right] ,对 i[1,n]\forall i\in\left[1,n\right] 满足 anskansians_k\geq ans_i .
    即至多需要 kk 个不同元素使 ansians_i 达到 满秩

假设当 i>19i>19 时,ansi>ansi2ans_i>ans_{i-2} .
则说明至少需要 1919 个不同元素才能使 ansians_i 达到满秩,显然矛盾。
故当 i>19i>19 时,ansi=ansi2ans_i=ans_{i-2} .
只需对 i=1,2,,min(19,n)i=1,2,\dots,\min\left(19,n\right) ,用 FWTansians_i 即可。
设一长度为 2182^{18} 的序列 ff ,对 i[0,218)\forall i\in\left[0,2^{18}\right)

fi=[j[1,n], Aj=i]f_i=\left[\exists j\in\left[1,n\right],\ A_j=i\right]

ansi=max{jj[0,218), fji>0}ans_i=\max\left\{j\big|j\in\left[0,2^{18}\right),\ f^i_j>0\right\}

注意每次卷积完要 令大于 00 的项为 11 ,避免之后的卷积出现取模为 00 的情况。

时间复杂度:O(Alog2A)\mathcal O\left(A\log^2A\right) .

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
const int m = 1 << 18;
const int M = m + 5;
const int p = 998244353;
const int iv2 = (p + 1) >> 1;

int n;
int k, f[M], g[M], ans[N];

void solve(void);
void fwt_xor(int *a, int n, int f = 1);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d", &n), f[0] = 1;
for (int i = 1, a; i <= n; i++) scanf("%d", &a), g[a] = 1;
fwt_xor(f, m), fwt_xor(g, m), k = min(19, n);
for (int i = 1; i <= k; i++) {
for (int j = 0; j < m; j++) f[j] = f[j] * 1ll * g[j] % p;
fwt_xor(f, m, -1);
for (int j = m - 1; ~j; j--)
if (f[j]) f[j] = 1, ans[i] = ans[i] ? ans[i] : j;
fwt_xor(f, m);
}
for (int i = k + 1; i <= n; i++) ans[i] = ans[i - 2];
for (int i = 1; i <= n; i++) printf("%d%c", ans[i], " \n"[i == n]);
}

void fwt_xor(int *a, int n, int f) {
for (int i = 1, s = 2; i < n; i <<= 1, s <<= 1)
for (int j = 0; j < n; j += s)
for (int k = 0; k < i; k++) {
int x = a[j + k], y = a[i + j + k];
a[j + k] = (x + y) % p, a[i + j + k] = (x - y + p) % p;
if (!~f) {
a[j + k] = a[j + k] * 1ll * iv2 % p;
a[i + j + k] = a[i + j + k] * 1ll * iv2 % p;
}
}
}

Problem G. Greater and Greater

Description

给定一个长度为 nn (1n1.5×105)\left(1\leq n\leq1.5\times10^5\right) 的序列 AA .
再给定一个长度为 mm (1mmin(n,4×104))\left(1\leq m\leq\min\left(n,4\times10^4\right)\right) 的序列 BB (1Ai,Bi109)\left(1\leq A_i,B_i\leq10^9\right) .

ans=i=1nm+1[j[i,i+m1], AjBj]ans=\sum_{i=1}^{n-m+1}\left[\forall j\in\left[i,i+m-1\right],\ A_j\geq B_j\right]

Solution

为了方便,假定 bitset 下标从 11 开始。
bitset si,j=[AiBj], Im,i=[i=m]s_{i,j}=\left[A_i\geq B_j\right],\ I_{m,i}=\left[i=m\right] .
考虑如何求 ss ,注意到 ss 本质上只有 O(m)\mathcal O\left(m\right) 种。
将序列 BB 从小到大 排序记为 BB' ,再设一序列 pp 满足 Bi=BpiB'_i=B_{p_i} .
si,j=[BiBj]s'_{i,j}=\left[B'_i\geq B_j\right] ,则 si=si1Ipis'_i=s'_{i-1}|I_{p_i} .
对于 i=1,2,,mi=1,2,\dots,m ,令 j=max{kBkAi}j=\max\left\{k\big|B'_k\leq A_i\right\} .
jj 存在则 si=sjs_i=s'_j ,否则对 k[1,m], si,k=0\forall k\in\left[1,m\right],\ s_{i,k}=0 .
bitset

curi,j=[k[j,m], Ai+kjBk]cur_{i,j}=\left[\forall k\in\left[j,m\right],\ A_{i+k-j}\geq B_k\right]

则有

curi=((curi+1>>1)Im)&sicur_i=\left(\left(cur_{i+1}>>1\right)|I_m\right)\&s_i

边界条件,对 i[1,m], curn,i=[i=m, AnBm]\forall i\in\left[1,m\right],\ cur_{n,i}=\left[i=m,\ A_n\geq B_m\right] .
显然

ans=i=1nm+1[curi,1=1]=i=1n[curi,1=1]ans=\sum_{i=1}^{n-m+1}\left[cur_{i,1}=1\right]=\sum_{i=1}^n\left[cur_{i,1}=1\right]

时间复杂度:O(m(n+m)bit)\mathcal O\left(\frac{m\left(n+m\right)}{bit}\right) .

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;

const int N = 1.5e5 + 5;
const int M = 4e4 + 5;
int n, m, a[N], b[M];
int ans, t[M], p[M];
bitset<M> cur, s[M];

void solve(void);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) scanf("%d", a + i);
for (int i = 0; i < m; i++) scanf("%d", b + i), t[i] = b[i], p[i] = i;
sort(t, t + m), sort(p, p + m, [](int x, int y) { return b[x] < b[y]; });
for (int i = 1; i <= m; i++) s[i] = s[i - 1], s[i].set(p[i - 1]);
for (int i = n - 1; ~i; i--) {
cur >>= 1, cur.set(m - 1);
cur &= s[upper_bound(t, t + m, a[i]) - t], ans += cur[0];
}
printf("%d\n", ans);
}

Problem I. Interval

Description

给定一个区间 [1,n]\left[1,n\right] (2n5×102)\left(2\leq n\leq5\times10^2\right) ,区间 [l,r]\left[l,r\right] (l<r)\left(l<r\right) 有两种变化:

  • Shrinking :将 [l,r]\left[l,r\right] 变为 [l+1,r]\left[l+1,r\right][l,r1]\left[l,r-1\right] .
  • Expanding :将 [l,r]\left[l,r\right] 变为 [l1,r]\left[l-1,r\right] (l>1)\left(l>1\right)[l,r+1]\left[l,r+1\right] (r<n)\left(r<n\right) .

现有 mm (0mn(n1))\left(0\leq m\leq n\left(n-1\right)\right) 条禁令,每条禁令以 (l,r,dir,c)\left(l,r,dir,c\right) 的形式给出。
禁令 (l,r,dir,c)\left(l,r,dir,c\right) (l<r, 1c106)\left(l<r,\ 1\leq c\leq10^6\right)dirdir 为字符 LR ,表示:

  • dirdirL 时,可以代价 cc 禁止 [l,r]\left[l,r\right][l+1,r]\left[l+1,r\right] 相互变化。
  • dirdirR 时,可以代价 cc 禁止 [l,r]\left[l,r\right][l,r1]\left[l,r-1\right] 相互变化。

若通过禁令可使区间 [1,n]\left[1,n\right] 长度不可变化为 11 则求最小代价,否则输出 1-1 .

Solution

解决这道题需要先了解 平面图对偶图

  • 平面图 :可画在平面上且任意两边的交点都是 顶点 的图。
  • 对偶图 :一种和平面图相伴的图。

对于平面图 G=V,EG=\left\langle V,E\right\rangle ,设 GG 将平面划分为 kk 个面。
记第 ii 个面为 fif_i ,定义 GG 的对偶图 G=V,EG'=\left\langle V',E'\right\rangle 如下:

  • 对于 GG 划分的每个面 fif_i ,在其内部选一点 viv_i ,令 viVv_i\in V' .
  • 对每一条边 (u,v)E\left(u,v\right)\in E ,分情况考虑:
    • (u,v)\left(u,v\right) 是某两个面 fx,fyf_x,f_y 的公共边界,则 vx,vyv_x,v_y 之间连边 eu,ve_{u,v} .
      eu,ve_{u,v}(u,v)\left(u,v\right) 交于一点且边权相同,令 eu,vEe_{u,v}\in E' .
    • (u,v)\left(u,v\right) 仅是某一个面 fxf_x 的边界,则 vxv_x 连自环 eu,ve_{u,v} .
      eu,ve_{u,v}(u,v)\left(u,v\right) 交于一点且边权相同,令 eu,vEe_{u,v}\in E' .

视无向图 GG 为一容量网络,源点为 ss ,汇点为 tt .
先在 GG 中加一条连接 s,ts,t 的边 ee ,作 GG 的对偶图 GG' .
GG 因添加 ee 而得到的新面和最外的无限平面分别对应 GG' 中的点 s,ts',t' .
删去 ss'tt' 的连边,则 ss'tt' 的一条路径对应 GG 中的一个 ST 割
ss'tt' 的最短路长度即 GG最小割

考虑原问题,显然可以转化为一个 网格图网络流 问题。
设一 n×nn\times n 的网格图,记第 ii 行第 jj 列的网点为 (i,j)\left(i,j\right) .
令区间 [l,r]\left[l,r\right] 对应点 (l,r)\left(l,r\right) ,建图 GG 如下:

  • 取源点 ss(1,n)\left(1,n\right) ,并设一汇点 tt .
  • 对每一个禁令 (l,r,dir,c)\left(l,r,dir,c\right)
    • dirdirL ,则 (l,r)\left(l,r\right)(l+1,r)\left(l+1,r\right) 相互连边,容量为 cc .
    • dirdirR ,则 (l,r)\left(l,r\right)(l,r1)\left(l,r-1\right) 相互连边,容量为 cc .
  • 对其他未被禁令限制的区间变化,对应点间相互连边,容量为 inf\inf .
  • i[1,n]\forall i\in\left[1,n\right](i,i)\left(i,i\right)tt 连边,容量为 inf\inf .

显然答案即 GG最小割 ,在 对偶图 上用 Dijkstra最短路 即可。
当且仅当 最短路不存在或长度为 inf\inf 时无解。
注意边权为 inf\inf 的边对答案无影响,为了方便建对偶图可适当略去这些边。

时间复杂度:O(n2logn)\mathcal O\left(n^2\log n\right) .

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct edge {
int u;
ll d;
edge(int a = 0, ll b = 0): u(a), d(b) {}
bool operator<(const edge &t) const { return d > t.d; }
};

const int N = 5e2 + 5;
const int M = (N * N) >> 1;
const ll inf = 1e18 + 5;
int n, m;
char dir;
int s, t, idx[N][N];
int edg = 1, head[M], to[M << 2], nxt[M << 2];
ll dis[M], wei[M << 2], wgt[N][N][2];
priority_queue<edge> q;

void solve(void);
void add_edge(int u, int v, ll w);
void dijkstra(void);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d%d", &n, &m), s = 1, t = n * (n - 1) / 2 + 2;
for (int i = 1, id = 1; i < n; i++)
for (int j = i + 1; j <= n; j++)
idx[i][j] = ++id, wgt[i][j][0] = wgt[i][j][1] = inf;
for (int i = 1, l, r, d, c; i <= m; i++) {
scanf("%d%d %c%d", &l, &r, &dir, &c), d = dir != 'L';
wgt[l][r][d] = min(wgt[l][r][d], 1ll * c);
}
for (int i = 1; i < n; i++)
for (int j = i + 1; j <= n; j++) {
if (i > 1) {
add_edge(idx[i][j], idx[i - 1][j], wgt[i][j][1]);
add_edge(idx[i - 1][j], idx[i][j], wgt[i][j][1]);
}
if (j < n) {
add_edge(idx[i][j], idx[i][j + 1], wgt[i][j][0]);
add_edge(idx[i][j + 1], idx[i][j], wgt[i][j][0]);
}
}
for (int i = 1; i < n; i++) {
add_edge(s, idx[i][n], wgt[i][n][0]);
add_edge(idx[1][i + 1], t, wgt[1][i + 1][1]);
}
dijkstra(), printf("%lld\n", dis[t] < inf ? dis[t] : -1);
}

inline void add_edge(int u, int v, ll w) {
to[++edg] = v, wei[edg] = w, nxt[edg] = head[u], head[u] = edg;
}

void dijkstra(void) {
memset(dis, 63, (t + 1) * sizeof(ll)), q.emplace(s, dis[s] = 0);
for (edge t; !q.empty();) {
t = q.top(), q.pop();
int u = t.u;
ll d = t.d;
if (d > dis[u]) continue;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
ll w = wei[i];
if (dis[v] <= dis[u] + w) continue;
q.emplace(v, dis[v] = dis[u] + w);
}
}
}

Welcome to my other publishing channels