• 等级
  • 15775 访问
  • 37 原创
  • 0 转发
  • 118192 排名
  • 19 评论
  • 6 获赞

2018 ICPC 徐州现场赛

2018ICPC徐州区域赛,这是我第一次参加的ICPC比赛,经过五个小时的奋斗,最后拿了一个铜奖。虽然对于各位dalao这次的题可能并不太难,但是我们队卡到比赛结束也只做出了A题,而且罚时几乎要排到铜尾。不过这次比赛对我来说真的非常有意义,我在ICPC赛场上做出了第一道题,也拿到了第一个ICPC奖项,还收获了很多宝贵的经验。回顾这次的比赛,开局一眼望去就觉得没有水题,我看了下C题和F题的题面,但...

2018-10-29 01:48:58

模板:随机数

随机数思路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\leL\leR0≤L≤R,该条件与数位有关,比如不包含数字444。思路时间复杂度O(log⁡n)O(\logn)O(logn)。实际上为nnn的位数,而nnn的位数可以表示为lg⁡n\lgnlgn,即log⁡nlog⁡10\frac{\logn}{\log10}log10logn​...

2018-10-12 14:16:49

模板:拓扑排序

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

2018-10-08 00:41:12

Android Studio:项目模板

AndroidStudio在新建项目时会根据模板生成初始文件,我们可以修改文件模板。项目模板模板所在目录:AndroidStudio\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.InSearchofanEasyProblem题意对于一道题,每个人进行评分,如果认为困难就给111分,认为简单就给000分。只要有人觉得这道题困难就是难题,问这道题是不是难题。思路记录评分1的数量,若大于0则为难题,否则为简单。B.VasyaandCornfield题意一个平面上有一个矩形和很多个点,...

2018-09-28 15:37:19

模板:逆元

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

2018-09-27 00:37:46

Codeforces Round #511 Div. 2

C题水题没做出来,反而猜对了D题,还好排名变化不大。A.LittleCLoves3I题意给出一个数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.VasyaAndPassword题意多组输入,有一个字符串,修改尽可能少的字符使得字符串中包含大写字母,小写字母和数字,保证存在修改后满足要求的字符串。思路先扫一遍字符串得到大写字母,小写字母和数字的数量。若均大于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\sump_i\times2_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()输出整数。模板非负整数输入/***@paramx:theinputnumber*@other:x>=0;*/voidFR(int&x){x=0;char...

2018-08-17 20:48:27

模板:快速幂

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

2018-08-16 10:35:33

模板:线性筛质数

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

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

模拟退火算法

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

2018-06-05 01:22:44

模板:最大公约数

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

2018-06-01 22:40:15

FantasticGold

关注
  • 中国 广东省 广州市