- 博客(26)
- 收藏
- 关注
RSS订阅
原创 图论小技巧以及一些良心的题目
MST相关先说几个这类题的套路：1、砍掉无意义的边。2、改变边的联通方式。3、lct大法好啊！再说几个MST的性质：1、一张图的所有MST拥有完全相同的边权集合。2、对于不同的MST，在加入所有<x的边后，连通性相同。3、只有权值相同的边才会互相影响。然后就是题目啦。AT2134这个题要用到第二个套路即第二个性质。显然，我们可以将a+1a+1a+1向bbb连的边改为向...
2019-03-02 21:25:07
609
原创 调试代码的一些技巧
1、检查变量名检查一遍所有变量在代码中出现的位置。看看它们是否应该在这个位置，或者有没有与其它变量搞混了。比较常见的有nnn和mmm混淆，以及复制粘贴的时候忘了改序号、左右儿子等。2、检查符号检查一遍所有符号，尤其是>，<，>=，<=这些。复制代码的时候同样要注意。3、查漏补缺有时候并不是一些语句写错了，而是少了某些语句。因为在调试过程中，我们更多注意到的是写在编...
2019-02-19 22:08:50
186
原创 一些乱搞的退火题
退火（全称叫模拟退火）是一种随机乱搞的玄学算法，大概是珂学家们发现随机贪心往往效果不好，所以出现了在原策略上进行改动的方法。后来发现单纯的小改动容易陷入局部最优解，就又有了这个玄学的退火。不过我并不想讲这个具体的过程，只是简单说一些细节：1、记住e−ans/te^{-ans / t}e−ans/t是接受解的概率（ansansans指当前解与最优解差了多少），很良心的，我给出这个函数的一些结果作...
2019-01-21 20:35:33
186
原创 珂朵莉树及一些相关题目
比分块还要暴力、比线段树还要好写的功能萎缩而强大的数据结构。只要有类似于区间赋值的操作且数据随机，珂朵莉树就可以完成几乎所有查询。先从一道例题说起：CF896C也许是珂朵莉树名字的由来？由于珂朵莉树更加珂学所以人们渐渐放弃了老司机树或者ODT的叫法区间赋值、数据随机，所以我们就要上乱搞了。很不显然，经过若干次随机操作后，假如把数字相同的一段区间看成一个点的话，原序列只会剩下lognlogn...
2019-01-18 17:48:06
917
原创 一些字符串（水）题
晚上不想写代码，就水一发博客吧qwq。P2444 [POI2000]病毒链接无限长的字符串就是能在ACAMACAMACAM上无限跑下去而不会撞到已有的字符串，所以建出ACAMACAMACAM判环即可。P3763 [TJOI2017]DNA链接建出SAMSAMSAM之后，由于可以有错误匹配的机会，所以我们可以考虑dpdpdp。令dp[i][j]dp[i][j]dp[i][j]表示匹配到i...
2019-01-03 19:30:54
213
原创 NOIP2018游记
day0颓了一下午，见到了poorpool，后来找了半天A考场，最后又颓了一晚上。day-1的时候我貌似说过我一定在10点前睡，然而欢迎来到实力至上主义的教室太好看了，再加上zzh十分毒瘤，所以最后就到了12点才睡。day1显然昨天没睡好~进入考场了，密码飞雪连天海星，大概是让全国OIer集体祭奠金庸老师吧orz。开始看题。t1看了老半天，甚至还去看了会样例解释，最后终于从内心决定它...
2018-11-16 22:46:32
154
原创 BSGS大法——有趣的分块打表
对于三个整数A,B,CA,B,CA, B, C，满足A,B<C<109A,B<C<109A, B < C < 10^9且A,CA,CA, C互质，求一个最小的x使得Ax≡B (mod C)Ax≡B (mod C)A^x \equiv B~(mod~C)，怎么做？ 分块打表！ 令t=⌈C‾‾√⌉,x=i∗t−j (i,j&...
2018-07-31 23:56:55
268
原创 树套树——树状数组套主席树
线段树套平衡树是什么脑残东西，复杂度就是假的，O(nlog3n)O(nlog3n)O(nlog^3n)让人感觉非常不靠谱。所以我们为什么不用更好写的树状数组代替线段树，更好写的主席树（权值线段树）代替平衡树呢？而且，不仅是好写，复杂度也是很对的O(nlog2n)O(nlog2n)O(nlog^2n)啊。我们来简单理解一下树套树是什么： 思想其实很简单，树状数组的每个节点都是一颗权值线段树，并...
2018-07-31 22:34:22
2517
3
原创 建立在点双上的圆方树及 APIO2018T3 铁人两项
圆方树是什么？ 其实很简单，就是点双的缩点形式。原图中的点用圆点表示，对于每个点双内部建立一个方点，并把这个方点向点双内所有点连边。对于一个单点，就把它连出去的每条边都改为方点并和原来这条边两端的节点连接。这样做之后，任意两个圆点以及任意两个方点都不相邻。接下来看题。 传送门 建立圆方树，方点权值为其代表的点双内的点数，如果这个方点是从一条边变过来的，那么其权值为2，同时令圆点权值为-1...
2018-07-31 19:46:55
199
原创 Kruskal重构树及 NOI2018D1T1 归程
Kruskal重构树，就是在运行Kruskal算法的时候，对于每次找到的一条边{x, y, w}，我们新建一个节点z，权值为边权w，连接fa[x], z和fa[y], z，然后用并查集的方式把x和y各自所在的集合都合并到z里，下一次的fa[x]和fa[y]就是z了。inline void kruskal(){ for (int i = 1; i &amp;amp;lt; n &amp;amp;lt;&amp;amp;lt; 1; ...
2018-07-31 16:04:00
232
原创 可持久化并查集
其实这已经快不能算并查集了。 维护可持久化的fa数组，因为不能路径压缩，所以就用按秩合并（启发式合并）就好了。 可持久化数组一个log，启发式合并一个log，总复杂度就是O(nlog2n)O(nlog2n)O(nlog^2n)了。#include &lt;iostream&gt;#include &lt;cstring&gt;#include &lt;cstdio&gt;con...
2018-07-31 15:12:53
280
原创 平衡树——Splay及其维护的相关信息
无限Orz Tarjan大神。Splay是一个神奇的数据结构，它可以维护一些数的权值集合、一个序列甚至是一棵树（一片森林）。权值其实权值线段树也可以处理平衡树的问题。在权值线段树外面套一个树状数组（树状数组套主席树）可以解决更复杂的带修改和区间查询权值相关的问题，那不要那个树状数组不就能解决一个平衡树的问题啦？ 不过今天不讨论权值线段树，我们只讲Splay。二叉查找树学S...
2018-07-31 00:15:21
630
1
原创 manacher算法
和KMP一样，是个字符串算法，是个O(n)算法，同样也是个通过减少无意义匹配来降低复杂度的算法。 但哪里不一样呢？ 哪儿都不一样。 解决的问题不一样，优化的方法和思路不一样，代码不一样，还有这个比KMP简单多了。 它解决的问题是这样的：给出一个字符串，求它以任意位置为中心的最长回文子串长度。这个任意位置可能是某个字符上（比如abcba中的c），也可能在两个字符中间（比如abba中间的两个b...
2018-07-21 23:30:27
501
原创 AC自动机
自动AC机是什么？交上去就能AC？ 要真是这样，那还要OI干什么。 AC自动机相当于是Trie上KMP，相对于KMP，解决多串匹配问题，但比KMP要简单，核心思想就是两句话。Code#include &lt;iostream&gt;#include &lt;cstring&gt;#include &lt;cstdio&gt;#include &lt;queue&
2018-07-21 22:09:36
93
原创 KMP字符串匹配
KMP是一个单串匹配O(n)O(n)O(n)的算法，不同于Hash，这个是保证正确的。 什么是单串匹配呢？就是给你一个模式串P和一个文本串T，问P在T中的哪些位置出现过。 暴力做法就是把T的每个位置都跟P匹配一遍，复杂度为O(len(T)∗len(P))O(len(T)∗len(P))O(len(T)*len(P))，也就是O(nm)O(nm)O(nm)。 以下，因为公式化的引号（包括单引号...
2018-07-21 21:30:51
230
原创 Miller-rabbin算法
这个算法用于快速判断一个数是否是质数。 那怎么判呢？ 首先，既然要快速，我们就不能用朴素的O(n‾√)O(n)O(\sqrt n)的试除法。我们会联想到质数的一些性质： ap−1≡1(modp)(0&lt;a&lt;p)ap−1≡1(modp)(0&lt;a&lt;p)a^{p-1} \equiv 1 (mod p)(0 < a < p) 也就是费马小定理了，我们可以由此想到一个简单的方法...
2018-07-21 18:28:17
614
原创 扩展欧几里得算法
这个算法是用来解决这样的问题的： 给定a,b,ca,b,ca, b, c，求 ax+by=cax+by=cax + by = c 这个不定方程的最小非负整数解。 扩欧求的实际上是 ax+by=gcd(a,b)ax+by=gcd(a,b)ax + by = gcd(a, b) 这个方程的解，所以只有当 gcd(a,b)|cgcd(a,b)|cgcd(a, b)|c 的时候才有整数解。 ...
2018-07-21 14:31:48
163
原创 高斯消元
高斯消元其实就是个模拟……想想初中怎么学的加减消元，模拟这个过程就好了。 主要看看代码里的一些技巧。Code#include <iostream>#include <cstring>#include <cstdio>#include <cmath>const int maxn = 107;const double eps =...
2018-07-21 13:37:25
87
原创 多项式各种操作
前些天学了一堆多项式的算法，今天总结一下。乘法朴素的NTT就不说了，主要说一下三模数NTT。 三模数NTT，顾名思义，就是选取三个适合做NTT的模数，然后把它们用CRT合并起来得到的答案再去对我们要求的模数取模。 为了方便，这三个模数分别是998244353, 1004535809和469762049。它们的原根都是3，且它们减去1的值都有超过20个2的因子。 如果你觉得能用in...
2018-07-21 13:28:28
388
原创 BZOJ5379: Tree
链接扯淡据说这道题是CF几个月前某场比赛的题，然后被出到了前几天雅礼集训T1，于是就又成为了一道BZOJ题。Description给定一棵树，树根初始为1，每个点有权值，有三种操作： 1.将根设为x； 2.将lca(x, y)的子树内所有点的权值加上z； 3.查询x的子树内所有点的权值和。Input第一行两个整数n, q，表示树的大小和操作个数。 接下来一行n个整数...
2018-06-23 21:12:59
253
原创 洛谷2577 午餐
链接 一道转移方程只有两行但调了一下午的dp。。。 先对所有人按吃饭时间排个序，因为吃饭慢的先打饭结果会更优。 设f[i][j][k]表示前i个人在第一列打饭总时间为j，第二列打饭总时间为k的最快集合时间，但是这样是MLE的。。。 可以发现k其实就是前i个人打饭总时间减掉在第一列的时间，所以只需要f[i][j]就够了。 但我们还是感到不爽，因为这个东西类似于一个背包，所以数组第一维i也就...
2018-04-29 18:20:53
133
原创 九省联考2018D1T3 秘密袭击
链接又是一道经典的暴力碾标算。对每个点分别计算贡献最后加一块就好了。假如当前正在计算s的贡献，设f[i][j]代表包含从s到i的路径且使得s为第j大的连通块个数，进行简单的树上dp，s最终带来的贡献就是f[s][k] * d[i]。具体实现见代码。#include <iostream>#include <cstring>#include <cstdio>...
2018-04-15 20:34:07
455
原创 九省联考2018D1T2 IIIDX
链接很容易发现，歌曲间的关系构成了一棵树，于是O(n)的贪心算法也就是显然的。但是我们对贪心带来的55~60分不满意，鉴于这个题是个nlogn范围，所以还是用数据结构吧。很容易发现，题目给出的n首歌的难度顺序不会影响最终答案，所以首先对这个难度值从大到小排序。不过树还是要构造的，接下来预处理出每个节点的子树大小。之后，每次找一个最靠左的位置，使得这个位置左边足够放下当前节点的子树。如果有多个值相同...
2018-04-15 16:05:56
326
原创 九省联考2018D1T1 一双木棋
链接可以观察到，整个对局过程中的任意时刻，棋盘总是被一条从左下到右上的轮廓线拆分成有子和无子的两部分。因此，我们可以考虑轮廓线dp，从左下角开始，向上的边为1，向右的边为0。设f[sta]表示当状态为sta时，双方都选择最优方案还能获得的收益，则初始状态（也就是最终对局结果）为f[11...1100...00]，最终状态（也就是开始对局的状态）为f[00...0011...11]。状态倒着读，因为...
2018-04-15 15:10:42
340
原创 Hello, stars!
蒟蒻star_city的第一篇博客，一个简单的开始。#include <iostream>#include <cstdio>using namespace std;int main(void){ puts("Hello, future!"); return 0;}
2018-04-15 12:54:24
211
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人