5.5\HUGE{5.5}5.5
P1198:
绿
期望耗时:20min
耗时:3h
实际耗时:15min 左右
做法:线段树,板板
代码:
P1775
难度:黄
石子合并弱化,上课学的。直接贴代码
P1122
难度:黄
实际用时:1s(
双倍经验
帮 wcqk 调代码顺手 AC,这里贴 wcqk 代码😋😋😋
P1880
石子合并强化版。
难度:绿
做法:
在弱化版的基础上再在后面加一圈,然后开两个 dpdpdp 数组存最大值最小值,然后就没了。
P6136
难度:蓝
实际用时:10min
思路:
平衡树板子,就加了个强制在线,根据题意修改即可,不难,10min 杀穿,但是之前我 Treap 为啥老被炸。注意有些变量要开 long long。这里选择了速度较快的红黑树实现。
还是跑了 9.5s,太慢了
P2820
刷到十倍经验看见的,MST 板子。
难度:黄
思路:边权总和减去 MST
实际用时:1min
P1669
难度:黄
思路:
最大生成树
总结:
黄+=3
绿+=2
蓝++
5.20\HUGE{5.20}5.20
我的 520 和线段树过。
字面意思,做了一个线段树,只写了一道题我就不管格式了。
思路:单点修改+建树+区间查询的维护最大值的线段树
代码:直接从区间和线段树改过来的,可读性为 000,但是相信这道题不放代码各位也能做对吧。
5.23\HUGE{5.23}5.23
P16597
难度:诈骗题
直接升序排序即可。
代码不放了。
6.6\HUGE{6.6}6.6
P1821
难度:黄
思路:
一个听常用的 trick了算是,建一个正图一个反图然后各跑一边 spfa 就行。注意答案的计算。
代码,马蜂稀烂:
P10491
难度:橙
简单广搜不说。
代码:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8.8\HUGE{8.8}8.8
好久没写了,其实是没有更新而已,一直在做初赛题。
P3009
做了个水 DP 找找感觉,令当前下标为 iii,显然区间 [1,i][1,i][1,i] 的最大子段和为下标为 iii 的数与 i−1i-1i−1 的最大子段和和当前数的最值。所以转移方程为 dpi=max(ai,dpi−1+ai)dp_i=max(a_i,dp_{i-1}+a_i)dpi =max(ai ,dpi−1 +ai )。然后做就行了。
8.9\HUGE 8.98.9
P3252
正难则反,每个节点往上搜,如果可以正好等于 sss 答案加一,如果大于 sss 或到根了结束,否则继续往上搜。
P4058
二分即可,被 __int128 hack 掉了。
8.10\HUGE 8.108.10
洛基俩题,A 水红不讲,B 核弹打蚊子红黑树卡常卡卡过。
树状数组学了