pinkyHead's blog

模板 洛谷 P4719 【模板】动态 DP 因为要动态维护树上的DP方程，所以很容易想到利用树链剖分进行优化。进而考虑使用重链的性质来化简DP过程的复杂度。这里将重链和轻链的对DP的贡献分开考虑，从而使用广义矩阵乘法，使DP过程得以在线段树上实现。 证明广义矩阵乘法的结合律 因为max，+，*都满足结合律和交换律，并且*对+有分配律，+对max也有分配律。我们将max和+分别看成*和+，和证明普通矩阵乘法的方法一样，把计算的每一项都展开即可。然后可发现对于矩阵A,B,CA,B,CA,B,C做广义矩阵乘法，满足(AB)C=A(BC)(AB)C=A(BC)(AB)C=A(BC) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410 ...

最近感觉越学越菜了… 一 蓝桥大题就出了两个，填空题就对了三个。大题里一个博弈，一个DP，全都差一点出，欸。感觉DP还是做太少了，本来DP状态都想好了，写法也明确了，就是具体写式子的时候出差错，菜的一匹。填空题更啥b，下午回去把错的题代码重写了一下，结果居然就和标准答案一样了，都搞不懂当时我是咋写错的。最后一个状压我也没写，当时写了个暴力跑不出来就跳了，如果知道第一时间反应过来是dp也能做的吧，欸。 二 天梯赛也是难顶，三个多小时，断线重连了十次 第一个题看都没看。第二个贪心还没想到，还以为这道题是Trie+DP（因为才补了一道Trie上矩阵快速幂加速DP的题）。其实写暴力也能过，但暴力写错了，忘记了首尾连接处要重合起来。 前面也是，字符串和STL的两道题卡了贼久…字符串相关的库函数不会用，map的hash也不会写 最后两百分草草收场，L3爆零了… 三 是怎么回事呢，明明每天都在做着自己喜欢的事情，明明每天都有一点进步，但是结果却是这样不尽如人意。 最近的cf一场没落，甚至还开了许多virtual contest。但我的rating居然不增返降，欸。 逐渐发现自己的实力其实并没有 ...

重链剖分 概述 由于重链剖分时，从根节点到叶子节点经过的重链数量必定小于等于lognlognlogn这一量级，故可以通过对每一条重链进行维护和求解得到最终答案。 只要经过了重链的某一个节点，就算是经过了该重链 一般来说，可以结合线段树维护dfs序，再通过类似于找LCA的方式向上跳，只不过这里向上跳是跳到该重链最上面的端点。然后在跳的过程中利用线段树对经过的每一条重链进行查询，对于每一次查询在log2nlog^2 nlog2n的复杂度求出答案。 例题 「SDOI2014」旅行 由于有多个不同类型的点，对于每个种类的点我们都要开一颗线段树。但是由于点的种类能达到10510^5105之多，故不能像以往那样每次都直接建立出一个大小为nlognnlognnlogn的线段树。这里在建树时，我们只能一个一个地加点，并且加点时只需要开辟根节点到该节点这条路径上的点即可（每次要存储lognlognlogn个点）。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950 ...

问题模型 给定一个有n个元素的数列a，其中第i个元素是aia_iai​ 。 求一个较短或最短的数列b，假设b有m个元素，那么要求满足∀m<i≤n,ai=∑j=1mai−jbj\forall m<i\leq n, a_i = \sum_{j=1}^m a_{i-j} b_j∀m<i≤n,ai​=∑j=1m​ai−j​bj​ 要求在O(n2)O(n^2)O(n2)的时间复杂度内解决此问题 Berlekamp_Massey 假设递推式经过c次更新，第i次更新后递推式为R[i]R[i]R[i]。初始时，定义R[0]R[0]R[0]为空。 假设当前递推式的长度为m，这时候考虑用递推式去算a[i]a[i]a[i]是否成立 设deltai=ai−∑j=1mai−jR[c][j]delta_i = a_i - \sum_{j=1}^m a_{i-j} R[c][j]deltai​=ai​−∑j=1m​ai−j​R[c][j] 如果deltai=0delta_i=0deltai​=0，那么R[c]R[c]R[c]依然合法，不用修改 否则，设failc=ifail_c=ifailc​ ...

因为服务器到期，已经好久好久没有更新博客了，哭了 阿里云太奇葩了，学生优惠只能买一年的服务器，但是续费的话就没优惠了 😦 但是更扯的是，虽然续费没有优惠，但是买新的服务器却还是可以的有优惠的不得不说这政策是真的啥b 所以又花了一番功夫才又把数据搬到这个新的服务器上面，期间又遇到了一些奇奇怪怪的坑。还是总结一下叭，希望以后换的时候就没这么恼火了 教程 带你跳过各种坑，一次性把 Hexo 博客部署到自己的服务器 大致内容就是这些，下面是一些需要注意的地方 注意熟悉vim的使用方法，例如进入编辑模式（按’i‘），退出（’按esc‘），保存并退出（按’：wq’），退出不保存（按’:q!’） 阿里云会默认占用80端口，所以会导致nginx运行不了，这时候要先执行命令杀死占用80端口的进程 1sudo fuser -k 80/tcp 修改nginx的配置文件时，一定要注意把要修改的内容前面的’＃‘删去（不然就相当于把它注释掉了，所以就会改了个寂寞我就是这里卡了好久，眼睛瞎没看到user root前面有个#，麻了） 如果重置了服务器，这时候本地的连接可能会出问题（没出现连接 ...

