碎碎念好久没有打 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