「SNOI 2019」Day1 所有题目【题解】

题目列表

  • T1. 字符串
  • T2. 数论
  • T3. 通信

简要题解

T1. 字符串

题目大意:给定一个长度为 nn 的字符串 SS,设删掉第 ii 个字符后的字符串为 TiT_i。请按照字典序对 T1,T2,,TnT_1, T_2, \cdots, T_n 从小到大排序。保证 n106n \leqslant 10^6

思路分析:求出 LCP(S[i:],S[i+1:])\text{LCP}(S[i:], S[i + 1:]) 就能 O(1)O(1) 比较。时间复杂度为 O(nlogn)O(n \log n)

比较 T(i) 和 T(j) 的示意图

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

const int maxn = 1000010;
int n, ans[maxn], lcp[maxn];
char s[maxn];

bool comp(int i, int j) {
if (i > j) return !comp(j, i);
if (i + lcp[i] >= j) return 1;
return s[i + lcp[i]] > s[i + lcp[i] + 1];
}

int main() {
scanf("%d %s", &n, s + 1);
for (int i = 1; i <= n; i++) {
ans[i] = i;
}
for (int i = n - 1; i; i--) {
if (s[i] ^ s[i + 1]) lcp[i] = 0;
else lcp[i] = lcp[i + 1] + 1;
}
sort(ans + 1, ans + n + 1, comp);
for (int i = 1; i <= n; i++) {
printf("%d ", ans[i]);
}
return 0;
}

T2. 数论

题目大意:给定整数 P,Q,TP, Q, T,以及整数集 AABB。求:

i=0T1[iA (mod P)][iB (mod Q)]\sum_{i = 0}^{T - 1} [i \in A \text{ (mod }P)] \cdot [i \in B \text{ (mod }Q)]

也就是问有多少个小于 TT 的非负整数 xx 满足,xxPP 的余数属于 AAxxQQ 的余数属于 BB。保证 A,B,P,Q106,\lvert A \rvert, \lvert B \rvert, P, Q \leqslant 10^6, T1018T \leqslant 10^{18}

思路分析:显然循环节为 lcm(P,Q)\text{lcm}(P, Q)。考虑对每个 aiAa_i \in A 求出 xx 的个数,即:

i=0(T1ai)/P[(ai+iP)B (mod Q)]\sum_{i = 0}^{\lfloor (T - 1 - a_i) / P \rfloor} [(a_i + iP) \in B \text{ (mod }Q)]

发现 aia_i 每次会加上 PP 再模 QQ,倍增优化即可。时间复杂度为 O(PlogP)O(P \log P)

还有一种做法是对不同的 gcd(P,Q)\gcd(P, Q) 剩余系分开处理 ((每个都是一个环))

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

typedef long long ll;
const int maxn = 1000010;
int P, Q, n, m, A[maxn], B[maxn], C[maxn], f[20][maxn], v[20][maxn];
ll R, T, ans;

int main() {
scanf("%d %d %d %d %lld", &P, &Q, &n, &m, &T);
R = 1LL * P * Q / __gcd(P, Q);
for (int i = 0; i < n; i++) {
scanf("%d", &A[i]);
}
for (int i = 0; i < m; i++) {
scanf("%d", &B[i]), C[B[i]] = 1;
}
for (int i = 0; i < Q; i++) {
f[0][i] = C[i], v[0][i] = (i + P) % Q;
}
for (int i = 1; i < 20; i++) {
for (int j = 0; j < Q; j++) {
f[i][j] = f[i - 1][j] + f[i - 1][v[i - 1][j]];
v[i][j] = v[i - 1][v[i - 1][j]];
}
}
ll tmp = Q / __gcd(P, Q);
for (int i = 0; i < n; i++) {
int cur = A[i] % Q;
for (int j = 19; ~j; j--) if (tmp >> j & 1) {
ans += T / R * f[j][cur], cur = v[j][cur];
}
}
tmp = (T %= R) / P;
for (int i = 0; i < n; i++) {
int cur = A[i] % Q;
for (int j = 19; ~j; j--) if (tmp >> j & 1) {
ans += f[j][cur], cur = v[j][cur];
}
if (T - 1 - A[i] >= 0 && (T - 1 - A[i]) / P >= tmp) {
ans += C[((T - 1 - A[i]) / P * P + A[i]) % Q];
}
}
printf("%lld\n", ans);
return 0;
}

