「2018 五校联考 Round1」题目讲解

本文受密码保护

密码:t1的输入文件名称(xxxx.in)

2018 五校联考 Round1

By - infinityedge

前排先%%%dzm神仙

Day 1

A. 骰子

Problem A (dice.c/cpp/pas)\text{Problem A (dice.c/cpp/pas)}Input file: dice.in Output file: dice.out\text{Input file: dice.in Output file: dice.out}Time Limit : 1 second Memory Limit: 512 megabytes\text{Time Limit : 1 second Memory Limit: 512 megabytes}

有一个 n×mn\times m 的网格,在网格的左上角(第 11 行第 11 列)有一个骰子。骰子的初始状态如下图所示(即上面为 11 ,下面为 66 ,左面为 44 ,右面为 33 ,前面为 22,后面为 55

img

现在按一定的规则滚动骰子。滚动骰子当然是有轨迹的。你需要从左到右滚动到右端,然后向下滚动一格然后在向左滚动到左端,再向下一格,如此反复,直到所有的格子都被经过为止。

你需要计算出骰子到达每个格点(包括初始的格子)时,骰子上方的数字之和

Input

一行两个整数 n, m

Output

一行一个整数表示答案

Examples

dice.indice.out
3 219
3 442
114 514205086

Notes

样例 11 解释:经过每个格子时骰子上面的数字依次为: 1 4 5 1 3 5\text{1 4 5 1 3 5}

对于 50%50\% 的数据,1n,m1031\le n, m \le 10^3

对于 100%100\% 的数据,1n,m1051 \le n, m\le 10^5

算法1 - 50 pts

一个简单的模拟(

时间复杂度 O(n×m)O(n\times m)

期望得分: 50 pts\text{50 pts}

算法2 - 100 pts

考虑到连续滚动的时候只有四个面接触,且和为 1414 ,我们只需要对于每行先 O(1)O(1) 处理出循环的部分,剩下的暴力模拟即可qwq(

时间复杂度 O(n)O(n)

期望得分: 100 pts\text{100 pts}


这个是真的签到题。。。

万人 A ....然而最菜的 Shq 并没有A.....(

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
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <complex>

#define inf 0x3f3f3f3f
#define MAXN 131072

using namespace std;

typedef long long ll;

ll n, m, ans;
ll s, x, z, y, q, h;
void soll() {
int t = s;
s = y, y = x, x = z, z = t;
ans += s;
}
void solr() {
int t = s;
s = z, z = x, x = y, y = t;
ans += s;
}
void sold() {
int t = s;
s = h, h = x, x = q, q = t;
ans += s;
}
int main() {
freopen("dice.in", "r", stdin);
freopen("dice.out", "w", stdout);

ans = s = 1, x = 6, z = 4, y = 3, q = 2, h = 5;
scanf("%lld %lld",&n,&m);
for(int i = 1; i <= n; i ++){
ans += ((m - 1) / 4) * 14;
if(i & 1)
for(int j = 1; j <= (m - 1) % 4; j ++) solr();
else
for(int j = 1; j <= (m - 1) % 4; j ++) soll();
if(i != n) sold();
}
printf("%lld\n", ans);
return 0;
}

B. 子序列

Problem B (sub.c/cpp/pas)\text{Problem B (sub.c/cpp/pas)}Input file: sub.in Output file: sub.out\text{Input file: sub.in Output file: sub.out}Time Limit : 1 second Memory Limit: 512 megabytes\text{Time Limit : 1 second Memory Limit: 512 megabytes}

给定一个长度为 nn 的序列 a1,a2,a3ana_1,a_2,a_3\cdots a_n

你需要求出有多少对这样的三元组 (i,j,k)(i, j, k)

满足 i<j<ki < j < k 并且 ai<aj<aka_i < a_j < a_kai>aj>aka_i > a_j > a_k

你只需要求出答案对 109+710^9+7 取模的结果

Input

第一行为一个整数 nn

第二行为用空格空格隔开的 nn 个整数,第 ii 个数为 aia_i

Output

一行,表示答案对 109+710^9+7 取模的结果

Examples

sub.insub.out
4 3 1 2 31

Notes

对于 20%20\% 的数据, n2×102n \le 2 \times 10^2

对于 50%50\% 的数据, n2×103n \le 2 \times 10^3

对于另 20%20\% 的数据, ai4×105a_i \le 4\times10^5

对于 100%100\% 的数据, 3n2×105,ai1093\le n \le 2 \times 10^5, a_i \le 10^9

算法1 - 20 pts

比较容易想的一个暴力

由于 1n2001 \le n \le 200

我们就直接暴力枚举 i,j,ki,j, k,然后暴力判断是否满足条件qwq(

时间复杂度:O(n3)O(n^3)

期望得分: 20 pts\text{20 pts}

算法2 - 50 pts

我们想想怎么做可以让时间复杂度降低

枚举中间的数,然后统计左边有多少个数比他小/大,右边有多少个数比他大/小,用乘法原理统计答案

期望得分: 50 pts\text{50 pts}

算法3 - 100 pts

1n2000001 \le n\le 200000

离散化后用树状数组统计即可。

是给不会离散化的人准备的(

时间复杂度 O(nlog2n)O(n \log_2 n)

期望得分: 100 pts\text{100 pts}

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

using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int n;
int tmp[200005], a[200005];
int bit1[200005], bit2[200005];

inline int lowbit(int x){
return x & -x;
}

void add(int *bit, int pos, int v){
for(int i = pos; i <= n; i += lowbit(i)){
bit[i] += v;
}
}
int query(int *bit, int pos){
int ret = 0;
for(int i = pos; i; i -= lowbit(i)){
ret += bit[i];
}
return ret;
}
ll ans = 0;
int main(){
freopen("sub.in", "r", stdin);
freopen("sub.out", "w", stdout);

scanf("%d", &n);
for(int i = 1; i <= n; i ++){
scanf("%d", &a[i]); tmp[i] = a[i];
}
sort(tmp + 1, tmp + n + 1);
for(int i = 1; i <= n; i ++){
a[i] = lower_bound(tmp + 1, tmp + n + 1, a[i]) - tmp;
add(bit2, a[i], 1);
}
for(int i = 1; i <= n; i ++){
add(bit2, a[i], -1);
ans = (ans + 1ll * query(bit1, a[i] - 1) * (query(bit2, n) - query(bit2, a[i]))) % mod;
ans = (ans + 1ll * query(bit2, a[i] - 1) * (query(bit1, n) - query(bit1, a[i]))) % mod;
add(bit1, a[i], 1);
}
printf("%lld\n", ans);
return 0;
}

算法4 - 100 pts

Lgy: 这个不是平衡树板子题吗?

平衡树搞即可

Code

代码来自Lgy

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
#include <cstdio>
#include <cstring>
#include <climits>
#include <ctime>
#include <algorithm>
#include <cstdlib>

const int MAXN = 2e5 + 7;
const int HA = 1e9 + 7;

int a[MAXN];
int low[MAXN], up[MAXN];
int l2[MAXN], u2[MAXN];

struct Node {
int val, pri, pos;
int size, num;
Node *left, *right;

void pushUp() {
size = num;
if (left != NULL) {
size += left->size;
}
if (right != NULL) {
size += right->size;
}
}
} poor[MAXN << 2], *tail = poor, *r1, *r2;

Node *newNode() {
Node *ret = ++tail;
ret->val = 0, ret->pri = rand();
ret->size = ret->num = 1;
ret->left = ret->right = NULL;
return ret;
}

void leftRotate(Node *&v) {
Node *tmp = v->right;
v->right = tmp->left;
tmp->left = v;
v->pushUp(), tmp->pushUp();
v = tmp;
}

void rightRotate(Node *&v) {
Node *tmp = v->left;
v->left = tmp->right;
tmp->right = v;
v->pushUp(), tmp->pushUp();
v = tmp;
}

void insert(Node *&v, int value, int pos) {
if (v == NULL) {
v = newNode();
v->val = value;
v->pos = pos;
return;
}

if (v->val == value) {
v->num++;
v->pushUp();
return;
}

if (value < v->val) {
insert(v->left, value, pos);
if (v->pri < v->left->pri) {
rightRotate(v);
}
else v->pushUp();
}
else {
insert(v->right, value, pos);
if (v->pri < v->right->pri) {
leftRotate(v);
}
else v->pushUp();
}
}

void getLow(Node *v, int value, int &num) {
if (v == NULL) return;

int s = 0;
if (v->left) {
s += v->left->size;
}

if (value < v->val) {
getLow(v->left, value, num);
} else if (value > v->val) {
num += v->num + s;
getLow(v->right, value, num);
} else {
num += s;
}
}

void getUp(Node *v, int value, int &num) {
if (v == NULL) return;

int s = 0;
if (v->right) {
s += v->right->size;
}

if (value > v->val) {
getUp(v->right, value, num);
} else if (value < v->val) {
num += v->num + s;
getUp(v->left, value, num);
} else {
num += s;
}
}

int main(int argc, char *argv[]) {
freopen("sub.in", "r", stdin);
freopen("sub.out", "w", stdout);
int n;
srand(time(0));
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++) {
if (i != 1) {
int l = 0, u = 0;
getLow(r1, a[i], l);
getUp(r1, a[i], u);
low[i] = l;
up[i] = u;
}
insert(r1, a[i], i);
}
long long ans = 0;
for (int i = n; i >= 1; i--) {
if (i != n) {
int l = 0, u = 0;
getLow(r2, a[i], l);
getUp(r2, a[i], u);
l2[i] = l;
u2[i] = u;
}
insert(r2, a[i], i);
ans = (ans + ((low[i] % HA) * (u2[i] % HA)) % HA) % HA;
ans = (ans + ((up[i] % HA) * (l2[i] % HA)) % HA) % HA;
}
printf("%lld\n", ans);
return 0;
}

C. 平面图

Problem C (planar.c/cpp/pas)\text{Problem C (planar.c/cpp/pas)}Input file: planar.in Output file: planar.out\text{Input file: planar.in Output file: planar.out}Time Limit : 1 second Memory Limit: 512 megabytes\text{Time Limit : 1 second Memory Limit: 512 megabytes}

平面图(Planar graph\text{Planar graph})是可以画在平面上并且使得不同的边可以互不交叠的图。

有一次数学课,你们正在学习选修 232-3 ,数学老师正在讲一道题,题目大意是给你一张图,要求用 44 种颜色给每个点染色,被一条边连接的两个点不能染成相同的颜色,求方案数。那张图如下:

img

你的数学老师问大家这张图是平面图还是立体图。而你——班里唯一的 OIer\text{OIer} ——是回答平面图的唯一的人。而此时,你的数学老师已经怒不可言,怒斥你没有学好立体几何。

为了教你的数学老师做人,你需要解决一个更复杂的问题:图是一个 nn 棱柱。形式化的讲,这张

图有 2n2n 个点,其中 ii 号点与 号点有边相连,i+ni+n 号点与 号点有边相连,ii 号点与 i+ni+n 号点有边相连。(所有的 ii 都满足 1in1\le i \le n)。你需要求的是对这张「平面图」 用 mm 种颜色给每个点染色,被一条边连接的两个点不能染成相同的颜色的总染色方案数(两种方案不同当且仅当存在一个点在两种方案里染成的颜色不同)。你只需求出答案对 109+710^9+7 取模的结果。

当然,仅仅解决这个问题还是不够让数学老师屈服,你需要用低于 O(n)O(n) 的算法解决这个问题。

Input

一行两个整数 n,mn,m

Output

一行一个数,表示答案对 109+710^9+7 取模的结果

Note

子任务 1155 分):满足 n4,m4n \le 4,m \le 4 。 子任务 221010 分):满足 n4n \le 4 。 子任务 3355 分):满足 m=2m = 2 。 子任务 441515 分):满足 。 子任务 553030 分):满足 。 子任务 663535 分):无特殊限制。 对于 100%100\% 的数据,满足

