「GXOI/GZOI 2019」所有题目【题解】

题目列表

  • D1T1. 与或和
  • D1T2. 宝牌一大堆
  • D1T3. 特技飞行
  • D2T1. 逼死强迫症
  • D2T2. 旅行者
  • D2T3. 旧词

简要题解

D1T1. 与或和

题目大意:给定一个 n×nn \times n 的矩阵,求出:

  • 该矩阵的所有子矩阵的 AND(&)\text{AND} (\&) 值之和。
  • 该矩阵的所有子矩阵的 OR()\text{OR} (|) 值之和。

输出答案对 109+710^9 + 7 取模的值。保证 n1000n \leqslant 1000,矩阵中的数 2311\leqslant 2^{31} - 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
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

const int maxn = 1010, P = 1000000007;
int n, tp, s1, s2, a[maxn][maxn], b[maxn][maxn], l[maxn];
pair<int, int> st[maxn];

int solve() {
memset(l, 0, sizeof(l));
int ans = 0;
for (int i = 1; i <= n; i++) {
int s = 0; tp = 0;
for (int j = 1; j <= n; j++) {
l[j] = b[i][j] ? l[j] + 1 : 0;
int tmp = 1;
while (tp && st[tp].x >= l[j]) {
s -= st[tp].x * st[tp].y, tmp += st[tp--].y;
}
st[++tp] = make_pair(l[j], tmp);
s = (s + 1LL * l[j] * tmp) % P;
ans = (ans + s) % P;
}
}
return ans;
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
}
}
int tmp = n * (n + 1) / 2;
tmp = 1LL * tmp * tmp % P;
for (int i = 1; ; i <<= 1) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
b[j][k] = a[j][k] & i;
}
}
s1 = (s1 + 1LL * i * solve()) % P;
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
b[j][k] = !(a[j][k] & i);
}
}
s2 = (s2 + 1LL * i * (tmp - solve() + P)) % P;
if (i == 1 << 30) break;
}
printf("%d %d\n", s1, s2);
return 0;
}

D1T2. 宝牌一大堆

题目大意((麻将中)) 制定若干种宝牌。对每种判定和牌的手牌定义一个达成分数:

从未打出的牌中选出若干张组成该手牌的方案数,再乘上手牌中 22 的宝牌数次方。

给定所有尚未打出的牌,求达成分数最高的可和牌的手牌有多少分。保证数据组数 2500\leqslant 2500,宝牌数 20\leqslant 20,宝牌不会重复给出。具体规则请参考原始题面。

思路分析:设 f(i,j,k,l,q)f(i, j, k, l, q) 表示处理了前 ii 种牌,有 jj 个面子 // 杠子,以 i1i - 1 开头的顺子选了 kk 个,以 ii 开头的顺子选了 ll 个,以及当前是否有雀头。国士无双和七对子单独处理即可。

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int T, cnt[35], b[35], ban[35], C[5][5];
ll f[36][5][5][5][2];
char s[3]; map<char, int> mp;
bool upd(ll &x, ll y) { if (x < y) x = y; }

ll solve1() {
memset(f, 0, sizeof(f)), f[1][0][0][0][0] = 1;
for (int i = 1; i <= 34; i++) {
for (int j = 0; j <= 4; j++) {
for (int k = 0; k <= 4; k++) {
for (int l = 0; l <= 4; l++) {
for (int q = 0; q <= 1; q++) {
if (!f[i][j][k][l][q]) continue;
upd(f[i + 1][j][l][0][q], f[i][j][k][l][q]);
if (!ban[i] && i < 26) {
int h = b[i] * b[i + 1] * b[i + 2];
for (int c = 1, g = 1; j + c <= 4; c++) {
if (k + l + c > cnt[i]) break;
if (l + c > cnt[i + 1]) break;
if (c > cnt[i + 2]) break;
upd(f[i + 1][j + c][l][c][q], f[i][j][k][l][q]
/ C[cnt[i]][k + l] * C[cnt[i]][k + l + c]
/ C[cnt[i + 1]][l] * C[cnt[i + 1]][l + c] *
C[cnt[i + 2]][c] * (g *= h));
}
}
if (k + l + 3 <= cnt[i] && j < 4) {
upd(f[i + 1][j + 1][l][0][q], f[i][j][k][l][q]
/ C[cnt[i]][k + l] * C[cnt[i]][k + l + 3]
* b[i] * b[i] * b[i]);
}
if (!k && !l && cnt[i] == 4 && j < 4) {
upd(f[i + 1][j + 1][l][0][q], f[i][j][k][l][q]
/ C[cnt[i]][k + l] * b[i] * b[i] * b[i] * b[i]);
}
if (!q && k + l + 2 <= cnt[i]) {
upd(f[i + 1][j][l][0][1], f[i][j][k][l][0]
/ C[cnt[i]][k + l] * C[cnt[i]][k + l + 2]
* b[i] * b[i]);
}
}
}
}
}
}
return f[35][4][0][0][1];
}

