最后的日记

· · 个人记录

- P2448 【无尽的生命】

对于有相同性质的连续的数，我们可以把它们合并成一个数，那样就可以节省空间了，也不用超时了

- P3149【排序】

下次可不要再对着这种题（这种出错了的题）死磕了，你忘了你csp是怎么没的吗。

终于学会了分析题目了，再接再厉，有些时候我们要从正反两面去思考问题，也许会有不一样的收获。

- P6040【课后期末考试滑溜滑溜补习班】

嗯，对单调队列理解更深了一些，用不用单队看方程，什么时候出队，什么时候进队也都看方程，嗯，加油！

- 启发式合并：

- CF600E 【Lomsat gelral】

- U41492 [树上数颜色]

要点： 要搜轻儿子，不记录，最后搜重儿子，记录，再搜轻儿子维护重儿子的信息向上合并（本质为优化后的暴力）

//dush为暴力搜索的代码
void dush(int u,int f,int val,int x=0){
    mp[dep[u]][c[u]]+=val*d[u];
    //暴力 维护 信息
    tu(u){
        vv;
        if(v!=f&&v!=x) dush(v,u,val,x);
        // 重儿子 节点的子树 不搜（其信息存在，并未撤销）
    }
}
// dfs2用来 遍历每个节点
void dfs2(int u,int  f,int is){
    tu(u){
        vv;
        if(v!=f&&v!=son[u]) dfs2(v,u,0);
    }
    //都先搜 轻儿子
    if(son[u]) dfs2(son[u],u,1);
    //然后搜重儿子
    dush(u,f,1,son[u]); 
    // dush准备 暴搜信息 向上合并
    for(int i=qhd[u];i;i=q[i].nt)
        ans[q[i].id]=mp[q[i].dep][q[i].col];
    // 用信息 记录答案
    if(!is) dush(u,f,-1);
    // 若 该节点 为 轻节点 则 信息 回溯（撤销）
}

- P6041 【ACOI2020】布丁暗杀计划

map与hash_table

1. map是所有哈希里最稳定的，增删改查什么的都是log

2. hash_table 的查询 是 O（1） 的 挺快的

3. 并没怎么搞懂原理，反正有这么个东西 有点快，当然也有缺点

#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table <int,int>g;
cc_hash_table <int,int>c;
//cc应该会更快 更稳一些。。。

看不太懂，关于头文件，可以去我的电脑 搜索 pbds 也可以 强记

- CF570D Tree Requests

莫队算法：

一个叫做莫涛的大神发明的一种极致优化美丽的暴力算法

应用范围：

斜率优化：

what：单调性优化的一种特殊情况

how：yy(j)=kk(i)xx(j)+zz(i) 写通式然后根据线性规划的知识o(1)转移

目前见到的题目：

- 模板

- P【2900】土地征用对于有两个属性的，先排序，再删除个别没用的元素，然后就是一个x递增y单减的序列就可以优化了

- P【5785】任务安排对于有些题目目标斜率不单调，维护凸包然后二分即可

DP的各种优化：关于DP的各种优化

网络流：加油