算法1 - 5 pts

暴力枚举。 期望得分: 5 pts\text{5 pts}

算法2 - 15 pts

n4n \le 4 。 用到的颜色数不多,暴力然后用组合数对应即可。

期望得分: 15 pts\text{15 pts}

算法3 - 20 pts

m=2m = 2

注意到 nn 为奇数时答案为 00,为偶数时答案为 22

* 这个可以理解为奇环无法进行二分图染色,偶环有两种方案

期望得分: 5 pts\text{5 pts},结合之前算法可得 20 pts\text{20 pts}

算法4 - 65 pts

1n1061 \le n \le 10^6 我们考虑转化一下问题

img

f[i][0/1/2][0/1/2] 表示当前填到第 ii 列,右上角的点颜色和左上角左下角都不同/和左上角相同/左下角相同,右下角的点颜色和左上角左下角都不同/和左上角相同/左下角相同的方案数。

递推即可。

m=3m = 3 是给忘记考虑某些特殊情况的人准备的。

期望得分: 65 pts\text{65 pts}

算法5 - 100 pts

把递推换成矩乘即可。

期望得分: 100 pts\text{100 pts}

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

using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int N = 7;
struct Matrix{
ll a[7][7];
void clear(){
memset(a, 0, sizeof(a));
}
void clearE(){
clear();
for(int i = 0; i < N; i ++) a[i][i] = 1;
}
Matrix operator * (const Matrix &b) const{
Matrix ret; ret.clear();
for(int i = 0; i < N; i ++){
for(int j = 0; j < N; j ++){
for(int k = 0; k < N; k ++){
ret.a[i][j] = (ret.a[i][j] + a[i][k] * b.a[k][j]) % mod;
}
}
}
return ret;
}
}A;

