- 博客(172)
- 收藏
- 关注
RSS订阅原创 2018年10月21日开学训练日记
周三的练习赛基本就是自己在打着玩，思维，数学，线段树，规律，很符合我的专场，自己a了四个，队友就因此打了酱油，但是也因此发现了模板的一个错误，我的线段树模板当时测试用题太过简单，导致做这个复杂的题出现了问题，后来更正了。 周六因为去拿药，远程协助了一个规律题，一个假的线段树dp，因为世东忘了给我说t的范围，于是tle。 周末就是上课加讲课，光想着补充技巧结果讲的有点慢，结果新生反应...
2018-10-21 23:13:10
278
原创 2018年10月6日开学训练日记
今天有点暴力+数学专场 a题区域赛居然还出a+b，结果还优秀的wr了一发 b题又是水题一枚，很快过了。 c题7阶矩阵快速幂用到了多项式的展开，（i+1）^4=i^4+4*i^3+6*i^2+4*i+1，利用这个关系建立矩阵， 之后矩阵快速幂 d题暴力，我和世东一人一发罚时的交，最后终于过了，明显一开始想的有点简单，后来经过大量剪枝。 之后一直g题公式，听他们说是个...
2018-10-06 20:49:01
524
原创 2018年10月5日开学训练日记
今天的比赛世东快速出了A题（猜的题意），之后我就一直在推公式，梁dalao在做模拟 当然，公式推得还算顺利，有点类似于期望dp的那个思想，不过因为是连续型的，求和变成了积分，然后用了数学物理方程里面的一个思想，求导之后把积分方程转化为微分方程，推了一页纸找到了公式。 我出了之后梁dalao也很快出了，D题居然还是期望，有点头疼就没继续想（赛后发现并没有那么难，虽然出的人挺少的）。...
2018-10-05 20:18:17
474
原创 2018年10月2日开学训练日记
今天的比赛是两个人打的，世东家里人来找他了。 H题，概率论题，结果公式推错了，wr了两发，导致后来有点慌。但因为梁dalao的j题出了还是冷静下来做出来了H题。 J题看起来是个题意题，并没有看懂，但是好像读懂了就挺简单的。 之后我又做了I题，一个计算几何的题，就是三角形的面积=0.5absin(theta) 然后D题，觉得数据范围挺小的，暴力了一发，结果tle，后来思路...
2018-10-03 20:13:46
246
原创 2018年10月2日开学训练日记
今天的比赛 D题简单数学题，想到gcd的倍数就是能构建的方案总数即可 B题我们用的kmp+数组优化，但是比赛过程中发现世东的kmp模板出现了问题，只有他的电脑能正常出结果，于是迷了很长时间，最后换了个模板成功通过，赛后听说他们用暴力过了，还比我们快，看了一下，应该是没卡他们的暴力，实际时间要比我们长的多。 之后我就一直在搞f的容斥定理，发现我的方...
2018-10-02 21:29:20
205
原创 2018年10月1日开学训练日记
今天早上看了周六的那个没做出来的数位dp，转换成3进制之后发现是个数位dp的裸题。 下午的比赛很快做出了签到题，之后自己搞了l题，结果过的很玄学，理论上讲应该是错的，但是题解上也写只有一条路径，于是这个break加的就还算合法。之后和梁dalao一起推了一下b题，暴力之后仍然是用进制找到了规律，从一个暴力题变成了一个构造题，结果因为后期自己老给自己造假样例就没敢提交，其实应该是对的。...
2018-10-01 18:07:19
414
原创 2018年9月29日开学训练日记
今天早上学了一下字典树和0-1字典树，因为之前周四的比赛中我用暴力过了一个0-1字典树的题，想顺便学习+补题 我只能说字典树是一个比较好用的数据结构，并不是一个很吓人的知识点，就是用一个树存某个串的状态，以达到节省空间又能快速访问多个字符串的状态量的一个数据结构。0-1字典树则是一个特例，是对数字的异或问题的一个贪心想法，根据数字的二进制结构枚举每个数位上达到最大的结果。而...
2018-09-29 18:42:34
222
原创 2018年9月9日开学训练日记
周六的比赛情况： 前两个小时做自己的c题，后来发现推不动，容斥复杂度过高，然后就转移阵地了。 之后： 助攻了k题，发现了题意读错了，然后修改之后过了。 助攻+完成了g题，一并推出容斥，并完成代码提交，代码：#include<iostream>#include<cstring>#include<cmath>#include&...
2018-09-09 18:34:37
301
1
原创 2018年9月2日暑假训练日记
周六的比赛其实又出现了省赛的状况，只不过这次更接近结果，被卡了1.6的常数（赛后虽然聚餐，出于愧疚一直在想，他那个解法正好卡时间过，我的时间复杂度相当于他的1.6倍），在1096ms超时了，赛后测试输出都是对的，可能再优化一点就能过了，和正解思路很类似的一个筛素数的改造，不过它用的那个筛素数更快一些，当然，比赛的时候我也想过这个问题，但是看着他那个格式我并没有敢进行改造，而我这个正好卡住了，当...
2018-09-02 22:22:38
153
原创 2018年8月30日开学训练日记
前两天由于是课程介绍，事情比较少，看了一下发的题目，其中简单的小技巧比较多，而大部分还是见过的题型，李世冬也经常给我发一些，正好我们看的不是一个，所以也能学到一些。周三来了就被王秉义拉住问了个题，我想了想说是个莫队的裸题，结果是题目看错了，白敲了一下，之后就没啥新奇的事情了，第一周就发现自己选的课都是些什么玩意，要么说难赶我们走，要么说难，还希望我们留下，终于体会到大一老师说学数学要拿时间才...
2018-08-30 16:56:21
250
原创 2018年8月22日暑假训练日记
最大流HDU 3549 Flow Problem：最大流模板题（其实学了图论之后发现，图论这方面的知识点模板是直接套用的，怎么套用是要费脑子的，这里的模板就是裸着告诉你他就是个最大流）POJ 1273 Drainage Ditches：最大流模板题，这里就是加了个裸的背景，比如池塘的容量，电厂输送，wif上网等等POJ 2391 Ombrophobic Bovines：同POJ 211...
2018-08-22 16:43:28
185
原创 2018年8月21日暑假训练日记
又是一天饶齐博客：并查集：HDU 4496 D-CITY(并查集)：并查集的基础题目，就是求连通分量的个数，这里一般用n-合并次数HDU 1213 How Many Tables：同求连通分量的个数UVA 1160 X-Plosives：这里给与了图一个化学的背景，依旧是求连通分量的个数，考虑不稳定的化合物在同一个连同分量里HDU 1272 小希的迷宫：并查集的又一个用法，判断...
2018-08-21 19:17:36
199
原创 2018年8月20日暑假训练日记
开始看饶齐博客，kmp和凸包前段时间看完了线段树：HDU 1166 敌兵布阵：单点更新，区间sum模板题HDU 1754 I Hate It：单点更新，区间最值模板题HDU 1394 Minimum Inversion Number：线段树求逆序数，以前不是很懂这个，现在一看就懂，就是按顺序更新，查询这个数之前插入了多少个比他大的数这个处理有点迷，码上//POJ 2828 Bu...
2018-08-20 17:13:36
198
原创 2018年8月17日暑假训练日记
昨天的那个期望题的正解：相当于每个点作为起点，枚举其终点所获得的期望之和。可以这样理解，枚举起点的时候，可以发现：...011...110...一个这样的字符串，只需要dp获得011...110这个串的概率，乘以这一段的取值，就是这一段贡献的期望，因为就相当于其他的点为任意情况而不考虑其贡献得到的期望，由于是对每个点作为起点并枚举其终点，因此不会造成重复，合理利用了期望的性质#in...
2018-08-17 17:40:50
218
原创 2018年8月16日暑假训练日记
宾馆租期到了，早上打理了一下宿舍的事儿。 下午很难受的暴零了，大佬做出来个区间dp，我现学了期望dp，然后写了个期望dp超时了，要是m变成原来的一半就过了，正好卡死了，然后搞了一发假dp，还是不是很理解区间dp，所以失败了。#include<iostream>#include<cstring>#include<cmath>#includ...
2018-08-16 17:17:17
198
原创 2018年8月15日暑假训练日记
早上看了一下基本的分治，因为cdq分治和整体二分都用到了这个，直接看cdq分治并看不懂。 下午的比赛一开始的签到世东过的有点艰难，好像是简单题写复杂了，我就不该偷懒扔给他。之后一道组合数+容斥，完全靠网络找到了公式，其实见过这一次之后也就知道了，直接推并不是毫无可能性。 记录一下就是k个球放到m个盒子最多不超过n-1的方案数，首先，如果没有限制就是c(m+k-1,m-1)，可以用挡...
2018-08-15 18:34:50
232
原创 2018年8月14日暑假训练日记
HDU 6386 Age of Moyu比赛的时候唯一做出来的一个dfs，有点贪心的意味，每次dfs只找花费为0的路径，并标记用过的边保证不超时，这样找到的第一个路径就是最小路径，因为再往后就会增加路径长度。HDU 6395 Sequence比赛刚开始的时候一眼就看出来是个矩阵快速幂加分块，用向下取整的性质加以分块，前面比较小的项打表（1000000以内的项打表），结果没人相信我，我就...
2018-08-14 17:40:42
175
原创 2018年8月13日暑假训练日记
昨天学长问我了一个今日头条的题目，我看着有点像线段树+二分，今早上就尝试了一下，但是还没交，所以不知道对不对，题意大概给定数列a,b求所有区间当中有多少区间满足a的最大值小于b的最小值，暴力枚举每个区间一定超时，就想到了n^log^log，也就是线段树+二分，用线段树处理最大值和最小值的查询，用二分查找最大值变更的位置，因为有个性质就是，区间越大，最大值只可能越大，而最小值只可能越小，我们只需要知...
2018-08-13 18:09:47
180
原创 2018年8月12日暑假周末总结
这周末去济南拿药了，回来已经比较晚了，就和老纪一起去健身了，我觉得现在的精力有些差，导致打比赛的时候不仅打不完全程，晚上大部分时间也是荒废的，所以决定加强一下。 这周并没有按照他们看题的方式看题，因为零散的看一些水题效果并不太好，我选择了看一些新的知识点，然后回头去看多校里面相应的习题，等李世冬看的差不多了，让他把水题给我讲一讲，然后说一些能看的题目，这样我觉得对我来说有着较高的效率。...
2018-08-12 20:38:23
173
原创 2018年8月11日暑假训练日记
计算几何一点不会比赛的时候总是手忙脚乱，正好以前看过凸包，顺便看看用法。UVA 10652 Board Wrapping(凸包求面积):求矩形板的面积占包围这些板子的凸包的面积比例可以说是个凸包裸题，提供了求凸多边形面积的方法：就是分解成多个三角形，然后分别求这些个三角形的面积：Area=sigma（叉积（c[i]-c[0],c[i+1]-c[0])）/2因为叉积本身表...
2018-08-11 19:09:27
204
原创 2018年8月10日暑假训练日记
首先，最后一个题，用最后五个点拼的结果有点厉害，我们是错在我们用点消的结果，没进行枚举，所以就错了，正解是枚举一下，但是并不能证明为什么5个点可以拼出来缺的任意值 昨天j题？又把水题读成了难题？？？直接暴力枚举行列能延展的范围，然后处理一下就过了 c题一个dfs+不优化居然算错了数据范围因为最后都没几个人过而没敢试一试 继续看看kmp的用法(一开始还问李世冬哪里有好的题可以...
2018-08-10 19:57:39
218
原创 2018年8月9日暑假训练日记
昨晚上拉肚子到3点，有点虚脱，早上就多休息了会。 果然下午又是签不了到专场，有刚开始管理员就说这次题比较难，请大家不要慌张。 和安逸凡一块推了半天的规律，刚验证完，发现李世冬敲完了，他的是搜索二进制补位，我们是转换成二进制后发现的和2的幂次相关的规律，结果被一点不验证的规律一发过了 后来e题就一直想用完全图构造，三个队都被多出来的两个点卡在了64%，就是没想到开c题的dfs，...
2018-08-09 20:49:13
155
原创 2018年8月8日暑假训练日记
上午Kmp:经常看到字符串的题就逃避，所以打算补补这块，正好队友的kmp只会个模板，并不理解，上次虽然热身赛出了个kmp俩人搞了半天我就在旁边干瞪眼，关于这个简单算法找不到好的资料也是很难受的，一开始觉得我初学，应该找个详细的资料，结果进了一个kmp详解的资料里，就看的一脸懵逼，洋洋洒洒几千字，最后只知道了，kmp比暴力优化在他的失配之后跳转的位置，至于怎么求算，一概不知后来又看了几篇...
2018-08-08 19:30:58
168
原创 2018年8月7日暑假训练日记
上午：HDU 5372 Segment Game（线段树）覆盖区间数=左端点大于L-右端点大于R由于区间比较大，所以进行离散化处理然后树状数组维护一下就可以了The shortest problem（hdu5373+11的倍数）结论题：能被11整除的数字，奇数和偶数位之和的差可以被11整除。HDU 5381 The sum of gcd（莫队+rmq+二分）:由于n...
2018-08-07 20:01:58
205
原创 2018年8月6日暑假训练日记
上午：HDU 5372 Segment Game（线段树）覆盖区间数=左端点大于L-右端点大于R由于区间比较大，所以进行离散化处理然后树状数组维护一下就可以了The shortest problem（hdu5373+11的倍数）结论题：能被11整除的数字，奇数和偶数位之和的差可以被11整除。HDU 5381 The sum of gcd（莫队+rmq+二分）:由于n...
2018-08-06 20:21:43
159
原创 2018年8月4号暑假训练日记
数据结构优化的dp：hdu 2604 Queuing（矩阵优化DP）递推式 ： f[i]=f[i-1]+f[i-3]+f[i-4]这个题目虽然题解怎么写的，但是不够典型如果数据范围改成1e9,就应该是个较为典型的题目优化矩阵：0 0 0 1 1 0 0 1 0 1 0 0 0 0 1 1快速幂搞一搞就行了HDU - 3450 ...
2018-08-04 19:54:56
269
原创 2018年8月3日暑假训练日记
多校相关：一些知识点入门之后，决定看看在多校中是怎么体现的2018年牛客网暑期ACM多校训练营（第一场） J 记忆尤新的是这道题目的解法在当时讲的是后接数组，然后树状数组板子题今天看到了一个清奇的题解说是莫队的板子题，当然用莫队写法就比较简单了，但是有个优化就是可以适当放大块的大小HDU5381【莫队算法+区间GCD特性】这道题又开拓了一下思路，突然发现l r的区间查询大部...
2018-08-03 17:43:39
166
原创 2018年8月2日暑假训练日记
上午：莫队算法：以前对莫队算法的理解就是一个离线分块处理，简单了解了一下觉得没有基础也能写，但是昨天的题发现见到这样的题基本没有什么想法，于是今天重新学习，简单小总结一下吧：首先莫队算法的时间复杂度：O((m+n)sqrt(n)）时间复杂度不大不小，大概可以处理1e5的区间*1e5的询问这种询问有特点就是可以相邻区间进行跳转，比如已知（x,y）的状态可以O(1)知道（x-1,y...
2018-08-02 20:40:44
175
原创 2018年8月1日暑假训练日记
想整理一个splay模板，因为学了之后满脑子都是splay的骚操作，可是发现，这个东西看懂只是说看懂思路，大部分的模板都不一样，就算觉得它这里写的不好，也不敢改动，今早就对照了好几个模板整理了一部分，结果比赛完有点卡忘了保存就关机了.......很难受。 下午出来一道水题和一道模拟之后，一直觉得b题可以出来，逆元打表+各种优化，但是发现一直超时，推了半天的公式，莫队的公式都写在纸上了，就...
2018-08-01 21:09:23
379
原创 2018年7月31日暑假训练日记
来了之后去给学弟学妹讲了一下逆元，顺便复习了一下中国剩余定理的结论使用，书上代码太过简单，所以手动打代码翻译了一遍MZL's xor：求一个序列的所有的（a[i]+a[j])的异或和。对(a[i]+a[j])xor(a[j]+a[i])xor......由于a[i]xora[i]=a[j]xora[j]=0,因此原序列变成了2a[i]xora[j]xor......以此类推...
2018-07-31 20:01:12
141
原创 2018年7月30日暑假训练日记
上午：SplayHDU 3436 Queue-jumpers (Splay tree)Splay的三大操作，查询某个点的位置，查询第k个位置，和旋转点到队首。这里离散化比较六，把没有用到的区间压缩成了一个点HDU 3487 Play with Chain (Splay tree)这就是上次没做出来的题目的升级版，加了一个反转操作，果然是个splay的模板题，由于操作l,r，所以...
2018-07-30 20:56:16
199
原创 2018年7月28日暑假训练日记
早上看完了splay的区间操作，指针的没看懂，找了个非指针的看完了，还不知道具体怎么使用。 下午比赛推出来个规律题，矩阵构造的题目，这种题目还是得大胆猜想，不然永远也做不出来，结果队友搞另外两个题目罚时上天，不然名次就还可以了，这几个题目做出来的都比较早。...
2018-07-28 20:20:52
130
原创 2018年7月27日暑假训练日记
FFT：比较常见的一个知识点，所以想了解一下，据说有模板题。知识点和算法算是看懂了，还没看怎么用。简单总结一下就是把n次系数多项式相乘转化成为n+1个特殊的点表示的多项式，相乘之后再转换回来，操作比较复杂，根据奇偶进行了若干次的分治解。Splay树：怎么说呢，看一开始的介绍好像是在一个二叉搜索树（二叉搜索树就有点懵逼，现看的）上添加了一个旋转操作，跟预想的不一样1588: ...
2018-07-27 20:02:51
135
原创 2018年7月26日暑假训练日记
上午：区间dp：NYoj - 737 区间dp入门题目大意：求n堆排成一排的石头合并成为一堆的最小花费状态转移：dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);最基础的区间dp，枚举区间长度，起点，以及合并中点，其中w[i][j]是一个前缀和，和区间dp的基本思想完全相同这里一个优化：s[i,j-1]≤s[i,j]≤s[i+...
2018-07-26 20:27:32
174
原创 2018年7月25日暑假训练日记
上午：树形dp:HDU 3452树形DP题目大意：最简单的求树上的割权值和最小状态转移：dp[i]+=min(w[i],dp[j]);也就是判断是在这个点割断好还是在下面的点割断好Hdu 4616 树形DP题目大意：求一棵树上经过k个雷停止的路径所能得到的最大权值。状态转移：dp[u][j+c[u]][1] = max2(dp[u][j+c[u]][1],dp[v][...
2018-07-25 19:46:06
148
原创 2018年7月24日暑假训练日记
状压dp：1.’&’符号，x&y，会将两个十进制数在二进制下进行与运算，然后返回其十进制下的值。例如3(11)&2(10)=2(10)。2.’|’符号，x|y，会将两个十进制数在二进制下进行或运算，然后返回其十进制下的值。例如3(11)|2(10)=3(11)。3.’^’符号，x^y，会将两个十进制数在二进制下进行异或运算，然后返回其十进制下的值。例如3(11)...
2018-07-24 19:44:53
161
原创 2018年hdu多校1007 Chiaki Sequence Revisited（谜之Meta-Fibonacci，二分+求n！中a出现的次数）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6304 题目大意：求Meta-Fibonacci的前缀和。 谜之求和，打表得到前几项发现是，1 1 2 2 3 4 4 4 5 6 6 7 8 8 8 8 9.......明显除了1之外，其他数字出现的次数跟它当中含有2的幂次有关，比如奇数中不含有2，所以只出现1次，而2=2^1，6=2...
2018-07-24 11:23:58
433
原创 2018年7月23日暑假训练日记
早上看了前三道题目。 第一个是纯暴力，一眼看出来了，Question for the Leader是一个结论题，对于一棵树，如果可以把这棵树分成大小都为k的n/k份，那子树大小是k的倍数的节点恰好有n/k个。(任意选定一个根)，这个结论叙述的并不是很好，所以就花了一段时间，第三个则是一个状压dp，由于不会状压dp，就去专门看了一下，但是还没入门就开始了下午的比赛。 下午总共出了四道...
2018-07-23 20:35:17
180
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人