- 博客(281)
- 收藏
- 关注
RSS订阅原创 SDOI 2016 ROUND 2
day 0几天前就得知了教练有事要班主任带我们去济南&%￥#%……班主任？! 顿时感觉这一波雪崩。。又不能愉快的颓了，感觉班主任领着这次r2会非常exciting………… 因为一些奇怪的原因，10点就从学校出发了，到了WF车站不到11点，随便找了一家餐馆吃完饭这时刚好11:30，接下来无聊了2h……到了13:23坐上去济南的动车。 下车后随口把出站口读成了出口站……瞬间被语文大师fqk打野和班
2016-05-14 22:09:05
1945
6
原创 4557: [JLoi2016]侦察守卫|树形DP
let’s Orz yts大爷//#pragma comment(linker, "/STACK:20240000,20240000") #include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#inclu
2016-05-02 09:42:24
4009
1
原创 2670: Almost|分块|三分
先处理出前缀和sumisum_i 区间[l..r][l..r]的几乎平均数为sumr−suml−1r−l\frac{sum_r-sum_{l-1}}{r-l} 也就是求一个斜率的最大值，假如左端点确定，找一个右端点使得几乎平均数最大的话,可以求出凸包，然后再凸包上3分找到最大值 然后就可以分块设立TT个关键点求出每个点到关键点这个区间的最大的几乎平均数 询问的时候可以先拽出跨过关键点的答案，
2016-04-26 16:17:39
1076
原创 4521: [Cqoi2016]手机号码|数位DP
数据范围这么小..感觉暴力可过啊.. DP也是随便设计状态 F[i][j][k][s][l]F[i][j][k][s][l] 表示前ii位，最后一位是jj 最后一位连续出现kk次(如果k已经等于3那么就一直不变）ss表示4,84,8的出现状态 ll表示前缀是否和原数的前缀相同 转移就是枚举下一位转移,也很简单..#include<algorithm>#include<iostream>#i
2016-04-24 16:36:32
3585
原创 4537: [Hnoi2016]最小公倍数|分块
暴力的做法就是直接找到所有a,ba,b都小于等于某个询问的边然后并查集合并，维护每个集合的a,ba,b得最大值看是否等于询问的a,ba,b 然后就可以考虑分块，把边按照aa排序，每隔n−√\sqrt{n}分为一块 块前的按照bb值排序按顺序插入，块内的暴力判断，并查集合并,每次都把块内合并的记录下来，处理完某个询问时就撤回并查集的操作 块的大小为n−√\sqrt n可能会TT 改成n∗log
2016-04-24 14:36:54
1396
原创 4542: [Hnoi2016]大数|莫队
HN一天考两个莫队是什么鬼..或者说莫队不是正确的姿势..? 考虑已经知道了l..rl..r的答案新添入r+1r+1如何更新当前答案 需要先预处理出后缀modpmod p的值bib_i，假设子序列l..rl..r模pp的值为xx 那么x∗10r−l+b[r]=b[l]x*10^{r-l}+b[r]=b[l] 然后就可以直接莫队统计了 模数为2或5的时候要特判一下#include<algori
2016-04-23 19:16:03
3068
3
原创 4540: [Hnoi2016]序列|莫队+ST表
考虑现在已经知道了[l,r][l,r]的答案新添入一个r+1r+1如何更新答案 也就是右端点在r+1r+1处左端点在l..r+1l..r+1之间的所有的子序列的答案 可以找出l..rl..r中最小的数的位置pp，然后pp以及pp左侧作为左端点的答案就可以直接计算了 考虑左端点在p+1....r+1p+1....r+1时对答案的贡献，可以与处理一个前缀和SiS_i表示以ii为右端点的所有子序列的
2016-04-23 09:06:57
2658
1
原创 2959: 长跑|LCT+并查集
慎入…此人代码自带5倍常数。。 静态的话就是随便搞出一棵生成树来，然后把环缩起来，询问的答案就是路径上的权值和 动态的就需要LCT来维护生成树，每遇到连起边来就形成环的情况时，就把这个环缩成一个点 动态的查询一条链上的权值和。 为什么我的代码的常数这么大…….后几个点在本地跑5s#include<algorithm>#include<iostream>#include<cstdlib>
2016-04-21 10:00:49
944
原创 3073: [Pa2011]Journeys|线段树|BFS
一种比较暴力的方法就是直接线段树优化建图，跑dijkstradijkstra 但是这题的边权都是11可以考虑BFS的方法 首先按照yy将所有的边排序，然后按照xx的大小插入到线段树中 这样每次询问一个点pp下一步能走到哪些点可以直接在线段树中找到x<=px<=p并且y>=py>=p的点 因为已经按照yy排序，所以最终线段树中的连边的yy是递减的，这样就可以做到线性的BFSBFS#includ
2016-04-18 15:30:41
975
原创 3589: 动态树|树链剖分|线段树
直接树链剖分，然后查询一段路径的时候顺便在线段树中打上标记，如果再查到这个地方的时候就直接忽略掉这部分对答案的贡献#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#include<queue>#in
2016-04-18 15:16:48
819
原创 4456: [Zjoi2016]旅行者|分治+最短路
每次将矩形划分成两个部分，枚举中间点跑最短路更新答案，不断递归分治#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#include<queue>#include<ctime>#include<se
2016-04-18 15:13:50
1306
2
原创 4455: [Zjoi2016]小星星|状压DP|容斥原理
OrzSDOIR1ak的晨神 可以考虑状压DP枚举子集，求出只保证连通性不保证一一对应的状态下的方案数，然后容斥一下就是最终的答案#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#include<q
2016-04-18 15:08:49
1494
1
原创 1808: [Ioi2007]training 训练路径|树形DP
http://adn.botao.hu/?p=80胡波涛的题解说的很详细,这里就不赘述了#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#include<queue>#include<ctime>
2016-04-18 15:04:40
1096
2
原创 2164: 采矿|树链剖分|DP
DP比较显然，但是直接DP会Tle，这时需要树链剖分用线段树维护dp值同时维护链上的和子树的dp值#include<algorithm>#include<iostream>#include<complex>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#include<
2016-04-18 14:58:55
780
1
原创 4518: [Sdoi2016]征途|斜率优化
裸的斜率优化。。我考场上SB#include<algorithm>#include<iostream>#include<complex>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#include<queue>#include<ctime>#include<set
2016-04-15 08:33:59
1618
原创 4514: [Sdoi2016]数字配对|费用流
这道题只要看出是个二分图就可以直接费用流搞一搞了#include<algorithm>#include<iostream>#include<complex>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#include<queue>#include<ctime>#i
2016-04-15 08:27:39
1301
原创 4516: [Sdoi2016]生成魔咒|后缀数组|线段树|ST表
将原串倒过来，每次添加一个字符相当于增加一个后缀。 问题转化为向集合中动态添加后缀求本质不同的字串的个数，离线求出SASA 找出当前添加的串与集合中的串的最大的LCPLCP，就是重复出现的子串的个数，线段树维护集合中rank的前驱和后继， 考场上的原代码(SDOI唯一A掉的一道题QAQ)#include<algorithm>#include<iostream>#include<cstdli
2016-04-15 08:22:43
1404
1
原创 3160: 万径人踪灭|FFT|manacher
答案可以转化为所有的回文子序列减去回文子串 回文子串的个数可以用manachermanacher来求出 回文子序列的个数可以这样求： 先求出以每个点为中心左右对称的点的个数xx，那么以这个点为中心的回文子序列的个数就是2x−12^x-1，然后现在只需要求出以每个点为中心左右对称的点的个数，就是a[i+p]==a[i−p]a[i+p]==a[i-p]这种情况的个数，发现和卷积非常类似。。。然后还
2016-04-07 17:19:48
2956
1
原创 2194: 快速傅立叶之二|快速傅里叶变换
很容易发现就是把bb序列反过来直接FFT搞一下#include<algorithm>#include<iostream>#include<complex>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<queue>#include<ctime>#include<cmath>#in
2016-04-07 14:14:29
2601
原创 2179: FFT快速傅立叶|快速傅里叶变换
背板子大法吼#include<algorithm>#include<iostream>#include<complex>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<queue>#include<ctime>#include<cmath>#include<map>#inclu
2016-04-07 07:37:17
1421
2
原创 2124: 等差子序列|线段树维护哈希值
集训队的题是厉害啊 从左到右枚举每一个数作为等差序列的中间项，判断是否存在等差子序列 考虑枚举到一个位置ii，假设a[i]−xa[i]-x在前面出现过，那么如果不存在等差子序列，a[i]+xa[i]+x肯定也在前面出现，同理a[i]−xa[i]-x若在前面没出现过，那么a[i]+xa[i]+x也不能在前面出现，否则就存在了等差子序列。 从前向后枚举，如果出现了某个数，就为11否则就为00，这样
2016-04-06 11:34:55
2048
1
原创 2006: [NOI2010]超级钢琴|ST表|堆
由于K很小，所以就直接取出最大的K个值加起来即可 考虑一个(i,l,r)(i,l,r)表示以i开始以[l,r][l,r]中的某个位置结束的区间和的最大值，假设这个位置为pp，然后把这些东西都存起来一起扔到堆中，每次取出区间和最大的一个元素，然后继续向堆中添加新的元素，直接对(i,l,p−1)(i,l,p-1),(i,p+1,r)(i,p+1,r)这两个组合再分别找出最大的区间和再扔到堆中，然后重复
2016-04-06 10:08:40
1582
原创 3930: [CQOI2015]选数|递推|数论
题目让求从区间[L,H][L,H]中可重复的选出nn个数使其gcd=kgcd=k的方案数 转化一下也就是从区间[⌈Lk⌉,⌊Hk⌋][\lceil\frac{L}{k}\rceil,\lfloor\frac{H}{k}\rfloor]中可重复的选出nn个数使其gcd=1gcd=1的方案数 然后f[i]f[i]表示gcd=igcd=i的方案数，考虑去掉所有的数都是重复的情况，这种情况最后在判断一下
2016-03-23 20:07:59
1544
1
原创 3747: [POI2015]Kinoman|线段树
枚举左区间线段树维护最大值#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#include<queue>#include<set>#include<map>#define ll long lon
2016-03-23 15:32:22
1098
原创 4418: [Shoi2013]扇形面积并|二分答案|树状数组
为何感觉SHOI的题好水。。。又是一道SB题 从左到右枚举每一个区间，遇到一个扇形的左区间就+1，遇到右区间就-1，然后再树状数组上2分答案，还是不会码loglog的。。SHOI2013似乎还有一道题发牌也是类似的维护方法。。#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cst
2016-03-23 11:08:12
1307
原创 1640: [Usaco2007 Nov]Best Cow Line 队列变换|后缀数组|贪心
做完1692发现还有弱化版本1640 打板子刷水题大法好，骗访问量大法好#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<vector>#include<cstdio>#include<queue>#include<cmath>#include<set>#include
2016-03-23 07:55:23
1007
原创 1692: [Usaco2007 Dec]队列变换|后缀数组|贪心
将字符串翻转后接到原串的后面，中间加一个分隔符，每次都贪心选择$rank$小的那个其实就是练习一发后缀数组的模板```#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<vector>#include<cstdio>#include<queue>#include<cmath>#includ
2016-03-23 07:38:11
980
原创 3203: [Sdoi2013]保护出题人|三分|凸包
Orz iwtwiioi神犇#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#include<queue>#include<set>#include<map>#define ll long lo
2016-03-22 20:17:47
985
原创 1069: [SCOI2007]最大土地面积|旋转卡壳
旋转卡壳就是先求出凸包，然后在凸包上枚举四边形的对角线两侧分别找面积最大的三角形 由于在两侧找面积最大的三角形的顶点是单调的所以复杂度就是n2n^2 单调的这个性质可以自行画图感受一下，似乎比较显然#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include
2016-03-22 15:20:03
1033
原创 4444: [Scoi2015]国旗计划|贪心|倍增
因为没有区间被其他区间包含这个条件，也就是如果li<ljl_{i}<l_{j}那么一定满足ri<rjr_{i}<r_{j}，就可以贪心搞一搞了。 假如区间[l,r][l,r]都已经被覆盖，那么可以继续找一个lil_{i}在[l,r][l,r]范围内的最大的一个，继续扩展覆盖的区间，然后再以同样的方式找下一个战士 这样可以按照左端点排序，然后每一个战士要找的下一个战士都是确定的，然后用倍增找出一
2016-03-22 10:34:28
1551
原创 4448: [Scoi2015]情报传递|主席树|离线操作
可以把所有的操作离线，然后树链剖分将所有人搜集情报的时间加入到主席树中，查询的时候可以直接查询搜集情报时间≤i−C[i]−1\leq i-C[i]-1的人的个数 时间复杂度n∗log22nn*log_{2}^2n，空间复杂度n∗log2nn*log_{2}n#include<algorithm>#include<iostream>#include<cstdlib>#include<cstri
2016-03-22 07:48:50
1534
原创 4443: [Scoi2015]小秃玩矩阵|二分答案|匈牙利
第KK大看成第KK小各种WA。。。 第KK大也就是第n−K+1n-K+1小，所以就可以愉快的二分答案了 二分答案找出比当前答案小的数的位置的坐标，判断一下是否可以选出满足不在同一行同一列的n−K+1n-K+1个数，然后就可以愉快的跑匈牙利了，对于一个坐标(x,y)(x,y)如果满足a[x][y]≤a[x][y]\leq当前答案，就把第xx行向第yy列连边，然后跑匈牙利判断最大匹配是否大于n−K+
2016-03-21 16:22:16
1484
1
原创 1951: [Sdoi2010]古代猪文|数论大合集
做这个题大概需要直到以下姿势：快速幂，费马小定理，卢卡斯定理，中国剩余定理。（大概也就这些题目大概是让求g∑d|nCdnmodpg^{\sum_{d|n}C_{n}^d}\quad mod\quad p 然后根据费马小定理原式=g∑d|nCdnmod(p−1)modp=g^{\sum_{d|n}C_{n}^d\quad mod\quad (p-1)}\quad mod\quad p 然后也就是要
2016-03-21 08:34:30
1583
3
原创 3813: 奇数国|树状数组|欧拉函数
题目显然让求φ（∏i=lrai）φ（\prod_{i=l}^{r}a_{i}） 可以用线段树维护一下乘积然后求逆元再求欧拉函数，用压位的方法可以缩小60倍的常数。考虑一下树状数组的做法，因为只有6060个质因子，所以可以开6060个树状数组维护每一个质因子，最初维护了前缀的乘积然后T飞了。因为乘法比起加法还是比较慢的所以可以维护一个前缀的指数和，这样就可以在BZOJ成功卡进最后一页QAQ，然而UO
2016-03-20 15:48:07
1095
原创 1408: [Noi2002]Robot|快速幂|欧拉函数
真是一道神题，语文渣渣表示已经给题意描述跪烂了。。 独立数显然就是欧拉函数φφ 然后政客军人他们的分解成的奇素数的指数显然都是11，最初的思想就是暴力枚举只有1个奇函数的情况，2个，3个…………这样显然是会超时，可以发现欧拉函数是满足积性的，所以可以放到一起乘起来算用一种类似于DP的“前缀和”的思想来做 ans1ans1表示当前有奇数个奇数质因子的”前缀和” ans2ans2表示当前有偶数个
2016-03-20 10:46:49
1477
原创 2751: [HAOI2012]容易题(easy)|快速幂
很显然就是每一个位置可以取得数字之和都乘起来 然后限制并不多，也就是说大部分位置上的数字之和是相同的，然后用快速幂单独把这些的乘积搞出来，然后再单独算那些有限制的位置。 PS:PS:限制可能有重复，所以要特判一下，不过样例良心给了重复的#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#inclu
2016-03-20 08:42:10
1416
原创 2721: [Violet 5]樱花|约数个数
先跪一发题目背景QAQ 显然x,y>n!x,y> n!,然后可以设y=n!+dy=n!+d 原式子可以化简成x=n!2d+n!x=\frac{n!^2}{d}+n! 那么解的个数也就是n!n!的因子个数，然后线性筛随便搞一搞#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<queue>#
2016-03-20 07:44:56
1360
原创 3105: [cqoi2013]新Nim游戏|贪心|高斯消元
显然先手取完后需要保证剩余的火柴数不存在抑或和为0的子集，否则先手必败。 这样可以选择出让不存在抑或和为0的子集的集合尽量大，然后用总数减去最大的这个值，然后就是BZOJ2460BZOJ2460http://blog.csdn.net/ws_yzy/article/details/50931193 这根本就是双倍经验吗#include<iostream>#include<algorithm>
2016-03-19 15:47:00
940
2
原创 2460: [BeiJing2011]元素|线性基|高斯消元|贪心
贪心从大到小加入，正确性不是很会证（根本不会证），需要用到拟阵来证明 总之做法就是从大到小贪心加入，如果不与已选的元素冲突，那么就贪心选他#include<iostream>#include<algorithm>#include<cstdlib>#include<cstdio>#include<cstring>#include<vector>#include<cmath>#inclu
2016-03-19 15:19:43
1102
原创 3629: [JLOI2014]聪明的燕姿|约数和|DFS
设M(x)M(x)为xx的约数和，那么考虑约数和的求法，约数和显然是一个积性函数。 设x=pt11∗pt22∗pt33∗......∗ptnnx=p_{1}^{t_{1}}*p_{2}^{t_{2}}*p_{3}^{t_{3}}*......*p_{n}^{t_{n}} 那么M(x)=∑c1=0t1pc11∗∑c2=0t2pc22∗∑c3=0t3pc33∗......∗∑cn=0tnpcnnM(
2016-03-19 09:59:01
1126
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人