写了棵可持久化线段树，因为模拟赛里用到了主席树，而我却从来没写过。。。 凭借自己对当年上过的课的印象写的，因为翻了很多博客没看懂 概述 每当有修改操作时，把需要修改的节点复制一份，在新复制的节点上完成修改操作。这里的修改也包括对点与点连接结构的修改。然后将每个版本的根节点存入root数组。 结构 这棵线段树需要动态开点，所以要有struct 12345struct node {...

hdu 2196 Computer 树形dp，贼鸡儿难 题目 传送门 给你一棵有边权的树，求每个点到离它最远的点的距离 输入： ? 一个n ? 接下来n行每行两个整数j,w，其中第i行表示从(i+1)到j有一条权值为w的边 为什么我要把输入放在这里，因为我最开始看错了。。。 解法 首先把1（或者其他点）作为根。 一个节点的最远距离就可以从它的儿子里面或者父亲里面找 所以只要取他“儿子...

没卵用的卡常实验 想起有人说，三目运算符比if-else慢， 也有人说，加了inline其实会更慢 那么，来做个实验吧。 （好智障的实验我都不好意思放上来） 准备 三种方式写的“函数”。因为我太蒟了，所以用了最简单的max 1#define max(a, b) ((a) > (b) ? (a) : (b)) 1234int max (int a, int b) { ...

Too Young 今天做了一套模拟题，成功爆20。 这套题出题人全程暴力%，今朝笑话讲的好，——。 但我笑着笑着就笑不出来了。 然后就爆20了 。 在众多毒瘤题的包围下来一套简单的小水题，可以愉悦身心、增加信心… 这么简单地一套题相信大家都已经轻松AK了，不过CSP-S可就不一定也这么水了，希望大家在CSP-S的第一年也能RP++，虐场快乐 ——出题人 我：？ 这是第一题，后两道...

1024程序员日考试总结 大过节的，考什么试啊 今天的题在洛谷上都能找到，所以就不放题面了。。 数学题（math 1S 128M） P3123 贝茜说哞Bessie Goes Moo 提交的时候电子教室卡死，拿u盘拷上去math.cpp又变成了乱码。。。虽然只写了30分 首先，这道题直接枚举的复杂度是5007500^75007，是过不了的。 而因为余数可加、可乘的性质，所以只要统计除以...

状压dp入门 状态压缩嘛，就是把连续的一坨可以用01表示的状态，搞进个整数里，然后用位运算来进行检查、转移等操作。 例题 [SCOI2005]互不侵犯 每行国王分布的情况可以用01表示，这样就可以把每一行的状态用一个整数表示。 先预处理出一行里面没有会打架的的所有情况，和该情况对应的国王数量 f[i][j][k]为第i行的状态为第j种时，一共用了k个国王的方案数 那么f[i][j][k...

N0lP 2018 货币系统 划水一周就写了个这玩意儿？ 题目 传送门 货币种数为 nnn、面额数组为 a[1..n]a[1..n]a[1..n]的货币系统记作 (n,a)(n,a)(n,a)。 两个货币系统$ (n,a)$ 和$ (m,b)是等价的，当且仅当对于任意非负整数是等价的，当且仅当对于任意非负整数是等价的，当且仅当对于任意非负整数x$，它要么均可以被两个货币系统表出，要么不...

经过了一周的划水，我终于搞懂了cdq分治。 总的来说，cdq分治处理偏序问题就是 先把左边和右边当成一个完整的问题处理 然后把左边对右边的影响合并到右边 例题 园丁的烦恼 传送门 求静态区域内的点数，二维偏序模板题。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546...

Dijkstra嘛，就是每次从最短路未固定的点中找到已知最短路最短的点，然后将它固定，并更新这个点连接的其他点的最短路。最开始时，源点到源点的最短路为0。 所以，复习了一遍Dijkstra然后发现了几个函数 make_heap (first, last, comp) : 把一个数组搞成一个堆 push_heap (first, last, comp) : 让数组末尾的数浮到堆中正确的位置...

强连通分量 染色为搜索树根节点编号： 12345678910111213141516171819202122232425void tarjan (int p) { dfn[p] = low[p] = ++tim; v[p] = 1; s.push(p); for (int i = head[p]; i; i = e[i].nex) { ...