SNOI2019

SNOI2019

字符串

首先我们知道如果一个串中间有连续的相同字符我们可以直接把这一段缩成一个字符的,然后问题就变成了求解\(a_i\ne a_{i+1}\)的这种情况.

记删掉第\(i\)个字符剩下的串为\(s_i\).

因为比较两个字符串\(s_1,s_2\)的大小是比较\(s_1[\text{lcp}(s_1,s_2)+1]\)\(s_2[\text{lcp}(s_1,s_2)+1]\),并且\(\text{lcp}(s_i,s_j),j>i\)都是相同的,所以我们只用考虑\(s_i\)\(s_{i+1}\)的大小关系就好了,这个只用比较原串的第\(i+1\)\(i\)个字符就好了.然后我们按照这种字典序大小关系建出一颗二叉树(字典序小的丢左儿子),中序遍历输出就是答案.感觉说不清啊,结合代码食用吧!

复杂度\(O(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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/*
* 3095.cpp
* This file is part of 3095
*
* Copyright (C) 2019 - ViXbob
*
* 3095 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.
*
* 3095 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 3095. 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;

using namespace std;

const int maxn = 1e6 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

int n, cnt, root, Lim;
char s[maxn], t[maxn];
vector<int> a[maxn], G[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;
}

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 void solve(int l, int r, int x) {
if(l == r) { G[x].pb(r); return; }
if(t[l] > t[l + 1]) {
G[x].pb(l);
G[x].pb(++cnt);
} else {
G[x].pb(++cnt);
G[x].pb(l);
}
solve(l + 1, r, cnt);
}

inline void dfs(int x) {
if(x <= Lim) {
for(auto v : a[x]) printf("%d ", v);
return;
}
for(auto v : G[x]) dfs(v);
}

int main() {
// freopen("s3.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read();
scanf("%s", s + 1);
for(int l = 1, r; l <= n; l = r + 1) {
r = l; t[++cnt] = s[l]; a[cnt].pb(l);
while(s[r + 1] == s[l]) a[cnt].pb(r + 1), r++;
}
Lim = cnt; root = ++cnt;
// cerr << Lim << endl;
solve(1, Lim, root);
dfs(root);
return 0;
}
/*
baaab
aaaab
abaab
abaaa
2 4 3 1

bab
aab
abb
aba
2 4 3 1

转化为求解subtask2
*/

数论

一个膜\(P\)意义下的余数\(i\),一个膜\(Q\)意义下的余数\(j\),如果存在一个数\(x\)满足: \[ \begin{aligned}\begin{cases}x \equiv i \pmod{P}\\x\equiv j\pmod{Q}\end{cases}\end{aligned} \] 那么也就是说\(i \equiv j \pmod{\gcd(P,Q)}\).

因为如果一个\(i\)合法,那么\(i + k\times lcm(P,Q)\)也一定合法.所以如果\(T = k\times lcm(P,Q)\)的话是可以直接算的, 因为必定会遍历到所有的情况.所以我们只需要分别记录\(A\)集合和\(B\)集合中在膜\(\gcd(P,Q)\)等于\(i\)的个数, 对应相乘然后加起来就是一个\(lcm(P,Q)\)中的答案.所以下文考虑的均是求解\(T \bmod lcm(P,Q)\)的情况.

我们考虑枚举一个\(d, d < \gcd(P,Q)\):

然后枚举一个\(k\)\(x = k \times P + d\).且\(x \bmod Q\)是成环的.然后就可以直接做了, 具体的:

我们把所有\(B\)集合内可以被表示为\((k \times P + d) \bmod Q\)的数丢到值域数轴上去,然后维护一个值域的前缀和后,再枚举一个\(A\)集合中在膜\(\gcd(P,Q)\)意义下等于\(d\)的数直接算就好了.

复杂度\(O(P+Q)\).

PS:建议配合代码食用.

代码:

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
/*
* 3096.cpp
* This file is part of 3096
*
* Copyright (C) 2019 - ViXbob
*
* 3096 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.
*
* 3096 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 3096. 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;

using namespace std;

const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const int maxm = maxn << 1;

int bacP[maxn], bacQ[maxn], a[maxn], b[maxn], sum[maxn];
bool visP[maxn], visQ[maxn];
ll P, Q, n, m, T, d, lcm, ans;
unordered_map<int, int> mp;

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 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; }

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
P = read(); Q = read(); n = read(); m = read(); T = read();
d = __gcd(P, Q); lcm = P * Q / d;
rep(i, 1, n) a[i] = read(), bacP[a[i] % d]++, visP[a[i]] = 1;
rep(i, 1, m) b[i] = read(), bacQ[b[i] % d]++, visQ[b[i]] = 1;
//
// if(P < Q) swap(P, Q), swap(a, b), swap(n, m), swap(bacP, bacQ), swap(visP, visQ);
// 我TM为什么要交换P, Q????????? 我TM是不是有病啊
rep(i, 0, d - 1) ans += 1ll * bacP[i] * bacQ[i];
ans *= T / lcm; T %= lcm;
int Len = T / P, Lim = T % P, Z = Q / d;
rep(i, 0, d - 1) {
mp.clear(); sum[0] = 0;
rep(j, 1, Z) {
int val = ((j - 1) * P + i) % Q;
sum[j] = visQ[val]; mp[val] = j;
sum[j] += sum[j - 1];
}
rep(j, 0, P / d - 1) {
if(visP[j * d + i]) {
int R = mp[(j * d + i) % Q];
// assert(R > 0);
if(R + Len - 1 <= Z) ans += sum[R + Len - 1] - sum[R - 1];
else ans += sum[Z] - sum[R - 1] + sum[R + Len - 1 - Z];
ans += (j * d + i < Lim && visQ[(j * d + i + Len * P) % Q]);
}
}
}
cout << ans << endl;
return 0;
}
/*
*/

通信

按照题意建图边数是\(n^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
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
/*
* 3097.cpp
* This file is part of 3097
*
* Copyright (C) 2019 - ViXbob
*
* 3097 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.
*
* 3097 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 3097. 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;

using namespace std;

const int maxn = 5e4 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

int n, W, a[maxn], tot, pos[maxn], coc;

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; }

namespace NetFlow {
int S, T, head[maxn], cnt = 1;
struct Graph {
int to, fr, nt, f, w;
Graph(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0) {
to = a; fr = b; nt = c; f = d; w = e;
}
} e[maxn << 3];

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

bool vis[maxn];
ll delta, dis[maxn], MaxFlow, MinCost;

inline void Reduce() {
rep(i, 2, cnt) e[i].w += dis[e[i].to] - dis[e[i].fr];
delta += dis[S];
}

inline bool SPFA() {
queue<int> q;
static bool inq[maxn];
memset(inq, 0, sizeof(inq));
memset(dis, 0x3f, sizeof(dis));
q.push(T); dis[T] = 0;
while(q.size()) {
int u = q.front(); q.pop(); inq[u] = 0;
for(int i = head[u]; i; i = e[i].nt) {
int v = e[i].to;
if(dis[v] > dis[u] + e[i ^ 1].w && e[i ^ 1].f > 0) {
dis[v] = dis[u] + e[i ^ 1].w;
if(!inq[v]) inq[v] = 1, q.push(v);
}
}
} return dis[S] != dis[0];
}

inline bool Dijkstra() {
priority_queue<pair<ll, int> > q;
memset(dis, 0x3f, sizeof(dis));
q.push(mp(dis[T] = 0, T));
while(q.size()) {
int u = q.top().second, now = -q.top().first; q.pop();
if(now != dis[u]) continue;
for(int i = head[u]; i; i = e[i].nt) {
int v = e[i].to;
if(dis[v] > dis[u] + e[i ^ 1].w && e[i ^ 1].f > 0) {
dis[v] = dis[u] + e[i ^ 1].w;
q.push(mp(-dis[v], v));
}
}
} return dis[S] != dis[0];
}

inline int dfs(int x, int flow) {
if(x == T || flow <= 0) return flow;
int res = flow; vis[x] = 1;
for(int i = head[x]; i; i = e[i].nt) {
int v = e[i].to;
if(e[i].w == 0 && e[i].f > 0 && !vis[v]) {
int tmp = dfs(v, min(e[i].f, res));
e[i].f -= tmp; e[i ^ 1].f += tmp;
res -= tmp;
}
} return flow - res;
}

inline void Augment() {
int CurFlow = 0;
memset(vis, 0, sizeof(bool) * (tot + 5));
while(CurFlow = dfs(S, inf)) {
MaxFlow += CurFlow;
MinCost += CurFlow * delta;
memset(vis, 0, sizeof(bool) * (tot + 5));
}
}

inline void PrimalDual() {
if(!SPFA()) return;
Reduce(); Augment();
while(Dijkstra()) Reduce(), Augment();
}
}

struct FSEG {
#define mid (l + r >> 1)
int root[maxn];
struct Node {
int ls, rs;
} t[maxn];

inline void insert(int l, int r, int pos, int u, int &p, int type, int x) {
p = ++tot; t[p] = t[u];
if(l == r) return NetFlow :: add(p, x + 2 * n, inf, a[x] * type);
if(pos <= mid) insert(l, mid, pos, t[u].ls, t[p].ls, type, x);
else insert(mid + 1, r, pos, t[u].rs, t[p].rs, type, x);
if(t[p].ls) NetFlow :: add(p, t[p].ls, inf, 0);
if(t[p].rs) NetFlow :: add(p, t[p].rs, inf, 0);
}

inline void Link(int l, int r, int ql, int qr, int p, int type, int x) {
if(!p || ql > qr) return;
if(l == ql && r == qr) return NetFlow :: add(x + n, p, inf, a[x] * type);
if(qr <= mid) Link(l, mid, ql, qr, t[p].ls, type, x);
else if(ql > mid) Link(mid + 1, r, ql, qr, t[p].rs, type, x);
else Link(l, mid, ql, mid, t[p].ls, type, x), Link(mid + 1, r, mid + 1, qr, t[p].rs, type, x);
}
#undef mid
} posi, nega;

using NetFlow :: S;
using NetFlow :: T;

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); W = read();
rep(i, 1, n) pos[++coc] = a[i] = read();
sort(pos + 1, pos + 1 + coc);
coc = unique(pos + 1, pos + 1 + coc) - pos - 1;
tot = 3 * n;
NetFlow :: S = ++tot; NetFlow :: T = ++tot;
rep(i, 1, n) {
NetFlow :: add(S, i, 1, 0);
NetFlow :: add(i, i + n, 1, 0);
NetFlow :: add(i + n, T, 1, W);
NetFlow :: add(i + 2 * n, T, 1, 0);
}
rep(i, 1, n) {
int p = lower_bound(pos + 1, pos + 1 + coc, a[i]) - pos;
if(i > 1) {
nega.Link(1, coc, 1, p, nega.root[i - 1], 1, i);
posi.Link(1, coc, p + 1, coc, posi.root[i - 1], -1, i);
}
posi.insert(1, coc, p, posi.root[i - 1], posi.root[i], 1, i);
nega.insert(1, coc, p, nega.root[i - 1], nega.root[i], -1, i);
}
NetFlow :: PrimalDual();
cout << NetFlow :: MinCost << endl;
return 0;
}