T3. 通信

题目大意:有 nn 个点,第 ii 个点的权值为 aia_i。每个点需要选择以下二者之一:

  1. 直接连接到中心,代价为 WW
  2. 连接到前面的某个点 jj (j<i)(j < i),代价为 aiaj\lvert a_i - a_j \rvert

每个点只能被后面的至多一个点连接。求最小的代价和。保证 n103,n \leqslant 10^3, ai109a_i \leqslant 10^9

思路分析:可以建立费用流模型。离散化,按 aia_i 建立主席树,拆虚点优化连边。

时间复杂度的上界为 O(VE2)=O(n3log2n)O(\lvert V \rvert \lvert E \rvert^2) = O(n^3 \log^2 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
#include <bits/stdc++.h>
#define mid (l + r >> 1)
using namespace std;

typedef long long ll;
const int maxn = 40000;
int n, W, cnt, tot, a[maxn], head[maxn], inq[maxn], incf[maxn], pre[maxn];
int cur1, cur2, S, T, rt1[maxn], rt2[maxn];
struct node { int l, r, id; } t1[maxn], t2[maxn];
ll ans, dist[maxn]; queue<int> q;
struct edge { int to, cap, nxt; ll cost; } e[200000];

void add(int from, int to, int cap, int cost) {
e[cnt] = (edge){to, cap, head[from], cost}, head[from] = cnt++;
e[cnt] = (edge){from, 0, head[to], -cost}, head[to] = cnt++;
}

bool spfa(int s, int t) {
memset(dist, 0x3f, sizeof(dist));
q.push(s), dist[s] = 0;
while (!q.empty()) {
int v = q.front(); q.pop(), inq[v] = 0;
for (int i = head[v], u; ~i; i = e[i].nxt) {
if (e[i].cap && dist[u = e[i].to] > dist[v] + e[i].cost) {
dist[u] = dist[v] + e[i].cost, pre[u] = i;
if (!inq[u]) q.push(u), inq[u] = 1;
}
}
}
return dist[t] < 1e18;
}

void upd(int s, int t) {
for (int i = t; i ^ s; i = e[pre[i] ^ 1].to) {
e[pre[i]].cap--, e[pre[i] ^ 1].cap++;
}
ans += dist[t];
}

void ins(node *t, int &cur, int &k1, int k2, int l, int r, int p, int v, int tmp) {
t[k1 = ++cur] = t[k2], t[k1].id = ++tot;
if (l == r) { add(t[k1].id, tmp, 1, v); return; }
if (mid >= p) ins(t, cur, t[k1].l, t[k2].l, l, mid, p, v, tmp);
else ins(t, cur, t[k1].r, t[k2].r, mid + 1, r, p, v, tmp);
if (t[k1].l) add(t[k1].id, t[t[k1].l].id, n, 0);
if (t[k1].r) add(t[k1].id, t[t[k1].r].id, n, 0);
}

void get(node *t, int k, int l, int r, int ql, int qr, int id, int p) {
if (!k) return;
if (l >= ql && r <= qr) { add(id, t[k].id, 1, p); return; }
if (mid >= ql) get(t, t[k].l, l, mid, ql, qr, id, p);
if (mid < qr) get(t, t[k].r, mid + 1, r, ql, qr, id, p);
}

int main() {
memset(head, -1, sizeof(head));
scanf("%d %d", &n, &W);
S = 0, T = tot = n + n + 1;
vector<int> v;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]), v.push_back(a[i]);
add(S, i, 1, 0), add(i, T, 1, W), add(i + n, T, 1, 0);
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
for (int i = 1; i <= n; i++) {
int t = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
get(t1, rt1[i - 1], 1, n, 1, t, i, a[i]);
get(t2, rt2[i - 1], 1, n, t, n, i, -a[i]);
ins(t1, cur1, rt1[i], rt1[i - 1], 1, n, t, -a[i], i + n);
ins(t2, cur2, rt2[i], rt2[i - 1], 1, n, t, a[i], i + n);
}
while (spfa(S, T)) upd(S, T);
printf("%lld\n", ans);
return 0;
}