挑了一些简单点的题乱做。。。

题目链接:传送门

HNOI2019

「HNOI2019」多边形

这里

「HNOI2019」校园旅行

myy的题解

更详细的题解

稍微提一下,考虑优化暴力。暴力每次是往两边扩展一个点,那么我们就每次扩展一堆点。事实上,我们也并不需要知道每次往两边加多少个,只需要考虑奇偶性即可,于是就有了这个做法。

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

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 5e3 + 100, Maxm = 5e5 + 100;

int N, M, Q, Ans[Maxn][Maxn];
char S[Maxn];

struct graph
{
int e, Begin[Maxn], To[Maxm << 1], Next[Maxm << 1];
inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }
} G[2];

struct info
{
int x, y, op;
} E[Maxm];


inline void Bfs ()
{
static queue <pii> Que;
for (int i = 1; i <= N; ++i) Que.push (mp (i, i)), Ans[i][i] = 1;
for (int x = 1; x <= N; ++x)
for (int i = G[1].Begin[x]; i; i = G[1].Next[i])
{
int y = G[1].To[i];
if (S[x] == S[y]) Que.push (mp (x, y)), Ans[x][y] = Ans[y][x] = 1;
}

while (!Que.empty ())
{
int x = Que.front ().x, y = Que.front ().y; Que.pop ();

for (int i = G[1].Begin[x]; i; i = G[1].Next[i])
for (int j = G[1].Begin[y]; j; j = G[1].Next[j])
{
int u = G[1].To[i], v = G[1].To[j];
if (S[u] == S[v] && !Ans[u][v]) Ans[u][v] = Ans[v][u] = 1, Que.push (mp (u, v));
}
}
}

int Col[Maxn];

inline int dfs (int x, int k)
{
int fl = 0;
for (int i = G[0].Begin[x]; i; i = G[0].Next[i])
{
int y = G[0].To[i];
if ((S[x] == S[y]) != k) continue ;
if (Col[y] == -1)
{
Col[y] = Col[x] ^ 1;
G[1].add_edge (x, y), G[1].add_edge (y, x);
fl |= dfs (y, k);
}
else if (Col[y] == Col[x]) fl = 1;
}
return fl;
}

inline void Rebuild ()
{
for (int k = 0; k < 2; ++k)
{
memset (Col, -1, sizeof Col);
for (int i = 1; i <= N; ++i)
{
if (Col[i] == -1)
{
Col[i] = 0;
if (dfs (i, k)) G[1].add_edge (i, i);
}
}
}
}

inline void Solve ()
{
Rebuild ();
Bfs ();

while (Q--)
{
int x = read<int>(), y = read<int>();
printf("%s\n", Ans[x][y] ? "YES" : "NO");
}
}

inline void Input ()
{
N = read<int>(), M = read<int>(), Q = read<int>();
scanf("%s", S + 1);
for (int i = 1; i <= M; ++i)
{
int x = read<int>(), y = read<int>();
G[0].add_edge (x, y), G[0].add_edge (y, x);
}
}