ll solve2() {
vector<int> V;
for (int i = 1; i <= 34; i++) {
if (cnt[i] >= 2) {
V.push_back(C[cnt[i]][2] * b[i] * b[i]);
}
}
if (V.size() < 7) return 0;
ll ans = 7; sort(V.begin(), V.end());
for (int i = 1; i <= 7; i++) {
ans *= V[V.size() - i];
}
return ans;
}

ll solve3() {
ll ans = 13, mx = 0;
ans *= cnt[1] * cnt[9] * b[1] * b[9];
ans *= cnt[10] * cnt[18] * b[10] * b[18];
ans *= cnt[19] * cnt[27] * b[19] * b[27];
for (int i = 28; i <= 34; i++) {
ans *= cnt[i] * b[i];
}
if (!ans) return ans;
upd(mx, ans * C[cnt[1]][2] * b[1] / cnt[1]);
upd(mx, ans * C[cnt[9]][2] * b[9] / cnt[9]);
upd(mx, ans * C[cnt[10]][2] * b[10] / cnt[10]);
upd(mx, ans * C[cnt[18]][2] * b[18] / cnt[18]);
upd(mx, ans * C[cnt[19]][2] * b[19] / cnt[19]);
upd(mx, ans * C[cnt[27]][2] * b[27] / cnt[27]);
for (int i = 28; i <= 34; i++) {
upd(mx, ans * C[cnt[i]][2] * b[i] / cnt[i]);
}
return mx;
}

