某岛

… : "…アッカリ~ン . .. . " .. .
August 11, 2021

Codeforces Round #737 (Div. 2)

传送门

https://codeforces.com/contest/1557

说着要回 Div1,结果分越来越低了。。。
上紫名好难啊。。。。(暴风哭泣)

Problem B. Moamen and k-subarrays

给定一个数组,拆成 k 个 子段,再重新排序,问这样是否能将这个数组排序,保证数字不相同。

然后开始默认需要拆 n 份,然后看相邻位置如果再排序后也相邻就让需要拆的份数 -1.

Problem C. Moamen and XOR

给定 n,k 问有多少组长度为 n 的数组 a,满足 && 和大于等于 xor 和。(ai <= 2^k)

对 n 分奇偶讨论即可,比赛的时候对幂次取模结果 debug 了好久不能更蠢。。。

Problem D. Ezzat and Grid

给定一个 01 矩阵,问至少删掉多少行,使得相邻行 至少再某一列都有 1。

对于每一行,我们向下连边,这个东西显然是一个 dag,dp 求最长链即可。
因为是求最长链,可以对图可以有所简化,将边的规模缩小为 O(n)。

所以难点在于如何用数据结构帮助建图。
最简单的方式当然是用 set 去维护区间集合,这个东西在很多计算几何题目里应该经常会用到。

Problem E. Assiut Chess

交互题。棋盘上有一个看不见的 King,给你一个 Queen,在限定步数内将死这个 King。
King 不能走到被你一步可以将死的位置。

基本想法是固定我的位置,然后一步步把对手卡到四角。
但是貌似有一些情况需要特殊处理,我想不太清楚。。。然后看步数比较宽松试图用随机化乱搞过去但是失败了。。。
嘛。。。感觉这种题数据着实也不太好出。。。果不其然,现场也确实被各种乱搞爆过去了。。

Comments are closed.