int main()
{

#ifdef hk_cnyali
freopen("tour.in", "r", stdin);
freopen("tour.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}

GXOI/GZOI2019

「GXOI / GZOI2019」与或和

按位拆分,转化为求有多少个子矩阵全为11,以及总方案数减去有多少个子矩阵全为00

以全为11为例,预处理出len[i][j]len[i][j]表示从(i,j)(i, j)这个位置往右最长连续为11的长度。考虑每一列,我们即要求出这一列上所有区间 的最小值之和

问题转化为,有一个数列,你需要求其中每个区间的最小值之和

显然考虑贡献,用单调栈维护左边第一个小于等于它的位置,右边第一个小于它的位置即可

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

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1000 + 100;
const int Mod = 1e9 + 7;

int N, A[31][Maxn][Maxn];
int Len[Maxn][Maxn];
int Left[Maxn], Right[Maxn];

inline void Add (int &a, int b) { if ((a += b) >= Mod) a -= Mod; }

inline int solve (int k, int op)
{
for (int i = N; i >= 1; --i)
for (int j = N; j >= 1; --j)
{
if (A[k][i][j] == op) Len[i][j] = Len[i][j + 1] + 1;
else Len[i][j] = 0;
}

int Stack[Maxn], top;
LL ans = 0;

for (int j = 1; j <= N; ++j)
{
Stack[top = 1] = 0;
for (int i = 1; i <= N; ++i)
{
while (top > 1 && Len[Stack[top]][j] > Len[i][j]) --top;
Left[i] = Stack[top];
Stack[++top] = i;
}

Stack[top = 1] = N + 1;
for (int i = N; i >= 1; --i)
{
while (top > 1 && Len[Stack[top]][j] >= Len[i][j]) --top;
Right[i] = Stack[top];
ans += (LL) (i - Left[i]) * (Right[i] - i) * Len[i][j];
Stack[++top] = i;
}
}
return ans % Mod;
}

inline void Solve ()
{
int ans1 = 0, ans2 = 0, all = (LL) (1 + N) * N / 2 % Mod; all = (LL) all * all % Mod;
int sum = 1;
for (int k = 0; k <= 30; ++k)
{
Add (ans1, (LL) solve (k, 1) * sum % Mod);
Add (ans2, (LL) (all - solve (k, 0) + Mod) * sum % Mod);
sum = 2ll * sum % Mod;
}
cout << ans1 << ' ' << ans2 << endl;
}

inline void Input ()
{
N = read<int>();
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
{
int x = read<int>();
for (int k = 0; k <= 30; ++k)
if (x & (1 << k)) A[k][i][j] = 1;
}
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}

「GXOI / GZOI2019」逼死强迫症

nn列的答案为fnf_n,斐波那契数列为gng_n,其前缀和为hnh_n,那么

fn=fn1+fn2+2i=1n3gi=fn1+fn2+2hn3=fn1+fn2+2(gn11) \begin{aligned} \displaystyle f_n &= f_{n - 1} + f_{n - 2} + 2\sum_{i=1}^{n-3}g_i\\ &= f_{n - 1} + f_{n-2} + 2*h_{n - 3}\\ &= f_{n-1} + f_{n-2} + 2*(g_{n-1} - 1) \end{aligned}

考虑枚举1×11\times 1的砖块放在哪里,如果两个1×11\times1的都放在前n1n-1n2n-2个位置,答案就是

如果右边那个砖块放在第nn列,左边那个砖块放在第ii列,那么从第ii列到第nn列的方案其实是固定的

关于hn=gn+21h_{n} = g_{n + 2} - 1那里的证明:

hn=i=1ngi=i=1ngi+1gi1=(i=2n+1gi)(i=0n1gi)=gn+1+gn1=gn+21 \begin{aligned} h_n &= \sum_{i=1}^{n}g_i\\ &= \sum_{i=1}^{n}g_{i + 1} - g_{i - 1}\\ &= \Big(\sum_{i=2}^{n + 1}g_{i}\Big) - \Big(\sum_{i=0}^{n - 1}g_{i}\Big)\\ &= g_{n + 1} + g_{n} - 1\\ &= g_{n + 2} - 1 \end{aligned}

然后矩阵快速幂优化即可


这里顺便记录一下矩阵快速幂优化线性齐次常系数递推的套路

假设dp转移方程是从f1,f2...fnf_{1}, f_{2} ... f_{n}转移成(a1,1f1+a2,1f2+...+an,1fn),...,(a1,nf1+a2,nf2+...+an,nfn)(a_{1, 1}f_1 + a_{2, 1}f_2 + ...+a_{n, 1}f_n), ... ,(a_{1, n}f_{1} + a_{2, n}f_2 + ... + a_{n, n}f_n)

那么矩阵就是

简单来说,ai,ja_{i, j}表示从fif_i转移到fjf'_{j}需要乘的系数

这个东西我现在才会。。。


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

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Mod = 1e9 + 7;
const int Maxn = 5;

int N;

inline void Add (int &a, int b) { if ((a += b) >= Mod) a -= Mod; }

struct Matrix
{
int A[Maxn][Maxn];

Matrix () { memset (A, 0, sizeof A); }

inline Matrix operator * (const Matrix &rhs) const &
{
Matrix ans;
for (int i = 0; i < Maxn; ++i)
for (int k = 0; k < Maxn; ++k)
{
if (!A[i][k]) continue;
for (int j = 0; j < Maxn; ++j)
Add (ans.A[i][j], (LL) A[i][k] * rhs.A[k][j] % Mod);
}
return ans;
}

inline Matrix operator ^ (const int b) const &
{
Matrix a = *this, ans;
for (int i = 0; i < Maxn; ++i) for (int j = 0; j < Maxn; ++j) ans.A[i][j] = (i == j);
for (int i = b; i; i >>= 1, a = a * a) if (i & 1) ans = ans * a;
return ans;
}
};

inline void Solve ()
{
if (N == 1 || N == 2) { puts("0"); return ; }
Matrix sum;
sum.A[0][0] = sum.A[0][1] = 1;
sum.A[1][0] = 1;
sum.A[2][2] = sum.A[2][3] = 1, sum.A[2][0] = 2;
sum.A[3][2] = 1;
sum.A[4][0] = sum.A[4][4] = 1;

Matrix ans;
ans.A[0][2] = 2, ans.A[0][3] = 1, ans.A[0][4] = Mod - 2;

ans = ans * (sum ^ (N - 2));

printf("%d\n", ans.A[0][0]);
}

inline void Input ()
{
N = read<int>();
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

int T = read<int>();
while (T--)
{
Input ();
Solve ();
}

return 0;
}

「GXOI / GZOI2019」旅行者

考虑每条边的贡献。处理出fif_i表示到ii点最近的关键点,gig_i表示从ii出发能到达的最近的关键点。如果 就能用这条边贡献答案

此外,还能直接二进制分组做。即枚举二进制下每一位,把关键点按这一位为0/10/1划分成两个集合,跑两个集合之间的最短路即可。因为原问题起点终点集合有交,于是不能直接跑最短路。而通过二进制分组分成两个不交的集合后就能直接跑了

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

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/sefl/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100;
const int Maxm = 5e5 + 100;

int N, M, K;
int A[Maxn];

struct edge
{
int x, y, z;
} E[Maxm];

struct Graph
{
const LL inf = 1e18;
int e, Begin[Maxn], To[Maxm << 1], Next[Maxm << 1], W[Maxm << 1];
inline void init ()
{
e = 0;
memset (Begin, 0, sizeof Begin);
}

inline void add_edge (int x, int y, int z) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; W[e] = z; }

LL Dis[Maxn];
int from[Maxn];

inline void dijkstra ()
{
static priority_queue <pii, vector <pii>, greater <pii> > Q;
for (int i = 1; i <= N; ++i) Dis[i] = inf, from[i] = 0;
for (int i = 1; i <= K; ++i) Dis[A[i]] = 0, from[A[i]] = A[i], Q.push (mp (0, A[i]));

while (!Q.empty())
{
int x = Q.top ().y; Q.pop ();
for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i];
if (Chkmin (Dis[y], Dis[x] + W[i]))
{
from[y] = from[x];
Q.push (mp (Dis[y], y));
}
}
}
}

} G[2];

