成功搬家，正在逐渐把老博客里东西搬过来。
预计下周装修完毕。

暂无

* 傅云濠推荐：cf#639 F 下文有链接

下次一定

CF#639

这里

笔记本风扇问题拿去维修，本周白给

鸽

Codeforces Round #639 (Div. 2)

Puzzle Pieces

就是问用题中特定形状的拼图能不能拼出$n \times m$的矩形

分析一下可以发现，如果$n=1$或者$m=1$肯定是可以的

然后发现最大的块就是$2 \times 2$了，也就是说n和m在其它情况都不能大于2

Card Constructions

简单题

Hilbert's Hotel

题意是有无穷个房间，标号为全体整数，现在以$n$为周期进行调整，在每个周期内模$n$余$k$的房间的客人向前移动$a_k$个房间【$a_k$可能为负】，问是否会有客人冲突。

显然，如果$0$到$n - 1$通过$a_k$变换形成一个与$0$到$n-1$一一对应的映射，那么对于移动后的每个房间，都唯一对应一个开始的位置，没有冲突。

一但形成的映射不是一一对应的，那么一定会有房间冲突。

Monopole Magnets

题意是有一个$n \times m$的矩阵，你可以向其中每个位置放置任意个黑点和白点。符合如下规则：

1、每一列每一行必须有白点

2、所有黑点可以向同一行或同一列的白点所在方向移动任意格。要求带#点必须可以被移动到，剩余带.点必须不能被移动到。

求最少需要多少黑点，或者无解。

分析发现，任意#之间的路径可达，如果两个#之间存在.，那么一定是不合法的。也就是说，#形成的联通块是凸的。

其次如果存在一行全为.且任意一列都有#，那么不合法。因为那一行一定要放置白点，无论放置在哪都会导致该列#处的黑点到达。

然后数一数#联通块个数就是答案了

Quantifier Question

【当天cf一直in queue，写到这题就停了，但大概想到做法了】

题意是给出一个公式包含$n$变量的若干个$\left(x_i < x_j\right)$的合取的形式，要求给出一个合适的量词，使得公式为真。

量词中$x_i$顺序固定，要求使用尽量多的全称量词$\forall$

首先我们发现，一个$\left(x_i <x_j\right)$中，假如$i < j$，那么$\forall x_j$一定不合法，因为$x_i$在这之前已经固定，存在$x_j$使得式子不成立。

所以一开始我们就能确定一些$x_i$必须取量词$\exists x_i$

对于剩余的，由于不等式的传递性，我们可以进行建图，那么这个图一定是拓扑图，否则公式永假。

然后对于图上每一条路径，形成一个不等关系，路径上每两点之间的不等关系就确定了，同上分析，只有最小的点能取$\forall$

那么问题就简单了，只要统计有多少点是进过其路径上编号最小的点。在拓扑图上正着反着dp一下当前最小值就算出来了。