- 博客(32)
- 收藏
- 关注
RSS订阅原创 2021.10.15CSP模拟
审题 怎么说呢，感觉不是很能理解题目意思。T1（14:00-14:56） 考虑状态压缩，然后写了一个自以为正确的代码，拍了一会儿没什么问题就过了T2（14:58-15:40） 读着读着发现不对经，这道题貌似是个大模拟。在思考了一会儿后就直接按照题意写了一个模拟代码，然后跑了几组大样例，然后debug。。。。(也就用了半个小时吧)。T3（15:42-16:20） 没推出样例。。。T4（16:20-17:00） 思考了好大一会儿，然后因为空间原因放弃了对每个物质开数组记录的想法
2021-10-15 18:41:36
171
原创 2021年zhengruioiCSP-7连测总结day6
审题（18:03-18:10） 感觉是dp专练。。。T1(18:12-) 考虑到我们要求最短距离之和，容易想到最短路，同时，由于所有房屋在一个数轴上，容易想到用中位数求解。1.0版本（18:12-18:24） 考虑朴素做法，可以尝试处理出所有从0到1的最短路径，从而O(n)O(n)O(n)求解。 但这种做法预处理是O(n2)O(n^2)O(n2)的，所以应该只能拿40分的档。1.1版本（18:24-18:30） 1.0版本主要是预处理复杂度过高，所以考虑优化预处理。 可以发现我
2021-10-09 21:58:39
258
原创 2021.10.3
某次伪装为好题分享的考试的总结考试思路T1 没看出是区间DP，于是当机立断写了一段暴力算法，然而bug de不完。。。T2 思考了一段时间，然后放弃。T3 思考了一段时间，然后放弃。T4 敲了老大一晌代码，紧接着发现样例推不出来。。。T5 看到题目，当机立断写了一个kmp（裸的），然而数据范围是10510^5105。。。考试时间分配8:00-9:40码T1暴力并且尽力debug。9:40-10:20把T5的kmp打了出来10:20-10:50硬敲T4，结果。。。
2021-10-03 13:04:49
1345
原创 2021.10.2
2021.10.12 某次考试总结。T1 从题目上感觉出来是组合计数相关，但没有找到关系，于是写了个暴力的算法放那了。T2 没推出来样例，更没看懂题。T3 考试时感觉可以用数学方法做，于是推了一大会儿的数学计算式，结果。。。。。。T4 看到第一眼认为时完全背包，然后被数据范围劝退了（101810^181018的完全背包！？）T5 最有把握的一题，然而。。。 思路大概就是类似于暴力处理，对链进行遍历，在遍历的同时进行权值的累加。当时以为至少能拿一点部分分，然而。。。总结
2021-10-02 14:00:51
136
原创 zhengruioicsp-7连测 day5
审题(6:00-6:20) 正常地审题，感觉这次比赛没有上次那么狗血至少题目看起来很正常。T1(6:20-7:00) 发现第一题实际上挺简单的，枚举每一位数字就可以了，于是快速打了一下，自己测了几组数据后就过了T2(7:00-7:40) 正式读题时发现最初审题时有点问题，实际上没有我审题时想象的那么难，于是用我的思路打了一下，测了几组样例之后就过了。T3(7:40-8:30) 发现这道题挺有意思的，仔细推了一下后发现好像可以在拓扑序上搞个贪心来过这道题，于是快速打了一边之后de了一会b
2021-09-27 19:36:12
175
原创 zhengruioi csp7连-day4
审题(6:00-6:20) 发现这套题貌似不是很正经（T1有点奇葩），其他题没太多思路。于是就尝试去码题。T1(6:20-7:20) 越读发现越不对经，这套题的T1不再是送分题，于是一边打暴力解法（枚举雷的位置）一边想正解（没想到）。T2(7:20-8:10) ...
2021-09-27 19:15:05
1267
原创 2021-09-12
读题（6:10-6:20 读题时发现有几道题很熟悉。PS:之所以晚了10分钟，是因为吃饭迟到了。。。T1(6:20-6:40) 读完题后感觉这道题挺水的，又读了几遍题后就打出了代码，比赛感觉良好。T2(7:00-8:00) 这道题我似曾相识，于是很快就打出了基本思路。PS：之后Debug耗费了大量时间。T3(8:00-8:50) 这道题和T2一样令我感到熟悉，在打出暴力的部分分代码后就开始想正解，但是毫无头绪，又调试了一会后就换T4了。T4(8:50-9:10) 思考了一会儿
2021-09-12 21:14:19
100
原创 【数据结构】链表(含链式前向星)
链表为什么断不了？是拿振金做的吗？ 说了队列，说了栈，无论什么数据结构都离不开只能按一定顺序储存的结果，向特定位置加入某值的复杂度达不到O(1)O(1)O(1)。天空一声巨响，链表闪亮登场 链表就是这千千万万数据结构中的一个例外。 链表的模型就是一条链！我们可以向这条链的任意一个地方加入一个新的节点，也可以删除任意的一个节点。...
2021-09-05 21:14:31
220
原创 那年那事那些错题
2021.9.4 今天打的zhengruioi七连测T1大翻车：读题时将每个数字的先导零理解为了数字的先导零，结果仅考虑的第一个数字的先导零。奇葩篇： 某位和我一同参加七连测的大佬在写T2的过程中惨遭RE。经过一系列检查后发现：该题数据较大，他在使用 stringstringstring 类型时出现了RE。同时这件事告诉我们：当同时需要使用字符串和单个字符时，使用 charcharchar 数组来处理字符串更加安全。To be continue→To\ be\ continu
2021-09-05 21:12:25
101
原创 2021.9.4zhengruioi七连测day2
读题用时：6:00-6:25 读题时大致发现了我能快速打出的范围：T1、T2、T3能拿到60档的分。T1用时：6:25-6:37 很快的，写出了一个暴力（自认为）的算法。满怀期望的进行了粗略的认证后就换题了。PS:结果得了50分（没有判断每个前导0…）。T2用时：6:38-7:10 思考了一会儿后发现用栈模拟就行了，于是手写了一个栈放了上去，检查了一下就过了。PS:赛后成功AC。T3用时：7:10-7:53 先把能快速做出来的打了一下。原本想着用map，结果发现不会用，最后
2021-09-05 21:04:35
199
原创 【数据结构】堆
堆，是一种十分有用的数据结构，其优异的时间复杂度决定了它在求区间最大值（或最小值）中的地位。尽管堆也有极大的局限性，但它仍然是我们在算法竞赛中的一种常用数据结构。概念 堆，本质上是一个完全二叉树。同时，堆满足父亲节点一定不大于（或不小于）儿子节点的性质。常见的堆有二叉堆与斐波那契堆等。从时间复杂度上来讲，斐波那契堆是比二叉堆要优一些的（但本蒟蒻没学23333）。为了方便，我们实际上使用的一般是STLSTLSTL提供的优先队列（二叉堆）。二叉堆的实现1.手写实现（不建议） 要手写实现二叉堆，
2021-05-27 18:30:32
180
原创 【模板】小根堆
本博客仅为模板，具体思路请参见作者博客堆#include<cstdio>#include<string>#define Size 100000#define LL long longusing namespace std;class p_q_l { private: int size; LL num[Size]; void up(const int n) { int e = n / 2; int temp = n; while (te
2021-05-26 20:57:54
168
1
原创 【模板】大根堆
本博客仅为模板，具体思路请参见作者博客堆#include<cstdio>#include<string>#define Size 100000#define LL long longusing namespace std;class p_q_u{ private: int size; LL num[Size]; void up(const int n) { int e = n / 2; int temp = n; while (te
2021-05-26 20:57:20
168
1
原创 栈 与 队列
本篇博客来谈一谈栈与队列的爱恨情仇。 作为两个OIOIOI中最常见的数据类型，栈与队列可以说是必不可少的。1.栈 相信所有人都对电梯不陌生，对于单门开的电梯而言，如果其横向面积够小（只能容下一个人），那么显然先进电梯的人只能当在他后面进来的人出来后才能出电梯，而栈就像是这样的一个电梯，它仅允许栈顶的元素出栈，如图：在图中，最大的一个上端不封口的矩形就代表一个栈，每一组元素仅能从beginbeginbegin一端进行插入。例如，现在栈里共有A,B,C,D,E,FA,B,C,D,E,FA,B,C,D
2021-05-26 20:24:54
134
原创 【题解】SP1805
Largest Rectangle in a HistogramLargest\ Rectangle\ in\ a\ HistogramLargest Rectangle in a Histogram 如上图所示，在一条水平线上方有若干个矩形，求包含于这些矩形的并集内部的最大矩形的面积（在上图中即为阴影部分的面积）。 那么。这个问题跟单调栈有神马关系呢？（废话，当然是可以用单调栈解啦！！！） 显然，当矩形从左到右递
2021-05-25 21:12:23
228
原创 线段树总结[经典、权值、动态开点]
ps:这是本蒟蒻的第一篇数据类型博客。 线段树，这是一种非常常用、普遍的信息统计技术。其基本思想是分治（二分），该数据类型本质上是一个储存区间数据二叉树
2021-05-11 16:05:29
1110
原创 2021.5.9
T1 见到这道题，我首先是将前kkk个字符和后kkk个字符对比，有几处差异就需要改几次（50%限制， k<⌊n2⌋k <\lfloor\frac{n}{2}\rfloork<⌊2n⌋），然后想到了如果前kkk个字符与后kkk个字符有重复，那么实际上不需要更改这么多次。 然后我进行了一下调整：在判断完了以后，储存有差异节点的编号，如果以后在用到这个节点，就相当于要同时满足于该节点有差异同时于其所标记的节点也有差异才增加更改次数。 这样的话可以过样例了，但是后来检查这道题时发现，
2021-05-09 13:28:47
118
原创 【数学】组合数学
组合数学可以说是所有数论技巧中最有用的一种之一，无论是在生活中还是在学习中，都是一种极为方便的技能。文章目录基本运算加法原理乘法原理排列数基本运算加法原理 若完成一件事的方法有 nnn 类，其中第 iii 类方法有 aia_iai 种不同的实现方法，且这些方法互不重复，那么完成这些事共有a1+a2+a3⋯+ana_1 +a_2 +a_3\cdots+a_na1+a2+a3⋯+an 种不同的方法。这就是加法原理。乘法原理 若完成一件事需要 nnn 个步骤，其中第 iii 个步骤有 a
2021-04-27 18:31:20
227
原创 求逆元
本博客主要讲解如何求一个数的乘法逆元。定义 对于任意整数a，m，ba，m，ba，m，b，若a，ma，ma，m互质，且 a∣ba|ba∣b ，则存在一个整数 xxx 使得 b/a≡b×x(mod m)b/a\equiv b\times x(mod\ m)b/a≡b×x(mod m)，则称 xxx 是 aaa 的模 mmm 乘法逆元，记为 a−1(mod m)a^{-1}(mod\ m)a−1(mod m)。求解方法1：费马小定理 因为 b/a≡b×a−1≡
2021-04-27 17:18:58
214
原创 同余
本博客主要介绍同余这一内容。当然，本博客仅代表作者自身观点如有错误，请您指出。 同余，是数论中一个特别重要的一部分，而且编程中需要用到数论的大部分都是同余相关的问题。所以本篇博客就来介绍一下关于同余的一些东西。文章目录模运算模运算 同余有一个十分基础的运算，叫做取模。而在计算机中，我们所说的取模一般都是进行下述运算：x mod y={x−⌊xy⌋×k (x≥0)−[(−x) mod y]
2021-04-27 10:27:21
335
原创 欧拉函数
在说欧拉函数前，先提一下一个数学关系：互质。 互质，是一种数学关系，它表示两个数除了1以外没有其他公因子。即对于两个数a, b而言, 若gcd(a, b) = 1,则称a、b互质。欧拉函数(φ\varphiφ)定义 111~NNN中与NNN互质的数的个数被称为欧拉函数记为φ(N)\varphi(N)φ(N)。...
2021-04-26 22:01:30
188
原创 约数处理
在计算机学中，有许多算法的证明需要用到约数的性质。因此掌握部分关于约数的知识是必要的，本博文主要介绍作者关于约数的理解。文章目录约数定义推论1.正约数个数及累加和2.试除法求约数code3.倍数法求约数约数定义 约数的定义为：若整数nnn除以整数ddd的余数为000，即d∣nd|nd∣n。则称ddd是nnn的约数，nnn是ddd的倍数。推论1.正约数个数及累加和 依据算术基本定理，很容易想到：对于任意一个整数nnn而言，他可以表示为p1c1p2c2p3c3⋯pmcmp_1^{c_1
2021-04-20 16:37:57
306
原创 扩展中国剩余定理
概述 扩展中国剩余定理(exCRT)(exCRT)(exCRT)是中国剩余定理(CRT)(CRT)(CRT)的更普遍版本。 它取消了中国剩余定理的互质条件，所以可能无解。同时，不一定互质也说明无法用CRTCRTCRT的方法解exCRTexCRTexCRT所以我们需要考虑新的算法。求解{x≡a1(mod m1)x≡a2(mod m2)x≡a3(mod m3)⋮x≡an(mod mn)\begin{cases}x\equiv a_1(mod\ m_1)\
2021-04-08 19:37:47
301
原创 中国剩余定理
概述 中国剩余定理(CRT)(CRT)(CRT)，又称孙子定理，其典型题目是著名的“韩信点兵”。求解类型中国剩余定理的典型题面为：{x≡a1(mod m1)x≡a2(mod m2)x≡a3(mod m3)⋮x≡an(mod mn) \begin{cases} x \equiv a_1(mod\ m_1) \\ x\equiv a_2(mod\ m_2) \\ x\equiv a_3(mod\ m_3) \\ \vdots \\ x\equ
2021-04-08 17:14:06
242
1
原创 最大公约数（GCD）
本篇博客主要介绍最大公约数及其求解方法。最大公约数 首先，最大公约数是什么？ 按照定义，最大公约数是两个数的公共因子中最大的一个。所以两个数最大公因数一定是确定的，同时最大公因数只能对于两个以上的数存在。求解1.枚举因数 按照定义，我们可以知道，两个数的最大公因数一定是这两个数的公因数，所以很容易想到，当我们将每一个公因子求出来时，其中的最大因子一定是最大公因数。 由此可以得到一个朴素算法：对于nnn,mmm两个数，枚举小于等于n\sqrt{n}n的每一个数，当这个数是nnn的因子时
2021-04-07 20:22:34
438
原创 质数处理
文章目录求素数1.暴力（傻瓜算法）求素数 素数是数学的一大分支，也是编程中数学解题的一大基础。因此，求素数是一项基础知识。1.暴力（傻瓜算法） 这是最没用的算法，时间复杂度太高：枚举nnn以内的每一个数，再用试除法判断该数是否为素数。...
2021-03-17 19:59:02
255
1
原创 进制转换
文章目录序言概念可行性实现序言 对于OI出题人的尿性研究得出结论：他们总会出一些题来刁难OIer。而这些题中最常见的莫过于高精度算法和进制转换了。他们十分基础，又十分难打代码，所以广受出题人青睐。本篇就来说一说本人了解的进制转换。 其实进制转换更多的是一种思路，实现方法有很多，有时候还可以与其他算法重合（参照某次周测趣题总结（水题篇））。所以本博客更多的是介绍该思路而不是算法。概念 首先，要了解进制转换是什么。人类为了计数方便，发明了数字，但由于计数数量的增加，定义数字越来越不方便，于是人类
2021-03-17 19:33:25
720
1
原创 《算法竞赛进阶指南》 0x01 a^b
a^b题目题目来源本题要求计算aba^bab模ppp的值。数据范围 1≤a,b≤109且1≤p≤1091\leq a,b \leq10^9且1\leq p \leq10^91≤a,b≤109且1≤p≤109样例输入3 2 7样例输出2题解1.暴力求解（pow函数）复杂度：O(b)O(b)O(b) 首先，考虑暴力求解，可以用for循环计算bbb个aaa的积。由于ppp的值较大且计算为幂运算，所以用longlonglong longlonglong来储存答案code#includ
2021-03-04 18:32:23
143
原创 求素数
在算法竞赛中很多时候要用到素数，因此快速有效地得到素数就是一个重要技能了。本蒟蒻在此列举几种求nnn以内素数的方法。1.暴力（傻瓜算法） 这是最没用的算法，时间复杂度太高：枚举nnn以内的每一个数，再用试除法判断该数是否为素数。code//Maxn 为数组q的大小。bool q[Maxn}bool check(int n){ for(int i = 0 ; i * i < n ; i ++) if(n % i == 0) return false; return
2021-03-02 14:03:22
508
1
原创 树上DP5
题目&empt;这道题就是看每一个点到其他点的距离和是多少。数据范围告诉我们绝对不 能用暴力求解（TLE自动机.jpg)。因为是在树上且很明显答案之间有某种联系（真实原因：看题目）所以考虑DP求解。...
2021-02-28 13:19:02
110
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人