- 博客(22)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 快速乘（配合快速幂）
文章目录写在前面价值：思想分析代码（协助理解）写在前面快速乘其实跟快速幂很像，思想都是差不多的。价值：乘法都是O(1)O(1)O(1)的，那要快速乘做甚么？一旦数变大（像long long），并且连modmodmod数都是longlonglong longlonglong级别的，那必然会爆。高精度，又难打又慢，许多题目本来就卡常，打来必是白给。于是，快速乘应运而生。思想小学有讲，四则运算加乘法的关系就是X∗Y=X+X+X+XX*Y=X+X+X+XX∗Y=X+X+X+X(Y(Y(Y个））
2020-07-28 20:43:51
182
原创 强连通分量 Tarjan
强连通分量 Tarjan前言其实很早就会用Tarjan打强连通了，但还是有些一知半解，也忘性大，现在总结一下。强连通分量的定义假设我们现在有这个图：很显然这三个点两两之间可以到达，那么我们就称这个图是强连通的。假设我们多加一个节点之前的子图强连通，但不是强联通分量，因为它不是最大的强连通子图，而{1,2，3,4}是强连通分量。一个图可能有多个强连通分量，但我们找强连通一定要找尽可...
2019-12-03 13:39:22
296
原创 【NOIP2016提高A组五校联考1】挖金矿
惯例发题……考场经验与分析比赛就A了……这道题符合二分规则（答案具有单调性）。所以很容易想到二分答案。正解首先，这里涉及到一个实数域的二分（就是小数二分）。这种二分本质上和二分答案是一样的，但是如果直接打会炸，因为小数可以无限二分（1/2,1/4,1/8,1/16,1/321/2,1/4,1/8,1/16,1/321/2,1/4,1/8,1/16,1/32……子子孙孙无穷匮...
2019-07-03 16:38:01
172
原创 差分（1）——差分数组
写这个博客主要的原因是解释另一道题运输计划的树上差分，另外也是记录一下，不然每次都以为差分好难，其实是非常容易的。差分的定义：我们先看看如下的数列：1 5 6 7 4 3 2那么假设我们需要区间修改这个数列多次，但最后只求一个区间和。如果我们每次都改区间的和，那么我们必然会浪费大量时间，如果数据变大就会很慢。想用前缀和？就求一个区间，你这样也没什么用呀！那么我们只能用差分了！...
2019-06-08 15:47:33
343
原创 DigitalCounter
日常发题：我们有一个N位数字的电子表，当时间到达10^N-1时，下一秒就归0。下面我们给出数字0 到 9的模拟图。 对于每个数字，相邻两个+之间会有一根电子管，当显示该数字时，这些电子管就会发亮。如上图所示：数字0到9，它们的电子管数量分别是：6、2、 5、 5、 4、 5、 6、 3、 7、 5。 设现在的时刻是X, 那么可以算出该时有多少根电子管是亮的。比如：现在时刻是：99，那么共...
2019-06-04 13:03:26
639
原创 【NOIP2015提高组Day2】运输计划
按惯例发题……分析：其实题目说那么多，一句话就是：给定一棵带权树与mmm条路径，你可以使一条树上的边的权值变为0，问你mmm条路径的长度的最大值最小是多少。这道题让我想到了货车运输这道题，但是更难，但方法可以借鉴。因为这是最大值最小问题，很显然可以二分答案。那这个二分判断怎么打呢？我们如果遇到某条边，所有超时的边（即超过当前二分的答案）都经过此边，且最长路径减当前边的权值小于等...
2019-05-31 20:05:20
505
3
原创 【NOIP2015提高组Day1】斗地主
先把题发一发……考场经验：这道题做的时候让我几近崩溃，因为如果要打暴力的话太烦了不想打 。但是我们发现：这样只要判断前六种方法就行了，打几个判断，30~正解来了：首先，做一下基本处理（简化题目）:因为一般的斗地主除了大王小王，没有花色的大小区别，但这里也不是让你赢，只是自己一个人快速打光牌。我们发现花色并没有什么用，所以可以免去。但，众所周知，虽然A是1,2是2，大...
2019-05-21 17:41:56
5483
9
原创 数字对
Description小H是个善于思考的学生，现在她又在思考一个有关序列的问题。她的面前浮现出一个长度为n的序列{ai}，她想找出一段区间[L, R](1 <= L <= R <= n)。这个特殊区间满足，存在一个k(L <= k <= R)，并且对于任意的i(L <= i <= R)，ai都能被ak整除。这样的一个特殊区间 [L, R]价值为
2019-05-15 13:29:41
218
1
原创 快速读入（C++）
快读，我们虽然可以抠标，但我不是一个不求甚解的人，所以我理解了才写（话说也很快理解啦）。还是很简单的。首先，我们为什么要写快读，cin，scanf不是很简单吗，难道这很慢吗，真的！（之前Pascal就无所谓，全部都read/readln）那么我们知道读入字符确是很快的（即getchar），那么很显然，我们可以用...
2019-05-08 13:09:21
8688
8
原创 单调队列（用点心，很简单）
先说点题外话，为什么要讲单调队列呢？因为我恨透了它的题解。前段时间，我一听到“单调队列”，我就心想：完了，是单调队列。因为我认为很难，好好看看，原来是题解讲得太复杂了，这十分简单，易理解，易实现。何为单调队列，就是一个由大到小或由小到大排列的队列，如图：到这里，大家一定都理解，但，这有什么用呢。这是用来解决一串数中一个移动的区间求最大、最小值的算法。如图：如求最大值：这个队列这样做...
2019-05-05 12:47:31
148
原创 倍增求LCA（最近公共祖先）
文章目录定义如何求$LCA$正题：倍增法定义LCA(Least Common Ancestors），最近公共祖先，如节点zzz是x，yx，yx，y的祖先，则称zzz是x,yx,yx,y的公共祖先，深度最最大的公共祖先称为LCALCALCA。比如说：LCALCALCA（4，5）=2，LCALCALCA（5，6）=1，LCALCALCA（2，3）=1。懂了？如何求LCALCALCA暴力...
2019-03-09 16:47:45
337
原创 链式前向星（数组模拟邻接表）
链式前向星，又称数组模拟邻接表……，这个数据结构有很多名字，了解就好。这个数据结构看懂了受益匪浅，十分简单。只要你想明白了，会茅塞顿开。重点来了（进入正题）：有些图要存储时，节点数很大，但是边数很小（即稀疏图），如果用平时的二维数组存储法，轻则会浪费空间，重则空超。那么我们引入一种存边来存图的数据结构——链式前向星。（注意，这是存边）首先，我们开三个数组:head[i]head[i]h...
2019-01-28 19:39:43
967
1
原创 浅谈RMQ(ST)
ST这种算法是少有的简单（理解）而又简单（实现）的算法。题目导入：题目描述2008年9月25日21点10分，酒泉卫星发射中心指控大厅里，随着指挥员一声令下，长征二号F型火箭在夜空下点火起飞，神舟七号飞船载着翟志刚、刘伯明、景海鹏3位航天员，在戈壁茫茫的深邃夜空中飞向太空，开始人类漫步太空之旅。第583秒，火箭以7.5公里／秒的速度，将飞船送到近地点200公里、远地点350公里的椭圆轨道入口...
2019-01-21 21:28:30
245
1
原创 【NOIP2018PJ正式赛】对称二叉树
对称二叉树，脑补一下，中间对分，一折，如果完全重合（形状数字都要），那就是对称二叉树。显然数据很小，暴力过。暴力过。dg(l[i],r[i])代表，递归i的左子树，i的右子树。...
2018-12-10 19:11:44
382
3
原创 【NOIP2018PJ正式赛】龙虎斗
这，看似一道水题，实际也是一道水题。总体思路是先求出龙、虎的气势，其实只要把天降神兵加上对应的兵营，再计算气势（小于m龙，大于m虎）。再枚举每一个点，求出气势差最小值。需要注意的是，m兵营也可以派p2个人。（第一个坑）在计算时，数值较大，需使用实数类型（第二个坑）更可恶的是直接计算时pascal会报错，需要“骗电脑”，定义一个乘法函数代码令人吃惊（这和直接算有什么区别？？？）（交...
2018-11-23 19:27:57
663
4
原创 【NOIP2018PJ正式赛】标题统计
题目描述凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时，空格和换行符不计算在内。输入输入文件名为 title.in。输入文件只有一行，一个字符串 s。输出输出文件名为 title.out。输出文件只有一行，包含一个整数，即作文标题的字符数（不含空格和换行符）。这题太水了，学过字符串的肯定都...
2018-11-23 12:35:32
2098
4
原创 win10设置默认浏览器
很多人也许会遇到这种情况：win10默认浏览器被篡改，下什么电脑管家占内存又有时无效（像我一样）。所以说，还是要直接在系统里设置。首先，打开控制面板第二步，打开“程序”第三步，打开“默认程序”第四步，打开设“设置默认程序”这时，会跳出一个窗口，第五步，打开“默认应用”、第六步，向下滑动，找到并点击“web浏览器”最后，选吧。关注走一走。...
2018-11-10 13:57:26
4338
1
原创 快速幂
用暴力求幂，时间复杂度为O(n)（代码都会了吧，这都不会不要往下看了，洗洗睡吧）但是当（设底数为a，次数为b）b较大时，即使a较小，时间也不能让人接受，如b=时，时间复杂度为O(10^11)，显然，这是不能被接受的。此时，则需要——快速幂，时间复杂度仅仅为O(logn)！！！！！！！！！！！！！一个非常基本的定理：不会有人不懂吧，举个例子x=2，a=4，b=3，我们可以分解一下发现...
2018-11-08 17:12:53
231
2
GeoGebra-Windows-Installer-6-0-536-0.exe
2020-07-23
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人