August 11, 2021
https://codeforces.com/contest/1557
说着要回 Div1，结果分越来越低了。。。
上紫名好难啊。。。。（暴风哭泣）
给定一个数组，拆成 k 个 子段，再重新排序，问这样是否能将这个数组排序，保证数字不相同。
然后开始默认需要拆 n 份，然后看相邻位置如果再排序后也相邻就让需要拆的份数 -1.
给定 n,k 问有多少组长度为 n 的数组 a，满足 && 和大于等于 xor 和。(ai <= 2^k)
对 n 分奇偶讨论即可，比赛的时候对幂次取模结果 debug 了好久不能更蠢。。。
给定一个 01 矩阵，问至少删掉多少行，使得相邻行 至少再某一列都有 1。
对于每一行，我们向下连边，这个东西显然是一个 dag，dp 求最长链即可。
因为是求最长链，可以对图可以有所简化，将边的规模缩小为 O(n)。
所以难点在于如何用数据结构帮助建图。
最简单的方式当然是用 set 去维护区间集合，这个东西在很多计算几何题目里应该经常会用到。
交互题。棋盘上有一个看不见的 King，给你一个 Queen，在限定步数内将死这个 King。
King 不能走到被你一步可以将死的位置。
基本想法是固定我的位置，然后一步步把对手卡到四角。
但是貌似有一些情况需要特殊处理，我想不太清楚。。。然后看步数比较宽松试图用随机化乱搞过去但是失败了。。。
嘛。。。感觉这种题数据着实也不太好出。。。果不其然，现场也确实被各种乱搞爆过去了。。
Posted by
xiaodao
Category: 日常
August 11, 2021
https://codeforces.com/contest/1557
说着要回 Div1，结果分越来越低了。。。
上紫名好难啊。。。。（暴风哭泣）
给定一个数组，拆成 k 个 子段，再重新排序，问这样是否能将这个数组排序，保证数字不相同。
然后开始默认需要拆 n 份，然后看相邻位置如果再排序后也相邻就让需要拆的份数 -1.
给定 n,k 问有多少组长度为 n 的数组 a，满足 && 和大于等于 xor 和。(ai <= 2^k)
对 n 分奇偶讨论即可，比赛的时候对幂次取模结果 debug 了好久不能更蠢。。。
给定一个 01 矩阵，问至少删掉多少行，使得相邻行 至少再某一列都有 1。
对于每一行，我们向下连边，这个东西显然是一个 dag，dp 求最长链即可。
因为是求最长链，可以对图可以有所简化，将边的规模缩小为 O(n)。
所以难点在于如何用数据结构帮助建图。
最简单的方式当然是用 set 去维护区间集合，这个东西在很多计算几何题目里应该经常会用到。
交互题。棋盘上有一个看不见的 King，给你一个 Queen，在限定步数内将死这个 King。
King 不能走到被你一步可以将死的位置。
基本想法是固定我的位置，然后一步步把对手卡到四角。
但是貌似有一些情况需要特殊处理，我想不太清楚。。。然后看步数比较宽松试图用随机化乱搞过去但是失败了。。。
嘛。。。感觉这种题数据着实也不太好出。。。果不其然，现场也确实被各种乱搞爆过去了。。
Posted by
xiaodao
Category: 日常