• 等级
  • 9053 访问
  • 36 原创
  • 0 转发
  • 122987 排名
  • 19 评论
  • 6 获赞

模板:随机数

随机数 思路1 在C++中,生成随机数的函数为rand(),返回一个不大于RAND_MAX的非负数。但是,如果生成随机数的种子和生成的次数相同,那么生成的随机数相同,因此rand()只能生成伪随机数。为了尽量得到真随机数,每次应该取不同的种子,由于time(NULL)返回从1970.1.1/00:00到现在的秒数,可以采用srand(time(NULL))。因为程序运行非常快,两次取随机数的间隔可...

2018-10-12 18:52:19

模板:数位DP

数位DP 问题 求区间[L,R][L, R][L,R]中满足条件的数有多少个, 0≤L≤R0 \le L \le R0≤L≤R,该条件与数位有关,比如不包含数字444。 思路 时间复杂度 O(log⁡n)O(\log n)O(logn)。实际上为nnn的位数,而nnn的位数可以表示为lg⁡n\lg nlgn,即log⁡nlog⁡10\frac {\log n}{\log 10}log10logn​...

2018-10-12 14:16:49

模板:拓扑排序

拓扑排序 定义 将一个有向无环图的所有顶点排成一个线性序列,满足所有单向边都由序号小的顶点指向序号大的顶点,这就是拓扑排序。 思路 计算所有顶点的入度,将入度为000的顶点排在前面,即序号较小的位置,然后删去这些顶点以及连接的边,再从剩下的顶点中选取入度为000的顶点排序,不断循环直到所有顶点均分配好序号。因为当顶点被分配序号时入度为000,即所有指向该顶点的边均来自序号更小的顶点,所以按序号形成...

2018-10-08 00:41:12

Android Studio:项目模板

Android Studio在新建项目时会根据模板生成初始文件,我们可以修改文件模板。 项目模板 模板所在目录:Android Studio\plugins\android\lib\templates 下面我将修改三个文件,分别是NewAndroidProject\root\build.gradle.ftl,NewAndroidModule\root\build.gradle.ftl和projec...

2018-09-28 16:49:00

Codeforces Round #512 Div. 2

本以为E题不可做,结果一看答案代码倒是不难写,思路很巧妙。 A. In Search of an Easy Problem 题意 对于一道题,每个人进行评分,如果认为困难就给111分,认为简单就给000分。只要有人觉得这道题困难就是难题,问这道题是不是难题。 思路 记录评分1的数量,若大于0则为难题,否则为简单。 B. Vasya and Cornfield 题意 一个平面上有一个矩形和很多个点,...

2018-09-28 15:37:19

模板:逆元

