六省联考做题笔记

0072Vf1pgy1g2yj49i0moj31cm0ppe812b62fbd8ecb7533e.jpg

六省联考

期末考试

如果我们知道最晚公布课程的时间\(T\), 我们是可以直接算出在当前时间\(T\)下的最小不愉快度的.

并且最小不愉快度是可以在一个固定的\(T\)下取到最小值的.可以看出这个东西可以三分(感性理解).

具体的我们三分一个时间点\(T\), 然后贪心的使用\(1, 2\)就好了.

注意有一个\(\text{C=}10^{16}\)的坑点.

代码:

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
/*
* 4868.cpp
* This file is part of BZOJ_4868
*
* Copyright (C) 2019 - ViXbob
*
* BZOJ_4868 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* BZOJ_4868 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with BZOJ_4868. If not, see <http://www.gnu.org/licenses/>.
*/

// Begin at 2019-04-27 16:53:31 - ViXbob

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)

typedef unsigned long long ull;
typedef long long ll;

using namespace std;

const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;

int n, m, A, B, t[maxn], b[maxn];
ll C;

inline ll read() {
char ch = getchar(); ll u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline ll F(int mid, ll rnt = 0) {
ll L = 0, R = 0;
rep(i, 1, n) if(t[i] <= mid) rnt += 1ll * (mid - t[i]) * C;
rep(i, 1, m) if(b[i] <= mid) L += mid - b[i]; else R += b[i] - mid;
if(A < B) {
if(L >= R) rnt += 1ll * A * R;
else rnt += 1ll * A * L + 1ll * (R - L) * B;
} else rnt += 1ll * R * B;
return rnt;
}

inline ll ThreePoint(int l, int r) {
int mid = (l + r) / 2;
while(l <= r) {
mid = (l + r) / 2;
// cerr << "F(" << mid << ") = " << F(mid) << endl;
if(F(mid - 1) > F(mid + 1)) l = mid + 1;
else r = mid - 1;
}
// cerr << l << " " << r << endl;
mid = l + r >> 1;
return min(F(mid), min(F(mid - 1), F(mid + 1)));
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
A = read(); B = read(); C = read(); n = read(); m = read();
rep(i, 1, n) t[i] = read();
rep(i, 1, m) b[i] = read();
sort(b + 1, b + 1 + m);
sort(t + 1, t + 1 + n);
if(C == 1e16) cout << F(t[1]);
else cout << ThreePoint(b[1], b[m]) << endl;
return 0;
}

相逢是问候

一开始暴力都打萎了,我就说为啥没找到规律.

首先我们得知道欧拉定理: \[ \begin{aligned}a^b=\begin{cases}a^b&,b<\varphi(p)\\a^{b\bmod \varphi(p)+\varphi(p)}&, b \ge \varphi(p)\end{cases}\pmod{p}\end{aligned} \] 这样就愉悦的打暴力了.然后我们可以发现经过若干次\(0\)操作后,最后的值是个定值.我们大力猜想:不管是什么数被操作\(log\)次以后一定是个常数.

然后这道题就做完了, 对于\(0\)操作我们直接对每个数暴力算并更新线段树维护一下区间和就好了.

因为每个数有效的操作次数只有\(log\)次,并且每次计算的复杂度是\(log\)的.所以复杂度为\(O(nlog^2n)\)(要用\(O(1)\)快速幂,否则复杂度是\(O(nlog^3n)\)的).

考虑证明一下上述结论:

设:\(\varphi^k(p)=\varphi(\varphi(\varphi(....\varphi(p))))\), 说人话就是对\(p\)\(k\)\(\varphi\).

上述结论等价于证明当\(k \ge 2\times log(p)\)\(\varphi^k(p) = 1\), 现在有两个结论:

  1. 如果\(p\)为偶数, \(\varphi(p) \le \frac{n}{2}\).
  2. 如果\(p\)为奇数, \(\varphi(n)\)为偶数.

这个两个结论都非常好证明.所以每取两次\(\varphi\)原数必定会减小\(\frac{1}{2}\).因此当\(k \ge 2 \times log(p)\)\(\varphi^k(p)=1\).

PS:\(2 \times log(p)\)只是一个非常非常松的上界而已.

代码:

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
/*
* 4869.cpp
* This file is part of BZOJ_4869
*
* Copyright (C) 2019 - ViXbob
*
* BZOJ_4869 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* BZOJ_4869 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with BZOJ_4869. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)

typedef unsigned long long ull;

using namespace std;

const int maxn = 5e4 + 5;
const int inf = 0x3f3f3f3f;
const int U = 1 << 16;

int n, m, kphi[55], P, Lim, c, a[maxn];
int mi[55][U + 5], mmi[55][U + 5];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int Phi(int x) {
int rnt = x;
for(int i = 2; i * i <= x; i++) if(x % i == 0) {
while(x % i == 0) x /= i;
rnt = rnt / i * (i - 1);
}
if(x > 1) rnt = rnt / x * (x - 1);
return rnt;
}

inline int getmi(int i, int n) { return 1ll * mi[i][n & (U - 1)] * mmi[i][n >> 16] % kphi[i]; }
inline int calc(int a, int n) {
// cerr << "a = " << a << ", n = " << n << endl;
// if(!a) a = kphi[n];
// cerr << n << " " << Lim << endl;
n = min(n, Lim);
dep(i, n, 1) {
if(a >= kphi[i]) a = a % kphi[i] + kphi[i];
// cerr << a << endl;
a = getmi(i - 1, a);
// cerr << kphi[i - 1] << endl;
// cerr << "a = " << a << endl;
if(!a) a = kphi[i - 1];
}
// cerr << "ans = " << a << endl;
return a;
}

int mn[maxn << 2], sum[maxn << 2];
#define ls p << 1
#define rs p << 1 | 1
#define mid (l + r >> 1)
inline void Build(int l, int r, int p) {
if(l == r) return (void)(a[r] = sum[p] = read());
Build(l, mid, ls); Build(mid + 1, r, rs);
sum[p] = (sum[ls] + sum[rs]) % P;
}

inline void modify(int l, int r, int p) {
if(mn[p] > Lim) return;
if(l == r) {
++mn[p]; if(mn[p] > Lim) return;
return (void)(sum[p] = calc(a[r], mn[p]));
}
modify(l, mid, ls); modify(mid + 1, r, rs);
sum[p] = (sum[ls] + sum[rs]) % P;
mn[p] = min(mn[ls], mn[rs]);
}

inline void modifz(int l, int r, int ql, int qr, int p){
if(ql == l && qr == r) return modify(l, r, p);
if(qr <= mid) modifz(l, mid, ql, qr, ls);
else if(ql > mid) modifz(mid + 1, r, ql, qr, rs);
else modifz(l, mid, ql, mid, ls), modifz(mid + 1, r, mid + 1, qr, rs);
sum[p] = (sum[ls] + sum[rs]) % P;
mn[p] = min(mn[ls], mn[rs]);
}

inline int query(int l, int r, int ql, int qr, int p) {
if(l == ql && r == qr) return sum[p];
if(qr <= mid) return query(l, mid, ql, qr, ls);
else if(ql > mid) return query(mid + 1, r, ql, qr, rs);
else return (query(l, mid, ql, mid, ls) + query(mid + 1, r, mid + 1, qr, rs)) % P;
}
#undef ls
#undef rs
#undef mid

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); m = read(); P = read(); c = read(); kphi[0] = P;
while(kphi[Lim] > 1) kphi[Lim + 1] = Phi(kphi[Lim]), Lim++;
// cerr << kphi[Lim] << endl;
kphi[++Lim] = 1;
// rep(i, 0, Lim) cerr << "kphi[" << i << "] = " << kphi[i] << endl;
rep(i, 0, Lim) {
mi[i][0] = 1 % kphi[i];
rep(j, 1, U) mi[i][j] = 1ll * mi[i][j - 1] * c % kphi[i];
mmi[i][0] = 1 % kphi[i];
rep(j, 1, U) mmi[i][j] = 1ll * mmi[i][j - 1] * mi[i][U] % kphi[i];
}
// cerr << calc(3, 1) << endl;
// cerr << calc(1, 2) << endl;
// cerr << calc(1, 3) << endl;
// cerr << calc(0, 8) << endl;
// return 0;
Build(1, n, 1);
rep(i, 1, m) {
int opt = read(), l = read(), r = read();
// cerr << "opt_" << i << " = " << opt << endl;
if(!opt) modifz(1, n, l, r, 1);
else printf("%d\n", query(1, n, l, r, 1) % P);
}
return 0;
}
/*
4 4 3 2
1 2 3 4
0 1 4
1 2 4
0 1 4
1 1 3


*/

组合数问题

矩阵快速幂模板题?

设: \[ \begin{aligned}f[i][j] &= \sum _ {r=0}^{+\infin}\binom{i}{rk+j}\\&=\sum_{r = 0} ^ {+\infin}\binom{i-1}{rk+j}+\sum_{r=0}^{+\infin}\binom{i-1}{rk+(j-1)}\\&=f[i-1][j]+f[i-1][(j-1)\bmod k]\end{aligned} \] 直接矩阵快速幂就好了,复杂度\(O(k^3\log n)\)

代码:

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
/*
* 4870.cpp
* This file is part of BZOJ_4870
*
* Copyright (C) 2019 - ViXbob
*
* BZOJ_4870 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* BZOJ_4870 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with BZOJ_4870. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)

using namespace std;

typedef long long ll;

const int maxn = 5005;
const int inf = 0x3f3f3f3f;

int n, r, k, P;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

struct Matrix {
int H, W;
vector<vector<int> > mat;
Matrix(int a = 0, int b = 0) {
H = a; W = b;
mat.resize(H);
for(auto &v : mat) v.resize(W);
}

vector<int> &operator [] (int i) { return mat[i]; }

Matrix operator * (const Matrix &t) const {
Matrix rnt(H, t.W);
rep(i, 0, H - 1) rep(j, 0, W - 1) rep(k, 0, t.W - 1)
rnt[i][j] = (rnt[i][j] + 1ll * mat[i][k] * t.mat[k][j] % P) % P;
return rnt;
}
} T, A, tmp;

inline int ksm(int x, ll k, int rnt = 1) {
for(ll i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}

int main() {
// freopen("1.in", "r", stdin);
n = read(); P = read(); k = read(); r = read();
if(k == 1) { printf("%d\n", ksm(2, 1ll * n * k)); return 0; }
if(k == 2) { printf("%d\n", ksm(2, 1ll * n * k - 1)); return 0; }
T = Matrix(k, k); A = Matrix(1, k); tmp = Matrix(k, k);
// cerr << "ok" << endl;
rep(i, 0, k - 1) T[i][i] = 1, T[(i - 1 + k) % k][i] = 1, tmp[i][i] = 1;
// cerr << "ok" << endl;
A[0][0] = 1;
for(ll i = 1ll * n * k; i; i >>= 1, T = T * T) if(i & 1) tmp = tmp * T;
A = A * tmp;
printf("%d\n", A[0][r]);
return 0;
}
/*
*/

摧毁「树状图」

愁死我了啊, 怎么这种普及\(\text{dp}\)给我打了一天.吃枣药丸的说.

一句话题意:选出两条没有边交的链, 使得删掉和选出的链上所有点相关的边后联通块个数最大.

经过计算我们发现联通块的个数等于选出的点的度数和\(-\)边数\(\times 2-\)链的个数+1, 边数又等于选出的点数\(-\)链的个数.所以答案为选出的点的度数和-点数\(\times 2+\)链的个数$+$1.(没有点交,并且没有两个点属于不同的链但是有直接边相连的这两种情况.特殊的这两种情况答案都要减一.)

考虑\(\text{dp}\), 设\(f[i][0/1/2][0/1/2/3]\)表示\(\text{dp}\)完了\(i\)这个子树, 确定了\(0/1/2\)条链, \(i\)的度数为\(0/1/2/3\)(只考虑选出来的链对度数的影响)的最优答案.特别的一个点的链这个点的度数为\(1\).

定义几个函数:

  1. \(\text{MxSum(S)}\)表示\(S\)集合中最大元素和次大元素的和.
  2. \(\text{MaxF(x,d)}\)表示\(\max_{0 \le k\le 3}(f[x][d][k])\)
  3. \(\text{EMaxF(x,d)}\)表示\(\max_{0 \le k \le 3}(f[x][d][k]-[k>0])\)

转移有点毒瘤, 要分类讨论一下:

  1. \(f[i][1][0] \leftarrow f[v][1][k], v \in son_i, k\in [0,2]\).
  2. \(f[i][1][1] \leftarrow f[v][1][1], v\in son_i.\)
  3. \(f[i][1][2] \leftarrow \text{MxSum}(\{f[v][1][1], v \in son_i\}).\)
  4. \(f[i][2][0] \leftarrow \max(\max_{v\in son_i}(\text{MaxF(v,2)}),\text{MxSum}(\{\text{MaxF(v,1)}, v\in son_i\}))\).

上面这\(4\)种转移比较简单,剩下的四种较为复杂:

一.\(f[i][2][1]\):

  1. 这个点单独成一条链,然后儿子节点的子树当中再选一条链.\(f[i][2][1]\leftarrow \max(f[v][1][0], f[v][1][1]-1), v\in son_i\).
  2. 从某一个儿子的子树当中延伸出来一条链, 另外的一个儿子的子树中选一条链.\(f[i][2][1]\leftarrow f[u][1][1]+\max_{v\in son_i, v \ne u}(\text{EMaxF(v,1)}), u\in son_i\).

二.\(f[i][2][2]\):

  1. 从某一儿子的子树中延伸出来的一条链(这个子树确定了两条链),另外的一个儿子的子树中再选一条可以延伸的链(这个子树确定了一条链).\(f[i][2][2] \leftarrow \max(f[u][2][3], f[u][2][1])+\max_{u \in son_i, u \ne v}(f[u][1][1]), v \in son_i\).
  2. 从某一个儿子的子树中选择一条链, 另外两个儿子的子树中都有一条可以延伸出来的链(这两个子树都只确定了一条链).\(f[i][2][2]\leftarrow \text{EMaxF(u,1)}+\text{MxSum}(\{f[u][1][1], u \in son_i, u \ne v\}),v \in son_i\).

三.\(f[i][2][3]\)\(f[i][2][4]\):

都是直接选择儿子节点中\(f[v][1][1]\)中前\(3/4\)大的进行转移即可.因为这两种情况都是有点交的,所以答案减一.

PS:\(f[i][2][4]\)这个状态不用记下来,只用更新一下答案就好了.并且处理完每一个节点后将所有度数大于零的状态加上\(deg[i]-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
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
/*
* 4871_new.cpp
* This file is part of 4871
*
* Copyright (C) 2019 - ViXbob
*
* 4871 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 4871 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 4871. If not, see <http://www.gnu.org/licenses/>.
*/
/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;
typedef unsigned long long ull;

template <typename T> bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T &a, T b) { return a > b ? a = b, 1 : 0; }

using namespace std;

const int maxn = 1e5 + 15;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

int f[maxn][3][4], T, x;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int max(int a, int b, int c) { return max(a, max(b, c)); }
inline int max(int a, int b, int c, int d) { return max(a, max(b, c, d)); }

namespace ViXbob {
int n, fa[maxn], z, deg[maxn], ans;
vector<int> G[maxn];

inline void init() {
n = read(); ans = 0; z = x;
rep(i, 1, n) G[i].clear();
rep(i, 1, n) rep(j, 0, 2) rep(k, 0, 3) f[i][j][k] = -inf;
memset(fa, 0, sizeof(int) * (n + 5));
memset(deg, 0, sizeof(int) * (n + 5));
}

inline int calcout(int x) { return max(f[x][2][3], f[x][2][1], f[x][1][1]); }
inline int calcall(int x, int d) { return max(f[x][d][0], f[x][d][1], f[x][d][2], f[x][d][3]); }
inline int calcall0(int x) { return max(f[x][1][0], max(f[x][1][1], f[x][1][2], f[x][1][3]) - 1); }

struct Node {
int g0, g1;
Node(int a = -inf, int b = -inf) { g1 = a; g0 = b; }
Node operator & (const Node &t) const {
Node rnt = *this;
if(t.g0 >= g1) return t;
else {
if(t.g1 >= rnt.g1) rnt.g0 = rnt.g1, rnt.g1 = t.g1;
else rnt.g0 = max(rnt.g0, t.g1);
} return rnt;
}
int sum() { return g0 + g1; }
} ;

inline void dfs(int x) {
vector<int> Ans;
f[x][1][1] = 0;
for(auto v : G[x]) if(v != fa[x]) {
fa[v] = x; dfs(v);
Ans.pb(f[v][1][1]);
chkmax(f[x][1][1], f[v][1][1]);
chkmax(f[x][1][0], calcall(v, 1));
chkmax(f[x][2][0], calcall(v, 2));
chkmax(f[x][2][1], max(f[v][2][3], f[v][2][1], f[v][1][0], f[v][1][1] - 1));
}
if(Ans.size() >= 2) {
vector<Node> pre, preout;
pre.resize(G[x].size() + 1);
preout.resize(G[x].size() + 1);
Node suc, sucout, mx0;
rep(i, 0, SIZE(G[x]) - 1) {
int v = G[x][i];
pre[i + 1] = pre[i]; preout[i + 1] = preout[i];
if(v == fa[x]) continue;
pre[i + 1] = pre[i + 1] & Node(calcall0(v));
preout[i + 1] = preout[i + 1] & Node(f[v][1][1], -inf);
mx0 = mx0 & Node(calcall(v, 1));
}
chkmax(f[x][2][0], mx0.sum());
chkmax(f[x][1][2], preout.rbegin() -> sum());
dep(i, SIZE(G[x]) - 1, 0) if(G[x][i] != fa[x]) {
int v = G[x][i];
chkmax(f[x][2][1], f[v][1][1] + (pre[i] & suc).g1);
chkmax(f[x][2][2], max(f[v][2][3], f[v][2][1]) + (preout[i] & sucout).g1);
if(SIZE(Ans) >= 3) chkmax(f[x][2][2], (preout[i] & sucout).sum() + calcall0(v));
suc = suc & Node(calcall0(v), -inf);
sucout = sucout & Node(f[v][1][1], -inf);
}
}
if(Ans.size() >= 3) {
sort(Ans.begin(), Ans.end(), greater<int>());
int rnt = 0;
rep(i, 0, 2) rnt += Ans[i];
chkmax(f[x][2][3], rnt - 1);
if(Ans.size() >= 4) chkmax(ans, rnt + Ans[3] + deg[x]);
}
rep(i, 1, 2) rep(j, 1, 3) f[x][i][j] += deg[x] - 2;
}

int main() {
while(T--) {
init();
while(z--) read(), read();
rep(i, 1, n - 1) {
int x = read(), y = read();
G[x].pb(y); G[y].pb(x);
deg[x]++; deg[y]++;
}
if(n <= 2) { putchar(n - 1 + '0'); putchar('\n'); continue; }
dfs(1);
rep(i, 1, 2) rep(j, 0, 3) chkmax(ans, f[1][i][j] + i + 1);
printf("%d\n", ans);
} return 0;
}
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
T = read(); x = read();
ViXbob :: main();
return 0;
}
/*
*/

分手是祝愿

显然最小次数就是直接贪心的由编号从大到小的关所需的次数.可以获得80pts.并且这个最优策略是唯一的并且和按灯的顺序无关.

我们先贪心的求出初始状态最小所需要的按灯次数\(x\), 设\(f[i]\)为现在还需要按\(i\)下才能熄灭所有的灯,变到\(i-1\)次的期望按灯次数.

首先所有\(i \le k\)的状态\(f[i] = 1\).(最优策略)

否则分两种情况:

  1. 直接按到我们需要的灯, 概率为\(\frac{i}{n}\).

  2. 按到一个不需要的灯, 概率为\(\frac{n - i}{n}\)并且我们需要从\(i+1\)这个状态转移回来.

则有: \[ \begin{aligned}f[i] =& \frac{i}{n}+\frac{n - i}{n}\left(f[i]+f[i+1]+1\right)\\=&\frac{n+(n-i)f[i+1]}{i}\end{aligned} \]

\[ ans = n!\left(\sum_{i = 1} ^ xf[i]\right) \]

求解\(x\)的复杂度为\(O(n\log n)\), 线性处理逆元后\(\text{dp}\)复杂度为\(O(n)\).

总复杂度\(O(n\log n)\).

代码:

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
/*
* 4872.cpp
* This file is part of BZOJ_4872
*
* Copyright (C) 2019 - ViXbob
*
* BZOJ_4872 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* BZOJ_4872 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with BZOJ_4872. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 1e5 + 3;

int n, k, ans, fac[maxn], f[maxn], inv[maxn], mn;
bool a[maxn];
vector<int> Fac[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int main() {
n = read(); k = read(); fac[0] = 1; inv[1] = 1;
rep(i, 1, n) a[i] = read(), fac[i] = 1ll * fac[i - 1] * i % P;
rep(i, 1, n) for(int j = i; j <= n; j += i) Fac[j].pb(i);
dep(i, n, 1) if(a[i]) { for(auto v : Fac[i]) a[v] ^= 1; mn++; }
rep(i, 2, n) inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
f[n] = 1; f[0] = 0;
dep(i, n - 1, k + 1) f[i] = 1ll * (n + 1ll * (n - i) * f[i + 1]) * inv[i] % P;
rep(i, 1, k) f[i] = 1;
rep(i, 1, mn) ans = (ans + f[i]) % P;
cout << 1ll * ans * fac[n] % P;
return 0;
}
/*
*/

寿司餐厅

裸地最大权闭合子图模型?

必选子区间直接\([l, r] \to [l + 1, r], [l, r] \to [l, r - 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
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
117
118
119
120
121
122
123
124
125
/*
* 4873.cpp
* This file is part of BZOJ_4873
*
* Copyright (C) 2019 - ViXbob
*
* BZOJ_4873 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* BZOJ_4873 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with BZOJ_4873. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define id(x, y) (1000 + (x - 1) * n + y)

typedef unsigned long long ull;
typedef long long ll;

using namespace std;

const int maxn = 2e4 + 5;
const int maxm = 2e4 + 5;
const int inf = 0x3f3f3f3f;

int n, m, a[maxn], ans, vis[1005];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

namespace NetFlow {
int cnt = 1, head[maxn], dep[maxn], S, T, cur[maxn];
ll MaxFlow;

struct Graph {
int to, nt, f;
Graph(int a = 0, int b = 0, int c = 0) { to = a; nt = b; f = c; }
} e[maxm << 2];

inline void add(int x, int y, int f) {
e[++cnt] = Graph(y, head[x], f); head[x] = cnt;
e[++cnt] = Graph(x, head[y], 0); head[y] = cnt;
}

inline bool BFS() {
queue<int> q;
memset(dep, -1, sizeof(dep));
memcpy(cur, head, sizeof(cur));
dep[S] = 1; q.push(S);
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = head[u]; i; i = e[i].nt) {
int v = e[i].to;
if(!~dep[v] && e[i].f > 0) {
dep[v] = dep[u] + 1;
if(v == T) return true;
q.push(v);
}
}
} return false;
}

inline int dfs(int x, int flow) {
if(x == T || flow <= 0) return flow;
int used = 0;
for(int &i = cur[x]; i; i = e[i].nt) {
int v = e[i].to, f = 0;
if((dep[v] == dep[x] + 1) && (f = dfs(v, min(flow, e[i].f)))) {
used += f; flow -= f;
e[i ^ 1].f += f; e[i].f -= f;
if(flow <= 0) break;
}
} return used;
}

inline void Dinic() { while(BFS()) MaxFlow += dfs(S, inf); }
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); m = read();
NetFlow :: S = n * n + 1000 + 1; NetFlow :: T = NetFlow :: S + 1;
rep(i, 1, n) {
a[i] = read();
if(!vis[a[i]]) NetFlow :: add(a[i], NetFlow :: T, m * a[i] * a[i]); vis[a[i]] = 1;
NetFlow :: add(id(i, i), a[i], inf); NetFlow :: add(id(i, i), NetFlow :: T, a[i]);
}
rep(i, 1, n) rep(j, i, n) {
int w = read(); if(w > 0) ans += w;
if(w > 0) NetFlow :: add(NetFlow :: S, id(i, j), w); else NetFlow :: add(id(i, j), NetFlow :: T, -w);
if(j > i) NetFlow :: add(id(i, j), id(i + 1, j), inf), NetFlow :: add(id(i, j), id(i, j - 1), inf);
}
NetFlow :: Dinic();
cout << ans - NetFlow :: MaxFlow << endl;
return 0;
}
/*
*/