pinkyHead's blog

重链剖分 概述 由于重链剖分时，从根节点到叶子节点经过的重链数量必定小于等于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 ...

你好呀墨茶。在知乎上看到你的消息的时候，我就已经很难过了。今天早上在b站上面翻了翻你动态，又哭的稀里哗啦的。 看到你做了四月是你的谎言的视频，相信你也一样被薰的故事打动了吧。薰让有马公生得到了救赎，而你对生活的执着，也许也会在不经意间帮助到和你一样遭遇的人们。 我肚子里没什么墨水，写不来太多话，但我还是想写下这一篇博客，就当是我这个陌生人对你的一点纪念吧 祝你在另一边过得快乐

源起 经过两次电路程序设计作业的洗礼——谁叫我这个憨憨不想用Matlab呢（逃），对python的掌握更进了一步，也对电路的求解有了更深的认识。索性就把第二次实验，即设计程序求解高阶电路的过程和思路搬到博客上来其实是因为老师说放在博客上会有额外的加分，也算是对这些天工作的一个小小的总结 框架 程序采用了python的tkinter库来实现可视化操作，虽然界面比较朴素，但也还算是勉强实现了人机交互的功能。然后在使用了matplotlib,numpy以及scipy实现微分方程的求解和作图 这次大作业算是对我们手下留情了，所有的高阶原件都在同一个支路中，所以可以直接使用戴维宁等效化简再求解即可，从而免去了设状态方程的过程（主要是python求解微分方程必须要化成标准方程的形式，这样的话会使得问题的难度成倍增大）。 这样一来，只要解决了等效电路的求解，问题就迎刃而解了 建立系数矩阵+高斯消元 将高阶原件所在的支路首尾端点连起来，建立一个含有假想的新元件的支路 首先将这条支路上的原件设为值为0的电流源，代入求解开路电压uoc 然后再将该原件变为值为1欧姆的电阻，代入求得电压u1 即可得到r ...