银当taki
银当taki
全部文章
分类
题解(31)
归档
标签
去牛客网
登录
/
注册
银当taki的博客
全部文章
(共29篇)
25暑期第八场
B 逆序对 循环移位 给一个排列,问每次循环移位一个区间后,序列逆序对奇偶性 交经典结论,换两个相邻元素,保证元素不同,逆序对奇偶反转。循环移位这个区间,相当于把移动到左边,其他不变,也就是交换次。根据的奇偶,即可知道操作完,整个序列逆序对的奇偶。 F 状压 枚举 二分 不大,保留灯管的所有情况最...
2025-08-30
0
8
25暑期第七场
C 贪心 每次可以选一个子序列,全部减一。问最少多少次操作可以变成不减。 只能减不能加,那么贪心的想,最后一个元素一定不能减,否则它变小了,可能需要前面的元素减更多次才能保证序列不减。 所以处理完一个后缀之后,一定比后缀里的所有都要小,也就是比小。如果初始,需要减小到,如果本来就比小则不用操作。 最...
2025-08-30
0
7
25暑期第十场
F 双指针 扫描线 线段树 确定两个指针把数组分成三段,求一个方案使得三个集合的交集最大 有两个指针的位置需要确定,显然考虑枚举,然后对每个确定三个集合交集最大的的位置 对于每种元素,想要这个元素出现在交集里,也就是三个集合都有这个元素,如果确定,设这个元素在里最左出现位置是,最右出现是,那么想让三...
2025-08-14
3
37
25暑期第九场
A 树形dp 观察 可以删点,加点,问把一个二叉树变成avl的最少操作次数? avl的要求就是左右子树都是avl树,且左右子树高度差不超过1. 注意到这是个递归定义,可以考虑树形dp,计算出一个点的两个子树变成avl树的最小代价,然后再用这两个一个变成avl的子树,和当前点拼起来,就能计算当前点为根...
2025-08-13
3
26
25暑期第六场
C 计数 dp优化 对一个长度为n的排列跑单调栈,最后栈中剩下的元素个数为, 注意到一个排列增加一个元素,对剩余元素个数的影响时很好分析的,如果给一个长度n的排列增加一个元素n+1,只有在n+1插入到排列的结尾时,单调栈中剩余元素个数才会增加,其余位置元素个数都不变。 增加一个元素,变化可以求,很适...
2025-08-13
0
18
2025暑期第四场
B BFS 思维 网格图上从起点到终点,只能往上下右走,人有一个视野,超出范围的看不到。问是否存在一个死胡同,会误导人走进来 等价于是否存在一个路径,人没走进来时无法确定是不是死路,只有等走进来了才能发现是死路(由于不能往左走,此时已经晚了,游戏失败) 首先需要找到所有死路的点,这可以通过找到所有能...
2025-07-31
1
27
2025暑期第五场
J 二分 多源BFS 切比雪夫距离 01矩阵,最多把一个0变成1,然后每个1每一秒会把曼哈顿距离为1的相邻0变成1,问变成全1的最小时间? 注意到肯定是越早越困难,越晚越容易,答案具有单调性,可以二分变成全1的时间。 从多个源点出发的染色,故check里考虑多源bfs,发现我们从所有1出发bfs,只...
2025-07-30
3
28
2025暑期第三场
D 思维 可以把长度a的连续1变成0,可以把长度a+1的连续0变成1,问最多能得到多少1? 只要有一段长度a的1,我们把他们变成0,然后和两侧的0,肯定可以构成一个长度至少a+1的连续0,然后我们可以把他们再变成1,重复这个操作可以把所有0都变成1 如果开始没有长度a的1,但是有长度a+1的0,可以...
2025-07-23
5
30
2025暑期第二场
A 计数DP 1表示看到白天,0表示看到晚上,-1表示看到不确定。给个序列,问所有把-1变成0或1的方案中,白天天数的和? 首先如果只是求方案数是好求的,但是这里每个方案都有贡献,要求的是所有方案的贡献和。这种一般就维护两个dp数组,一个是贡献和,一个是方案数,方案数正常转移,什么时候能产生贡献了,...
2025-07-23
1
38
2025暑期第一场
2025暑期第一场 G 模拟 数学 给两个01串,问分别从两个位置开始的子串,有多少个子区间完全相同? 注意到这是01串/手玩,可以推出,对于每段相等的最长子区间,长度的话,对答案贡献是 #include <bits/stdc++.h> #define rep(i, a, b) for(...
2025-07-16
4
43
首页
上一页
1
2
3
下一页
末页