- 博客(70)
- 问答 (1)
- 收藏
- 关注
RSS订阅
原创 莫比乌斯函数的由来及推导
网上搜莫比乌斯函数大多都没有写莫比乌斯函数的由来，而是直接写的定义式，这里对莫比乌斯函数进行推导。学习了狄利克雷卷积后，我们来看以下几个常见的积性函数：常函数:ξ(n)=1\xi(n)=1ξ(n)=1单位元:I(n)=[n=1](I∗f=f)I(n)=[n=1] (I*f=f)I(n)=[n=1](I∗f=f)莫比乌斯函数对于一个数我们可以对其求逆，那么函数是否也可以求逆呢？答案是肯定的...
2019-07-14 22:03:16
860
原创 欧拉函数及其相关证明(极清晰)
预备知识剩余系:指对于某一个特定的正整数ｎ，一个整数集中的数mod n所得的余数域。完全剩余系:设m∈Z+，若r0,r1,...rm−1为m个整数，并且两两模m不同余，则r0,r1,...rm−1叫作模m的一个完全剩余系。设m∈Z+，若r_0,r_1,...r_{m-1}为m个整数，并且两两模m不同余，则r_0,r_1,...r_{m-1}叫作模m的一个完全剩余系。设m∈Z+，若r0...
2019-06-29 11:51:36
549
原创 给OIer节约5s的快速创建子目录的程序
每次考试考完的时候教练都会要求建立子目录，然后又会在这个时候浪费我们生命中美好的5s，这个时候，这个轮子孕育而生，有了它，你就比其他人多拥有了5s的美好时光～用法：在选手文件夹下输入Mkdir回车，即可为当前文件夹的所有cpp文件创建一个文件夹，同时把文件复制进去方法: 复制以下内容到一个叫做"Mkdir"的文件里#!/bin/bashif [[ "$1" == "-h" ]]then...
2019-06-01 10:35:53
170
原创 KD树详解
K-Dimension-Tree (KDT)顾名思义，kd树其实就是多维二叉树（空间二叉树的一种特殊情况）， 里面储存着k维的点的信息，是对k维空间进行划分的一种数据结构。在竞赛中一般用来解决二维空间和三维空间的信息检索KD树可以解决以下几个任务:KNN问题。即查询离某个点第k邻近的点查询最近最远（就是 KNN问题）查询矩阵和图像处理（与竞赛无关）对于KD树,我...
2019-04-13 16:50:07
17087
6
原创 算法竞赛中的结构体简单重载运算符
结构体运算符的简单重载在算法竞赛中我们经常会使用结构体来保存我们需要的变量,但在我们需要进行排序或使用一些需要运算符的STL容器时,我们往往会定义一个函数cmp来保存,但这不是一个万全的方法.假如现在需要保存每个人的名字,身高,年龄等信息我们很容易想到要用结构体 来进行保存const int maxn=1e6;st...
2018-08-11 18:31:43
1036
4
原创 DELL G15 5511突然开不了机情况解决办法及求助
背景： 人在宿舍坐，黑屏突然出现，淡定地按了下电源键毫无反应。解决办法 若是突然关机，且按电源键毫无反应，可以考虑是静电积累造成的，只需要买一把螺丝刀，拧开后盖，把电池连接的地方拔了，然后多按几次电源键即可插上电池。连上充电器，重启成功。成功节约100块钱。小插曲 拆后板时有四个螺丝是拧不下来的，只需要拧松即可。ps 第一次出现这个问题的时候我拿去修电脑花了100，后来百度解决了问题。但现在不知为何电脑突然开不起机的情况越来越频繁，基本上每天都会开不起机。不知是天气情况还是咋的。坐标天津10月份。如果
2021-10-24 13:48:14
15536
4
原创 cin.getline()与cin.get()的区别
cin.getline()cin.getline()cin.getline()与cin.get()cin.get()cin.get()的区别$ cin.getine() $用法:cin.getline(char*,size);注意: 1. cin.getline();读取到最后的换号符后会丢掉换行符，也就是可以继续输入其他 2. cin.getline()只读取size-1个字符，并把第size个位置改为'\0' 3. cin.getline()如果字符数目多于size-1个，
2021-09-16 19:53:00
315
原创 浮点计数法
浮点数计算机中的浮点数是表示小数的一种类型，而浮点数则是用科学计数法来表示的。对于一个32位的 float float float 型所保存的数从左往右第1位保存的是该数字的符号，即符号位(s)之后8位保存的是该数字的指数，即阶码位(e)，这8位用的是移码来保存指数之后23位用来保存有效数字，即尾数位(m)，尾数用原码表示那么这个浮点数用科学计数法表示出来则是(−1)s×1.m×2e(-1)^s \times 1.m \times 2^e(−1)s×1.m×2e。移码阶码位使用的是移码来保存
2021-09-11 20:11:49
1533
原创 我又回来了
沉寂了一年半多，我又可以继续编程了。虽然没有进入大学的计算机学部，但并不影响我学习编程，而且还能够转专业。今后的编程可能不会再以竞赛算法为中心了，会记录我学习编程的路程。...
2021-09-11 14:05:02
116
1
原创 题解 Cheapest Palindrome
题解 Cheapest PalindromeCSP−SCSP-SCSP−S考前倒数第二天,发现这种字符串dpdpdp题总是不会往dpdpdp方向想。题目描述见洛谷 P2890[USACO07OPEN]便宜的回文Cheapest Palindrome具体做法与心路历程这个题没有立马想出来是真的还需要加强了。看到题目我好像立马就想到了manachermanachermanacher，然后再是...
2019-11-14 19:42:27
241
原创 题解 石子
题解 石子题目描述具体做法与心路历程考试时一直在想怎么dpdpdp,没有仔细研究它的性质。具体做法这种题一定要注意观察独立性。我们仔细观察a1a_1a1和aia_iai,发现不论如何，aia_iai在a1a_1a1之前被选的概率都是aia1+ai\frac{a_i}{a_1+a_i}a1+aiai。设a1a_1a1被选的时间期望为EEE,那么有E=∑i=2nai...
2019-11-07 21:07:53
241
原创 RSA加密与解密讲解
RSA加密与解密这里只是讲讲RSARSARSA是怎么加密以及怎么解密。加密与解密过程采用RSARSARSA的方法后可以得到一个公钥(n,e)(n,e)(n,e)和私钥(n,d)(n,d)(n,d)。对于一个明文aaa,我们把它加密得到bbb,b=ae mod nb=a^e~~mod~~nb=ae mod  ...
2019-11-06 22:35:24
285
原创 Miller Rabin 素数测试
Miller Rabin 素数测试Miller Rabin 是一种快速判断素数的方法。有非常小的概率可能出错。费马小定理和二次探测Miller Rabin 素数测试主要就是用到了以上两个理论。费马小定理: 如果ppp为质数，那么有ap−1≡1 mod pa^{p-1} ≡1~~mod~~ pap−1≡1 mod &...
2019-11-06 20:47:36
596
原创 题解 蓝精灵的要求 二分图判定+简单背包
题解 蓝精灵的请求题目描述具体做法与心路历程考试时想了想，只想出了前面60pts60pts60pts,考完只有40pts40pts40pts(判错了)。觉得思路还是没有正确，一坨浆糊。具体做法题目大意:把图分成两个完全图，且两个完全图直接的点数差尽量少。考虑把没有关系的蓝精灵之间连边，建出补图。它应该是若干个联通块。对于每一个联通块，因为如果两点之间没有连边，它们实际上是有边的，所...
2019-11-05 20:49:25
221
原创 题解 世界树的考验 状压dp
题解 世界树的考验题目描述具体做法与心路历程考试时的心情:懵逼.jpg二分答案走一波，不行不行，边权这么小，这复杂度太底了。那么考虑DPDPDP?感jiojiojio无法满足后效性。。最后瞎写了个20pts20pts20pts的算法，喜提000分。。具体做法我还是太菜了又是一个小技巧。这种边权异或的题目，我们往往可以把点权设为其周围所有边的边权的异或和。在这道题中使所有边权为...
2019-11-05 19:26:44
159
原创 题解 抛硬币 期望
题解 抛硬币题目描述具体做法与心路历程对于这种期望题可以直接设方程，然后递推。一般是不连续的带系数，连续的不带系数。具体做法设f[i]f[i]f[i]表示连续iii次正面朝上的期望步数。有f[i]=f[i−1]+1+(1−p)×f[i]f[i]=f[i-1]+1+(1-p)\times f[i]f[i]=f[i−1]+1+(1−p)×f[i]。化简得:f[i]=f[i−1]×1p+...
2019-11-04 21:30:42
985
原创 题解 运输 树状数组+乘除分块+离线差分
题解 运输题目描述具体做法与心路历程一开始没想到正解，于是开始码O(mw)O(mw)O(mw)的暴力，码暴力的时候发现了正解。具体做法考虑将询问离线下来，然后差分到树上，暴力的方法就是在dfsdfsdfs树的时候用一个数组ans[i]ans[i]ans[i]表示从根走到当前节点，经过的边在询问的电量为iii时所需要的最少次数。那么在dfsdfsdfs时从对每个ans[i]ans[i...
2019-11-04 21:08:56
118
原创 题解 [LNOI2014]LCA 树链剖分+离线差分
题解 [LNOI2014]LCA题目描述题目链接具体做法与心路历程这道题搁了有一段时间，趁周六晚上没有划水的时间里写了这道题。这道题。。也算得上是套路吧。具体做法这种问题每次询问一堆点的贡献一般是把贡献进行某种转换，使其与它到祖先这条链扯上关系。一般是能够变成区间修改和区间查询。我们看题目要求的是depth[LCAu,v]depth[LCA_{u,v}]depth[LCAu,v]...
2019-11-02 22:44:23
179
原创 题解 子树问题 dp
题解 子树问题题目描述数据范围:n,k≤500n,k \leq 500n,k≤500具体做法与心路历程考试时想了一下，只能设出dpdpdp方程，然后不会转移。具体做法设f[size][dep]f[size][dep]f[size][dep]表示有sizesizesize个节点，最大深度不超过depdepdep的合法的树的数目。考虑怎么转移f[size][dep]f[size][de...
2019-11-02 16:40:14
183
原创 题解 修改字符串 DDP基础题
题解 修改01串题目描述数据范围:具体做法与心路历程这道题作为T1T1T1真心觉得出题人毒瘤好吧是我太菜。看这题目感觉妥妥的贪心，贪心思路都有，且还是对的。可惜只有50pts50pts50pts,然后开始优化贪心，搞了个线段树，一码就是300+300+300+，结果错了。CYJian线段树贪心A了，还只有200+。考完才知道正解是DP!DP!DP!，然而我连想都没想。具体做法方法是D...
2019-11-02 14:59:42
368
原创 题解 中等的字符串 AC自动机+矩阵优化dp
题解 中等的字符串题目描述数据范围:具体做法与心路历程碰到这种给出多个字符串要求构造一个新的字符串求概率或者价值的题刘汝佳在<<算法竞赛入门经典>>里告诉我们：做法一般都是先建出ACACAC自动机然后再来做dpdpdp。首先设出dpdpdp方程:设fu,Lf_{u,L}fu,L表示从节点uuu开始走，走LLL步后能得到的最大价值。把每个字符串的价值...
2019-10-31 22:05:09
174
原创 题解 猴猴吃苹果 长链剖分
题解 猴猴吃苹果题目描述具体做法与心路历程比较简单吧。题目要求我们每次找最长的链走，然后删去点权。以kkk为根，我们发现如下性质:走的路径一定是叶子节点每个点走后就没有贡献了我们把一颗树画出来，观察即可发现，这就是长链剖分！！！我们把链的长度赋给叶子节点，然后排序即可。注意排序的比较！！！Code\mathcal{Code}Code/******************...
2019-10-30 18:58:34
285
原创 题解 [51nod 1463] 找朋友
题解 [51nod 1463] 找朋友题目描述给定：两个长度为n的数列A 、B一个有m个元素的集合K询问Q次每次询问[l,r]，输出区间内满足|Bi-Bj|∈K 的最大Ai+Aj数据约定：n,Q<=100000m <= 100<=A[i]<=10000000001<=B[i]<=n1<=K[i]<=n保证B[i]互不相等具...
2019-10-29 20:53:50
179
原创 题解 三只企鹅 树链剖分
题解 三只企鹅题目描述数据范围:n,m,w≤105,u,v≤nn,m,w \leq 10^5,u,v \leq nn,m,w≤105,u,v≤n具体做法与心路历程考场上的错误方法不多说。具体做法我们把查询操作写出来:ans=∑v∈Modifydisu+disv−2dislcau,vans=\sum_{v \in Modify}{dis_u+dis_v-2dis_{lca_{u,v...
2019-10-29 16:33:39
247
原创 题解 或与异或
题解 或与异或题目描述具体做法与心路历程没什么好的想法，只能想到一个nS2nS^2nS2的dpdpdp。(S=214)(S=2^{14})(S=214)。设f[i][Xor][Or]f[i][Xor][Or]f[i][Xor][Or]表示前iii个数中异或值为XorXorXor,或值为OrOrOr的方案数。转移显然。发现跑个ai≤50,n=50a_i \leq 50,n=50ai≤...
2019-10-29 15:27:51
249
原创 题解 三角形
题解 三角形题目描述具体做法与心路历程这道题一眼过去。。。暴力O(QNlogN)O(QNlogN)O(QNlogN)我会！，每次询问将区间排序，然后贪心从最大的开始匹配，然后一路往下匹配！然后就没了。考试时原本想打个莫队维护setsetset来卡一卡，结果忘记怎么打待修莫队了～，胡乱对后面404040 分打了个线段树，每次选出区间最大值，然后再去掉最大值，一路选下去知道出结果，最后再改...
2019-10-29 14:41:49
260
原创 题解 [USACO18OPEN] Talent Show 01分数规划
题解 [USACO18OPEN] Talent Show题目描述题目描述网上有。具体做法01分数规划入门题！考虑我们为每个数设一个xix_ixi,xix_ixi只有0,10,10,1两种取值。那么题目要求的式子为:∑i=1ntixiwixi\sum_{i=1}^{n}{\frac{t_ix_i}{w_ix_i}}i=1∑nwixitixi相当于我们要求解每个xi...
2019-10-27 22:35:58
238
原创 题解 [SDOI2009]Bill的挑战 容斥
题解 [SDOI2009]Bill的挑战题目描述给nnn个字符串，每个字符串由a~z或者?组成，其中?可以匹配任意字符。现在问有多少个串TTT，满足能够恰好与nnn个串中的kkk个匹配。n≤20,n \leq 20,n≤20,字符串长度≤50\leq 50≤50。具体做法这是一道容斥题，当然一看数据范围也可以用状压dpdpdp写。考虑我们能够预处理出什么，数据这么小那么我们可以爆...
2019-10-27 21:37:08
168
原创 题解 网格染色 容斥
题解 网格染色题目描述有一个n×mn \times mn×m的网格，可以给任意多个格子染色，问要使得每行每列都至少有一个格子被染色有多少种方案？具体做法与心路历程考试时也想怎么容斥，想法是先每行考虑，再每列考虑，最后在减去多了的。还是容斥题做少了，这种明显的1,−11,-11,−1容斥都没做出。具体做法题目有两个大的限制条件:行，列。如果我们同时考虑两个不好做，那么只先考虑一个。...
2019-10-27 15:56:44
820
原创 双端队列LIS问题
双端队列LISLISLIS问题题目描述具体做法与心路历程考试时都想出来了结果犯了个sbsbsb问题导致了爆零。一开始想的dpdpdp到后来乱搞。论途中想出了正解结果被自己否定是什么感觉?具体做法考虑先搞出一个最长上升子序列:(图中青涩部分)那么接下来就是首先在111前面选一截倒过来接在111前面，1,21,21,2中间选一截再搞过了接在前面，再在3,43,43,4中间选一截倒过来往...
2019-10-24 21:22:59
338
原创 题解 不知道该叫啥 数论分块优化dp
题解 不知道该叫啥题目描述【数据范围】 n≤100,m≤109n \leq 100 , m \leq 10^9n≤100,m≤109具体做法与心路历程考场上首先想到的是O(nm)O(nm)O(nm)的做法。后来推不动了就去看后面的题，后面题也推不动了上了个厕所回来就想出来了。真的要充分利用。还是太菜了,别人10min的切的题，我用了1h具体做法按照考试时的时间顺序的想法。首...
2019-10-24 20:59:49
296
原创 题解 辩论 贪心
题解 辩论题目描述具体做法与心路历程看到这道题我秒想了网络流,搞了下没出来，发现是个简单的贪心，不难想。具体做法设A,BA,BA,B表示支持议题111的人数和支持议题222的人数，没选一个就把对应的+1,−1+1,-1+1,−1如果态度为111111，那么可以贪心的全选了。如果A,B>0A,B>0A,B>0,那么01,1001,1001,10各选一个后A,BA,...
2019-10-24 20:21:42
279
原创 根号分治练手题 西比拉先知系统 题解
西比拉先知系统题目描述【数据范围】n,m,Q≤3×105,y≤1000n,m,Q \leq 3 \times 10^5 , y \leq 1000n,m,Q≤3×105,y≤1000具体做法与心路历程考试时一开始想的是怎么搞，先想了线段树，后来发现不行，看数据范围O(nn)O(n\sqrt{n})O(nn)能过，于是想了莫队发现不好做，突然想起昨天提到了的根号分治，发现好像可行，于是...
2019-10-23 20:32:10
465
原创 题解 曾有两次 树链剖分
题解 曾有两次题目描述具体做法与心路历程我是真的sb。都把树建出来了竟然没有去想树的经典做法，我竟然在想怎么dpdpdp！！！思维是真的不够深，就只差一步了。考时想法题目即为要求对每个点求出与最短路相连的一条边后的最短路。考虑先跑一边最短路，由于边权>0>0>0，所以如果我们仅仅只保留最短路上的边的话，可以组成一颗树（最短路树)。这时再对每个点分析：枚举每条...
2019-10-22 21:48:49
181
原创 题解 博士之时
题解 博士之时题目描述具体做法与心路历程考试时没看懂题目意思我太菜了，所以没做。考后搞懂题目意思后发现不是很难。题目意思差不多为每条边要么连出一条000边，要么连出一条111边，要么不连边，要么连出一条000边一条111边。给出图，问图的同构数。这个就是否简单了。具体做法容易发现，图只有链和环（环为偶环）。考虑环，一个长度为nnn的环可以旋转n2\frac{n}{2}2n次...
2019-10-22 21:30:48
219
原创 题解 时之终结
题解 时之终结题目描述[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EGc42131-1571749660475)(https://miao.su/images/2019/10/22/_52c105.png)]具体做法与心路历程这是一道简单的构造题。因为要使点数尽量少，那么我们边可以尽可能多的连。若只有一个点，那么最多有000条路径。若有两个点，那么最...
2019-10-22 21:08:00
342
如图所示，ubuntu用java连接mysql连不上
2021-11-20
TA创建的收藏夹 TA关注的收藏夹
TA关注的人