2025.8.5

Acwing每日一题 :

1. 图的连通分量 ：注意该题，需要用到一个技巧，即：比方说你对于一个二进制求子集，可以枚举他的任何一个去掉一个1的位置，就这样递归下去，例如: 10011 可分为10010 和 10001 和 10000，然后以此类推进行下去，这样对于很多数的时候（比如都小于10^5时）dfs一下，记忆化，效率会很高

2. 十滴水 首先，该题需要排序，因为pos这位可能是乱序，其次对左右都有的情况，应当优先遍历左边，我们可以写两个if,然后，把l放在最后，这样，l满足条件时，可以覆盖掉r

2025.8.9

DMY 挑战赛Round 24:

1. 发光的数码管 不要被数据蒙蔽了双眼，其实这题很简单，数位DP，对于每个x1x2..xi的一个数，他其实会进行x1x2...xi-1轮0到1,1到2,... 9到0, 剩下的就是0到1,1到2,...,2到xi, 对于每一位都进行加一下,最后结果是f(r) - f(l);

2. 成环概率 注意该题,你的分母应该为\sum_{i = 1}^n dp[n][i] ,即n生成所有环的方案数的综合

2025.8.15

DMY:

1. 区间和 对于这种，我其实可以发现，看似一个区间问题，其实我们可以分别算他们的贡献，就行了

2025.8.19

CF:

1. Edu R20 E : 额，这道题DP！设DPi,j表示第i个位置，差为j的情况，当然，j 可以为负数，所以加上n,这题搜索记忆化也可以搞定,也更好写

2. Edu R6 D : 额，这道题注意到K其实很小，所以枚举一下，k = 0, k = 1暴力, k = 2,我们观察一下其实发现最后为sa - sb + 2 * (b_i+b_j) - 2 * (a_i + a_j), 所以我们预先处理出2*（a[i] + a[j]）的所有值， 然后最求前面的，即可

3. Edu R12 E ： 额这道题，注意要找一个区间>=k <=> qz[l] ^ qz[r - 1] >= k, 所以我们只用把所有的前缀异或值放入trie树里即可