CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 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编程）（感觉不是正解）
CVBB ACM Team

用户工具

站点工具

页面工具
