- 博客(96)
- 资源 (3)
- 收藏
- 关注
RSS订阅
原创 预告/计划
初三过了。一段旅程结束了。暑假开始了。又一段旅程开始了。好吧，初三终于过去了，可以搞信息学了。终于可以连写一个小时博客，刷一天题目，深夜爬起来做比赛了。 那么我想应该在暑假期间将所需要复习的东西再列一个清单。
2017-06-27 10:57:48
994
3
原创 [ARC095F]Permutation Tree
最近刷AtCoder，觉得刷得挺爽的，每次的F题都有一定难度，但是却还是挺可做的>_<反正AtCoder对于我这种英文不好的选手来说非常友善，看一眼就读完题面了题意Takahashi有一种能力以以下步骤用一个排列(p1,p2,⋯,pn)(p1,p2,⋯,pn)(p_1,p_2,\cdots,p_n)来生成一棵树：首先，按照以下操作准备顶点1⋯N1⋯N1\cdot...
2018-04-16 21:29:25
943
原创 [BZOJ2957]楼房重建
貌似已经很久没有写blog了的说……一直在用为知笔记都快忘记博客了emm 这次先拿这样一道水题来写一下吧，这个思想好像很常用，最近这几天已经遇到很多次了。题意一个长度为nnn的序列wiwiw_i表示楼房高度，初始都是000，有mmm个操作，每次单点修改一个位置的高度，可以变成正的也可以变成负的，问有多少个位置能够在每次修改后被看到（也就是说，其最高点与原点连线上没有其他楼...
2018-04-16 19:53:47
343
原创 纪中集训18.01.19 多项式总结
怎么感觉讲的这么快，我好菜啊终于差不多把多项式水过去了……来波总结多项式真好玩1.FFT这里主要搞一个裸的FFT，原理已经讲过了 放个模板跑：# include # include # include # include # define N 262144using namespace std;const double PI=acos(-1);typede
2018-01-19 20:37:26
2989
原创 BZOJ 2716/1648
双倍经验题…… 终于补上k-d tree的题解惹……据说是水分神器题意求平面曼哈顿距离最近点对分析k-d tree模板题，所以裸上就可以了 顺便总结下k-d tree，其实这东西思想非常简单，就是直接分治的结构，每次递归一个维度，然后把这个维度下坐标中位数的点选为子树的根，然后剩下的依序排成两块，递归下去继续做就可以建好树了 具体实现上，建树时可以用nth_el
2018-01-19 08:28:17
8073
原创 纪中寒假集训1.18总结
qaq题目好难啊 不过也还是可以水分的今天做的THUWC模拟，简要放个题解：【A：群】题意求对于大小为nn的置换对于“复合”这一运算a∘ba\circ b所构成的阶为kk的群的个数 1≤n≤1051\leq n\leq 10^5，1≤k≤51\leq k\leq 5分析最近怎么总是遇到群论的题目……之前loj上碰到两道，今天又来…… 这里kk很小，所以可以考
2018-01-18 22:29:52
456
原创 【FAKE-ACM】2017-CCPC-FINAL泛刷总结
感觉这个CCPC-FINAL的题目非常常规啊，感觉不少题目都能很快口胡，作为一个向往WF的OIer，自然要刷刷国内的毒瘤题目来提高下姿势水平辣~ 另外就是我写/看最后几题的时候HDU挂掉了……导致看不了题目
2018-01-02 17:23:34
2425
3
原创 泛刷水题记17.12.27
SHOI的题目质量好高啊，感觉都是些不错的题目……（我都不会做）LOJ 2142「SHOI2017」相逢是问候题意：给定一个序列，在模pp意义下，兹瓷区间对给出的一个常数cc取幂（原来是aia_i，变成caic^{a_i}），以及区间求和的操作，注意pp不一定是质数，ai,c≤p≤108a_i,c\leq p\leq 10^8 分析：一看到模意义，我们马上想到指数循环节，由于am≡am%φ(p)
2017-12-27 20:12:28
508
原创 泛刷水题记17.12.22
目前处于康复期，所以做多一点题目……感觉自己码力退步了QAQ连初二的时候都比不上了（现在连LCT都写不动了……颓颓颓）LOJ 2038 「SHOI2015」超能粒子炮・改 题意：求∑i=0k(ni)(mod2333)\sum\limits_{i=0}^k\binom{n}{i}\pmod{2333}，其中n,k≤1018n,k\leq 10^18 分析：一般组合数取模的题目我们都可以马上想
2017-12-21 22:05:27
336
原创 模板集
KMP：【NOI2014】 动物园# include # include using namespace std;typedef long long ll;const int mod = 1e9+7;const int maxl = 1000010;char s[maxl];int pre[maxl],dep[maxl];void getFail(){ int l = s
2017-10-29 12:28:56
470
原创 17/10/25题目泛做
发现集训题比模拟题画风正常了许多……终于不那么鬼畜了……今天的题目还是可以切的 orz本校神犇%%%zfr AK辣 另外ubuntu pastebin竟然也被封掉了？？那我放不了代码了orz
2017-10-25 16:16:53
428
原创 BZOJ 2440 中山市选2011 完全平方数
这道题目就是问你第k个不是完全平方数正整数倍的数。 好像挺显然的，直接乱搞就好。我们考虑下二分，将问题转化为求函数
2017-09-29 20:40:43
378
原创 生成树计数的MatrixTree定理
在省选级别的题目里面，我们会发现有一类生成树计数的题目。就是给定一个图G={V,E}G=\{V,E\}，问这个图生成树有多少棵（节点和边都不同）。 这里我们可以用基尔霍夫矩阵做。我们定义一个图有度数矩阵AA，有邻接矩阵BB，其中AiiA_{ii}表示节点ii的度数，其余为0，Bij=1B_{ij}=1表示有边(i,j)，反之为00。那么基尔霍夫矩阵就是C=A−BC=A-B 这里先给出结论，生成树
2017-09-23 10:47:49
351
原创 纪中集训8/14题目泛做
今天的题目太水了，但是我没有AK 【A T1：亲戚(Relatives)】 本质上是求一种对树的拓扑排序序列方案数问题，形式化地说，就是给出mm个限制pi<pjp_i<p_j（这里pip_i表示ii在序列中的位置），问长度为nn的排列的方案数。 题目中给的是若干森林然后排列，但是我们直接用0来做一个超级根，就变成树上DP的问题了。我们现在考虑对于一个根，该怎么合并他的儿子。 我们先设f(x)
2017-08-14 17:15:37
409
原创 2017百度之星Astar资格赛 1001度度熊保护村庄
这道题目并不难，但是真的很难想到~一开始我的思路也是各种乱贪心…… 题目链接：http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=774&pid=1001
2017-08-07 15:17:45
843
原创 纪中集训d2 提高A组模拟
这次情况稍微好了点，但是还是各种写跪23333……不得不说，纪中的OIer数学推演能力好像都太好了点，就是讲的课很容易让人听不懂……
2017-08-06 21:56:55
392
原创 纪中集训d1 提高A组模拟
【T1】 这题实际上是大水题……但是脑抽忽略了DP的阶段性特征，而且明明已经写好了搜索却没有想到直接改记忆化……讲的是对于[1,n][1,n]的数的所有排列，有mm个限制，即令某个数要在另一个数后面，问如果违反最多kk个限制，存在多少种方案数，这里用搜索的思路先推一个暴力，记下目前选了的点，同时违反了jj个限制，然后一个记忆化令f(i,j)\text f(i,j)中ii为选了哪些点，用二进制数来记
2017-08-05 19:37:59
504
1
原创 浴谷夏令营第一期 d2上午例题分析
好的，这一次这个浴谷的夏令营我参加主要是为了各种练手，毕竟初三几乎半年多没有打过程序啦……这里先放一些简要的分析。 【例1.1】 这道题目可以无脑做，比如用直接埃氏筛法筛出足够质数，然后再枚举一个H-质数（先设为ii），然后再枚举na\frac{n}{a}，反正数据范围太小。由于是质数，所以规模平均下来甚至是logn\log n级别的…… 另外打表也是可以的。 【例1.2】 和上面那个用到
2017-08-01 23:50:50
633
翻译 USACO 2017 US OPEN PLATINUM题目翻译（未完）
Problem 1. Modern Art 世界各地的现代批评家们刚刚才开始认识到毕牛索，这位伟大的牛画家的富有创造力的天分。 毕牛索使用一种非常特殊的绘画方法。她首先从一面N×NN\times N的空白画布开始，这用一个N×NN\times N的零方阵代表，其中00表示画布上一个空白的格子。然后她在画布上画下N2N^2个矩形，各自用N2N^2种颜色中的任何一种。举个例子，他有可能先用颜色2画一
2017-08-01 21:42:40
779
原创 替罪羊树
平衡树，是平衡的二叉排序树，精确地说，是有一定限度下的平衡。在信息学竞赛中平衡树是一个相当重点的数据结构，而绝大多数的平衡树都是需要旋转的。比如说AVL树和红黑树是两个要在节点上附带信息的带旋转平衡树，这两种平衡树效果不错，但是写起来有点麻烦（貌似AVL树有六种情况需要旋转，红黑树中的删除操作似乎有更多的旋转情况），而SBT（Size Balanced Tree，子树大小平衡树）虽然写起来挺简单的
2016-09-28 13:53:26
4959
4
原创 强连通分量
强连通分量仍然是信息学中的基础内容，在图论中和连通分量一样都是相当重要的东西。而强连通分量类型的题不知为什么出现频率很高，比如缩环什么的，考了好多次……
2016-08-13 14:38:50
1455
原创 后缀树与后缀数组
后缀树和后缀数组是字符串处理的两大神器，几乎可处理掉一切的字符串处理问题，但是在实际中，后缀数组比后缀树更好写、好调，同时时间上也不差（常数很小），所以后缀数组绝对是OI竞赛之必备神器。
2016-08-12 11:14:36
2038
原创 Manacher算法详解
Mancher算法如今已是一个常被涉及的的算法，主要适用于和回文串相关的一些题目，虽然说不常用（对于OI的其他算法而言），但却是一个很重要的算法。
2016-08-08 09:45:30
1356
4
原创 KMP(MP)算法详解
Written with StackEdit. 由于CSDN服务器的维护，我迫不得已地用了和CSDN版本相近的StackEdit.KMP算法，是一种字符串匹配的算法。当然，我们已经学过了一两种字符串匹配算法，先来稍微回顾一下。
2016-08-07 18:44:31
3313
7
原创 状态压缩的动态规划
状态压缩的动态规划，简称状压DP，是一种将DP和枚举结合起来的方法，可以说是枚举的一种巧妙的优化。 简单来说，如果我们能够划分状态，但是很难继续细分(或者说是状态中的元素都彼此有关，但没有明显的规律)，比如说可以将方阵按行划分，但是每行中的每个元素间都有一定的关系时，就可以枚举每一行的状态，再进行DP。也就是说，将状态的表示也作为DP状态表示的一(或几)维，然后相应的进行转移。这真是一个革命性的想
2016-08-05 18:52:43
1317
原创 2016-8-4夏令营入营测试总结
本次的测试从思维和编程角度上来说都是很简单的，然而在时间上却并不简单。虽然说我们现在的水平已经相当不错，但是考的仍然不是很好，估计是久离算法的缘故了。题目的链接是http://pan.baidu.com/s/1hrIQMry。
2016-08-05 07:28:17
1030
原创 方案数（fas）程序
具体题解请参考《NHOI2016简单分析》，程序如下：# include <algorithm># include <cstring># include <cstdio>using namespace std;const int MAXN = 100010;const int MAXC = 25;const int MOD = 10007;int T[MAXN*2][MAXC];in
2016-06-05 11:36:01
892
原创 NHOI2016简要分析
话说这次考崩了……本来很容易就能够考到第二的……但是第一题没有用long long然后就只剩15分了……另外最后一题更加神奇地没有搞到分数……本来我推出了30%数据的一个暴力递推式，但是没有搞对……不过考完之后5分多钟就知道怎么回事了。如果中途车不出问题就可以做出来了吧……好吧，话不多说，先上分析： 【T1：购书】 应该来说相当容易……但是我没有发现数据规模的问题。其实注意用一下64
2016-05-26 13:53:42
1574
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人