SG专题模拟赛

Posted on | In |
Words count in article: 2.4k | Reading time ≈ 12

又是一场相当无聊（毒瘤）的模拟赛QwQ

A. 电话微波炉（暂定）

题意：给出一个序列 $a$ ，一次操作的内容是

问最后序列中所有元素的和最大是多少。

思路：其实就是一个思博贪心，很显然的一点是最终状态下每次操作都不会让结果更优，即对于每一个 $a_i$ ，都有

移项后则有：

然后我们再来看一下操作：

假设对 $a_i$ 进行了一次操作，则

移项，则

我们会发现实质上每次操作就是交换前后的差值，那么只要一开始按照这个差值从大到小排个序就行了。

注意：要记得开 long long

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

template <typename T>
il void read(T &x)
{
	x = 0;
	T f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	x *= f;
}

int n;
ll a[N], del[N];

int main()
{
#ifndef Wepdekr
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	read(n);
	for (ri i = 1; i <= n; i++)
		read(a[i]);
	for (ri i = 1; i <= n + 1; i++)
		del[i] = a[i] - a[i - 1];
	sort(del + 1, del + n + 2);
	ll now = 0, ans = 0;
	for (ri i = n + 1; i; i--)
	{
		now += del[i];
		ans += now;
	}
	printf("%lld", ans);
	return 0;
}

B. 世界线的波动

题意：给出 $n$ 个不同的点，求这些点能构成的每个点的度数不超过 $2$ 且无 $3n$ 无向图的数量。

思路：其实就是个 $\text{DP}$ ，但是这个出题人就很无聊，非要考压位高精，然后导致这个题的难点就变成了高精（雾

讲一下 $\text{DP}$ 部分：

我们令 $f_i$ 表示选前 $i$ 个点的数量，然后不难发现每加入一个点就有以下三种情况：

  1. 这是孤立的一个点，这种情况下

  2. 这个点加在了某条链上，这种情况下

    这种情况其实并不难，就相当于在 $i - 1$ 个点中选 $j - 1$ 个点组成链然后用乘法原理乘一下就行了。重要的是虽然链上的点的顺序会影响图，但是由于是无向图，所以正着和反着其实是一条链，所以要除 $2$ 。

  3. 这个点放进了某个非 $3n$ 元环里，这种情况下

    这种情况和上面的差不多，我也懒得讲了（雾

所以就把以上三种情况加起来就行了

注意：高精不能打挂！高精不能打挂！高精不能打挂！

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 310;
const int inf = 0x7fffffff;
const double eps = 1e-8;
const ll base = 1e8;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n;

template <typename T>
struct Big_Int
{
	int len, f;
	ll val[125];
	
	Big_Int()
	{
		memset(val, 0, sizeof(val));
		f = len = 1;
	}
	
	Big_Int(T x)
	{
		len = 0, f = 1;
		memset(val, 0, sizeof(val));
		if (x < 0)
			f = -1, x = -x;
		while (x)
		{
			val[len++] = x % base;
			x /= base;
		}
	}
	
	void print()
	{
		printf("%lld", val[len - 1]);
		for (ri i = len - 2; i >= 0; i--)
			printf("%08lld", val[i]);
		putchar('\n');
		return;
	}
	
	Big_Int operator + (const Big_Int &x)
	{
		Big_Int ret;
		ret.len = max(x.len, len);
		for (ri i = 0; i < ret.len; i++)
			ret.val[i] = val[i] + x.val[i];
		for (ri i = 0; i < ret.len; i++)
			ret.val[i + 1] += ret.val[i] / base, ret.val[i] %= base;
		if (ret.val[ret.len] > 0)
			ret.len++;
		return ret;
	}
	
