1731 Codeforces Round 841 (Div. 2) and Divide by Zero 2022
FallenGemini

碎碎念

好久没有打 Codeforces 了,有预感这一场会掉分,但没关系,直接冲

比赛

A. Joey Takes Money (0:02)【496/500】

题意

给一个数组 ,可以进行任意次操作,每次操作选择两个下标 ,找到两个数 ,满足 ,用 替换 ,用 替换
使 最大

分析

考虑两个数字 ,在 不变的条件下,要使 最大,应该让
于是推到 个数字,就是让其中 个数字变为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve()
{
int n;
std::cin >> n;
i64 res = 1;
for(int i = 0; i < n; i++)
{
i64 x;
std::cin >> x;
res = res * x;
}
res = res + n - 1;
std::cout << res * 2022 << '\n';
}

B. Kill Demodogs (0:14)【944/1000】

题意

给一张 的地图,起点为 ,终点为 ,每次移动可以向右或者向下。
坐标为 的点贡献为 ,总贡献为路径上所有点的贡献之和,求最大值。

分析

不难发现,尽可能多得经过对角线能使贡献最大,于是考虑右下右下的方式
贡献为

化简一下

1
2
3
4
5
6
7
8
9
10
void solve()
{
i64 n;
std::cin >> n;
i64 res1 = n * (2 * n - 1) % mod * (n - 1) % mod * ksm(3,mod - 2) % mod;
i64 res2 = n * (n - 1) / 2;
i64 res3 = n * n;
i64 res = (res1 % mod + res2 % mod + res3 % mod) * 2022 % mod;
std::cout << res << ' ' << '\n';
}

C. Even Subarrays (0:37)【1178/1500】

题意

给一个数组 ,寻找有多少对 满足 的异或和的因子个数为偶数个。

分析

不难发现,因数个数为奇数的数都是完全平方数
结合数据范围,考虑用总数减去不合法的情况
用数组 记录前缀异或和中 的出现次数,对于当前的前缀异或和 ,枚举完全平方数 ,去掉不合法的情况

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
void solve()
{
int n;
std::cin >> n;
for(int i = 0; i < n; i++)
std::cin >> a[i];
memset(cnt,0,sizeof(cnt));
cnt[0] = 1;

i64 res = 0;
int sum = 0;

for(int i = 0; i < n; i++)
{
res += i + 1;
sum ^= a[i];
for(int j = 0; j * j < N; j++)
{
int op = sum ^ (j * j);
res -= cnt[op];
}
cnt[sum]++;
}

std::cout << res << '\n';
}

D. Valiant’s New Map (0:49)【1206/1500】

题意

给一个 的矩阵 ,找到一个最大的 ,满足能够从矩阵中选出一块 的子矩阵,子矩阵中的所有数字都不小于

分析

答案有一个很显然的单调性,考虑二分
记当前判断的值为 ,新开一个矩阵 ,将 的标记 ,用矩阵 记录二维前缀和,枚举一遍所有点,判断是否存在一个二维区间满足区间和为

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
void solve()
{
int n,m;
std::cin >> n >> m;
std::vector map(n,std::vector<int> (m));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
std::cin >> map[i][j];
auto check = [&](int x)
{
std::vector f(n + 1,std::vector<int> (m + 1));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(map[i][j] < x) f[i + 1][j + 1] = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
f[i][j] = f[i][j] + f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
for(int i = x; i <= n; i++)
for(int j = x; j <= m; j++)
{
if(f[i][j] + f[i - x][j - x] - f[i - x][j] - f[i][j - x] == 0)
return true;
}
return false;
};

int l = 1, r = std::min(n,m);
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
std::cout << l << '\n';
}

E. Graph Cost

题意

给一张图,有 个点,标记为 条边,要求给图恰好加 条边
每次操作时选择一个 ,之后从图中选出恰好 ,要求 ,其中 不能重复被选择,花费代价为 给图加上这 条边,求最小代价。

分析

不难发现,每次选择的 尽可能大能使代价尽可能小。
于是 枚举,问题转换为 中有多少对 满足
首先算出有多少对 有共同的因数 ,设对数为 ,即从 中选择两个数的方案
之后去除掉有共同因数 的有序对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve()
{
i64 n,m,res = 0;
std::cin >> n >> m;
std::vector<i64> t(n + 1);
for(int i = n; i >= 2; i--)
{
i64 sum = (n / i) * (n / i - 1) / 2;
for(int j = 2 * i; j <= n; j += i)
sum -= t[j];
t[i] = sum;
}
for(i64 i = n; i >= 2; i--)
{
i64 k = std::min(t[i] / (i - 1),m / (i - 1));
res += k * i;
m -= k * (i - 1);
}
std::cout << (m == 0 ? res : -1)<< '\n';
}

总结

表现分:1898

太久没练习,脑子有点转不动了

题忘记 的公式了0.0

题开 std::vector T了几次

题一眼题,开始还在想要不要用二维树状数组,想了想不需要

题又卡了一个小时,大体思路推出来了,但是找 的时候写挂了,第一次写的是正向推上去,就是对于当前的 ,给 打个标记,一直 WA2。
赛后对拍时才发现, 的情况我给标记成
数论还是有点菜了0.0

掉分挺正常的,等状态慢慢调整回来就继续上分0.0


博客的渲染好像出了点问题,所以有些地方改的很啰嗦。
等后续的版本更新会不会改好,前端好难TvT