- 博客(107)
- 收藏
- 关注
RSS订阅
原创 计数dp小结
序：除了刚开始的看了几道题的题解，后来也自己肛出了几道 剩下不可做的题不也没做吗 这些题目最大的特点是在于需要自己构造状态，这往往会成为一道题的最大卡点 穷举表示水不到几分题目选讲： E： 如果直接模拟，复杂度为k∗n2k*n^2 既然每一步只能往上下或往左右走， 那么我们可以把题目分解为在x轴上行走k步与在y轴上行走k步的方案数都处理出来 k∗nk*n 然后枚举往左右走i步，往
2017-11-01 18:11:58
1085
原创 期望dp小结
前言：期望dp状态的定义是较为显然的，但对于状态的转移往往需要一些公式的推导。关键的几点是状态之间的互通性，和状态转移的花费，以及转移的概率解决期望dp的几个技巧如下：一.利用期望的线性性质：E[X+Y]=E[X]+E[Y]E[X+Y]=E[X]+E[Y] 我们所求的期望可以化为多个步骤的期望累和 相关题目:J,L二.采用逆序的方式：在目标确定的情况下，可以得知在目标到达目标的期望值为0，然后根
2017-10-31 22:21:57
1305
2
原创 区间dp小结
序：这次的专题刷得很蛋疼有趣 各种大神代码和题解 区间dp，异于普通的线性dp，它的转移往往是建立于不同的规则上且诡异复杂的 区间dp的解题要点是找到一种转移使得我们能够得到最优解HDU4283 因为要保持栈的合法，所以不能排序乱排瞎搞 取一段区间，可以保证区间的做端点能在该区间的任意点后出去 那么利用这一点，就可以来更新区间for(int i=1;i<=n;i++){ sca
2017-10-28 21:47:26
380
原创 概率dp小结
序：感觉概率什么的相比于其他的dp还是较为容易的 几乎都是线性的解决概率问题的关键在于利用独立性对概率进行处理（乘乘加加）A：显然概率不能作为下标，那么就把钱数作为下标（由于总钱数<=10000） 然后贪心地取最小被抓概率 状态转移方程为dp[i]=min(dp[i],dp[i−V[i]]∗P[i])dp[i]=min(dp[i],dp[i-V[i]]*P[i]) P[i]为被抓概率，V[i
2017-10-26 11:27:45
326
原创 深搜专题小结
前言：花了三天，终于刷完了深搜专题的所有题目 纯看题解，copy代码 剪枝的方式有很多 从大的方面讲，会有两大类： 1.可行性剪枝 2.最优性剪枝关于可行性剪枝的几种实现方法： 1.上下界剪枝 1）前缀和预处理 2）dp预处理 3）直接估计 2.奇偶剪枝 总而言之就是根据枚举方案是否与目标有冲突，或无法实现 有些可以在枚举前就预测出来，如能否整除什么的 有些需要在过程中实现
2017-10-17 17:29:26
360
原创 NOIP复赛模板及技巧积累（不定期更新）
一.对拍新建 1.bat，然后编辑:loopdate.exepro.execheck.exefc pro.out check.outif %errorlevel%==0 goto loop二.考试须知1.内存（小心开炸，爆零）若使用了结构体 可在主函数中：printf("%lf\n",sizeof(P30)/1024.0/1024);2.两数相
2017-09-21 22:12:41
895
原创 STL数据结构小结
STL数据结构**1.队列 queue –> 优先队列 priority_queue 2.栈 stack 3.向量 vector 4.双向链表 list 5.集合 set –> 可重复集合 multiset 6.映射map**队列先进先出 push(x) 将x加入队列 pop( ) 将第一位移除队列 front( ) 队头元素 back( ) 队尾元素 size(
2017-09-16 13:22:48
406
原创 排序算法小结
各种排序一.稳定排序 1.记数排序 2.基数排序 3.插入排序 4.冒泡排序 5.归并排序 6.希尔排序 二.不稳定排序 1.选择排序 2.快速排序 3.堆排序计数排序int cnt[105],A[105],B[105];void sort(int n){ FOR(i,1,n){ int x; scanf("%d",&A[i]);
2017-09-15 21:10:29
414
原创 莫比乌斯系数的筛法
利用线性筛完成的莫比乌斯系数（函数）的推导 注意mu[1]=1;void init(){ mu[1]=1; FOR(i,2,M-1){ if(!mark[i])prime[++cnt]=i,mu[i]=-1; for(int j=1;j<=cnt;j++){ int t=i*prime[j]; i
2018-01-06 20:05:32
538
原创 线性筛
线性筛O（n） 推导一下复杂度： 对于第二重循环 可发现30=2*3*5是由15=3*5推出来的 有一个数的最小质数为x 则可用小于等于这个x的质数推出其他合数 那么每个数只会被推出一次(它只有一个最小质数) 所以总的复杂度为O(n)#includeusing namespace std;#define FOR(i,x,y) for(int i=(x),i##_END=(
2018-01-04 21:24:25
318
原创 中国剩余定理
中国剩余定理，是建立在扩展欧几里得上的算法 用来求线性模方程的解 即给出许多模数mi，然后给出余数ai，求原数x 代码如下struct China{ #define N 5 LL A[N],p[N],T[N],m[N],T1[N],M; int n; void exgcd(LL a,LL b,LL &x,LL &y){ if(!b){x=1;y=
2017-12-28 22:09:31
350
原创 莫队算法
莫队算法较为朴素，适用于大部分的区间查询，主要在于对询问的排序 和区间的滑动 排序参照一下模板struct node{ int l,r,id; bool operator <(const node &_)const{ if(_.l/S!=l/S)return l<_.l; return r<_.r; }}Q[M];然后是L和R的滑动int
2017-12-19 21:39:32
289
原创 AC自动机专题小结
最近比较忙，AC自动机专题花了两个大周才勉强推完关于与AC结合的一些题型如下： 1.AC自动机模板题 废话 2.AC自动机结合dp 经常会和矩阵联系起来或是一些转移的预处理（trie图），但都比较裸 3.AC自动机加fail树 个人理解是前缀树上的后缀树模板题就不说了Problem J可以看出是道dp题 但是发现串的长度很大 这种题的一般思路是： 1.先敲暴力 2.矩阵快速幂优化
2017-12-17 22:24:56
309
原创 矩阵快速幂
一道模板题 可以发现相乘的三个for可以都for到n 矩阵可以把时间复杂度缩为n3logkn^3logk#include<bits/stdc++.h>using namespace std;#define FOR(i,x,y) for(int i=(x);i<=(y);i++)#define P 1000000007void Add(int &a,int b){ a+=b;
2017-12-13 22:15:31
270
原创 AC自动机
一个自动AC的东西... 套用KMP的fail指针，然后再是利用字典树进行字典与文章的匹配 以下是模板#include<bits/stdc++.h>using namespace std;#define FOR(i,x,y) for(int i=(x),i##_end_=(y);i<=i##_end_;i++)#define DOR(i,x,y) for(int i=(x),i##_end
2017-12-08 18:57:32
197
原创 树上统计
解法很多，主要有主席树+dfs序 树上差分 树上启发式合并 线段树合并1.主席树+dfs序#include<bits/stdc++.h>using namespace std;#define FOR(i,x,y) for(int i=(x),i##_end_=(y);i<=i##_end_;i++)#define DOR(i,x,y) for(int i=(x),i##_end_=(y
2017-12-04 22:33:36
1472
原创 2017NOIP游（gun cu）记
Day 0 就像初赛那样，天上飘着小雨，放眼望去，所有人都躲在屋檐下 穿着各色的校服，扎堆在一起 下了车，和zyl撑一把伞，缓缓向人群中走去…没有想到时间是如此之快4月21日，我在125上A了第一道题——A+B problem 记得那时连全角半角都分不清，导致交上去CE了好多次 旁边的小C帮我指出了错误 我急着在提交板上改，结果就被gay了… 记得那时有很多同学去那学了两三天，但放弃的
2017-12-01 18:21:58
395
原创 区间第K值（可持久化线段树）
可持久化数据结构的一个经典应用 可以说是建k个线段树，但只用nlogn个节点 代码实现#include<bits/stdc++.h>using namespace std;#define FOR(i,x,y) for(int i=(x),i##_end__=(y);i<=i##_end__;i++)#define DOR(i,x,y) for(int i=(x),i##_end__=(y)
2017-12-01 14:57:04
358
原创 Trie树
一种用于检索的数据结构 大致就是开一个数组，记录节点 然后记录经过这个节点的字符串个数，以及这个节点表示的字符串个数 分别用pre pass end记录 复杂度大约为len∗mlen*mm为操作数，len为字符串长度 复杂度很小，但内存会比较大 代码实现如下：struct Trie_Tree{ static const int M=3000005; int pre[M][
2017-11-28 20:58:25
223
原创 2017-11-9离线赛总结 （NOIP七连测第七场）
失分小结： 估分：175 实际分数：155 最后一题范围判错，痛失20分 这个NOIP最后一场离线赛全程敲暴力听说是用来攒rp的 第二题有想法是个人都有，然后无法实现…. 最后一题其实还是蛮水的，有时正解还是要冲一冲的 但想都没想就丢了个暴力上去，然后就被拉开四五十分了题解就不挂了毕竟最后一场，没什么心情写题解距离NOIP还有一天 fighting ！
2017-11-09 18:23:13
253
原创 2017-11-8离线赛总结 (NOIP七连测第六场)
失分小结： 估分：160 实际分数：170 今天身体不舒服，第三题理所当然地爆零了搞起来状态好就会写一样 前面两题还过得去，该水的分都水到了，只是第二题的正解敲了半天没调出来有些可惜还是代码功底弱的原因 第一题： 感觉自己的写法有些鬼畜瞎凑出答案 bfs+dfs， bfs保证每步最优，dfs求联通块struct node{int x,y,sp;};queue<node>q;int
2017-11-08 18:04:11
323
原创 2017-11-7离线赛总结（NOIP七连测第五场）
失分小结： 估分:290 实际分数：270 今天的题目难度较小，除了第二题炸了longlong 致命错误以外，整个流程走的还是不错的，先是花了一个多小时水到200（100+60+40） 然后回头看第二题，发现是到水题，直接gang掉 然后第三题，想了蛮久的，正打算打表找规律的时候，xiaoC过来说set中没有重复元素 ？？？这不是道水题吗 然后一波高精，除了3的数据其他的数据都过了
2017-11-07 16:23:23
291
原创 2017-11-6离线赛总结（NOIP七连测第四场）
失分小结： 估分：155 100+20+35 实际分数：140 100+20+20 考完太突然发现第二题的正经切分的运算被删掉了，实际的20分是玄学解法帮我水的… 第三题由于造数据太烦，就没有怎么去管他，然后dp顺序的错误导致又失去15分 本来的考试note上写的预估分数是100+30+50，后来感觉第二题只有20分不太好，就放弃写第三题下面15分，回过头去写第二题 但又因为第二题
2017-11-06 19:45:04
368
原创 2017-11-5离线赛总结（NOIP七连测第三场）
失分小结： 估分：100+80+40=220 实际分数：100+10+35=145 和估分相差甚远，主要是由于第一题的难度提升 又在第一题上卡了太久，导致第二题随便打了个暴力后又去水第三题 虽然主体顺序是没有错的，但是心态就不一样了，想着多水点分，又感觉时间来不及，虽然最后第二题想到了最小生成树，但又因为取边取错爆炸，暴力（dp）写错 题解： Task 1： 第一题如果直接考虑两个数
2017-11-05 20:47:13
294
原创 Tarjan求强连通分量
强连通分量可以用Tarjan求 比两遍dfn大概快30%定义一个栈 把点压进去，然后根据自己所能到的点，求出能到达的dfn序最小的点 由此得到从此点到low点中的点（在栈中）可以成为一个强连通分量 具体实现是当x点满足dfn==low时，将栈中的点全部弹出至x点; 可以证明每个点最多被弹出1次，每条边最多被遍历一次 复杂度为O(n+m)O(n+m)int col[N],sz[N],cnt
2017-11-04 22:13:28
362
原创 2017-11-4离线赛总结（NOIP七连测第二场）
估分：270 实际分数：280 这次的难度略小于NOIP 最后一道题作为水题竟然没有做出来 第二题又又又叒卡过去了hahahahhahahahahah 实际正解也是好敲的，谁知道其实内存开的是256MB 题解： 第二题： 一看到颜色的个数如此诡异，就可以想到是用状压 然后模拟颜色的排序，求逆序对（预处理） 直接状压dp的复杂度是n2∗2nn^2*2^n 可以水到90分 然后如果
2017-11-04 15:47:40
302
原创 LCP 最长公共前缀
定义dp[i][j]为从n到i点及j点的最长匹配长度 状态转移方程为if(str[i]==str[j])dp[i][j]=dp[i+1][j+1]+1else dp[i][j]=0循环顺序for(int i=n;i>0;i--){ for(int j=n;j>0;j--){ }}这种算法可以快速地O(1)求出两个子串的匹配长度 可以运用于dp的优化
2017-11-03 18:10:58
880
原创 2017-11-3离线赛总结
有一段时间没有离线赛了，感觉这次考得还过得去 失分小结： 估分：240 实际分数：230 万万没想到自己第二题的n^3可以卡过去，正解为LCP(最长公共前缀) 第三题就是抽直径，然后就分类讨论 注意直径的性质：距离一点最远的点一定是直径两端点中的一点 设两个机房分别在a，b，他们在直径上对应的点为u，v 那么答案就会在Lt到u或u到v或v到Rt的路径上，然后由于满足单调性 对于中间
2017-11-03 18:00:43
239
原创 树链剖分求lca模板
传说中比O(1)还快的求LCA的方法 再加上正向表优化，#include<cstdio>#include<cstring>#include<vector>using namespace std;#define M 100005#define FOR(i,x,y) for(int i=(x);i<=(y);i++)#define DOR(i,x,y) for(int i=(x);i>=(
2017-11-02 08:53:15
345
1
原创 2017-10-30离线赛总结
失分小结： 估分：150 实际分数：170 最后半个小时发现自己第一题敲错了，心态爆炸，拿暴力对拍，拍一组错一组 直到最后还没调出来，就只好把暴力丢上去，胡了50分 后面两题不敢想正解，就随便每题切了60分（后来发现机房的神犇门都想出了正解，泪奔） 两天一共375分 感觉两天都只敲了暴力 比省一线高了45分 如果是现场比赛估计也不会有这个分收获： 对拍一定要是最暴力的！！！题解：
2017-10-30 19:53:59
265
原创 2017-10-29离线赛总结
失分小结： 估分：220 实际分数：205 第二题的有15分切错了，但总体上能把自己切的大部分分数给弄到还是不错的 （虽然这次的发挥并不是特别好，感觉考试全程敲暴力）这次考试裸分应该是有（256）[100+80+76] 其实切分是很重要的 像机房里另外几个大佬对于第三题都是切m=0,1,2 而像我这样的蒟蒻切了好多鬼畜的：性质2，m=0,… 切得太杂了，所以并不能得多少分第一题模拟题
2017-10-29 22:34:26
289
原创 2017-10-27离线赛小结
估分：280 实际分数：260 这次考得还过得去，终于逃脱了炸零魔咒，但最后一题线段树敲错Tle了20分还是很悲伤的 小C:你怎么那么low啊 是时候总结一下考试要干些什么了 1.敲模板（头文件，读入挂） 2.写备注（long long double 文件名 乘法 调试） 3.把文件名复制到freopen里（一定要复制!） 4.敲暴力（以前第一题炸零的经历告诉我，前面两题一定要敲暴力
2017-10-28 13:25:46
239
原创 2017-10-26离线赛总结
失分小结： 估分：230+ 实际分数：110 又是爆炸的一场，感觉自己太不稳了，审题还要仔细，写的代码一定要静态检查一下，第三题切分都没看仔细，就写了n=4的情况(n=2,n=3呢？) 然后又是调正解调半天，最后bug有没有de出来(100+0+10) 爆零还是最伤的 主要还是太容易被外界所影响 感觉自己好失败啊，正解打不出来，暴力又打错，切分不会切，简单题又爆零 。。。。。。 题
2017-10-26 19:47:40
218
原创 2017-10-24离线赛总结
失分小结： 估分：260 实际分数：160 第一题爆零。。。原因是题目没有看清楚就开始写了 又痛失100分 与day1加起来只有460 幸好day1AK，勉强省一第一题O(n)被我强行O(nlogn)分治强搞 第二题是近几年最简单的一道dp题，数据结构优化就好了，也有贪心的O(n)做法 第三题华容道是到贼恶心的题目 正解是很早就想到了，但实现上却困难重重整场考试只写这道也未必能调出来
2017-10-25 09:31:06
219
原创 2017-10-23离线赛总结
失分小结： 估分：300 实际分数：300 。。。一个半小时就打完了。。开始怀疑人生。。。 但幸好后来有检查，第三题有很多小bug，如果没看出来可能就要爆零了。。。 题解： 第一题 根据题意得 ans=(x+m∗10k)%n(x+m*10^k)\%n 可以看出这里面较难处理的就是10^k 将n移进来，得x%n+m∗10k%mx\%n+m*10^k\%m 10k%n10^k\
2017-10-24 08:09:33
212
原创 2017-10-21离线赛总结
失分小结： 估分：240 实际分数：250 本来觉得240应该是一个挺正常的分数，但是很多人都考得不好 感觉第三题的思维还是太局限了，就算打暴力也只能想着模拟。。考试流程： 前两题打得很顺，大概就一个小时多一点，最后一题玄学debug到考试结束 最后十分钟灵感爆发，想到80分解法。。题解： 第一题： 应该是一个裸的前缀和题目 反正这种题打完之后对拍一般就不会出什么问题了 第二题：
2017-10-22 17:27:30
228
原创 数据结构学习——动态逆序对
解法一: 分块套BIT利用树状数组算最初的逆序对个数 nlognnlogn 利用树状数组算出块中比x小的数的个数 lognlogn 遍历x所在的那个块 n/Sn/S 总复杂度O(m(n/S+Slogn)+nlognm(n/S+Slogn)+nlogn) S取nlogn−−−−−√\sqrt{nlogn}时 O(mnlogn−−−−−√+nlogn)m\sqrt{nlogn}+nlog
2017-10-20 16:38:05
655
原创 2017-10-19离线赛总结
失分小结： 估分：250 实际分数：145 这次又翻水水，本以为这次可以考的不错 结果第一题就wa了（字符串多输出了一位类似于空格的东西，看不见。。。） 第二题神判数据范围，切少了10分 第三题没什么时间，丢上去一个最无脑的暴力，还多水了5分题解： 第二题这种贪心题目，就是推一推 然后大胆地猜想 再拿暴力对拍 所以一定要先打暴力！ 第三题 这种在轴上单向移动的题目，都可归结到倍
2017-10-20 10:57:03
218
原创 2017-10-19数据结构学习
BIT求LCA#include<cstdio>#include<algorithm>using namespace std;#define M 1005int n;int B[M],A[M],C[M];int query(int x){ int ans=0; while(x){ ans=max(ans,B[x]); x-=x&(-x);
2017-10-19 16:45:15
259
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人