- 博客(16)
- 收藏
- 关注
RSS订阅原创 2018acm/icpc西安邀请赛总结
比赛一如既往还是在仙工大举办~Day1今天开始下了点小雨，作为第一次正式参加邀请赛（口胡，上一次不算，连门都没入就去了），虽说也来过这儿几次了，但这一次并不打算住在这儿（万恶的xx酒店）。今年参加邀请赛的队伍比去年多了很多，大概有将近400支队伍了，其中当然有要来屠榜的三大名校（西工大附中，西铁一中，高新一中），被誉为西安地界最强的中学生2333省赛依旧还是在机房举行，热身赛的话不太友好（尽管我也...
2018-05-23 20:30:41
1775
原创 区间专题（一）、分块及莫队算法
邀请赛之前可能只会更这一次了吧QAQ久闻莫队算法的大名，号称是“可以解决任何区间问题”的算法，今天就来稍微说一下莫队算法。这个算法是一位名叫莫涛的国家队队长发明的算法，所以尊称为莫队算法莫队的原版文章里面的题目有一定难度，所以可以先看一下这道例题：Description 有n个数字，给出k，以及m个查询。 每次查询的格式是L，r，求L~r（左右包含）这个区间内数字的出现次数刚好是k的数...
2018-05-14 21:20:14
942
原创 数学专题（三）、欧几里得与扩展欧几里得
五一之前再更一发，话说要为今年的邀请赛做准备了，但是我还什么都不会啊QAQ今天主要更Euclid这个人发明的算法。欧几里得算法（Euclidean Algorithm），又称辗转相除法，是用来求解两个数的最大公约数的一种算法。其主要的思想是，设有正整数a，b，不妨令a＞b，且a mod b≠0. gcd( a , b )=gcd( b , a mod b )，证明如下：由于a mod b≠0，设a...
2018-05-02 14:46:14
273
原创 字符串（一）、字符串Hash
今天开一手最不（tao）擅（yan）长的字符串算法：字符串Hash算法。似乎提到字符串的话，KMP应该是更为常见的一种，但是hash有它的优点，被犇们称为“优雅的暴力”。何谓hash？hash的中文称为哈希，这当然是音译，直译过来就是散列，或者也有叫预映射的。哈希的作用就是通过某个特殊函数的映射，将任意长度的输入映射为固定长度的输出。而字符串哈希涅，顾名思义当然就是把字符串转换为整数的函数。但是有...
2018-04-27 13:07:49
603
原创 POJ 2777 Count Color
这两天在练习各种线段树，于是就继续更一道线段树的题目QAQ题面如下：Count ColorTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 49616 Accepted: 14946DescriptionChosen Problem Solving and Program design as an optional course, ...
2018-04-20 21:54:58
165
原创 CodeForces 762C Two strings
今天补一下前天的一道题，我果然是太菜了TAT题面如下：C. Two stringsYou are given two strings a and b. You have to remove the minimum possible number of consecutive (standing one after another) characters from string b in such ...
2018-04-18 21:58:18
324
原创 POJ-2823 Sliding Window
这是我的第一发题解，纪念一下233题面如下： An array of size n ≤ 10 6 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right....
2018-04-17 21:30:03
165
原创 高级数据结构（2）、ST表
时隔多年，我又来更新了233昨天听雨神讲了一发差分/树上差分的问题，并且提到了LCA的求法，于是今天先决定更一发RMQ问题，然后过两天再更LCA的问题QAQRMQ（Range Minimum/Maximum Query），即区间最值查询问题。该问题描述的是在一个数组上，如何快速地求出给定区间[ L , R ]的最值的问题。例如对于给定数组[ 3 , 2 , 4 , 5 , 6 , 8 , 1 , ...
2018-04-16 17:36:13
222
原创 图论（1）、最短路径
图论是离散数学中比较重要的一个分支；而图，恰好又是计算机中最重要的数据结构。所以今天开一个图论专题。说道图，最先想到也是最常用的，自然就是怎样求最短路径。我们常说的最短路径指的是单源最短路径。常见的解决单源最短路径问题的算法有Dijkstra算法和Bellman-Ford算法。这两种算法都是基于动态规划思想实现的，所以这两个算法都有一个核心操作，就是松弛（Relax）。但是它们适用的范围不太一样。...
2018-03-15 18:00:38
485
原创 数学专题（2）、快速幂
嗯，今天是快速幂专题。相信大家应该都会求幂，即求a^n.那么这个东西有什么可讲的呢？当然有！朴素的幂计算复杂度是O(n)的，而我们的快速幂则能够达到O(logn)级别。可能你会觉得线性复杂度已经够快了，但是在实际应用中，你就会发现快速幂的高效之处。那什么是快速幂呢？快速幂就是在计算a的b次方的时候，把b写成二进制和的形式。比如说计算a^43,我们就可以把43写成二进制数101011，每一位乘以对应...
2018-03-08 16:42:31
353
原创 数学专题（1）、基础数论
好久没更博客，今天更一发数论。题目和表述部分来自数一小姐姐，还望不要打我233333数论是数学的一个重要分支，主要研究的是整数的性质。今天讲一下数论里面比较重要的几个东西。1、素数筛；2、欧拉函数与欧拉定理；3、快速幂；4、米勒罗宾、rho、费马小定理等一系列balabala的定理。关于数论有一些基本概念在此就不强调了，如GCD，LCM，同余，欧几里得算法等，如不清楚可以先去了解一下。素数筛素数，...
2018-03-07 21:06:21
379
原创 DP进阶（1）、状压DP
关于DP的入门之前已经说过了，所以就不再赘述。DP进阶系列会选取DP的一些难度较大的部分进行探讨，有状压DP、概率DP、树型DP、DP优化，包括斜率优化、FFT加速等。今天主讲状压DP。我们都知道，DP的关键点在于“状态”。而这个状态就是用一组参数来表达的。状态压缩的作用就是将高维的状态压缩成低维的状态，从而能够简化我们的计算。常见的状态压缩就是二进制压缩。部分材料来自艾神赞助，感谢艾吉奥(づ￣ ...
2018-03-06 16:08:40
355
原创 高级数据结构（1）、线段树与树状数组
鉴于去年西安赛区被吐槽为线段树专题赛区，就先更一发线段树2333333线段树（Segment Tree）本质上来讲是一棵二叉搜索树。它与区间树类似，它的每一个结点都是一段区间。线段树的功能是快速查找某个结点在若干线段中出现的次数，时间复杂度为O(logn)，单纯空间复杂度为O(2n)。实际应用中，为了避免越界一般来说开4n的数组。树状数组(Binary Indexed Tree(B
2018-02-05 19:06:05
341
原创 基础算法（3）、搜索与模拟
搜索（search）也是计算机常见的一种操作。常见的搜索有深度优先搜索（DFS）和广度优先搜索（BFS）。而不管是深搜还是广搜，实际上都隶属于图论中的算法。深搜的基本思路如下：1、访问结点2、对与其关联的点进行深搜直至所有的结点均被访问过3、若图中尚有结点未被访问，则从此开始继续深搜深搜被发明的时候，人们常用它来寻找迷宫的解，事实上，广搜也可以达到相同的目的。广搜的思路如下：
2018-02-04 18:33:46
415
原创 基础算法（2）、分治
分治（divide and conquer）分治是一种常见的解决复杂问题的算法。它将一个庞大的难以解决的问题分解为若干个小的相同子问题，直到方便求解为止。解决之后再将答案合并起来，得到最终的解。在计算机科学中有许多应用，如快速排序、归并排序，快速傅里叶变换（FFT），解决矩阵乘法的Strassen算法等。在CLRS上，有一道使用分治算法的经典计算几何例题，即
2018-02-01 23:17:11
261
原创 基础算法（1）、有技巧的枚举
实际上，枚举是计算机科学中最常使用的一种算法，几乎所有问题都可以通过枚举来解决。那为什么我们还要发明别的算法呢？因为CPU的运算速度有限，内存容量有限。如果计算速度无限快，内存无限大，那么我们发明算法就没有任何必要了。本文谈论的枚举是在基础枚举之上，通过一些特殊的技巧，给我们的枚举剪枝，从而达到优化时间复杂度或空间复杂度的目的。枚举的技巧有折半枚举、树上差分等，今天主要讲折半枚
2018-01-31 19:11:16
284
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人