2018年全国多校算法寒假训练营练习比赛(第五场)简易题解

A. 逆序数

  • 树状数组或归并排序求逆序对……姿势有很多。注意不要爆int
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
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int maxn = 1 << 17;
int bit[maxn];
int a[maxn];
inline void add(int x)
{
for (int i = x; i < maxn; i += i & -i) bit[i]++;
}

inline int query(int x)
{
int t = 0;
for (int i = x; i; i -= i & -i) t += bit[i];
return t;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
a[i] = num + 1;
}
ll ans = 0;
for (int i = n - 1; ~i; i--)
{
add(a[i]);
ans += query(a[i] - 1);
}
cout << ans << endl;
return 0;
}

B. Big Water Problem

  • ……水题直接做就好了。
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
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int maxn = 1 << 17;
ll bit[maxn];

inline void add(int x, int v)
{
for (int i = x; i < maxn; i += i & -i) bit[i] += v;
}

inline int sum(int x)
{
ll t = 0;
for (int i = x; i; i -= i & -i) t += bit[i];
return t;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n, m, x, y, op;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &x);
add(i, x);
}
while (m--)
{
scanf("%d%d%d", &op, &x, &y);
if (op == 1)
add(x, y);
else
printf("%lld\n", sum(y) - sum(x - 1));
}

return 0;
}

C. 字符串的问题

  • KMP。知道失配指针含义,就可以乱搞了。
  • 沿着失配边往前找到一个在原串中出现两次以上的前缀即可。
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
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int N = 1 << 20;
// 返回y中x的个数
int Next[N];
void initkmp(char x[], int m)
{
int i = 0, j = Next[0] = -1;
while (i < m)
{
while (j != -1 && x[i] != x[j]) j = Next[j];
Next[++i] = ++j;
}
}
int kmp(char x[], int m, char y[], int n)
{
int i, j, ans;
i = j = ans = 0;
// initkmp(x, m);
while (i < n)
{
while (j != -1 && y[i] != x[j]) j = Next[j];
i++, j++;
if (j >= m) ans++, j = Next[j];
}
return ans;
}

char s[N];

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
scanf("%s", s);
int n = strlen(s);
initkmp(s, n);
int t = n;
while (t = Next[t])
{
if (kmp(s, t, s, n) > 2)
{
s[t] = '\0';
printf("%s\n", s);
return 0;
}
}
puts("Just a legend");
return 0;
}

D. 集合问题

  • 开两个虚拟的结点,并查集搞一下就好了。
  • 能放A的就放A,不然放B。能放B的就放B,不然放A。
  • 最后检查一下两个集合是不是相交了就好。
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
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int MAX = 1 << 18;
int n, a, b, p[MAX], fa[MAX];
map<int, int> M;

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void unite(int x, int y)
{
x = find(x), y = find(y);
if (x != y) fa[x] = y;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
scanf("%d%d%d", &n, &a, &b);
int Max = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &p[i]);
M[p[i]] = i;
Max = max(Max, p[i]);
}
if (Max >= max(a, b))
return puts("NO"), 0;
for (int i = 0; i <= n + 1; i++) fa[i] = i;
for (int i = 1; i <= n; i++)
{
if (M[a - p[i]])
unite(i, M[a - p[i]]);
else
unite(i, n + 1);
if (M[b - p[i]])
unite(i, M[b - p[i]]);
else
unite(i, 0);
}
int A = find(0);
int B = find(n + 1);
if (A != B)
{
puts("YES");
for (int i = 1; i <= n; i++) printf("%d%c", find(i) != A, " \n"[i == n]);
}
else
puts("NO");
return 0;
}

E. 情人节的电灯泡

  • ……水题直接做就好了
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
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int maxn = 1005;
struct BIT
{
int n;
int val[maxn][maxn];
void init(int n)
{
clr(val, 0);
this->n = n;
}
inline int lowbit(int x) { return x & -x; }
void add(int x, int y, int v)
{
for (int i = x; i <= n; i += lowbit(i))
for (int j = y; j <= n; j += lowbit(j))
val[i][j] += v;
}
int sum(int x, int y)
{
int ret = 0;
for (int i = x; i; i -= lowbit(i))
for (int j = y; j; j -= lowbit(j))
ret += val[i][j];
return ret;
}
int query(int x1, int y1, int x2, int y2) { return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1); }

} ans;

bool a[maxn][maxn];

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n, m;
while (cin >> n >> m)
{
int op;
ans.init(n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
scanf("%d", &a[i][j]);
if (a[i][j]) ans.add(i, j, 1);
}
while (m--)
{
scanf("%d", &op);
if (op == 1)
{
static int x, y;
scanf("%d%d", &x, &y);
a[x][y] ^= 1;
ans.add(x, y, a[x][y] ? 1 : -1);
}
else
{
static int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", ans.query(x1, y1, x2, y2));
}
}
}
return 0;
}

F. The Biggest Water Problem

  • 按题意暴力模拟即可。
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
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n;
cin >> n;
while (n >= 10)
{
string s = to_string(n);
n = accumulate(s.begin(), s.end(), 0, [](int a, char b) { return a + b - '0'; });
}
cout << n << endl;
return 0;
}

G. 送分啦-QAQ

  • 经典的斐波那契博弈,有兴趣自己去看证明……
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
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n, fib[45];
fib[0] = 2;
fib[1] = 3;
for (int i = 2; i < 45; i++)
fib[i] = fib[i - 1] + fib[i - 2];
cin >> n;
puts(binary_search(fib, fib + 45, n) ? "Sha" : "Xian");
return 0;
}

H. A Simple Problem with Integers

  • 线段树乱搞就好了……
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
#include<bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

#define lson rt << 1
#define rson rt << 1 | 1
#define Lson l, m, lson
#define Rson m + 1, r, rson
const int maxn = 1e5 + 5;
ll sumv[maxn << 2], addv[maxn << 2];

void pushup(int rt) { sumv[rt] = sumv[lson] + sumv[rson]; }

void pushdown(int rt, int m)
{
if (addv[rt] == 0)
return;
addv[lson] += addv[rt];
addv[rson] += addv[rt];
sumv[lson] += addv[rt] * (m - (m >> 1));
sumv[rson] += addv[rt] * (m >> 1);
addv[rt] = 0;
}

void build(int l, int r, int rt)
{
addv[rt] = 0;
if (l == r)
{
scanf("%lld", &sumv[rt]);
return;
}
int m = (l + r) >> 1;
build(Lson);
build(Rson);
pushup(rt);
}

void update(int L, int R, ll add, int l, int r, int rt)
{
if (L <= l && r <= R)
{
addv[rt] += add;
sumv[rt] += add * (r - l + 1);
return;
}
pushdown(rt, r - l + 1);
int m = (l + r) >> 1;
if (L <= m) update(L, R, add, Lson);
if (m < R) update(L, R, add, Rson);
pushup(rt);
}

ll query(int L, int R, int l, int r, int rt)
{
if (L <= l && r <= R) return sumv[rt];
pushdown(rt, r - l + 1);
int m = (l + r) >> 1;
ll ans = 0;
if (L <= m) ans += query(L, R, Lson);
if (m < R) ans += query(L, R, Rson);
return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n, q;
scanf("%d%d", &n, &q);
build(1, n, 1);
while (q--)
{
char op;
int l, r;
ll add;
scanf(" %c", &op);
if (op == 'Q')
{
scanf("%d%d", &l, &r);
printf("%lld\n", query(l, r, 1, n, 1));
}
else
{
scanf("%d%d%lld", &l, &r, &add);
update(l, r, add, 1, n, 1);
}
}
return 0;
}
捐助作者