回顾 总的来说，这一学期过得还是挺惬意的。 想翘的课就翘，作业也是想做才做，实在不行就抄了了事。虽然最后期末考试栽了，但也算是意料之中吧。 经过一年半的大学生活，慢慢地成“老油条”了，并不会像刚开始那样各种不适应，心态什么的慢慢地调整过来了一些，也算是找到了自己的状态。 这学期找了位电吉他老师，感觉有人带着确实比自学轻松多了（笑）。老师也是玩乐队的呢，不知道我未来两年多的大学生活，是否也会有机会去组个乐队啥的。如果真的有这回事了，也许也是ICPC拿金之后了叭（又一个flag）。 现在的我，似乎比以前坚定了不少，又不知不觉又成长了许多呢。 目标 这学期开始渐渐明晰了自己的人生方向，有了努力的目标。但是不论是练琴还是准备算法竞赛，我投入的时间和精力还不是很多，还是有些过于悠闲了。 希望这学期能坚持下去，每一天都不白废掉。周末或者平时没事的话，多去去图书馆；一周还是要多锻炼几次，不要天天宅在宿舍。 今年五月就是校赛了，在这里再立个flag（这个flag我是认真的），我要拿全校的rank1，拭目以待吧！

感觉人生是真的奇妙，刚好在寒假的最后一个晚上，我上紫了 这场Global_Round太有意思了，就连tourist都卡了一会儿C题了哈哈哈。本来我E题想出来正解了，结果就是一直wa，看来我还是太菜了。再接再厉吧~ 希望这是一个好的开始叭，虽然当初说的是半年内上橙（又一个flag倒了0_0），但是为了准备期末考试耽搁了训练，结果一路“滑铁卢”，花了一个寒假才把分补回来。 上学期还是太水了，这学期要多努力，已经到大二下，时间不多了。冲冲冲！！ 老规矩，放张图纪念一下

这一场总共6题，本菜鸡只过了前四题（rank为215）QAQ，再接再厉吧 这次的D,E,F都挺有意思的，所以就写个题解总结一下。不过以后补完题还是尽量都写一写总结叭，不然太懒了也不好www A. Add and Divide 123456789101112131415161718192021222324#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=2e5+10;int a,b;int main(){ int T;scanf("%d",&T); while(T--){ int cnt=0,ans=1e9; scanf("%d%d",&a,&b); for(int i=0;i<=100;i++){ int x=a,y=b+i;if(y==1)continue; cnt=0; while(x){ x/=y ...

中断函数 中断函数不需要在main函数前定义 12345678910111213EA=1;//开总中断EX0=1;//开外部中断0IT0=1;//设置为边沿触发方式//默认情况下是电平触发方式，即IT0=0；//"IT0=1;"等价于"TCON=0x01;"//"IT0=0;"等价于"TCON=0x00;"void exter0 interrupt 0 // iterrupt是关键字，表明这是中断函数。其后的数字代表终端函数的编号（范围是0~4）//这里的编号是0，表明是外部中断对应的中断函数{} 定时/计数器应用举例 在中断函数内部定时器仍会计时，所以要尽量控制中断函数内代码长度小于计时时长 1234567891011121314TMOD=0x01;//前四位控制定时器1，后四位控制定时器0//这里表示令定时器0处于工作方式“1”下TH0=(256*256-50000)/256;TL0=(256*256-50000)%256;//设置定时时长为50000微秒EA=1;//打 ...

记忆化搜索 记忆化搜索不依赖于任何外部变量（外部变量即指定义于dfs函数外且值随dfs运行而改变的变量） 答案以返回值的形式存在，而不能以参数的形式存在 对于同一组参数，dfs的返回值是相同的 背包问题&单调队列优化 引例 C. Watching Fireworks is Fun 设fi,jf_{i,j}fi,j​表示在放第i个烟花时，在位置j能获得最大的快乐值 状态转移方程 fi,j=max{fi−1,k+bi−∣ai−j∣}f_{i,j}=max \{ f_{i-1,k} +b_i-\lvert a_i-j \rvert \}fi,j​=max{fi−1,k​+bi​−∣ai​−j∣} 注意这里的k是有范围的 j−(ti−ti−1)×d≤k≤(ti−ti−1)×dj-(t_i-t_{i-1})\times d\le k \le (t_i-t_{i-1}) \times dj−(ti​−ti−1​)×d≤k≤(ti​−ti−1​)×d 最终式子化为 fi,j=max{fi−1,k−∣ai−j∣}+bi=max{fi−1,k}−∣ai−j∣+bif_{i,j}=max ...