inline void Solve ()
{
G[0].dijkstra ();
G[1].dijkstra ();

LL ans = 1e18;

for (int i = 1; i <= M; ++i)
{
int x = E[i].x, y = E[i].y, z = E[i].z;
if (G[0].from[x] != G[1].from[y])
Chkmin (ans, G[0].Dis[x] + G[1].Dis[y] + z);
}

cout << ans << endl;
}

inline void Input ()
{
N = read<int>(), M = read<int>(), K = read<int>();
for (int i = 1; i <= M; ++i)
{
E[i].x = read<int>(), E[i].y = read<int>(), E[i].z = read<int>();
G[0].add_edge (E[i].x, E[i].y, E[i].z);
G[1].add_edge (E[i].y, E[i].x, E[i].z);
}
for (int i = 1; i <= K; ++i) A[i] = read<int>();
}

inline void Init ()
{
G[0].init ();
G[1].init ();
}

int main ()
{

#ifndef ONLINE_JUDGE
freopen ("A.in", "r", stdin);
freopen ("A.out", "w", stdout);
#endif

int Testcase = read<int>();

while (Testcase--)
{
Init ();
Input ();
Solve ();
}

return 0;
}

「GXOI / GZOI2019」旧词

一个很简单的套路。没有kk次方的话就是把可选点到根的路径全部+1+1,然后求所求点到根路径上的权值和

