2 Messhiro

尚未进行身份认证

学习计算机技术的渣新

等级
博文 16
排名 107w+

2018acm/icpc西安邀请赛总结

比赛一如既往还是在仙工大举办~Day1今天开始下了点小雨,作为第一次正式参加邀请赛(口胡,上一次不算,连门都没入就去了),虽说也来过这儿几次了,但这一次并不打算住在这儿(万恶的xx酒店)。今年参加邀请赛的队伍比去年多了很多,大概有将近400支队伍了,其中当然有要来屠榜的三大名校(西工大附中,西铁一中,高新一中),被誉为西安地界最强的中学生2333省赛依旧还是在机房举行,热身赛的话不太友好(尽管我也...

2018-05-23 20:30:41

区间专题(一)、分块及莫队算法

邀请赛之前可能只会更这一次了吧QAQ久闻莫队算法的大名,号称是“可以解决任何区间问题”的算法,今天就来稍微说一下莫队算法。这个算法是一位名叫莫涛的国家队队长发明的算法,所以尊称为莫队算法莫队的原版文章里面的题目有一定难度,所以可以先看一下这道例题:Description   有n个数字,给出k,以及m个查询。  每次查询的格式是L,r,求L~r(左右包含)这个区间内数字的出现次数刚好是k的数...

2018-05-14 21:20:14

数学专题(三)、欧几里得与扩展欧几里得

五一之前再更一发,话说要为今年的邀请赛做准备了,但是我还什么都不会啊QAQ今天主要更Euclid这个人发明的算法。欧几里得算法(EuclideanAlgorithm),又称辗转相除法,是用来求解两个数的最大公约数的一种算法。其主要的思想是,设有正整数a,b,不妨令a>b,且amodb≠0.gcd(a,b)=gcd(b,amodb),证明如下:由于amodb≠0,设a...

2018-05-02 14:46:14

字符串(一)、字符串Hash

今天开一手最不(tao)擅(yan)长的字符串算法:字符串Hash算法。似乎提到字符串的话,KMP应该是更为常见的一种,但是hash有它的优点,被犇们称为“优雅的暴力”。何谓hash?hash的中文称为哈希,这当然是音译,直译过来就是散列,或者也有叫预映射的。哈希的作用就是通过某个特殊函数的映射,将任意长度的输入映射为固定长度的输出。而字符串哈希涅,顾名思义当然就是把字符串转换为整数的函数。但是有...

2018-04-27 13:07:49

POJ 2777 Count Color

这两天在练习各种线段树,于是就继续更一道线段树的题目QAQ题面如下:CountColorTimeLimit:1000MS MemoryLimit:65536KTotalSubmissions:49616 Accepted:14946DescriptionChosenProblemSolvingandProgramdesignasanoptionalcourse,...

2018-04-20 21:54:58

CodeForces 762C Two strings

今天补一下前天的一道题,我果然是太菜了TAT题面如下:C.TwostringsYouaregiventwostringsaandb.Youhavetoremovetheminimumpossiblenumberofconsecutive(standingoneafteranother)charactersfromstringbinsuch...

2018-04-18 21:58:18

POJ-2823 Sliding Window

这是我的第一发题解,纪念一下233题面如下:Anarrayofsizen≤106isgiventoyou.Thereisaslidingwindowofsizekwhichismovingfromtheveryleftofthearraytotheveryright....

2018-04-17 21:30:03

高级数据结构(2)、ST表

时隔多年,我又来更新了233昨天听雨神讲了一发差分/树上差分的问题,并且提到了LCA的求法,于是今天先决定更一发RMQ问题,然后过两天再更LCA的问题QAQRMQ(RangeMinimum/MaximumQuery),即区间最值查询问题。该问题描述的是在一个数组上,如何快速地求出给定区间[L,R]的最值的问题。例如对于给定数组[3,2,4,5,6,8,1,...

2018-04-16 17:36:13

图论(1)、最短路径

图论是离散数学中比较重要的一个分支;而图,恰好又是计算机中最重要的数据结构。所以今天开一个图论专题。说道图,最先想到也是最常用的,自然就是怎样求最短路径。我们常说的最短路径指的是单源最短路径。常见的解决单源最短路径问题的算法有Dijkstra算法和Bellman-Ford算法。这两种算法都是基于动态规划思想实现的,所以这两个算法都有一个核心操作,就是松弛(Relax)。但是它们适用的范围不太一样。...

2018-03-15 18:00:38

数学专题(2)、快速幂

嗯,今天是快速幂专题。相信大家应该都会求幂,即求a^n.那么这个东西有什么可讲的呢?当然有!朴素的幂计算复杂度是O(n)的,而我们的快速幂则能够达到O(logn)级别。可能你会觉得线性复杂度已经够快了,但是在实际应用中,你就会发现快速幂的高效之处。那什么是快速幂呢?快速幂就是在计算a的b次方的时候,把b写成二进制和的形式。比如说计算a^43,我们就可以把43写成二进制数101011,每一位乘以对应...

2018-03-08 16:42:31

数学专题(1)、基础数论

好久没更博客,今天更一发数论。题目和表述部分来自数一小姐姐,还望不要打我233333数论是数学的一个重要分支,主要研究的是整数的性质。今天讲一下数论里面比较重要的几个东西。1、素数筛;2、欧拉函数与欧拉定理;3、快速幂;4、米勒罗宾、rho、费马小定理等一系列balabala的定理。关于数论有一些基本概念在此就不强调了,如GCD,LCM,同余,欧几里得算法等,如不清楚可以先去了解一下。素数筛素数,...

2018-03-07 21:06:21

DP进阶(1)、状压DP

关于DP的入门之前已经说过了,所以就不再赘述。DP进阶系列会选取DP的一些难度较大的部分进行探讨,有状压DP、概率DP、树型DP、DP优化,包括斜率优化、FFT加速等。今天主讲状压DP。我们都知道,DP的关键点在于“状态”。而这个状态就是用一组参数来表达的。状态压缩的作用就是将高维的状态压缩成低维的状态,从而能够简化我们的计算。常见的状态压缩就是二进制压缩。部分材料来自艾神赞助,感谢艾吉奥(づ ̄...

2018-03-06 16:08:40

高级数据结构(1)、线段树与树状数组

鉴于去年西安赛区被吐槽为线段树专题赛区,就先更一发线段树2333333线段树(SegmentTree)本质上来讲是一棵二叉搜索树。它与区间树类似,它的每一个结点都是一段区间。线段树的功能是快速查找某个结点在若干线段中出现的次数,时间复杂度为O(logn),单纯空间复杂度为O(2n)。实际应用中,为了避免越界一般来说开4n的数组。树状数组(BinaryIndexedTree(B

2018-02-05 19:06:05

基础算法(3)、搜索与模拟

搜索(search)也是计算机常见的一种操作。常见的搜索有深度优先搜索(DFS)和广度优先搜索(BFS)。而不管是深搜还是广搜,实际上都隶属于图论中的算法。深搜的基本思路如下:1、访问结点2、对与其关联的点进行深搜直至所有的结点均被访问过3、若图中尚有结点未被访问,则从此开始继续深搜深搜被发明的时候,人们常用它来寻找迷宫的解,事实上,广搜也可以达到相同的目的。广搜的思路如下:

2018-02-04 18:33:46

基础算法(2)、分治

分治(divideandconquer)分治是一种常见的解决复杂问题的算法。它将一个庞大的难以解决的问题分解为若干个小的相同子问题,直到方便求解为止。解决之后再将答案合并起来,得到最终的解。在计算机科学中有许多应用,如快速排序、归并排序,快速傅里叶变换(FFT),解决矩阵乘法的Strassen算法等。在CLRS上,有一道使用分治算法的经典计算几何例题,即

2018-02-01 23:17:11

基础算法(1)、有技巧的枚举

实际上,枚举是计算机科学中最常使用的一种算法,几乎所有问题都可以通过枚举来解决。那为什么我们还要发明别的算法呢?因为CPU的运算速度有限,内存容量有限。如果计算速度无限快,内存无限大,那么我们发明算法就没有任何必要了。本文谈论的枚举是在基础枚举之上,通过一些特殊的技巧,给我们的枚举剪枝,从而达到优化时间复杂度或空间复杂度的目的。枚举的技巧有折半枚举、树上差分等,今天主要讲折半枚

2018-01-31 19:11:16
奖章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!