int main() {
for (int i = 0; i <= 4; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
mp['E'] = 28, mp['S'] = 29, mp['W'] = 30;
mp['N'] = 31, mp['Z'] = 32, mp['B'] = 33;
mp['F'] = 34, mp['m'] = 1, mp['p'] = 10, mp['s'] = 19;
ban[8] = ban[9] = ban[17] = ban[18] = 1;
scanf("%d", &T);
while (T--) {
for (int i = 1; i <= 34; i++) {
cnt[i] = 4, b[i] = 1;
}
while (scanf("%s", s) && s[0] != '0') {
if (strlen(s) == 1) cnt[mp[s[0]]]--;
else cnt[mp[s[1]] + s[0] - '1']--;
}
while (scanf("%s", s) && s[0] != '0') {
if (strlen(s) == 1) b[mp[s[0]]] = 2;
else b[mp[s[1]] + s[0] - '1'] = 2;
}
printf("%lld\n", max(solve1(), max(solve2(), solve3())));
}
return 0;
}

D1T3. 特技飞行

题目大意:有 nn 条起点和终点横坐标相同的线段。当两个线段相交时,如果交换接下来的部分 ((变为折线)) 可以获得 bb 的收益,否则可以获得 aa 的收益。另外给出 kk 个正方形,第 ii 个正方形包含区域 xpi+yqiri\lvert x - p_i \rvert + \lvert y - q_i \rvert \leqslant r_i 的所有点。一个交点若落入一个或多个区域,就可以再获得 cc 的收益。求可以获得的最低收益和最高收益。保证 n,k105n, k \leqslant 10^5 且交点数 5×105\leqslant 5 \times 10^5

示意图

思路分析:显然本题是二合一。注意到每个交点就是一个逆序对,所以可以先暴力求出所有交点。

考虑第一个问题。其实可以发现有两种极端情况:

  • 第一种 (a(a 最大)):所有逆序对全部交换,最后一定恰好变成正序。
  • 第二种 (a(a 最小)):总次数为 (len1)\sum (\text{len} - 1),其中 len\text{len} 为循环节的长度。

考虑第二个问题。注意到这些正方形都是斜的,所以要旋转坐标系,即 (x,y)(x+y,xy)(x, y) \to (x + y, x - y)。显然是一个经典的扫描线,用动态开点线段树维护即可。

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
#include <bits/stdc++.h>
#define mid (l + r >> 1)
using namespace std;

const int maxn = 100010;
const double EPS = 1e-6;
int n, K, a, b, c, st, ed, ans, tot, rt, cnt;
int s1, s2, g0[maxn], g1[maxn], p[maxn], vis[maxn];
struct event { double x, y; int tp, val; };
vector<event> V; set<pair<int, int> > S;
struct node { int l, r, s; } t[2000010];
bool comp1(int i, int j) { return g1[i] < g1[j]; }
bool comp2(event i, event j) { return i.x < j.x; }

void ins(int &k, int l, int r, int p, int v) {
if (!k) k = ++tot; t[k].s += v;
if (l == r) return;
if (mid >= p) ins(t[k].l, l, mid, p, v);
else ins(t[k].r, mid + 1, r, p, v);
}

int sum(int k, int l, int r, int ql, int qr) {
if (!k || l >= ql && r <= qr) return t[k].s;
int s = 0;
if (mid >= ql) s += sum(t[k].l, l, mid, ql, qr);
if (mid < qr) s += sum(t[k].r, mid + 1, r, ql, qr);
return s;
}

int main() {
scanf("%d %d %d %d %d %d", &n, &a, &b, &c, &st, &ed);
for (int i = 1; i <= n; i++) {
scanf("%d", &g0[i]), p[i] = i;
}
for (int i = 1, x; i <= n; i++) {
scanf("%d", &g1[i]);
}
sort(p + 1, p + n + 1, comp1), scanf("%d", &K);
for (int i = 1, t1, t2, p, q, r; i <= K; i++) {
scanf("%d %d %d", &t1, &t2, &r);
p = t1 + t2, q = t1 - t2;
V.push_back((event){p - r - EPS, q - r, 0, 1});
V.push_back((event){p - r - EPS, q + r + 1, 0, -1});
V.push_back((event){p + r + EPS, q - r, 0, -1});
V.push_back((event){p + r + EPS, q + r + 1, 0, 1});
}
for (int i = n; i; i--) {
set<pair<int, int> >::iterator it = S.begin();
for (; it != S.end(); it++) {
if (it->first > g1[i]) break;
double x = g1[i] - it->first, y = it->second - g0[i];
double ix = (st * x + ed * y) / (x + y);
double iy = g0[i] + (g1[i] - g0[i]) * (ix - st) / (ed - st);
V.push_back((event){ix + iy, ix - iy, 1, 0}), cnt++;
}
S.insert(make_pair(g1[i], g0[i]));
}
sort(V.begin(), V.end(), comp2);
for (int i = 0; i < V.size(); i++) {
if (!V[i].tp) ins(rt, -5e7, 5e7, V[i].y, V[i].val);
else if (sum(rt, -5e7, 5e7, -5e7, floor(V[i].y))) ans += c;
}
for (int i = 1; i <= n; i++) if (!vis[i]) {
int j = i, k = vis[i] = 1;
while (i ^ p[j]) vis[j = p[j]] = 1, k++;
s2 += k - 1;
}
s1 = cnt * a, s2 = s2 * a + (cnt - s2) * b;
printf("%d %d\n", ans + min(s1, s2), ans + max(s1, s2));
return 0;
}

D2T1. 逼死强迫症

题目大意:要用 nn2×12 \times 1 的方砖来铺 2×n2 \times n 的路,但是有一块砖断裂为两块 1×11 \times 1 的砖块。求有多少种铺路方法,使得两块砖没有相邻的边。保证数据组数 500,\leqslant 500, n2×109n \leqslant 2 \times 10^9

思路分析:设 fif_i 表示 n=in = i 时的答案,gig_i 表示斐波那契数列,那么有:

fi=fi1+fi2+2gi12f_i = f_{i - 1} + f_{i - 2} + 2g_{i - 1} - 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
#include <bits/stdc++.h>
using namespace std;

const int P = 1000000007;
int T, n;
struct mat { int a[5][5]; } A, B, C;

mat operator * (const mat &A, const mat &B) {
mat C; memset(C.a, 0, sizeof(C.a));
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
for (int k = 0; k < 5; k++) {
C.a[i][k] = (C.a[i][k] + 1LL * A.a[i][j] * B.a[j][k]) % P;
}
}
}
return C;
}