的本质其实是 ,那么这道题变成 即可

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
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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 5e4 + 100;
const int Mod = 998244353;

inline void Add (int &a, int b) { if ((a += b) >= Mod) a -= Mod; }

inline int Pow (int a, int b)
{
int ans = 1;
for (int i = b; i; i >>= 1, a = (LL) a * a % Mod) if (i & 1) ans = (LL) ans * a % Mod;
return ans;
}

int N, M, K;
int e, Begin[Maxn], To[Maxn << 1], Next[Maxn << 1];
int fa[Maxn], dep[Maxn], dfn[Maxn], idfn[Maxn], son[Maxn], size[Maxn], top[Maxn], dfs_clock;
int Sum[Maxn];

struct info
{
int x, y, id;
} Q[Maxn];

inline int cmp (info a, info b) { return a.x < b.x; }

inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }

inline void dfs (int x)
{
dep[x] = dep[fa[x]] + 1, size[x] = 1;
for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i];
dfs (y);
size[x] += size[y];
if (size[y] > size[son[x]]) son[x] = y;
}
}

inline void dfs (int x, int now)
{
idfn[dfn[x] = ++dfs_clock] = x, top[x] = now;
if (son[x]) dfs (son[x], now);
for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i];
if (y == son[x]) continue;
dfs (y, y);
}
}

namespace SEG
{
#define mid ((l + r) >> 1)
#define ls root << 1
#define rs root << 1 | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r
struct info
{
int sum, tag;
} node[Maxn << 2];

inline int get_val (int l, int r) { return (Sum[r] - Sum[l - 1] + Mod) % Mod; }

inline void push_up (int root) { node[root].sum = (node[ls].sum + node[rs].sum) % Mod; }

inline void push_down (int root, int l, int r)
{
if (!node[root].tag) return ;
Add (node[ls].sum, (LL) node[root].tag * get_val (l, mid) % Mod);
Add (node[ls].tag, node[root].tag);
Add (node[rs].sum, (LL) node[root].tag * get_val (mid + 1, r) % Mod);
Add (node[rs].tag, node[root].tag);
node[root].tag = 0;
}

inline void update (int root, int l, int r, int x, int y)
{
if (x <= l && r <= y)
{
Add (node[root].sum, get_val (l, r));
Add (node[root].tag, 1);
return ;
}
push_down (root, l, r);
if (x <= mid) update (lson, x, y);
if (y > mid) update (rson, x, y);
push_up (root);
}

inline int query (int root, int l, int r, int x, int y)
{
if (x <= l && r <= y) return node[root].sum;
else
{
push_down (root, l, r);
int ans = 0;
if (x <= mid) Add (ans, query (lson, x, y));
if (y > mid) Add (ans, query (rson, x, y));
return ans;
}
}

#undef mid
#undef ls
#undef rs
#undef lson
#undef rson
}

inline void Update (int x)
{
while (x)
{
SEG :: update (1, 1, N, dfn[top[x]], dfn[x]);
x = fa[top[x]];
}
}

inline int Query (int x)
{
int ans = 0;
while (x)
{
Add (ans, SEG :: query (1, 1, N, dfn[top[x]], dfn[x]));
x = fa[top[x]];
}
return ans;
}

int Ans[Maxn];

inline void Pre ()
{
dfs (1);
dfs (1, 1);
// for (int i = 1; i <= N; ++i) cout << idfn[i] << ' ' << dep[idfn[i]] << endl;
for (int i = 1; i <= N; ++i)
Sum[i] = ((LL) Sum[i - 1] + Pow (dep[idfn[i]], K) - Pow (dep[idfn[i]] - 1, K) + Mod) % Mod;
}

inline void Solve ()
{
Pre ();

for (int i = 1; i <= M; ++i) Q[i].x = read<int>(), Q[i].y = read<int>(), Q[i].id = i;
sort (Q + 1, Q + M + 1, cmp);

int j = 1;
for (int i = 1; i <= M; ++i)
{
while (j <= Q[i].x) Update (j++);
Ans[Q[i].id] = Query (Q[i].y);
}

for (int i = 1; i <= M; ++i) printf("%d\n", Ans[i]);
}

inline void Input ()
{
N = read<int>(), M = read<int>(), K = read<int>();
for (int i = 2; i <= N; ++i) add_edge (fa[i] = read<int>(), i);
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}