	Big_Int operator * (const Big_Int &x)
	{
		Big_Int ret;
		ret.len = len + x.len;
		for (ri i = 0; i < len; i++)
			for (ri j = 0; j < x.len; j++)
				ret.val[i + j] += val[i] * x.val[j];
		for (ri i = 0; i < ret.len; i++)
			ret.val[i + 1] += ret.val[i] / base, ret.val[i] %= base;
		while (!ret.val[ret.len - 1] && ret.len > 1)
			ret.len--;
		return ret;
	}
	
	Big_Int operator * (const T &x)
	{
		Big_Int ret, k(x);
		ret = (*this) * k;
		return ret;
	}
	
	Big_Int operator / (const T &x)
	{
		Big_Int ret;
		ret.len = len;
		T tmp = 0;
		for (ri i = ret.len - 1; i >= 0; i--)
		{
			tmp = tmp * base + val[i];
			ret.val[i] = tmp / x;
			tmp %= x;
		}
		while (!ret.val[ret.len - 1] && ret.len > 1)
			ret.len--;
		return ret;
	}
	
	Big_Int operator = (T x)
	{
		len = 0, f = 1;
		memset(val, 0, sizeof(val));
		if (x < 0)
			f = -1, x = -x;
		while (x)
		{
			val[len++] = x % base;
			x /= base;
		}
		return *this;
	}
};

Big_Int <ll> dp[MAXN], C[MAXN][MAXN], fac[MAXN];

int main()
{
#ifndef Wepdekr
	freopen("b.in", "r", stdin);
	freopen("b.out", "w", stdout);
#endif
	n = read();
	C[0][0] = 1;
	for (ri i = 1; i <= n; i++)
	{
		C[i][0] = 1;
		for (ri j = 1; j <= i; j++)
			C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
	}

	fac[0] = 1;
	for (ri i = 1; i <= n; i++)
		fac[i] = fac[i - 1] * i;

	dp[0] = 1;
	for (ri i = 1; i <= n; i++)
	{
		dp[i] = dp[i - 1];
		for (ri j = 2; j <= i; j++)
		{
			Big_Int <ll> tmp;
			tmp = C[i - 1][j - 1] * fac[j];
			tmp = tmp / 2;
			dp[i] = dp[i] + tmp * dp[i - j];
			// C(i - 1, j - 1) * j ! / 2
		}
		for (ri j = 4; j <= i; j++)
		{
			if (j % 3 == 0)
				continue;
			Big_Int <ll> tmp;
			tmp = C[i - 1][j - 1] * fac[j - 1];
			tmp = tmp / 2;
			dp[i] = dp[i] + tmp * dp[i - j];
			// C(i - 1, j - 1) * (j - 1) ! / 2			
		}
	}
	dp[n].print();
	return 0;
}

当然，还有更投稽取巧的做法：我会 $\text{Python}$ ！

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
n = int(input())
c = [[] for i in range(n + 1)]
c[0].append(1)
c[0].append(0)
for i in range(1, n + 1):
	c[i].append(1)
	for j in range(1, i + 1):
		c[i].append(c[i - 1][j] + c[i - 1][j - 1])
	c[i].append(0)
fac = [1]
for i in range(1, n + 1):
	fac.append(fac[i - 1] * i);
dp = [1]
tmp = 0
for i in range(1, n + 1):
	dp.append(dp[i - 1])
	for j in range(2, i + 1):
		tmp = dp[i - j] * c[i - 1][j - 1] * fac[j]
		tmp = tmp // 2
		dp[i] += tmp
	for j in range(4, i + 1):
		if j % 3 == 0:
			continue;
		tmp = dp[i - j] * c[i - 1][j - 1] * fac[j - 1]
		tmp = tmp // 2
		dp[i] += tmp
print(dp[n])

C. Time Leaper

题意：给出一个金字塔型结构，每一层都是一个正方形网格结构，层数越高边长越小（顶层边长为 $1$ ）。到达每一个方格都需要一定的代价，当且仅当两个方格有公共边或公共面积时它们能互相到达，且只能从下层走向上层。同时还有若干条需要支付一定代价的直达通道，问从最下层左上角走到最上层的最小代价是多少。