int main() {
scanf("%d", &T);
C.a[0][0] = C.a[0][1] = C.a[1][0] = 1;
C.a[2][2] = C.a[2][3] = C.a[3][2] = C.a[4][4] = 1;
C.a[2][0] = 2, C.a[4][0] = P - 2;
while (T--) {
scanf("%d", &n), n -= 3;
if (n < 0) { printf("0\n"); continue; }
memset(A.a, 0, sizeof(A.a));
A.a[0][0] = 2, A.a[0][2] = 3;
A.a[0][3] = 2, A.a[0][4] = 1;
for (B = C; n; n >>= 1, B = B * B) {
if (n & 1) A = A * B;
}
printf("%d\n", A.a[0][0]);
}
return 0;
}

D2T2. 旅行者

题目大意:给定一张 nn 个点、mm 条边的有向图 ((有边权)) 和选定的 kk 个点,求这 kk 个点之间两两最短路的最小值。保证 2kn105,2 \leqslant k \leqslant n \leqslant 10^5, m5×105m \leqslant 5 \times 10^5

思路分析:预处理出 kk 个点到每个点的距离最小值 d1d_1,以及每个点到 kk 个点的距离最小值 d2d_2。枚举每条边 uvu \to v ((边权为 w)w),答案即为下式的最小值,注意不能把环算进答案:

d1(u)+w+d2(v)d_1(u) + w + d_2(v)

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, int> P;
const int maxn = 100010;
int T, n, m, K, a[maxn], b[maxn], c[maxn];
ll d1[maxn], d2[maxn];
struct edge { int v, w; };
vector<edge> G[maxn], H[maxn];
priority_queue<P, vector<P>, greater<P> > q;

void dijkstra(ll *d, vector<edge> *G, int *t) {
while (!q.empty()) {
P p = q.top(); int v = p.second; q.pop();
if (d[v] ^ p.first) continue;
for (int i = 0, u; i < G[v].size(); i++) {
if (d[u = G[v][i].v] > d[v] + G[v][i].w) {
t[u] = t[v], q.push(P(d[u] = d[v] + G[v][i].w, u));
}
}
}
}

int main() {
scanf("%d", &T);
while (T--) {
scanf("%d %d %d", &n, &m, &K);
for (int i = 1; i <= n; i++) {
G[i].clear(), H[i].clear();
}
for (int i = 1, u, v, w; i <= m; i++) {
scanf("%d %d %d", &u, &v, &w);
G[u].push_back((edge){v, w}), H[v].push_back((edge){u, w});
}
memset(d1, 0x3f, sizeof(d1));
memset(d2, 0x3f, sizeof(d2));
for (int i = 1; i <= K; i++) {
scanf("%d", &a[i]), q.push(P(d1[a[i]] = 0, b[a[i]] = a[i]));
}
dijkstra(d1, G, b);
for (int i = 1; i <= K; i++) {
q.push(P(d2[a[i]] = 0, c[a[i]] = a[i]));
}
dijkstra(d2, H, c);
ll ans = LLONG_MAX;
for (int i = 1; i <= n; i++) {
for (int j = 0, k; j < G[i].size(); j++) {
if (b[i] == c[k = G[i][j].v]) continue;
ans = min(ans, d1[i] + G[i][j].w + d2[k]);
}
}
printf("%lld\n", ans);
}
return 0;
}

D2T3. 旧词

题目大意:给定一棵 nn 个点的有根树和常数 kk,有 qq 个询问,每次给定 x,yx, y,求:

ixdepth(lca(i,y))k\sum_{i \leqslant x} \text{depth}(\text{lca}(i, y))^k

输出答案对 998244353998244353 取模的值。保证 n,q5×104,n, q \leqslant 5 \times 10^4, 1k1091 \leqslant k \leqslant 10^9

思路分析:本题与 【LNOI 2014】LCA 类似。设结点 vv 差分后的值为:

wv=depth(v)kdepth(fa(v))kw_v = \text{depth}(v)^k - \text{depth}(\text{fa}(v))^k