TJOI2019

「TJOI2019」甲苯先生的字符串

矩阵快速幂随便搞下

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

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100;
const int Mod = 1e9 + 7;

LL N;
char S[Maxn];

inline void Add (int &a, int b) { if ((a += b) >= Mod) a -= Mod; }

inline int Pow (int a, int b)
{
int ans = 1;
for (int i = b; i; i >>= 1, a = (LL) a * a % Mod) if (i & 1) ans = (LL) ans * a % Mod;
return ans;
}

struct Matrix
{
int A[30][30];
inline Matrix () { memset (A, 0, sizeof A); }
inline Matrix operator * (const Matrix &rhs) const &
{
Matrix ans;
for (int i = 0; i < 26; ++i)
for (int k = 0; k < 26; ++k)
{
if (!A[i][k]) continue;
for (int j = 0; j < 26; ++j)
Add (ans.A[i][j], (LL) A[i][k] * rhs.A[k][j] % Mod);
}
return ans;
}

inline Matrix operator ^ (const LL &n) const &
{
Matrix a = *this, ans;
for (int i = 0; i < 26; ++i) ans.A[i][i] = 1;
for (LL i = n; i; i >>= 1, a = a * a) if (i & 1) ans = ans * a;
return ans;
}
} trans;

inline void Solve ()
{
Matrix Ans;
for (int i = 0; i < 26; ++i) Ans.A[0][i] = 1;
Ans = Ans * (trans ^ (N - 1));

int ans = 0;
for (int i = 0; i < 26; ++i) Add (ans, Ans.A[0][i]);
cout << ans << endl;
}

inline void Input ()
{
N = read<LL>();
scanf("%s", S);
for (int i = 0; i < 26; ++i) for (int j = 0; j < 26; ++j) trans.A[i][j] = 1;
for (int i = 1, len = strlen (S); i < len; ++i)
trans.A[S[i - 1] - 'a'][S[i] - 'a'] = 0;
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}

「TJOI2019」甲苯先生的滚榜

无脑上pb_ds,当然也可以权值线段树维护

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef unsigned int UI;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e6 + 100;

int N, M;
UI seed;
int lastans = 7;

inline UI randNum () { seed = seed * 17 + lastans; return seed % N + 1; }

struct info
{
int num, t, id;
inline bool operator < (const info &rhs) const & { return num == rhs.num ? (t == rhs.t ? id < rhs.id : t < rhs.t) : num > rhs.num; }
};

info A[Maxn];

#include<bits/extc++.h>
using namespace __gnu_pbds;
tree <info, null_type, less <info >, rb_tree_tag, tree_order_statistics_node_update> S;

inline void Solve ()
{
int tot = 0;
for (int i = 1; i <= N; ++i) A[i].num = A[i].t = 0, A[i].id = ++tot, S.insert (A[i]);
while (M--)
{
int x = randNum(), y = randNum();
S.erase (A[x]);
++A[x].num, A[x].t += y;
S.insert (A[x]);
lastans = S.order_of_key ((info){A[x].num, A[x].t, 0});
printf("%d\n", lastans);
}
}

inline void Input ()
{
N = read<int>(), M = read<int>(), seed = read<int>();
S.clear ();
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

int Testcase = read<int>();

while (Testcase--)
{
Input ();
Solve ();
}

return 0;
}

「TJOI2019」唱、跳、rap 和篮球

考虑容斥。设 ,枚举至少有 cxk,则

ans=i=0m(1)i(n3ii)fn4i ans = \sum_{i=0}^{m} (-1)^{i}\binom{n - 3i}{i}f_{n-4i}

其中 表示剩下的 个人的排列方案

前面那个(n3ii)\binom{n-3i}{i}是因为cxk不能拆开,于是把每个cxk看成一个整体,所以总共有n3in-3i个元素,要从中选出ii个元素

后面的部分,设四种同学分别有aja_j个,那么就是(n4i)!j=14aj!\displaystyle \frac{(n-4i)!}{\prod_{j=1}^{4} a_j!}

分母部分就直接把四个指数型生成函数的多项式卷起来即可

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

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1000 + 100;
const int Mod = 998244353;

int N, Num[4], M;

