- 博客(116)
- 收藏
- 关注
RSS订阅原创 C++回炉之_C++PrimerPlus_第十三章 类继承
类的成员初始化表类的成员变量总是在构造函数执行前创建完毕但有此成员变量只能在初始化时赋值 – 如const型常量 和 引用使用初始化表可以使指定构造函数中的参数或常量作为成员的初始值Point::Point(int i, int j): x(i), y(j) {}初始化表只能用于构造函数必须使用初始化表来初始化const型常量和引用成员初始化的顺序与它们出现在类声明中的位置有关...
2018-04-02 14:21:36
434
原创 C++回炉之_C++PrimerPlus_第十二章 类和动态内存分配
复制构造函数如果没有定义复制构造函数 – C++会自动提供原型class_name(const class_name&);Point(const Point&);功能 逐个复制非静态成员的值 – 浅复制如果含有成员的类型也是类， 则使用此成员的复制构造函数来复制此对象当类成员里含有指针的时候，那么这两个对象的此成员都会指向同一个内存 – 这很不好 此时会使用...
2018-03-31 09:47:00
235
原创 C++回炉之_C++PrimerPlus_第十一章 使用类
运算符重载运算符重载是多态的一种形式C++允许赋予运算符多种含义运算符重载可使使用自定义类型看起来更像基本的数据类型一个例子使用 operator声明重载函数调用 z = x + y; 相当于 z = x.operator+(y);#pragma onceclass Point{private: double m_x; double m_y;pr...
2018-03-25 19:52:03
321
原创 C++回炉之_C++PrimerPlus_插曲 编程习惯
我的编程习惯尽量使用下划线(_)而非大写字母类 类首字母大写类成员变量 – 加 m_ 前缀静态成员变量 – 加 s_ 前缀类成员函数 公有函数 – 不加任何前缀私有函数 – 加 pri_ 前缀保护函数 – 加 pro_ 前缀静态函数 – 加 sta_ 前缀声明顺序 先声明构造和析构相关的函数再声明对成员变量纯存取的函数最后声明其他功能函数访问控制符按 privat...
2018-03-23 17:30:53
207
原创 C++回炉之_C++PrimerPlus_第十章 对象和类
OOP的特性抽象封装 和 数据隐藏多态继承代码可重用类将抽象转换为用户定义类型的C++工具数据表示 + 操纵数据的方法组成 类声明 – 蓝图 以数据成员的方式描述数据部分以成员函数(方法)的方式描述公有接口 接口 – 供用户使用以操纵数据的共享框架类定义 – 细节 描述如何实现类成员函数来看一个例子// Object.h#pragma onc...
2018-03-19 15:16:33
280
原创 C++回炉之_C++PrimerPlus_第九章 内存模型名称空间
头文件包含内容 使用#define或const定义的符号常量函数原型结构体声明类声明模板声明内联函数头文件的作用 对包含头文件的源代码文件(.cpp)进行单独编译时，预处理器将其与源文件合并从而创建临时文件(.cpp)使用系统头文件用#include <XXX.h> 用户头文件用#inllude "XXX.h"使用条件编译防止多次包含头文件#if...
2018-03-17 10:41:21
519
1
原创 C++回炉之_C++PrimerPlus_第八章 函数探幽
内联函数内联函数的编译代码与其他的程序代码“内联”到一块了 即编译器使用相应的函数代码来替代函数调用，从而不需要像函数调用那样跳来跳去内联函数的运行速度比常规函数快，但需要更多的内存在处理函数调用机制所占时间比执行函数代码的时间还长时，使用内联可节约大量的时间 即对代码执行很短，但调用非常频繁的函数，最好使用内联使函数变为内联的方法在函数声明前加关键字 inline在函数定义...
2018-03-14 15:03:15
428
2
原创 C++回炉之_C++PrimerPlus_第七章 函数 -- C++的编程模块(二)
函数和二维数组使用二维数组作为参数， 必须指定第二维的维数 – 元素的类型表示arr为一个数组名，而数组的每一个元素也是一个数组， 由2个int组成即arr的类型是指向由2个int组成的数组的指向其中的括号必不可少，因为 int *arr[2]表示由2个指向int的指针组成的数组 – 函数参数不能为数组另一种格式 – int sum(int arr[][2], int n);二者...
2018-03-11 22:33:51
341
原创 C++回炉之_C++PrimerPlus_第七章 函数 -- C++的编程模块(一)
函数定义及声明type_name function_name (parament_list) { // 返回值类型 函数名 参数列表 statements; return value; // value的类型为 type_name}#include <iostream>#include <...
2018-03-11 11:11:23
273
原创 C++回炉之_C++PrimerPlus_第六章 分支语句和逻辑运算符
if语句if(test) statement;if(a > b) cout << a << endl;if(test) { statement_1; }else { statement_2;}if(test_1) { statement_1; }else if(test_2) { statement_2; }els...
2018-03-08 18:08:25
179
2
原创 C++回炉之_C++PrimerPlus_第五章 循环和关系表达式
for循环for(init; test; update) { // 初始化; 测试条件; 更新(步长) statement;}for(int i = 0; i < 10; ++i) { cout << i << endl;}for(int i = 0; i <= 10; i += 2) cout &...
2018-03-07 14:07:08
188
原创 C++回炉之_C++PrimerPlus_第四章 复合类型(二)
指针声明和初始化int a = 5;int* p = &a; // & 取地址使用cout << *p << endl; // * 取值指针的危险 空指针 没有指向具有一定意义的内存野指针 指针变量未初始化 – 可手动初始化为nullptr 或 NULL指针释放后之后未置空 – 可手动初始化为null...
2018-03-05 22:39:30
238
原创 C++回炉之_C++PrimerPlus_第四章 复合类型(一)
数组数组的声明 int a[100];typename array_name[array_size];array_size 不能是变量可通过索引(下标)对数组元素进行访问 – 下标范围[0, array_size) a[3] = 100;数组的初始化 int a[4] = { 3, 6, 8, 10};只有创建时才能初始化， 此后便不能使用初始化表初始化了也不能将一个数组赋...
2018-03-04 22:46:45
238
原创 C++回炉之_C++PrimerPlus_第三章 处理数据
变量命名只能使用 字符字母 数字 下划线(_)第一个字符不能为数字不能将C++关键字作为名称区分大小写以两个下划线或下划线和大写字母打头的名称被保留给实现(编译器及其使用的资源)使用以一个下划线打头的名称被保留给实现，用作全局标识符对名称长度无限制， 但C99的限制是63个字符整型short 至少16位int 至少和short一样长long 至少32位, 且至...
2018-03-04 17:24:10
252
原创 C++回炉之_C++PrimerPlus_第二章 开始学习C++
第一滴血// hello.cpp/* This is my first code*/#include <iostream>using namespace std;int main() { cout << "hello world" << endl; return 0;}输出结果 hello world...
2018-03-04 00:15:03
195
原创 C++回炉之_C++PrimerPlus_第一章 预备知识
C ++ 其人诞生 – 20世纪80年代 Bjarne Stroustrup 贝尔实验室发展 – C++98 C++11 性格 – OOP(面向对象) Generic(泛型编程) 后面会展开讲程序创建的技巧使用IDE创建源代码 常用IDE VS(工程党推荐) codeblocks(竞赛党推荐) Xcode(土豪推荐) CodeLite(开源推荐)编译和链接 ...
2018-03-03 23:38:39
252
原创 50行头文件+宏：acm专用 -- 初级版
//#include <bits/stdc++.h>#include <algorithm>#include <iostream>#include <sstream> //stringstream#include <iomanip> //cout输出小数格式#include <utility> //pair#include <bitset> //
2017-09-27 01:02:37
428
原创 单例模式：Singleton Pattern
定义 保证一个类仅有一个实例，并提供一个访问它的全局访问点适用条件 当系统需要某个类只能有一个实例时适用大致有六种写法，每一种写法各有特点： 懒汉 – 线程不安全 懒汉 – 线程安全 懒汉 – 线程安全 – 双检锁(DCL) 懒汉 – 线程安全 – 静态内部类 饿汉 – 线程安全 饿汉 – 线程安全 – 枚举类图实现(java)懒汉 – 线程不安全public class
2017-09-22 09:12:08
234
原创 十进制小数：循环节等问题
小数化为分数 可以化为分数形式的小数有两类：一类是有限小数，一类是无限循环小数。 对于有限小数，我们只要将小数点移到最右，然后除以相应的10的几次方， 最后再约分即可。例如0.1234 就是1234/10000。 而对于无限循环小数，我们先从一个最简单的例子来分析 – 0.(1) , 即0.11111…， 这里使用括号表示最小的循环节， 那么它对应的分数是多少呢？我们很容易得知如果将0.(1
2017-09-21 20:18:29
1242
原创 FFT NTT FWT： 傅立叶变换， 求卷积
原理贴(时间紧迫， 来不及自己整理了， %下大佬) Ichimei FFT算法学习笔记 A神 多项式乘法运算初级版 FFT A神 多项式乘法运算终极版 NTT Picks 讲FWT 咸鱼 Fast Walsh-Hadamard Transform (快速沃尔什变换)模板FFT 递归实现//复数类struct cp { double r, i; cp(
2017-09-12 00:58:59
655
原创 a^b === c (mod p)知二求一: p已知
知a b求c 求x满足ab≡x(modp)a^b \equiv x \pmod p， 即求x=abmodpx = a^b \mod p快速幂。。。LL pow_mod(LL a, LL b, LL p) { LL r = 1; a %= p; while(b) { if(b&1) r = (r*a) % p; a = (a*a) % p;
2017-08-24 13:03:24
3729
原创 Baby Step Giant Step(好奇怪的名字)及其扩展: 求离散对数
定义关于离散对数，请移步至此 => 离散对数:这个好难。。。 Baby Step Giant Step 中文名叫”大步小步算法”，用来求解如下同余方程x的最小正整数解: ax≡b(modp)其中0<=x<pax≡b(modp)其中0<=x<pa^x \equiv b \pmod p\qquad\qquad\qquad 其中0ppp为素数, a、b、pa...
2017-08-21 17:40:21
1972
1
原创 离散对数:这个好难
定义 设g是m的一个原根，对于满足(k, m) = 1 的k, k关于g的离散对数(mod m)定义为一整数t,使gt≡k(modm)g^t \equiv k \pmod m 且t为一个最小剩余(modϕ(m))\pmod {\phi(m)}。 记作indgkind_gk。 //此处可类比整式里的loggklog_gk, 不过这里对ϕ(m)\phi(m)取模了。举
2017-08-17 23:49:39
4131
原创 阶 和 原根
阶定义 设m > 1 且 (a, m) = 1, 则使得at≡1(modm)a^t \equiv 1 \pmod m 成立的最小的正整数t称为a对模m的阶, 记为δm(a)\delta_m(a)。定理 定理1 若m>1且(a, m) = 1, 且an≡1(modm)a^n \equiv 1 \pmod m, n > 0, 则δm(a)|n\delta_m(a)\,|\, n。
2017-08-17 21:19:27
6820
4
原创 欧拉定理 和 欧拉函数
欧拉定理定义 设m >= 2, (a, m) = 1。 若ϕ(m)\phi (m)表示小于m且与m互素的正整数的个数，则有aϕ(m)≡1(modm)a^{\phi(m)} \equiv 1 \pmod m //m不一定为素数 //若m为素数，则ϕ(m)=m−1\phi(m) = m-1, 上式变为费马小定理，即am−1≡1(modm)a^{m-1} \equiv 1 \pmod m
2017-08-17 15:51:59
471
原创 二次同余式(草稿)
原理求解方法实现/*==================================================*\| 二次同余式 x^2 === a (mod p) 的解 -- 最多两个| p为奇素数 且 (a, p) = 1\*==================================================*/LL modSqrt(LL a, LL p) {
2017-08-17 09:52:49
782
原创 威尔逊定理：素数的充要条件
定义 p为素数的充要条件为(p−1)!≡−1≡p−1(modp)(p-1)! \equiv -1 \equiv p-1 \pmod p 也可以说p|(p−1)!+1p\quad|\quad{ (p-1)!+1 }证明 百度百科的证明特别简明易懂 => 点此跳转应用 可以将一些与阶乘有关的同余式和素数联系起来，以解决某些特定的问题 YAPTCHA HDU - 2973 Zb
2017-08-16 19:56:10
1564
原创 费马小定理 ： 求逆元 降幂
定义 若p为素数， (a, p) = 1, 则ap−1≡1(modp)a^{p-1} \equiv 1 \pmod p证明 引理1 若(a, m) = 1, 则a,2a,3a,...,(m−1)aa, 2a, 3a, ..., (m-1)a 的最小剩余(mod m) 按某种次序排列后为1,2,3,...,m−11, 2, 3, ..., m-1 //关于引理1的证明不作赘述，
2017-08-16 15:48:20
729
原创 乘法逆元: 扩展欧几里德 费马小定理 递推 带余数同余式的一般解法
定义 若 a∗x≡1(modp),(a,p)=1a*x \equiv 1 \pmod p, \quad(a, p) = 1 则称x为a的乘法逆元(mod p)。 //其中(a, b) 表示a和b的最大公约数。有解条件正如上面所言，当且仅当a和p互素时，a才有关于p的乘法逆元x。求解方法先总结一些这里要讲的四种情况 1. 拓展欧几里德求逆元 2. 费马小定理求逆元
2017-08-15 17:34:05
894
原创 单调队列 和 单调栈
单调队列定义 有一个队列(双端队列)， 队列中的元素满足下面四种状态的任何一种都为单调队列: 单调递增 (如 1 2 3 5 9) 单调不减 (如 1 2 3 3 5) 单调递减 (如 9 5 3 2 1) 单调不增 (如 5 3 3 2 1) 性质 (以单增队列为例) 插入时，需要将尾部大于此数的全部出队。 删除时，根据需要使队首或者队尾的元素出队(所
2017-08-06 23:42:49
534
原创 HDU - 1506 Largest Rectangle in a Histogram: 单调栈入门题
题目点此跳转思路 题目意思是有一个由许多矩形组成的一个图形(下底对齐)， 求这个图形里能找到的最大矩形的面积, 输入的是各个矩形的高度。 例如下图 很显然，这一题就是要求对于每一个矩形而言，它往左或右最多的比他高的矩形的个数， 也就是说，对于输入的那个数组，我们只要求出每一个元素能往左右延伸到什么地方即可，延伸的定义是不比它小的才行。 使用单调栈是解决这个问题的一个很好的办法。 我们维护一个
2017-08-06 22:14:25
387
原创 POJ - 3017 Cut the Sequence : 单调队列优化dp
题目点此跳转思路 题目意思是给你一个数组， 现在让你将整个数组划分为几个子区间，并且要保证每个子区间的元素和不大于M, 求 每个子区间的最大值 的和 的最小值。 这是一道dp题， 单调队列的一个很大的应用就是可以优化某一类dp。 我们先将它当作一个纯dp题去写状态转移方程，之后再考虑使用单调队列优化。 设 f(i) 为数组A[1, , i]满足条件的每个子区间的最大值的和 的最小值, 则要求的结
2017-08-04 15:03:45
504
1
原创 HDU - 3530 Subsequence : 单调队列
题目点此跳转思路 题目意思是给你一个数组， 求一个最长的子区间的长度，此子区间要满足一个条件:在此区间内的最大值与最小值的差要在[m, k]范围内。 使用两个单调队列分别维护区间的最大值和最小值。 注意队首元素出队的条件: 当最大值的队首减最小值的队首不满足题目要求时，要将两者下标小的出队， 才能保证区间的连续性。而出队之前下标也要记录一下，表示此区间开始的地方。代码int n, m, k, a
2017-08-04 10:55:49
280
原创 HDU - 3415 Max Sum of Max-K-sub-sequence : 单调队列
题目点此跳转思路 题目意思是给你一全环形的数组(头尾相接)， 求所有长度不大于k的区间中 元素和 最大 的的区间 及 最大的元素和。 区间的和可以使用前缀和相减求出，设sum[i]为从0到i的前缀和， 区间[i, j]的和即为sum[j] - sum[i-1]; 那么对于每一个区间尾j,我们只要求出它前面i个内最小的sum[i]即可，显然单调队列是可以解决的。 每次区间尾j右移时，将j所在元素入
2017-08-04 10:44:44
287
原创 POJ - 2823 Sliding Window: 滑动窗口 单调队列
题目点此跳转思路 题目意思是给你一个数组，让你分别求出所有的区间长度为k的区间的最小值和最大值。 Window position Minimum value Maximum value [1 3 -1] -3 5 3 6 7 -1 3 1 [3 -1 -3] 5 3 6 7 -3 3 1 3 [-1 -3 5] 3 6 7 -
2017-08-04 10:14:00
578
原创 UVA - 1608 Non-boring sequences : 分治
题目点此跳转思路 题目意思是如果一个序列的任意连续子序列中至少有一个只出现一次的元素,则称这个序列是不无聊(non-boring)的。输入一个n(n≤200000)个元素的序列A(各个元素均为10 9 以内的非负整数),判断它是不是不无聊的。 分治法 在整个A[1,, n]里找到一个只出现一次的元素,记为A[p],然后以此为分治点, 分别对A[1,, p-1] 和A[p+1,, n]执行同样的操
2017-08-03 20:15:30
322
原创 UVA - 12627 Erratic Expansion : 递归
题目点此跳转思路 题目意思是(书上原话)一开始有一个红气球。每小时后,一个红气球会变成3个红气球和一个蓝气球,一个蓝气球会变成4个蓝气球,如图所示分别是经过0, 1, 2, 3小时后的情况。经过k小时后,第A~B行一共有多少个红气球?例如,k=3,A=3,B=7,答案为14。 需要设出如下变量: g(k, i): k 小时后最下面 i 行的红气球总数 c(k): k 小时后红气球的总数
2017-08-03 20:05:05
210
原创 UVA - 11572 Unique Snowflakes(唯一的雪花) : 滑动窗口
题目点此跳转思路 题目意思是输入一个长度为n（n≤106）的序列A，找到一个尽量长的连续子序列AL～ARA_L～A_R ，使得该序列中没有相同的元素。 首先定义L和R表示要找的结果的左右端点，一开始L = R = 0; 然后我们不断地增加R，直到不能增加了为止，不能增加是因为再增加的话就有相同的元素了; 这个时候我们维护一下最大值，然后开始增加L,直到将那个使R不能再增加的元素去掉为止；
2017-08-01 17:33:57
435
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人