Diary Ⅱ

上一篇博客太长了，重新开一篇

待解决：
1.图论的总结
2.区间dp和树形dp
3.斜率优化dp
4.二次元冒险的最短路做法+复杂度分析

2019/10/22

上午考试
中午+下午改题
晚上联赛真题
（如果任务完成了，晚上回家看会儿书呗）
期间自己找时间完成【待解决4】

上午考试：
T1 WOJ#4759 100pts
T2 WOJ#4760 30pts
T3 WOJ#4761 0pts
Total：130pts
最高：200pts

我太nan了……
如果Day1只能拿130，两天最多260.连一等都没有啊。
所以，我的猪猪，要加油ヾ(◍°∇°◍)ﾉﾞ
认真去做
脑子不够刷题凑

T1 三分
证明一波下凸函数即可
（斜率单调不减）

T2 数据结构
算法一：将题目转化一下，也就是统计大于等于当前海平面的点数，然后再统计相邻的情况
两个树状数组就可以了
有些时候信息不能一次性维护完，那我们就分开维护不就好了吗
算法二： 考虑维护每个连续的段，我们都在其最左边统计。也就是统计满足a[i]<h&&a[i+1]>=h的位置

一个感觉很有用的东西
统计一个序列中满足a[i]<h&&a[i+1]>=h的数个数
常规思路：对于每一个h，O(n)扫一遍
但如果数据组数很多，显然不可以
转化一下思路，看每个a[i]会对哪些h造成贡献
显然$a[i]+1$~$a[i+1]$这个区间内的h都满足条件
随便一个数据结构维护一下即可

T3
CE？掉了20pts
注意关键字冲突（不要用random）

其实这道题数据范围给的很妙啊。但我实在是辜负了出题人的好心，并没有理解到。
第二个数据范围$n<=5,m<=1e6$
难道不觉得很奇怪吗？点数如此之少，而边数竟然那么多。
说明实际上有用的边也很少–>连接两点的多的边方向互异，可以忽略
正解真的很妙！
不断地缩小边的数量，直到最后有n个点，n/2条边
然后再返回去一步一步倒推出答案
异或大法好%%%%%%

CF547D（T3的延展）

19:00~20:20 NOIP2014 寻找道路
w(ﾟДﾟ)w我没了……
啊啊啊啊啊啊啊啊啊，又错sb题！！！
（不不不，这不能算是sb题，应该是自己思维上的漏洞）
检验每个点是否能够到达终点，就以终点为起点建一个反图，然后跑bfs
至于我yy的那个从起点跑dfs，是有问题的
比如说

如果我先遍历到2，然后到达3，再到1
那么3就不会被标记为能到达终点（因为1已经被遍历过，但尚未到达终点）

吼吼吼，早上水了两道NOIPDay1T1
那今天算不算完成了三道NOIP真题呢？
差不多能算吧。再加一道#1228 解方程
然后敲一下CF547D啦

20：45~21：49 CF547D
这个转化真是妙不可言
而且作为弱化版的2019/10/22T3
值得一做

2019/10/23

今天练习……
（是的，不是考试）
T1 WOJ#4053 目录 78pts
T2 WOJ#4051 测试 30pts
T3 0pts
T4 24pts
Total: 132pts
最高：296pts

T1 模拟
细节较多
！！！！数组开小见祖宗！！！！

T2 拆绝对值
我真是太瓜了……
想到正解，但是没有去证明正确性，就只打了暴力
明明很好证的好吧！！！！
以后考试还是要自己动脑证明一下（不能习惯性地不证）

T3 单调栈
这个做法遇到过很多遍了……
怎么还是做不出来
两行压一行
确定上下界
矩形通常可以将其抽象为两组平行的线段
枚举一个矩形，一般而言都是n⁴，考虑降低复杂度，只确定两个，剩下的根据题意思考更nb的做法
（所以暴力的二维ST表是真的细节多。+1-1很恼火）

T4
不应该受别人影响。。
看到神仙弃了T4，我也跟着去gangT3
结果T3没做出来，T4也没看
好在-1有分……不然就真的凉了
考后才发现T4明显好做的多

随便乱搞啊。改题的时候dfs写挂了都还有50+
枚举一波骚整

要有自己的节奏，不能受别人影响

今天上午写了一下解方程
NOIP2014都是什么玩意儿啊。
Day2T3取模就完事儿（当然还是要卡卡常）
取模是有可能冲突的
也就是说如果原式子代入x后不等于0
但是取模后就有可能了
只是冲突的可能性比较小

当然如果没有想到取模也就完了
总结：一般遇到很大很大的数，记得取模！！！
取模：加减乘都可以
（除的话用逆元）

2019/10/24

咦？昨天写的又没保存起？
无所谓。

WOJ#1809 花匠
简单dp
一开始理解错题意了
两个条件只能满足其一（注意每个条件都是对所有的2*i成立呀）
···update 2019/10/25···
并不能用单调队列优化
因为高度不具有单调性，前面弹掉的东西可能会对后面造成影响
数据大水。

