- Happy Birthday, Polycarp!
- Make Them Odd
- As Simple as One and Two
- Let's Play the Words?
- Two Fairs
- Beautiful Rectangle
Happy Birthday, Polycarp!
\]
暴力枚举所有数字全为 \(i、i\in[1,9]\)，然后暴力判断有多个全为 \(i\) 的数在 \(n\) 以内即可。
Make Them Odd
\]
把数一直除 \(2\)，记录除了多少次。
那么对于剩余的数相同的数，只要记录变成他需要被除的最大次数就即可。
最后的答案就是变成这些剩余数的所需次数的累和。
As Simple as One and Two
\]
首先考虑 \(twone\)，这里因为的 \(o\) 被 \(one\) 和 \(two\) 都用到了，所以直接删除它就可以了。
在考虑其他情况，对于 \(one\) 可能存在 \(one、oneeee、oooone、oooneeee\)，那么我们可以发现，删掉 \(o\) 或者删掉 \(e\) 都不是很好的选择，但是 \(n\) 确实不能重复出现的，所以只要删掉 \(n\) 就可以了。对于 \(two\) 也是一样的道理，删掉 \(w\) 是最好的。
Let's Play the Words?
\]
把字符串分成四类，分别是 \(0..0、1...1、0...1、1...0\)。
首先可以发现，如果存在一个第 \(3/4\) 类的字符串，第 \(1/2\) 类的字符串都一定能够拼接起来，完全可以忽略掉。如果不存在第 \(3/4\) 类的字符串，那么 \(1/2\) 类的字符串只能独自出现，否则一定拼接不起来。
接下来考虑存在 \(3/4\) 类的字符串，第 \(3\) 类的字符串有 \(n\) 个，第 \(4\) 类的字符串有 \(m\) 个。
假设 \(n>m\)，那么我们只要暴力翻转第 \(3\) 类的字符串变成第 \(4\) 类的字符串，使得 \(abs(n-m)<=1\)，就一定可以拼接起来，对于 \(m>n\) 的情况也是类似，只要翻转第 \(4\) 类的字符串变成第 \(3\) 类的就可以。
为什么这么做可以呢？因为题目保证的一开始给出的字符串都是 \(different\) 的，那么我把第 \(3\) 类的字符串翻转过去，一定不会对其他第 \(3\) 类字符串是否需要翻转造成影响，那么我只要每次贪心翻转就够了。
Two Fairs
\]
对于给出的开始和终止位置 \(s、t\)，我需要找到的是从 \(s\) 出发不经过 \(t\) 可以到达的节点数和从 \(t\) 出发不经过 \(s\) 可以到达的节点数。
对于找从 \(s\) 出发不经过 \(t\) 的节点，可以先 \(dfs\) 一边把从 \(t\) 出发可以到达的节点数标记起来，终止条件为遇到 \(s\) 节点或者无路可走。然后再从 \(s\) 出发看哪些节点是没有被标记过的。这样找出来的节点就一定是满足条件的，第二种同理。
最后的答案就是这两种节点数的乘积。
Beautiful Rectangle
\]
首先发现可以枚举最后矩形的高，如果能够想办法计算出在高固定的情况下，最大可以放的宽是多少。那么枚举所有的高，就可以得到最后应该构造的矩阵是什么样的。
假设高为 \(h\) 且小于宽 \(w\)，那么对于同样的数字，最多只能放 \(h\) 个。所以我们可以计算所有数字出现的次数，那么对于出现次数小于 \(h\) 的数字，可以都取，对于出现次数大于 \(h\) 的，只取其中的 \(h\) 个出来用。这样就得到了最多可以放的元素的个数，也就可以得到对应的 \(w\)。
那么构造的时候，我们只要把每个元素按 \((i,1)、(i+1, 2)、(i+2,3)\) 这样斜着放下去就可以构造出矩阵。
但是我们还要防止一种情况的出现，也就是可用元素有 \(a、b、b、c、c\) 五个，而此时我需要四个，如果我从前往后希望先使用出现次数少的元素，我会拿到 \(a、b、b、c\) 四个，把原本后面的整体拆成前面就应该已经放完的类型，变成
a & b\\
c & b
\end{matrix}
\]
为了防止这种情况，我们可以从后往前取先使用出现次数多的元素来放，使用 \(c、c、b、b\) 放成
c & b\\
b & c
\end{matrix}
\]
这样就算拆开了某一部分，并不会改变这一部分原本应该放的顺序，就可以避免上面的情况。