洛谷8月月赛

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

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

T1

题意

给定序列 ,每次操作令 ,注意是批量更新。QQ个询问,求第xx次操作后a[y]a[y]的值。

n107,Q104,x2000n\le 10^7,Q\le 10^4,x\le 2000,其中有50%为n105,Q100,x500n\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

思路

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

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

进一步观察,可以得到以下结果(a[x][y]a[x][y]表示答案,x+ynx+y\ll n):

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

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

可以O(x2)\mathcal O(x^2)预处理,然后O(Qx)\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

题意

nn个数,每个数范围 。可以进行下面两种操作无限次:

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

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

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

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

1
2
5 10
6 10 7 5 4
1
24

思路

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

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

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

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

代码

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

O(nlogn)\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;
}

O(m)\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=0k=0k=1k=1就跑了。

T4

题意

n×mn\times m的中国象棋棋盘上放2×n2\times n个炮,互不攻击的方案数。

n,m105n,m\le 10^5,有20%为n,m5n,m\le 5

1
4 4
1
90

思路

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

首先我以为炮是可以斜着攻击的,于是我麻烦地按照八皇后写了两条对角线。然后在我印象中中国象棋的棋子是放在格点上的,转换为格子就是(n+1)×(m+1)(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分。