今天考试
（考完讨论，感觉大家都很稳……
就我一个人T1gang太久，还不能保证A。T2T3只会暴力，而且T3还打挂）
等待成绩ing

T1 80pts
T2 10pts
T3 15pts
Total:105pts
最高：215pts

T1
找到的子树size不一定是最小的那个！
主要写太久T1，到后面越写越绕，代码冗长

T2
dp？？
n³dp还是比较好想吧。
$[i,j]$表示i~j这个区间内算式的最大值
枚举最后一次被计算的运算符k
划分成两个子问题
（和之前做的那两道区间dp有啥子不一样吗？？！！）
模型的转化和应用
为什么在知道某一题正解为dp的时候可以想出来，其他情况就不敢想呢？反思！
注意性质：
括号嵌套的最大层数不需要超过 2
然后就可以优化到O（n）了
$f[i][0/1/2]$ 0，1，2分别表示i之前有几个未匹配的括号

考场推性质！！！

T3
考场推性质！！！
性质1：x单调递增，不走回头路
性质2：矩阵可以退化为线段，且只有左边上下端点有用

晚自习任务：
今天T2 \/
复习同余方程组\/
NOIp两道真题

2019/10/25

WOJ#1810 华容道
真的好题啊。。
我爱图论QwQ
1.复杂度 2.dfs

dp专题训练
我爱dpQwQ

1. dp比赛中剩下的题回顾做法
   （因为都是以前做过的，就不用写代码了。重在思想）
   填数游戏+保卫王国
2. 华容道问题解决×
3. 曾老的概率期望题单×

又复习了一下扩展欧几里得求同余方程组

刷了一天的dp
总结一下吧

Problem 愤怒的小鸟 只用一维？
emmm……好吧其实是可以的
只是我改挂了……

2019/10/26

晚上任务：

1. 今天考试的T2，T3
2. 扫描线的SOJ上那道题
3. 今天考试总结
4. 明天学习计划

实际上只改完了T2
我……欸，加油吧姑娘

补总结
考试
T1 100pts
T2 30pts
T3 40pts
Total：170pts
最高：230pts

T1 送分题
打表找规律。走n步的期望步数就是n
（一开始不相信有这么简单，还以为自己深搜挂了。硬生生耗了1h）
当然考后还是需要严谨的证明
考虑多走一步后期望的改变
当前的期望值假定为$x^2+y^2$
一步之后分别有四分之一的概率为
$(x+1{)}^2+y^2$
$(x-1{)}^2+y^2$
$x^2+(y+1{)}^2$
$x^2+(y-1{)}^2$
展开后相加即为 $s^2+y^2+1$

T2 树上差分好题
暴力还是很好做

由于这道题的限制，我们需要同时处理两棵树的信息（代码实现的时候记得封装）
在B树上差分，在C树上单点修改，链求和（代码实现时转化为子树加，单点求值）
其实本质上，B树上的差分相当于操作----告诉C树应该怎么做

T3 倍增
暴力还是很好做
一开始理解错题意。。并不理解那个字符串比较
不然应该有时间想更多的暴力分
字符串比较并不是优先看长度啊！
按位比较

感觉知道正解后，也不是很难
但就是想不到
而且不会分析复杂度（所以就不会自己构造重儿子）

其实整场考试也就只有大众分
正解想不出来，只会打暴力
差距还是很大……
加油努力吧

2019/10/27

10：00~11：00 考试T3
10：50完成
11：00~12：00 扫描线
12：00~12：30 昨天考试总结+题解
12：30~13：00 午饭
11:30~11:47 没有管理好自己，【颓】
12：00~12：15 吃饭
12：15~12：35 扫描线做完
12：35~13：10 考试总结
13：00~13：30 英语读报
13：35 完成
13：30~14：00 午休
14：55 起床。。。完全不能抵抗温暖的床的诱惑，冬天简直就想生根在床上/笑
事实上闹钟14：00就响了，但是我依然酣睡如猪( ¯(∞)¯）
下午得抓紧时间了啊！！！
14：00~15：00 斜率优化dp
完全出乎我的意料。。不知是斜率优化dp太难，还是我太笨，还是周末效率太低
反正15：00~18：00一直在弄这个玩意儿。。【我没了】
18：00~20：00 实在是效率太低，吃完晚饭后出去洗了个头（也许是为了换个脑子？）
20：00~21：00 开了一道斜率优化dp，想看看自己一下午到底有没有学到什么。。方程倒是推出来了，但是一上斜率优化就gg。。果然还是太笨了
15：00~16：00 概率期望dp
16：00~17：00 dp杂题
17：00~18：00 dp总结+下周学习安排
18：00~19：00 晚饭+休息
19：00~22：00 ldx给的题单
22：00 跑步