虚假的每日总结

[Wizmann]

我是傻逼

[Wizmann]

2021/01/01

题目列表

• Leetcode 909-Snakes and Ladders
• Luogu P7108 移花接木
• Luogu P7107 天选之人
• Luogu P7109 滴水不漏
• AtCoder F - Distributing Integers
  • 同类问题：CF 1187E. Tree Painting

感想与心得

1. DP不要莽，要同时考虑状态数与状态转移数。合理规划空间与时间复杂度 （AtCoder F - Distributing Integers）
2. 区分BFS与DFS的使用场景，不要把简单问题复杂化 （Leetcode 909-Snakes and Ladders）
3. 正确使用递推公式，并且学会从不同的角度尝试（Luogu P7109 滴水不漏，Luogu P7108 移花接木）
4. 不要使用随机算法，除非明确了解可以成功骗分（Luogu P7109 滴水不漏）
5. 考虑问题要全面，阻断所有可能的意外问题（Luogu P7107 天选之人）

[Wizmann]

2021/02/01

凑数的心得

1. 做简单题的时候，还是要想好了再做。一来节省出题时间，减少WA的次数；二来可以减少在纸上写代码时蒙逼的次数，因为纸上写代码不容易直接进行调试。

[Wizmann]

2021/05/08

回顾

• CodeForces 507E - Breaking Good
  通过列式+计算，找到变量与不变量，从而找到核心的变量来解决问题。

[Wizmann]

2023/10/19

什么垂死病中惊坐起

