Chrety

分类

C++(8) DOS(2) Python(2) 动态规划(12) 图论(8) 字符串(1) 学习笔记(10) 数学(10) 数据结构(14) 未归档(2) 杂(1) 算法(13) 详尽的思路(1) 题解(1)

/ 注册

全部文章（共85篇）

P1462 通往奥格瑞玛的道路 (二分+最短路)

题目 P1462 通往奥格瑞玛的道路给定\(n\)个点\(m\)条边，每个点上都有点权\(f[i]\)，每条边上有边权，找一条道路，使边权和小于给定的数\(b\)，并使最大点权最小。解析二分一下钱，然后跑最短路，判断一下如果只有这么多钱的话能不能到终点（最短路边权和是不是不超过\(b\)...

二分最短路算法

2019-04-27

0 752

P2447 [SDOI2010]外星千足虫 (高斯消元)

题目 P2447 [SDOI2010]外星千足虫解析 sol写到自闭，用文字描述描述了半个小时没描述出来，果然还是要好好学语文用高斯消元求解异或方程组。因为 \(奇数\bigoplus奇数=偶数\) \(偶数\bigoplus偶数=偶数\) \(奇数\bigoplus偶数...

数学矩阵高斯消元算法

2019-04-17

0 471

P3709 大爷的字符串题 (莫队)

题目 P3709 大爷的字符串题题意：求\([l,r]\)中众数的个数。解析维护两个数组： \(cnt[x]\)，数\(x\)出现的次数。 \(sum[x]\)，出现次数为\(x\)的数的个数。考虑往里添加元素时，直接取\(max\)；删除元素时，如果这个数是众数(...

莫队算法

2019-04-16

0 451

P4137 Rmq Problem / mex (莫队)

题目 P4137 Rmq Problem / mex 解析莫队算法维护mex，往里添加数的时候，若添加的数等于\(mex\)，\(mex\)就不能等于这个值了，就从这个数开始枚举找\(mex\)；若不等于\(mex\)，没有影响，因为它之前的所有数都出现过了，又出现一次不会怎样，放...

莫队算法

2019-04-16

0 547

HDU 2604 Queuing (矩阵快速幂)

题目 HDU 2604 Queuing 题意：给你一个数\(L\)代表一个队的长度，男女不限，随便排，\(f\)代表女生，\(m\)代表男生，但是其中不能出现\(fmf\),\(fff\) 这种子序列，问一共有多少种排的方法，结果需要\(mod m\). 解析：构思巧妙的一道矩阵快速幂我...

数学矩阵矩阵快速幂算法

2019-04-15

0 481

HDU 1757 A Simple Math Problem (矩阵快速幂)

题目 A Simple Math Problem 解析矩阵快速幂模板题构造矩阵 \[\begin{bmatrix}a_0&a_1&a_2&a_3&a_4&a_5&a_6&a_7&a_8&a_9\\ 1&0&am...

数学矩阵矩阵快速幂算法

2019-04-13

0 640

P2522 [HAOI2011]Problem b (莫比乌斯反演)

题目 P2522 [HAOI2011]Problem b 解析：具体推导过程同P3455 [POI2007]ZAP-Queries 不同的是，这个题求的是\(\sum_{i=a}^b\sum_{j=c}^dgcd(i,j)=k\) 像二维前缀和一样容斥一下，输出就完了。根据luogu某大...

莫比乌斯反演数学

2019-04-13

0 552

C++继承(一) 三种继承方式

继承定义继承是使代码可以复用的重要手段，也是面向对象程序设计的核心思想之一。继承就是不修改原有的类，直接利用原来的类的属性和方法并进行扩展。原来的类称为基类，继承的类称为派生类，他们的关系就像父子一样，所以又叫父类和子类。一般格式如下： class 派生类名 : 继承类型基类名派...

OOP

2019-04-13

0 449

P3455 [POI2007]ZAP-Queries(莫比乌斯反演)

题目 P3455 [POI2007]ZAP-Queries 解析莫比乌斯反演。给定\(n\)，\(m\)，\(d\)，求\[\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=d]\] 那我们设\[f(x)=\sum_{i=1}^{n}\sum_{j=1}^{m}[...

莫比乌斯反演数学

2019-04-12

0 537

莫比乌斯反演

莫比乌斯函数定义对\(d\)进行质因数分解：\(d=p_1^{r1}p_2^{r2}p_3^{r3}····p_k^{rk}\) \(r=max\{r_1,r_2,r_3···r_k\}\) 莫比乌斯函数的定义为 \[\mu(d) = \begin{cases}1\qquad d=1\\ 0...

数学莫比乌斯反演

2019-04-06

0 488