逆元 定义 一个数aaa的倒数a−1a^{-1}a−1满足a×a−1=1a \times a^{-1} = 1a×a−1=1。取aaa的逆元(amod  b)−1(a \mod b)^{-1}(amodb)−1满足(amod  b)×(amod&amp

2018-09-27 00:37:46

Codeforces Round #511 Div. 2

C题水题没做出来,反而猜对了D题,还好排名变化不大。 A. Little C Loves 3 I 题意 给出一个数nnn,要求取三个不为333倍数的数a,b,ca, b, ca,b,c,满足a+b+c=na+b+c=na+b+c=n。 思路 若nnn模333得000或111,则取a=1,b=1,c=n−2a=1, b=1, c=n-2a=1,b=1,c=n−2;否则取a=1,b=2,c=n−3a=...

2018-09-23 17:58:12

Educational Codeforces Round 51 Div. 2

前四题比较水,E题写出来有BUG最后没时间调试了,赛后才AC。 A. Vasya And Password 题意 多组输入,有一个字符串,修改尽可能少的字符使得字符串中包含大写字母,小写字母和数字,保证存在修改后满足要求的字符串。 思路 先扫一遍字符串得到大写字母,小写字母和数字的数量。若均大于000,则不修改;若两种字符的数量大于000,则取其中一种数量大于111的字符,取一位修改为剩下的字符,...

2018-09-21 15:11:24

Codeforces Round #510 Div. 2

最近一直在Codeforces打比赛,总体感觉Codeforces的题目比LeetCode的质量更高。我现在是大概能做3—4题的水平,只记录我已经AC的题。 A. Benches 题意 有一个数组,将一个数任意分配加给数组中的数,求数组中最大的数的最小可能值和最大可能值。 思路 对原数组中最大的数加上分配的数即为最大可能值;考虑将所有数加到和原数组中最大的数一样,若需要的数大于分配的数,则最小可能...

2018-09-20 08:37:08

模板:矩阵快速幂

矩阵快速幂 功能 快速计算矩阵AAA的bbb次方幂 思路 将快速幂算法中的乘法运算替换为矩阵乘法。若将bbb表示为∑pi×2i∑pi×2i\sum p_i \times 2_i,则AbAbA^b可以表示为∏(A2i)pi∏(A2i)pi\prod (A^{2^i})^{p_i},其中pipip_i表示bbb的二进制从右往左第iii位数字。 时间复杂度 O(logn)O(log⁡n)O(...

2018-08-17 22:15:21

模板:快速输入输出

快速输入输出 功能 对于大量数据进行快速输入输出。 思路 利用getchar()代替scanf()输入整数,利用putchar()代替printf()输出整数。 模板 非负整数输入 /** * @param x: the input number * @other: x >= 0; */ void FR(int& x) { x = 0; char...

2018-08-17 20:48:27

模板:快速幂

快速幂 功能 快速计算ababa^b 思路 若将bbb表示为∑pi×2i∑pi×2i\sum p_i \times 2^i,则ababa^b可以表示为∏(a2i)pi∏(a2i)pi\prod (a^{2^i})^{p_i},其中pipip_i表示bbb的二进制从右往左第iii位数字。 时间复杂度 O(logn)O(log⁡n)O(\log n) 测试 HDU:1061 模板...

2018-08-16 10:35:33

模板:线性筛质数

线性筛质数 功能 输出从000到100000010000001000000的所有质数。 思路 首先000和111不是质数,从222开始逐个判断是否为质数。如果ttt为质数,那么对于任意正整数kkk,k×tk×tk \times t不是质数,因此可以将k×tk×tk \times t筛去。如果ttt已经被筛去,那么ttt不是质数,但仍然要将k×tk×tk \times t筛去。为了避免重复筛...

2018-07-07 10:55:13

模板:连续整数因数求和

连续整数因数求和 功能 设f(x)f(x)f(x)为xxx所有因数的和。输入正整数nnn,输出∑ni=1f(i)∑i=1nf(i)\sum^n_{i=1} f(i)。 思路 对于任意整数ttt,每连续ttt个数的因数中有且仅有一个为ttt,因此从111到nnn的所有因数中共有⌊nt⌋⌊nt⌋\lfloor\frac {n}{t}\rfloor个ttt。若从111到nnn的所有因数中ttt的...

2018-07-07 09:33:59

模板:大数加法

对于无法用int类型甚至long long int类型表示的大整数,可以用数组来存储,那么大数的运算就需要手动实现。 大数加法 功能 输入两个大数a和b,输出a+b。 思路 从低位到高位逐位相加,并记录进位,若最高位有进位,则位数加1。必须保证a和b的最高位之前为0,这样在相加时无需根据a和b的位数分类讨论。 时间复杂度 O(n) 模板 const int B = 1...

2018-07-01 01:33:04

多周期CPU仿真

经过单周期CPU的洗礼,我们接下来要做的就是多周期CPU了。因为有很多单周期的代码可以复用,所以多周期写起来没有那么困难。 多周期CPU原理 多周期CPU就是指一条指令在多个时钟周期内完成,本身并不涉及多级流水线的设计,所以执行指令的性能反而不如单周期CPU。不过每一条指令在不同的时钟周期完成不同的阶段,因此执行指令的流程会更容易理解。每一条指令最多包含以下五个阶段: 1. 取指令:sI...

2018-06-19 21:33:55

单周期CPU仿真

之前的几周我们做了单周期CPU仿真的实验,虽然一开始做得一脸懵逼,但最后还是成功实现了一个简单的CPU。 单周期CPU原理 单周期CPU指的是一条指令的执行在一个时钟周期内完成,无论是哪种指令。处理指令有以下五个步骤: 1. 取指令:从PC取出下一条指令的地址并读取指令。 2. 指令译码:根据指令产生各种控制信号。 3. 指令执行:根据控制信号执行指令。 4. 存储器访问:读写存储...

2018-06-09 20:17:27

模拟退火算法

之前觉得模拟退火算法是很高大上的存在,一直没有去了解。然后上次数模校赛我们就用到了模拟退火算法,发现思路其实并不复杂。 模拟退火算法 模拟退火(Simulated Annealing),来源于热力学上的退火现象。退火现象就是,将固体加温再徐徐冷却,最后在常温时就会呈现晶体状态。从微观角度来看,固体加温时,内部粒子趋于无序,内能增大;徐徐冷却时,粒子趋于有序,内能减小,在每个温度都达到平衡态;最...

2018-06-05 01:22:44

模板:最大公约数

很快ACM校集训队要选拔了,想学一波算法,顺便记下模板。 最大公约数 功能 输入两个数a和b,输出a和b的最大公约数. 最大公约数: 1. 既可以整除a,也可以整除b的数,组成集合C 2. 集合C中的最大元素,即最大公约数 思路 辗转相除法: 1. 用a和b中较大值max除以较小值min 2. 若整除,则结果为min 3. 若不整除,则令a和b分别等于min和余数mod,递归...

2018-06-01 22:40:15

2018年数学建模校赛

最近每个周末都有好多作业,上周趁有空就参加了数学建模校赛,就用今年“深圳杯”数学建模挑战赛作题目。连续打了两天,最后已经没有时间做结果分析了,写的论文也不算理想,不过我觉得模型做得还不错,所以想记录一下。 我们选了B题——无线回传拓扑规划,其实就是一道图论题,重点是设计算法。题目输入为1000个节点的位置,用经纬度表示,输出为各节点的布置、连接关系以及总体成本。题目限制各节点只能为宿主站或者子站...

2018-05-23 15:37:51

FantasticGold

关注
  • 中国 广东省 广州市
奖章
  • 持之以恒