• P1019 [NOIP2000 提高组] 单词接龙
  题目有问题，数据比较水，用DFS/BFS硬过了就行了。时间复杂度上限大概是O(3^N * N）左右，搞一组强数据肯定挂。

• LC 2903. Find Indices With Index and Value Difference I
  暴力

• LC 2904. Shortest and Lexicographically Smallest Beautiful String
  暴力，优化个屁，能过不就完了

• LC 2905. Find Indices With Index and Value Difference II
  其实可以倒着O(n)来做，但是multiset也不是不能过题。O(nlogn)又有什么错呢？

• LC 2906. Construct Product Matrix
  模12345是什么玩意。一脑子乘法逆元，结果只能靠分块硬搞。为啥没想到prefix/suffix呢。。。
  讲究的就是一个力大砖飞，乱调参数，过了就是对了（什么鬼）。
  虽然我技术差，但是我力气大啊（

[Wizmann]

2023/10/20

• P1022 [NOIP2000 普及组] 计算器的改良
  坑：-1e9用print打出来是-0.000

• P1040 [NOIP2003 提高组] 加分二叉树
  日常DP瞎搞
  正常写法是dp[i][j] = { max_value, root }。但是遍历两次找最大值又不是不行。。。

• LC2899. Last Visited Integers
  傻逼题

• LC2902. Count of Sub-Multisets With Bounded Sum
  我是傻逼。
  想用DFS硬卡过去，未果。（卡不过去，怎么想都卡不过去吧。）
  然后想转成二进制压缩背包来做，但其实二进制压缩不适用于计数问题。
  看了题解（对不起我有罪）发现用正常DP思路，再套一个区间和优化可以做到O(n * logn)。这也确实补充了某一种特定背包问题的解法。可以归成经典题了。
  其实做题之前把DP公式写一写，思路会明确很多。但是对于Leetcode，这值得吗？（

所以靠肌肉记忆只能在1600分左右混了。还是得把脑子调动起来。
我是傻逼。

[Wizmann]

2023/10/21

• P1069 [NOIP2009 普及组] 细胞分裂
  日常题目，没有难度

[Wizmann]

2023/10/23

• projecteuler 79 - Passcode Derivation
  谜底就在谜面上，通过手算得出答案。。。=。=
  这大概就是题目风格的差异叭（

• LC2841. Maximum Sum of Almost Unique Subarray
  随便做道题凑数，又是一些前缀和问题

[Wizmann]

2023/10/26

• projecteuler 80 - Square Root Digital Expansion

大数开根号。可以用Python快速逃课，见51nod-1166的解法。（不过51nod好卡啊）

对于有内建大整数支持的语言（如Java，Python，golang等），可以使用二分。将x^2==a两边乘10'000，即可得到(100x)^2==10000a，方便获得x的前100位有效数字。

还可以使用牛顿迭代法加速，可以更快速的获得解。传说与泰勒展开相关，但是限制我数学知识的是左脑和右脑（以及泰勒是谁徒弟？

[Wizmann]

23/10/29

• Luogu P1128 [HNOI2001] 求正整数

最近命犯大数（指BigInteger）
并且处于“这题用DFS不是随便过？” 和 ”这题用DFS怎么TMD能过“的叠加态

此题的关键在于看透”不能贪心“的本质，以及打破”用优雅的数学方法直接得到答案“的幻想，直接进入DFS搜索的阶段。

根据数据规模得知，要求的数最多有50000个因子（记作n）。所以其最多有16个质因子（我们将此数记为m），质因子的指数乘积等于n。这里拍脑袋预估时间/空间复杂度为O(m)。

因为解的空间很少，所以我们可以用DFS暴力搜索。这里有一个小技巧，a1^b1 * a2^b2可以转化为b1 * log(a1) + b2 * log(a2)，在精度不高的情况下比较两个大数的大小。

最后我们将a1^b1 + a2^b2 ... 表示的大数打印出来，即得到最终解。

• Luogu P1108 低价购买

LIS变种，让我想起了令人闻风丧胆（其实只有我自己）的北大题。。。

第一问是简单的LIS，经典模型。第二问求有多少种不同的LIS，使用以下方法进行DP转移即可：

nums[i] -> 股票的价格
dp[i][j] -> 截止到第i天，以价格j为最后一个数的LIS的 { 长度， 个数 }

if dp[i][j].长度 == dp[i + 1][j].长度:
    dp[i + 1][j].长度 -= dp[i][j].长度

例如{ 4, 2, 2 }，这样做可以将2个{4, 2}记做同一个，从而得出正确的答案。

• Luogu P1052 [NOIP2005 提高组] 过河

小数据范围是一道非常典型的DP题，难度相当于Leetcode Medium。但是大数据需要额外的考虑。

比较直观的做法是离散化，对于距离比较近的点，直接使用+delta（s <= delta <= t）的方法尝试转移。对于比较远的点，使用数学方法判断是否可达。

方法1（愚蠢的方法，实现起来坑比较多）：

dis：两个点的距离
s, t：可以移动的距离区间

u = dis / s
if u * t >= dis: then 可达
else: 不可达

注：当前点和目标点之前不能经过有石块的点，否则不能保证移动时不踩到有石头的点。

方法2（数学含量更高的方法，实现起来应该比较简单（但是我没有写））：

易知（这句最不是人话），在dis >= lcm(s, t)时，当前点到目标点一定可达。所以对于dis >= lcm(s, t)的点，我们可以将其距离视作dis % lcm(s, t)。

于是我们可以试图将L <= 1e9压缩到L <= 10000左右，这对于实现的比较好的DP来说，O(n^2)是可以接收的时间复杂度了。

[Wizmann]

23/11/04

• Leetcode 2900. Longest Unequal Adjacent Groups Subsequence I

傻逼题，明明没有难度还在题意里放坑。鄙视。

• Leetcode 2894. Divisible and Non-divisible Sums Difference

略

• Leetcode 2895. Minimum Processing Time

纯贪心

• Leetcode 2896. Apply Operations to Make Two Strings Equal

DP。将两个数进行异或，目标是把所有的1消成0。方案有两种，一是用代价x强行把两个1变成0；二是把两个相邻的1变成0（e.g. 1001 -> 0101 -> 0011 -> 0000），代价是两个1之间的距离。

转移以下状态：

• 当前位置
• 当前（除了临近的最近的1）有几个1没有被消去
• 临近的最近的1是否被消去

之后可以考虑使用DP或者记忆化DFS来做。

• Leetcode 2897. Apply Operations on Array to Maximize Sum of Squares

精妙的题目与粪题其实并没有本质区别，想的出来就是精妙的题目，想不出来就是粪题

首先易得我们可以将大数放到数组的前部，把小数放到后部。因为大数的平方一定比小数大，并且小数之间的AND/OR一定不优于大数。

这道题有一个非常隐含的结论。我们可以使用任意次的AND/OR操作，将小数中的1 bit，转移到大数当中。

Num1	Num2	New Num1	New Num2
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

这样我们就可以尽可能将所有的1转移到最大数，次大数...直到第k大数。所以此题就转换为一道贪心题目了。