namespace MATH
{
int fac[Maxn], ifac[Maxn];
inline void Add (int &a, int b) { if ((a += b) >= Mod) a -= Mod; }
inline int Pow (int a, int b)
{
int ans = 1;
for (int i = b; i; i >>= 1, a = (LL) a * a % Mod) if (i & 1) ans = (LL) ans * a % Mod;
return ans;
}
inline int C (int n, int m)
{
if (n < m) return 0;
return (LL) fac[n] * ifac[m] % Mod * ifac[n - m] % Mod;
}
}

using namespace MATH;

namespace Poly
{
const int Maxn = 1e4 + 10;
const int g = 3;
int n, rev[Maxn];
int F[4][Maxn];

inline void init (int k)
{
int sum = 0;
for (int i = 0; i < 4; ++i) sum += Num[i] - k;

n = 1; while (n <= sum) n <<= 1;
for (int i = 0; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) + (i & 1 ? (n >> 1) : 0);

for (int i = 0; i < 4; ++i)
for (int j = 0; j < n; ++j)
F[i][j] = (j <= Num[i] - k) ? ifac[j] : 0;
}

inline void dft (int *A, int fl)
{
for (int i = 0; i < n; ++i) if (rev[i] < i) swap (A[rev[i]], A[i]);
for (int mid = 1; mid < n; mid <<= 1)
{
int Wn = Pow (g, (Mod - 1) / mid / 2);
if (fl) Wn = Pow (Wn, Mod - 2);
for (int i = 0; i < n; i += (mid << 1))
{
int W = 1;
for (int j = i; j < i + mid; ++j, W = (LL)W * Wn % Mod)
{
int x = A[j], y = (LL) W * A[j + mid] % Mod;
A[j] = (x + y) % Mod, A[j + mid] = (x - y + Mod) % Mod;
}
}
}

int inv = Pow (n, Mod - 2);
if (fl) for (int i = 0; i < n; ++i) A[i] = (LL) A[i] * inv % Mod;
}

inline int calc (int k)
{
init (k);
for (int i = 0; i < 4; ++i) dft (F[i], 0);
for (int i = 1; i < 4; ++i)
for (int j = 0; j < n; ++j)
F[0][j] = (LL) F[0][j] * F[i][j] % Mod;
dft (F[0], 1);
return F[0][N - 4 * k];
}
}

inline void Solve ()
{
int ans = 0;
for (int i = 0; i <= M; ++i)
{
int now = (LL) C (N - 3 * i, i) * Poly :: calc (i) % Mod * fac[N - 4 * i] % Mod;
if (i & 1) Add (ans, Mod - now);
else Add (ans, now);
}

cout << ans << endl;
}

inline void Input ()
{
N = read<int>(), M = N / 4;
for (int i = 0; i < 4; ++i) Chkmin (M, Num[i] = read<int>());
}

inline void Init (int maxn = 1000)
{
fac[0] = 1;
for (int i = 1; i <= maxn; ++i) fac[i] = (LL) fac[i - 1] * i % Mod;
ifac[maxn] = Pow (fac[maxn], Mod - 2);
for (int i= maxn - 1; i >= 0; --i) ifac[i] = (LL) ifac[i + 1] * (i + 1) % Mod;
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

Init ();
Input ();
Solve ();

return 0;
}

「TJOI2019」大中锋的游乐场

因为kk很小,直接把所有状态拿出来跑最短路

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

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef unsigned int UI;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e4 + 100, Maxm = 1e5 + 100, Maxk = 10 + 5;

int N, M, K, A[Maxn], S, T;
int e, Begin[Maxn], To[Maxm << 1], Next[Maxm << 1], W[Maxm << 1];
int Dis[Maxn][Maxk << 1];

inline void add_edge (int x, int y, int z) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; W[e] = z; }

inline void Dijkstra ()
{
static priority_queue <pair <int, pii>, vector < pair <int, pii> >, greater < pair <int, pii> > > Q;
memset (Dis, 0x3f, sizeof Dis);
Dis[S][K + A[S]] = 0;
Q.push (mp (0, mp (S, K + A[S])));

while (!Q.empty())
{
int x = Q.top().y.x, k = Q.top().y.y; Q.pop();
for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i], tok = k + A[y];
if (0 <= tok && tok <= 2 * K && Dis[y][tok] > Dis[x][k] + W[i])
{
Dis[y][tok] = Dis[x][k] + W[i];
Q.push (mp (Dis[y][tok], mp (y, tok)));
}
}
}
}

