Warning: session_start(): open(/tmp/sess_d90820df12258e8803b4d2b9b825fe06, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 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}