2020-2021:teams:mian:withinlover:codeforces_round_639
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:mian:withinlover:codeforces_round_639 [2020/05/08 20:40] withinlover 创建 |
2020-2021:teams:mian:withinlover:codeforces_round_639 [2020/05/10 00:17] (当前版本) withinlover |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | 咕咕咕 | + | ====== Codeforces Round #639 (Div. 1) (Practice) ====== |
| + | |||
| + | ===== A Hilbert’s Hotel ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一个数列$\{a_n\}$，做变换$a_i'=a_i + i \mod n$，判断数列$\{a_n'\}$中的元素是否互不相同。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 模拟即可，$sort() + unique()$随手就写出来了。 | ||
| + | |||
| + | ===== B Monopole Magnets ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定$n\times m$的一个黑白地图，你可以随意的在地图上添加单极磁铁$N$或$S$，对于任意的两个不同名的磁铁。若他们在同一列上或同一行上，则可以使$N$向$S$移动一格。 | ||
| + | |||
| + | 你需要适当的摆放两种磁铁，是得其满足： | ||
| + | |||
| + | * 在经过有限次操作后，所有的黑色格子都有$N$极磁铁经过 | ||
| + | * 无论多少次操作，白色格子上都不会有$N$极磁铁 | ||
| + | * 每行至少有一个$S$磁铁，每列至少有一个$S$磁铁。 | ||
| + | |||
| + | 判断是否优解，优解的话输出所需要的$N$极磁铁的最少数量 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | （不看样例读不懂题系列） | ||
| + | |||
| + | 如果优解的话，很容易想到每一个黑色的联通块只需要一个$N$极磁铁。答案即为联通块的数量。所以主要目标是判断是否有解。 | ||
| + | |||
| + | 结论： - 每一行，之多有一段连续的黑格子，列同理。 - 全白的行与全白的列必须同时存在。 | ||
| + | |||
| + | 第一个很容易想到，如果有两段黑色格子的话，由于这一列上至少有一个$S$极磁铁，所以$N$极磁铁必然可以走到两端黑色格子之间的白色格子中。 | ||
| + | |||
| + | 若存在全白的行而不存在全白的列，其实和第一个同理，无论将$S$极磁铁放置于哪一列上，该列均存在$N$极磁铁可以移动到白色区域。 | ||
| + | |||
| + | 正确性显然（其实是我不知道这玩意咋放图片）不过推一推也不难，咕咕咕。 | ||
| + | |||
| + | ===== C Quantifier Question ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 貌似是一个离散数学的题。 | ||
| + | |||
| + | 给定一个公式$f(x_1,x_2,\dots,x_n)=(x_{j_1}<x_{k_1})\land(x_{j_1}<x_{k_1})\land\dots\land(x_{j_m}<x_{k_m})$ | ||
| + | |||
| + | 要求依次给$x_1,x_2,\dots,x_n$添加全称量词或特称量词。问最多可以添加几个全程量词。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 之前离散上课讲到过，这玩意很容易想到偏序关系上。若$x_i < x_j$则在$i$和$j$之间建立单向边。有环则无解，否则必然优解。 | ||
| + | |||
| + | 之后找最多的全称量词我是贪心贪过去的。大概思路如下 | ||
| + | |||
| + | * 如果一个点状态未知，则这个点为全称量词 | ||
| + | * 如果这个点是全称量词，则所有与其有直接/间接大小关系的点均为特称量词。 | ||
| + | * 如果这个点是特称量词，则其连接到的不确定的点也是特称量词。 | ||
| + | |||
| + | 闭着眼睛感受了以下，是对的（不会证）（面向测试点5编程）（感觉不是正解） | ||
2020-2021/teams/mian/withinlover/codeforces_round_639.1588941619.txt.gz · 最后更改: 2020/05/08 20:40 由 withinlover