思路：似乎正解是神仙做法，不过这个东西很显然可以建图后跑最短路，具体做法就是暴力把能到达的点之间连接单向边然后跑 $\text{Dijkstra}​$ 就行了。

注意：同层之间走的时候来回的边权并不相等

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e7 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, m, cnt, num;
int head[N], dis[N];
int a[MAXN][MAXN][MAXN], id[MAXN][MAXN][MAXN];

struct edge
{
	int to, nxt, weight;
};
edge e[N];

struct element
{
	int vec, dist;
	friend bool operator < (element a1, element a2)
	{
		return a1.dist > a2.dist;
	}
};
priority_queue <element> q;

il void add_edge(int u, int v, int w)
{
	e[++cnt] = (edge) {v, head[u], w};
	head[u] = cnt;
}

il void Dijkstra(int s)
{
	memset(dis, 63, sizeof(dis));
	q.push((element) {s, a[n][1][1]});
	dis[s] = a[n][1][1];
	while (!q.empty())
	{
		element now = q.top();
		q.pop();
		int u = now.vec, d = now.dist;
		if (d != dis[u])
			continue;
		for (ri i = head[u]; i; i = e[i].nxt)
		{
			int v = e[i].to;
			if (dis[u] + e[i].weight < dis[v])
			{
				dis[v] = dis[u] + e[i].weight;
				q.push((element) {v, dis[v]});
			}
		}
	}
}

il void Insert(int i, int j, int k)
{
	if (i < n)
	{
		add_edge(id[i + 1][j][k], id[i][j][k], a[i][j][k]);
		add_edge(id[i + 1][j][k + 1], id[i][j][k], a[i][j][k]);
		add_edge(id[i + 1][j + 1][k], id[i][j][k], a[i][j][k]);
		add_edge(id[i + 1][j + 1][k + 1], id[i][j][k], a[i][j][k]);
	}
	if (j > 1)
		add_edge(id[i][j - 1][k], id[i][j][k], a[i][j][k]);
	if (k > 1)
		add_edge(id[i][j][k - 1], id[i][j][k], a[i][j][k]);
	if (j < i)
		add_edge(id[i][j + 1][k], id[i][j][k], a[i][j][k]);
	if (k < i)
		add_edge(id[i][j][k + 1], id[i][j][k], a[i][j][k]);
}
		

int main()
{
#ifndef Wepdekr
	freopen("c.in", "r", stdin);
	freopen("c.out", "w", stdout);
#endif
	n = read(), m = read();
	for (ri i = n; i; i--)
	{
		for (ri j = 1; j <= i; j++)
			for (ri k = 1; k <= i; k++)
				a[i][j][k] = read(), id[i][j][k] = ++num;
	}
	for (ri i = 1; i <= n; i++)
		for (ri j = 1; j <= i; j++)
			for (ri k = 1; k <= i; k++)
				Insert(i, j, k);
	for (ri i = 1; i <= m; i++)
	{
		int a1 = read(), b1 = read(), c1 = read(), a2 = read(), b2 = read(), c2 = read(), foo = read();
		add_edge(id[n - a1 + 1][b1][c1], id[n - a2 + 1][b2][c2], foo + a[n - a2 + 1][b2][c2]);
	}
	
	Dijkstra(id[n][1][1]);
	printf("%d", dis[id[1][1][1]]);
	return 0;
}
/*
4 2
4 1 5 2
4 3 4 7
1 9 2 8
0 3 5 1
2 8 5
9 3 9
1 1 8
7 4
4 2
42
1 1 2 2 3 1 1
1 3 2 2 2 1 7
*/

总结

考试的时候心态爆炸， $\text{A}$ 题那么思博的贪心只写了 $30pts$ 的暴力， $\text{B}$ 题思博考高精度就不谈了， $\text{C}$ 题最短路还看了半天才看出来，然后就很惨。

以后还是要提高思考的速度，有时候把式子在草稿纸上写出来会更明显一点。

0%