洛谷8月月赛

发表于 更新于 阅读次数： 本文字数： 3.9k 阅读时长 ≈ 4 分钟

以前很少参加洛谷月赛，因为很难。暑假里开始参加月赛，你们可能不知道7月月赛我爆蛋了，因为T1调不出来，就不想写T2了，后面更假，而且还是ACM，搞得不敢随便交。然而看了题解发现忘了1不是质数，而T2我本来的方法基本上是对的，就是个贪心。

然而这次8月是OI赛制，目测确实真多了。共4题，照样是两个半小时。

T1

题意

给定序列$a[1\dots n]$，每次操作令$a’[i]=a[i]+a[i\mod n+1]$，注意是批量更新。$Q$个询问，求第$x$次操作后$a[y]$的值。

$n\le 10^7,Q\le 10^4,x\le 2000$，其中有50%为$n\le 10^5,Q\le 100,x\le 500$。

1
2
3
4
5
5
1 2 3 4 5
2
1 2
2 2
1
2
5
12

思路

直接模拟$\mathcal O(nx)$，有50分。

考虑到$Q$很小，想象操作过程为$x$层，每层$n$个数的矩阵。对于每一个询问，至少要知道矩阵里的哪些数呢？假设$x+y\ll n$，就是个倒三角，有$\mathcal O(x^2)$个数。类似记忆化进行计算，复杂度为$\mathcal O(Qx^2)$，与$n$无关了。

进一步观察，可以得到以下结果（$a[x][y]$表示答案，$x+y\ll n$）：

$$
\begin{split}
a[x][y]&=a[x-1][y]+a[x-1][y+1]\
&=a[x-2][y]+2\times a[x-2][y+1]+a[x-2][y+2]\
&=a[x-3][y]+3\times a[x-3][y+1]+3\times a[x-3][y+2]+a[x-3][y+3]\
\vdots
\end{split}
$$

容易发现就是杨辉三角，因此

$$a[x][y]=\sum_{i=0}^x a[y+i]\times C_x^i$$

可以$\mathcal O(x^2)$预处理，然后$\mathcal O(Qx)$计算。

代码

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
#include <iostream>
using namespace std;
const int N = 1000005, M = 2000, MOD = 998244353;
int c[M + 5][M + 5], a[N];
int main()
{
	ios::sync_with_stdio(false);
	c[0][0] = c[1][0] = c[1][1] = 1;
	for (int i = 2; i <= M; i++)
	{
		c[i][0] = c[i][i] = 1;
		for (int j = 1; j < i; j++)
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
	}
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	int q;
	cin >> q;
	while (q--)
	{
		int x, y;
		cin >> x >> y;
		int ans = 0;
		for (int i = 0; i <= x; i++)
			ans = (ans + 1ll * a[(y + i - 1) % n + 1] * c[x][i]) % MOD;
		cout << ans << endl;
	}
	return 0;
}

T2

题意

有$n$个数，每个数范围$1\dots m$。可以进行下面两种操作无限次：

  • 选择任意两个相同的数，合并成它们的和。
  • 减小任意一个数。

求最终可以得到的最大值。

$n,m\le 10^7$，其中有30%为$n,m\le 10$，60%为$n,m\le 10^5$。有2s，256MB，数据随机。

为了方便把样例格式改为正常。

1
2
5 10
6 10 7 5 4
1
24

思路

毫无思路，但是数据随机。搜索看起来很难写。于是开始乱搞吧，这可是OI赛制。

首先得升序排序，$10^7$排序让我很担心，好在可以桶排。一开始想不能浪费数，要求每次合并时必须等于比这两个数大的最小数，以便继续合并。写了半天突然发现连上面那个样例都过不了，因为这样做答案最多只有$2\times m$。

把两个数强行缩小就是一种浪费，那不缩小不就行了？于是我有了有依据的乱搞：维护一个堆，每次取出最小的两个数合并，再放回去。这种方法可以过所有样例，但可能是错的。时间复杂度$\mathcal O(n\log n)$。

我本来打算就这样的，出去逛了一圈，突然想到放回去的数一定是单调的。这不就是蚯蚓吗？我昨天刚做过。于是改写成桶排和单调队列（只是单调的队列而已），做到$\mathcal O(m)$。其实也很好写。

代码

注意原题是以随机数种子为输入的，就是那个generate_array。

$\mathcal O(n\log n)$：我不会告诉你用set是为了卡常。

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
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
multiset<long long> S;
void generate_array(int n, int m, int seed)
{
	unsigned x = seed;
	for (int i = 0; i < n; ++i)
	{
		x ^= x << 13;
		x ^= x >> 17;
		x ^= x << 5;
		S.insert(x % m + 1);
	}
}
int main()
{
	int n, m, seed;
	cin >> n >> m >> seed;
	generate_array(n, m, seed);
	while (S.size() >= 2)
	{
		long long a = *S.begin();
		S.erase(S.begin());
		long long b = *S.begin();
		S.erase(S.begin());
		S.insert(min(a, b) * 2);
	}
	cout << *S.begin() << endl;
	return 0;
}

$\mathcal O(m)$：

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 <iostream>
#include <algorithm>
using namespace std;
const int N = 10000005;
const long long INF = 1e18;
int b[N], a[N];
long long q[N];
void generate_array(int n, int m, int seed)
{
	unsigned x = seed;
	for (int i = 0; i < n; ++i)
	{
		x ^= x << 13;
		x ^= x >> 17;
		x ^= x << 5;
		b[x % m + 1]++;
	}
}
int main()
{
	int n, m, seed;
	cin >> n >> m >> seed;
	generate_array(n, m, seed);
	int cc = 0;
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= b[i]; j++)
			a[++cc] = i;
	int l = 1, ql = 1, qr = 0;
	while ((n - l + 1) + (qr - ql + 1) >= 2)
	{
		long long u = min(l <= n ? 1ll * a[l] : INF, ql <= qr ? q[ql] : INF);
		if (u == a[l])
			l++;
		else
			ql++;
		long long v = min(l <= n ? 1ll * a[l] : INF, ql <= qr ? q[ql] : INF);
		if (v == a[l])
			l++;
		else
			ql++;
		q[++qr] = min(u, v) * 2;
	}
	if (l == n)
		cout << a[n] << endl;
	else
		cout << q[ql] << endl;
	return 0;
}

T3

比较难懂的题目，我骗了$k=0$和$k=1$就跑了。

T4

题意

在$n\times m$的中国象棋棋盘上放$2\times n$个炮，互不攻击的方案数。

$n,m\le 10^5$，有20%为$n,m\le 5$。

1
4 4
1
90

思路

没多少时间了，还是爆搜吧，虽然看上去像是原题。然而没有任何样例解释，就被坑了很久。

首先我以为炮是可以斜着攻击的，于是我麻烦地按照八皇后写了两条对角线。然后在我印象中中国象棋的棋子是放在格点上的，转换为格子就是$(n+1)\times(m+1)$个格子。好，答案居然有几万！

然后我只能改小棋盘，但数字还是很离谱。突然想到每行不一定放满两个，于是继续改，但依然离谱。

眼看比赛只有不到十分钟结束了，我终于决定查一下中国象棋。结果发现炮只能直走……又试了几次，发现棋子放在格子里才对。这样终于把搜索写完了。我想也没人要看我愚蠢的代码吧（每行不放满的部分懒得删）。

结果

名次 总分 时间 A B C D
#26 225 2244ms 100 90 15 20

~~StarClan~~天知道B怎么会是90。

题解很快就出了，还包括讲评的PPT。B原来如果取min(u,v)*2可能还是v大，应该取max，这只卡了10分。