inline void Solve ()
{
Dijkstra ();
int ans = 1e9;
for (int i = 0; i <= 2 * K; ++i) Chkmin (ans, Dis[T][i]);
if (ans > 1e8) cout << -1 << endl;
else cout << ans << endl;
}

inline void Input ()
{
N = read<int>(), M = read<int>(), K = read<int>();
for (int i = 1; i <= N; ++i) A[i] = (read<int>() == 1) ? 1 : -1;
for (int i = 1; i <= M; ++i)
{
int x = read<int>(), y = read<int>(), z = read<int>();
add_edge (x, y, z);
add_edge (y, x, z);
}
S = read<int>(), T = read<int>();
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

int Testcase = read<int>();
while (Testcase--)
{
Input ();
Solve ();
}

return 0;
}

「TJOI2019」甲苯先生和大中锋的字符串

SAM随便搞

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

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

const int Maxn = 1e5 + 100;

int N, K;
char S[Maxn];

namespace BIT
{
#define lowbit(x) (x & (-x))
LL sum[Maxn];
inline void init () { memset (sum, 0, sizeof sum); }
inline void add (int x, int val) { for (; x < Maxn - 5; x += lowbit(x)) sum[x] += val; }
inline void add (int x, int y, int val) { add (x, val), add (y + 1,-val); }
inline LL query (int x) { LL ans = 0; for (; x; x -= lowbit(x)) ans += sum[x]; return ans; }
}

namespace SAM
{
int node_cnt = 1, last = 1;
struct info
{
int ch[30], fa, maxlen, cnt;
} node[Maxn << 2];

inline int new_node (int pre)
{
++node_cnt;
node[node_cnt].maxlen = node[pre].maxlen + 1;
node[node_cnt].cnt = 1;
return node_cnt;
}

inline void extend (int c)
{
int now = new_node (last), pre = last; last = now;
for (; pre && !node[pre].ch[c]; pre = node[pre].fa) node[pre].ch[c] = now;
if (!pre) node[now].fa = 1;
else
{
int x = node[pre].ch[c];
if (node[x].maxlen == node[pre].maxlen + 1) node[now].fa = x;
else
{
int y = ++node_cnt; node[y] = node[x];
node[y].cnt = 0, node[y].maxlen = node[pre].maxlen + 1;
node[now].fa = node[x].fa = y;
for (; node[pre].ch[c] == x; pre = node[pre].fa) node[pre].ch[c] = y;
}
}
}

inline void build (char *s, int n)
{
for (int i = 1; i <= n; ++i) extend (s[i] - 'a');
}

vector <int> G[Maxn << 2];

inline void dfs (int x)
{
for (int y : G[x])
{
dfs (y);
node[x].cnt += node[y].cnt;
}
}

inline void solve ()
{
for (int i = 1; i <= node_cnt; ++i) G[node[i].fa].pb (i);
dfs (1);

for (int i = 1; i <= node_cnt; ++i)
{
if (node[i].cnt == K)
BIT :: add (node[node[i].fa].maxlen + 1, node[i].maxlen, 1);
}

int ans = -1;
LL times = 0;
for (int i = N; i >= 1; --i)
{
// cout << i << ' ' << BIT :: query (i) << endl;
if (Chkmax (times, BIT :: query (i))) ans = i;
}

cout << ans << endl;
}

inline void init ()
{
for (int i = 1; i <= node_cnt; ++i) G[i].clear (), memset (node[i].ch, 0, sizeof node[i].ch), node[i].fa = node[i].cnt = node[i].maxlen = 0;
node_cnt = last = 1;
}
}

inline void Solve ()
{
BIT :: init ();
SAM :: init ();
SAM :: build (S, N);
SAM :: solve ();
}

inline void Input ()
{
scanf("%s", S + 1);
N = strlen (S + 1);
K = read<int>();
}

int main ()
{

#ifndef ONLINE_JUDGE
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

int Testcase = read<int>();

while (Testcase--)
{
Input ();
Solve ();
}
return 0;
}