Closed Wizmann closed 3 years ago
Contest
日常水题，略
Rule可以这样规定。 取最小值的话，把第一个不是01的数位，替换成0或1（取决于是不是第一位）。 取最大值的话，把第一个不是9的数位，替换成9。
这题挺好的，corner case很多，但是每一个都是必须要考虑到的。
把两个字符串都排序，看是否有一个串在所有位置上都大于等于另一个串。
简单的贪心，证明就略吧。
DP好题。
DP的根本意义在于确定正确的归纳假设。但是一个正确的归纳假设有时候并不是最高效的那个。 本题最直接的DP思路是：DP[i][j]，i代表第几个人，j代表现在已经用过了几个帽子（二进制压缩）。这样的问题在于j的取值空间太大了：C(40, 10) > 8 * 10^8。强行用C++搞也没准能过，但一定不是正解。
我们考虑把i和j换过来，即i代表第i个帽子，j代表戴这i个帽子一共有哪些人（已有的帽子可以不戴，使用二进制压缩）。这样i的空间是40（帽子种数），j的空间是2^10（最多10个人）。这样虽然非常反直觉，但是其效率可以大大的提升。
此题为我们提供了一个非常好的DP思路。（CF的DP专题刷起来，笑）
Contest
1431. Kids With the Greatest Number of Candies
日常水题，略
1432. Max Difference You Can Get From Changing an Integer
Rule可以这样规定。 取最小值的话，把第一个不是01的数位，替换成0或1（取决于是不是第一位）。 取最大值的话，把第一个不是9的数位，替换成9。
这题挺好的，corner case很多，但是每一个都是必须要考虑到的。
1433. Check If a String Can Break Another String
把两个字符串都排序，看是否有一个串在所有位置上都大于等于另一个串。
简单的贪心，证明就略吧。
1434. Number of Ways to Wear Different Hats to Each Other
DP好题。
DP的根本意义在于确定正确的归纳假设。但是一个正确的归纳假设有时候并不是最高效的那个。 本题最直接的DP思路是：DP[i][j]，i代表第几个人，j代表现在已经用过了几个帽子（二进制压缩）。这样的问题在于j的取值空间太大了：C(40, 10) > 8 * 10^8。强行用C++搞也没准能过，但一定不是正解。
我们考虑把i和j换过来，即i代表第i个帽子，j代表戴这i个帽子一共有哪些人（已有的帽子可以不戴，使用二进制压缩）。这样i的空间是40（帽子种数），j的空间是2^10（最多10个人）。这样虽然非常反直觉，但是其效率可以大大的提升。
此题为我们提供了一个非常好的DP思路。（CF的DP专题刷起来，笑）
题目打分
一星，垃圾
四星，每次这种小思路+corner case题总是能搞我一把
一星，没新意
五星，DP新思路