考虑离线,将 ii 从小到大加入,每次将 ii 到根的路径上的所有点加上自己的 ww 值,查询时求 i=xi = xyy 到根的路径上的所有点的权值和即可。

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
#define mid (l + r >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;

const int maxn = 50010, P = 998244353;
int n, m, K, dfn, dep[maxn], fa[maxn], ans[maxn];
int sz[maxn], tid[maxn], top[maxn], son[maxn], pos[maxn];
vector<int> G[maxn];
struct node { int s, ans, mul; } t[maxn << 2];
struct query { int id, x, y; } q[maxn];
bool comp(query a, query b) { return a.x < b.x; }
void add(int &x, int y) { if ((x += y) >= P) x -= P; }

int qp(int x, int y) {
int z = 1;
for (; y; y >>= 1, x = 1LL * x * x % P) {
if (y & 1) z = 1LL * z * x % P;
}
return z;
}

int get(int x) {
return (qp(x, K) - qp(x - 1, K) + P) % P;
}

void dfs1(int v, int f, int d) {
fa[v] = f, dep[v] = d, sz[v] = 1;
for (int i = 0, u; i < G[v].size(); i++) {
dfs1(u = G[v][i], v, d + 1), sz[v] += sz[u];
if (sz[u] > sz[son[v]]) son[v] = u;
}
}

void dfs2(int v, int rt) {
pos[tid[v] = ++dfn] = v, top[v] = rt;
if (son[v]) dfs2(son[v], rt);
for (int i = 0, u; i < G[v].size(); i++) {
if ((u = G[v][i]) ^ son[v]) dfs2(u, u);
}
}

void build(int k, int l, int r) {
if (l == r) { t[k].s = get(dep[pos[l]]); return; }
build(ls, l, mid), build(rs, mid + 1, r);
t[k].s = (t[ls].s + t[rs].s) % P;
}

void pushdown(int k) {
add(t[ls].ans, 1LL * t[k].mul * t[ls].s % P);
add(t[rs].ans, 1LL * t[k].mul * t[rs].s % P);
add(t[ls].mul, t[k].mul), add(t[rs].mul, t[k].mul), t[k].mul = 0;
}

void upd(int k, int l, int r, int ql, int qr) {
if (l >= ql && r <= qr) { t[k].mul++, add(t[k].ans, t[k].s); return; }
if (t[k].mul) pushdown(k);
if (mid >= ql) upd(ls, l, mid, ql, qr);
if (mid < qr) upd(rs, mid + 1, r, ql, qr);
t[k].ans = (t[ls].ans + t[rs].ans) % P;
}

int sum(int k, int l, int r, int ql, int qr) {
if (l >= ql && r <= qr) return t[k].ans;
if (t[k].mul) pushdown(k); int s = 0;
if (mid >= ql) add(s, sum(ls, l, mid, ql, qr));
if (mid < qr) add(s, sum(rs, mid + 1, r, ql, qr));
return s;
}

void modify(int u, int v) {
for (; top[u] ^ top[v]; u = fa[top[u]]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
upd(1, 1, n, tid[top[u]], tid[u]);
}
if (dep[u] > dep[v]) swap(u, v);
upd(1, 1, n, tid[u], tid[v]);
}

int query(int u, int v) {
int s = 0;
for (; top[u] ^ top[v]; u = fa[top[u]]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
add(s, sum(1, 1, n, tid[top[u]], tid[u]));
}
if (dep[u] > dep[v]) swap(u, v);
add(s, sum(1, 1, n, tid[u], tid[v]));
return s;
}

int main() {
scanf("%d %d %d", &n, &m, &K);
for (int i = 2, f; i <= n; i++) {
scanf("%d", &f), G[f].push_back(i);
}
for (int i = 1; i <= m; i++) {
scanf("%d %d", &q[i].x, &q[i].y), q[i].id = i;
}
sort(q + 1, q + m + 1, comp);
dfs1(1, 0, 1), dfs2(1, 1), build(1, 1, n);
for (int i = 1, j = 1; i <= n; i++) {
modify(1, i);
for (; j <= m && q[j].x == i; j++) {
ans[q[j].id] = query(1, q[j].y);
}
}
for (int i = 1; i <= m; i++) {
printf("%d\n", ans[i]);
}
return 0;
}