2020-2021:teams:too_low:cf643_tj_cy
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:too_low:cf643_tj_cy [2020/05/23 03:04] member 创建 |
2020-2021:teams:too_low:cf643_tj_cy [2020/05/23 03:07] (当前版本) member |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== CF #643 (div2) ====== | ====== CF #643 (div2) ====== | ||
| + | cy | ||
| ==== A. Sequence with Digits ==== | ==== A. Sequence with Digits ==== | ||
| 行 6: | 行 7: | ||
| **题解**：刚开始的时候没想出什么好办法，想到了如果对于其中某一项，MinDig为0，则后面都是0,但这一项是否一定会出现呢？是否有一种构造使其永远不会出现0？不存在的，我们发现，每一项比前一项最多大$9*9=81$，现在考虑$[1000*(a_i/1000+1),1000*(a_i/1000+1)+99]$这一段区间，显然这段区间所有的数字都含有0这个数位，并且这段区间长度大于81，也就是说，$a_n$只要存在大于这个区间的值，就一定会有一项落到这个区间内，其必含有0，所以可以直接暴力计算$a_1,a_2$… | **题解**：刚开始的时候没想出什么好办法，想到了如果对于其中某一项，MinDig为0，则后面都是0,但这一项是否一定会出现呢？是否有一种构造使其永远不会出现0？不存在的，我们发现，每一项比前一项最多大$9*9=81$，现在考虑$[1000*(a_i/1000+1),1000*(a_i/1000+1)+99]$这一段区间，显然这段区间所有的数字都含有0这个数位，并且这段区间长度大于81，也就是说，$a_n$只要存在大于这个区间的值，就一定会有一项落到这个区间内，其必含有0，所以可以直接暴力计算$a_1,a_2$… | ||
| + | <hidden> | ||
| <code cpp> | <code cpp> | ||
| #include <iostream> | #include <iostream> | ||
| 行 42: | 行 43: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| ==== B. Young Explorers ==== | ==== B. Young Explorers ==== | ||
| **题解**：直接贪心，没啥好说的 | **题解**：直接贪心，没啥好说的 | ||
| + | <hidden> | ||
| <code cpp> | <code cpp> | ||
| #include <iostream> | #include <iostream> | ||
| 行 79: | 行 81: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | </code> | + | |
| + | </code></hidden> | ||
| ==== C. Count Triangles ==== | ==== C. Count Triangles ==== | ||
| 行 85: | 行 88: | ||
| **题解**：做的时候脑子不清醒，想错了，分了8类讨论。。。这题官方题解的方法非常好。 用一个大数组$A_i$来表示$x+y=i$的个数，计算数组$A$时，可以枚举x的值，然后用前缀和的方式来计算区间加法，然后对数组A再来一次前缀和，就能求出$x+y<=i$的个数，最后累加C到D之间的答案即可。 | **题解**：做的时候脑子不清醒，想错了，分了8类讨论。。。这题官方题解的方法非常好。 用一个大数组$A_i$来表示$x+y=i$的个数，计算数组$A$时，可以枚举x的值，然后用前缀和的方式来计算区间加法，然后对数组A再来一次前缀和，就能求出$x+y<=i$的个数，最后累加C到D之间的答案即可。 | ||
| + | <hidden> | ||
| <code cpp> | <code cpp> | ||
| #include <iostream> | #include <iostream> | ||
| 行 113: | 行 116: | ||
| cout << ans; | cout << ans; | ||
| } | } | ||
| - | </code> | + | |
| + | </code></hidden> | ||
| ==== D. Game With Array ==== | ==== D. Game With Array ==== | ||
| **题解**：这题很容易构造出来，条件放的太宽了。 | **题解**：这题很容易构造出来，条件放的太宽了。 | ||
| + | <hidden> | ||
| <code cpp> | <code cpp> | ||
| #include <iostream> | #include <iostream> | ||
| 行 145: | 行 149: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | </code> | + | |
| + | </code></hidden> | ||
| ==== E. Restorer Distance ==== | ==== E. Restorer Distance ==== | ||
| 行 151: | 行 156: | ||
| **题解**：如果有一个给定的h，那么最终花费很好求，只要求一个前缀和然后二分查找即可。问题在于这个h如何去确定，官方题解给出的答案是，先假设一个h，再给h增加1，观察最终花费的变化，最终发现，最优答案的h一定和某个柱子的砖块数量一样，或者是在均值附近，于是可以nlogn枚举答案，还有一种思路，发现最终答案和h的大小呈二次函数关系，于是三分。 | **题解**：如果有一个给定的h，那么最终花费很好求，只要求一个前缀和然后二分查找即可。问题在于这个h如何去确定，官方题解给出的答案是，先假设一个h，再给h增加1，观察最终花费的变化，最终发现，最优答案的h一定和某个柱子的砖块数量一样，或者是在均值附近，于是可以nlogn枚举答案，还有一种思路，发现最终答案和h的大小呈二次函数关系，于是三分。 | ||
| + | <hidden> | ||
| <code cpp> | <code cpp> | ||
| #include <iostream> | #include <iostream> | ||
| 行 197: | 行 202: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | <hidden> | ||
| <code cpp> | <code cpp> | ||
| #include <iostream> | #include <iostream> | ||
| 行 252: | 行 259: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
2020-2021/teams/too_low/cf643_tj_cy.1590174292.txt.gz · 最后更改: 2020/05/23 03:04 由 member