Matrix qpow(Matrix a, ll b){
Matrix ret; ret.clearE();
for(; b; b >>= 1, a = a * a){
if(b & 1) ret = ret * a;
}
return ret;
}
// 0 0 0
// 0 1 1
// 0 2 2
// 1 0 3
// 1 2 4
// 2 0 5
// 2 1 6
ll n, m;

int main(){
freopen("planar.in", "r", stdin);
freopen("planar.out", "w", stdout);

scanf("%lld%lld", &n, &m);
if(m == 2){
if(n & 1) printf("0\n");
else printf("2\n");
return 0;
}
if(m > 3) A.a[0][0] = (m - 3 + (m - 4) * (m - 4)) % mod;
A.a[0][1] = A.a[0][2] = A.a[0][3] = A.a[0][5] = (m - 3) * (m - 3) % mod;
A.a[0][4] = A.a[0][6] = (m - 2) * (m - 3) % mod;
A.a[1][0] = A.a[1][2] = A.a[2][0] = A.a[2][1] = A.a[3][0] = A.a[3][5] = A.a[5][0] = A.a[5][3] = m - 3;
A.a[1][3] = A.a[1][4] = A.a[1][5] = A.a[2][3] = A.a[2][5] = A.a[2][6] =
A.a[3][1] = A.a[3][2] = A.a[3][6] = A.a[5][1] = A.a[5][2] = A.a[5][4] = m - 2;
A.a[4][0] = A.a[4][1] = A.a[4][5] = A.a[4][6] = A.a[6][0] = A.a[6][2] = A.a[6][3] = A.a[6][4] = 1;
A = qpow(A, n);
printf("%lld\n", A.a[4][4] * m % mod * (m - 1) % mod);
return 0;
}

算法6 - 100 pts

OEIS 大法吼啊!

OEIS A277443

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>

const int MOD = 1e9 + 7;

inline long long pow(long long a, long long n) {
a = (a % MOD + MOD) % MOD;
long long res = 1;
for (; n; n >>= 1, a = a * a % MOD) if (n & 1) res = res * a % MOD;
return res;
}

int main() {
freopen("planar.in", "r", stdin);
freopen("planar.out", "w", stdout);

// https://oeis.org/A277443, search keyword: prism graph color
// FORMULA A(n,k) = (n^2-3n+3)^k+(n-1)((3-n)^k+(1-n)^k)+n^2-3n+1.

long long k, n;
scanf("%lld %lld", &k, &n);

long long ans = pow(pow(n, 2) - 3 * n + 3, k) + (n - 1) * (pow(3 - n, k) + pow(1 - n, k)) % MOD + pow(n, 2) - 3 * n + 1;
printf("%lld\n", (ans % MOD + MOD) % MOD);
}

先写到这里,Day 2回来再补吧(


Upd: 2018 - 08 - 27

Day 2

坚持原创技术分享,您的支持将鼓励我继续创作!