[综合] 树的直径题集

poj1985（模板题） 先随便找个点dfs一次找到距离最远的点，再从那个点再同样dfs一次，那个点到其他点最长的距离即为树的直径 不过这种方法不适用于有负权边 #include<cstdio> #include<cmath> #include<algorithm>...

[综合] Tire树总结（模板+例题）

题目来自《算法竞赛设计指南》 Tire树是一种可以快速查找字符串的数据结构 模板 #include<cstdio> #include<algorithm> #include<cstring> #defineREP(i,a,b)for(registerinti=(...

[综合] 2018 雅礼国庆集训

Merchant 有n个物品，第i个物品有两个属性ki,bi，表示它在时刻x的价值为ki×x+bi.当前处于时刻0，你可以选择不超过m个物品，使得存在某个整数时刻t,t≥0，你选择的所有物品的总价值大于等于S.给出S，求t的最小值。 很容易想到几个物品加起来的时候，价值是一个一次函数（合并同类项） ...

[综合] 分块总结

大佬总结 数列分块入门1 #include<bits/stdc++.h> #defineL(i)(bl[i]-1)*blo+1 #defineR(i)bl[i]*blo #defineREP(i,a,b)for(registerinti=(a);i<(b);i++) #defin...

[综合] KMP算法题集

模板 caioj1177KMP模板 #include<bits/stdc++.h> #defineREP(i,a,b)for(registerinti=(a);i<(b);i++) #define_for(i,a,b)for(registerinti=(a);i<=(b);i...

[综合] Hash大法

内容参考《算法竞赛进阶指南》 之前集训的时候听老师讲过，字符串题目中，hash一般不是正解，但是是一个优秀的暴力，可以拿比较多的部分分。 hash涉及内容很多，这里只讨论字符串hash 可以把字符串看成一个131进制位数，然后用ull储存，大过2的64次方后自动取模。 这样的话hash值相等的话可以...

[综合] 2018 noip 备战日志

我是写给自己看的…… Day110.8 今天开始停晚修课了，开始认真备战考试了。 今天晚上效率不错，竟然不会累，应该是平时一直这个时间写作业大脑高度集中， 现在换了编程也一样可以集中到这个状态 一些感悟： （1）不认真静下来研究一个题解，而是看n多个题解，浪费时间（2）行和列傻傻分不清，可以画图...

[综合] Manacher(最大回文字串)

很好的讲解 注意两端的字符要不同，同时数组要开大一些 【Manacher】最长回文子串 #include<bits/stdc++.h> #defineREP(i,a,b)for(registerinti=(a);i<(b);i++) #define_for(i,a,b)for(re...

[综合] 三分算法总结

和二分非常类似的一个算法，与二分不同的是 二分是单调的，而三分是一个先增后减或者先减后增 三分可以求出峰值。 注意三分一定是严格单调的，不能有相等的情况。 不过貌似只有求函数最值才用到这个东西，没有二分应用范围那么广。 「一本通1.2例3」曲线 画画图可以发现，满足先减后增 图和雅礼集训里Merch...

[综合] 二分题集

「一本通1.2练习2」扩散 显然联通块的个数是随时间越来越少的。 所以可以二分时间。 经过一波运算，可以得出两点需要联通的时间是 (abs(x[i]-x[j])+abs(y[i]-y[j])+1)/2 然后每次用并查集维护一下联通分块就好了。 第一次写这种开结构体的并查集，感觉很酷炫。 #inclu...

[综合] 质数总结

poj2689 要对数据敏感，L和R很大，但是L-R很小。 可以在（R-L）loglogR的时间内用筛法筛出所有质数。 然后扫一遍就好了。 有些细节要注意，有些地方会爆int，0和1不能算进去。 #include<cstdio> #include<cstring> #incl...

[综合] 约数总结

bzoj1053 比较经典的一道题。 首先要观察出一些结论 （1）质数不超过10个。前十个质数相乘已经超过最大值。 （2）质数的指数是递减的。如果不是，可以把指数小的和大的交换一下，答案更小。 然后就搜索就好了。 这是一类数论+搜索的题目，要从题目看出一些剪枝，然后搜索即可。 #include<...

[综合] 组合数学题集

bzoj1008 逆向思维。一共有m^n种状态 我们考虑不越狱的情况 第一个人有m种选择，后面的所有人均是m-1种选择 那么方案数就是m^n-m*(m-1)^(n-1)快速幂就好 其实不难，自己不要怕，心理不要有障碍 #include<bits/stdc++.h> #defineREP(...

[综合] dfs序题集

dfs序可以维护一个子树内的信息 需要记录dfs进的时间以及所有子树都遍历完的时间 voiddfs(intu,intfa) {L[u]=++id;for(inti=head[u];~i;i=e[i].next){intv=e[i].to;if(v==fa)continue;dfs(v,u);}R[u...

[综合] 一年后回归

当年noip拿了省二，挺遗憾的。 现在过了一年多了，高考考崩，去到深大计算机。 现在重新回来更新博客。 教是最好的学，一边学习编程课程，一边用自己的方式讲一遍，写博客，能提升学习效率。 高中更的主要是信息学竞赛。 现在我开始干Python，人工智能方面了。 至今为止，对我很重要的中考，高考，信息学...

[综合] 决定加入学校ACM！！

今天做了一个大决定，加入校ACM 弊处很明显，要投入大量时间。我可能要和大部分社团，学生组织，女朋友，所有假期说byebye了 但好处也很多。 一自己有基础，为什么不利用起来呢？我现在实力下滑地非常厉害，但是我可以通过学习自己曾经写的博客来学习，符合自己的思维方式。现在突然发现，一切都是最好的安排。...

[综合] 大一上第二周学习笔记

9.22周二 学习一定要清楚地知道自己学了什么，用这个博客记录一下自己究竟学了什么，不要一塌糊涂 算是一个反思总结吧。做题不要盲目做，做完花个5分钟反思总结一下到底学到了什么，列个一二三，这样印象更深。以后也可以回来复习 一道题一道题扎扎实实地独立做出并总结，这样稳步提升。算是费曼学习法的实践，把题...

[综合] 大一上第三周学习笔记

9.28周一 洛谷P1024一元三次方程求解 #include<bits/stdc++.h> #defineREP(i,a,b)for(inti=(a);i<(b);i++) #define_for(i,a,b)for(inti=(a);i<=(b);i++) usingn...

[综合] 大一上第四周学习笔记

10.5周一 国庆浪了好久 其实浪完了我真的不知道要干啥了 这种生活其实是很空虚的 我以前以为算法竞赛占据了我太多时间，没有时间享受其他事情 其实这说明我还不热爱它 这是编程这件事使我的生活变得充实 这也是我感兴趣，有天赋，有前景的东西 为什么不全力以赴呢 找回对编程的热爱，而不是为了保研 想起了我...

[综合] 大一上第五周学习笔记

10.12周一 P3373【模板】线段树2 这道题真的一波三折 这题干了好久，大概想了三四天，每天一两个小时刚这道题，终于tm独立想出来了 这题要写一个支持区间每个数乘法的线段树 第一个坎是怎么弄标记，这里我卡了挺久 想用一个标记，发现不行。那就用两个标记，加和乘 但是两个标记怎么共存，什么顺序，...