- 博客(56)
- 收藏
- 关注
RSS订阅原创 Codeforces #458 (Div1 + Div 2)
由于不是修仙党看见晚上12点开还3个小时就没打，后来线下开虚拟赛打的...估计现场打能涨不少分？不过现场状态会更好还是更坏也说不定A. Perfect Squares题意: 求给定集合中最大的完全平方数 n<=1000 |ai|<=1000000Sol:签到，我硬是没看见有负数WA了一发Code:#include<bits/stdc++.h>using namespace...
2018-01-22 20:59:15
1160
原创 POI2005 泛做
快NOIP了...最近又感觉无所事事...做点题写写总结找找状态= =只做了BZOJ上那些AC人数较多的题 (没几个人过的题不敢看-------------------------------------分隔线-------------------------------------BZOJ1529 [POI2005]ska Piggy banks题意:有n个小猪存钱罐，i号罐子的
2017-10-25 22:34:10
616
原创 BZOJ4596 黑暗前的幻想乡 Matrix_Tree定理 容斥原理
题意：n个点的图其中每条边都有颜色且共有n-1种颜色，求一个生成树满足每种颜色的边出现且仅出现一次Sol:容斥全靠猜系列答案=所有边生成树个数-少一种颜色生成树个数+少两个...生成树个数用矩阵树定理算一下，注意符号Code:#includetypedef long long ll;using namespace std;const int maxn = 19;co
2017-08-15 20:20:08
418
原创 Codeforces53E Dead Ends Matrix_Tree定理 容斥原理
题意：给出一个n个点的无向图，求恰好有k个叶子的生成树个数 nSol: 如果是完全图，n个点的带标号生成树个数为n^{n-2} 可以用矩阵树定理或者打表+oeis证明那么在完全图上求恰好k个叶子的生成树就考虑容斥，钦定有几个点一定是叶子，剩下的点用公式算，每个钦定的叶子都可以接在非钦定的点下面，乘起来在乘个组合数就行，复杂度可以做到O(nlogn) log是快速幂的复杂度现在给出图
2017-08-12 18:01:55
595
原创 Codeforces835E 二进制乱搞
题意：n个元素中有两个是特别的，"不特别的"元素都是x，"特别的"都是y，且x≠y,现在你可以最多询问最多19次找到特别的元素的位置询问可以询问一个子集元素的异或和,nSol:第一次见到这种题呢，长见识了desu...考虑如果只有一个怎么做，只要得到了一个子集的异或和就能知道特殊的是否在这个集合里，于是可以二进制分组然后确定每一位，需要操作logn次两个怎么办呢，首先还是二进制
2017-08-01 19:48:11
1479
原创 李超线段树
现在要求你在线动态维护一个二维平面直角坐标系，支持插入一条线段，询问与直线x=x0相交的所有线段中交点y的最大/最小值--李超线段树解决的问题现在我们只考虑询问最大，事实上最小是同理的线段树维护覆盖这个区间的"最优势线段"，"最优势线段"指覆盖此区间且暴露最多的线段比如对于区间A红色为"最优势线段"可以证明对于一个位置的询问，答案一定在所有包含这个位置的区间的"最优势线段"里
2017-07-28 21:44:57
6505
原创 BZOJ3122 [Sdoi2013]随机数生成器 数论
题意：对于递推式X_{i}=(a*X_{i-1}+b)%p | X_{1}=c 求最小的n满足X_{n}=t 其中a,b,c,t,p为给定非负整数且p为质数,0Sol:把递推式展开得 X_{n}=x1*a^(n-1)+(a^(n-1)+a^(n-2)...a^0)*b括号里是等比数列，根据求和公式得 X_{n}=x1*a^(n-1)+b*(1-a^(n-1))/(1-a)=a^(n-1
2017-07-27 18:49:24
344
原创 Coci2015泛做
最近比较颓废，写点题练练智商...感觉自己还是太弱了进入正题BZOJ3743 [Coci2015]Kamp 题意:一棵树有边权，有k个关键点，求在每个点出发遍历每个关键点一次的最小边权和Sol:对于一个点，ans_i=以i为根的k个点的虚树边权和*2-i出发最长链;一遍dfs求出子树边权和,向下最长/次长链，再dp一遍出解,时间复杂度O(n)BZOJ3745 [Coci
2017-07-09 20:51:14
508
原创 组合数取模
经典问题：怎么计算当n不大时 (n复杂度n稍大(np如果此时p是几个不同素数的乘积，可以分别lucas然后中国剩余定理合并但如果p=p1^k1*p2^k2...怎么办(保证pi^ki此时是不能用lucas的，因为pi^ki不是素数考虑能不能算出n! m! (n-m)!来做但是阶乘在模意义下一旦i>p就是0，逆元就没法算了，怎么办对于pi^ki 我们尝试把x! 分
2017-07-06 23:00:10
340
原创 BZOJ3926 [Zjoi2015]诸神眷顾的幻想乡 广义后缀自动机
神々が恋した幻想郷 ~ Kamigami ga Koishita Gensoukyou题意：一棵树点上有字符，求树上路径所组成的本质不同的字符串的个数，保证叶子数Sol:陈老师出的题..Orz首先由一个结论：树上任意一条简单路径都可以被以某个叶子为根的树上的一条纵向链表示，即枚举每个叶子作为根，所有纵向链的并集=所有路径的集合简单证明：随便选一个叶子作根，不是纵向链的简单路
2017-06-26 22:32:24
421
原创 BZOJ3676 [Apio2014]回文串 Manacher+后缀数据结构
题意：一个子串的价值被定义为长度*出现次数，求价值最大的回文子串Sol：首先本质不同的回文子串个数是O(n)级别的，可以用Manacher求出然后就是要求一个子串的出现次数可以用后缀数组+二分求，也可以用后缀自动机定位到子串所属前缀在自动机上的位置，要在Parent树上找这个点到根路径上满足 len ∈ [min,max] 的节点的 Right 集合大小因为max 满足单调
2017-06-23 23:43:41
358
原创 BZOJ2555 SubString 后缀自动机+LCT
题意：给一个串，支持1.询问一个串在当前串中的出现次数2.在串尾加一个字符串强制在线Sol：如果没有添加操作，答案就是将给定串在SAM上跑到的最终状态的Right集合大小(到不了就是0)Right集合大小可用Parent树算现在有了添加，Parent树是会变化(加边或删边)容易想到可用LCT维护Parent树形态每个点影响的范围是她到根的一条链，影响是链上加自己
2017-06-15 20:37:42
325
原创 BZOJ4516 [Sdoi2016]生成魔咒 后缀自动机/后缀数组
题意：一个串初始为空，n次像串尾添加元素，每次添加后回答本质不同的子串个数nSol:本质不同的子串个数，考虑后缀数据结构发现向结尾添加字符对后缀数组不友好，但是在开头添加很资瓷，相当于新添加一个后缀于是考虑离线，把最终串搞出来在翻转一下，建立后缀数组，问题转化成动态添加后缀求不同子串个数每次找到当前后缀应在位置，去掉后缀对前驱的影响，加上后继与前驱对她的影响，递推即可找
2017-06-14 21:18:51
504
原创 BZOJ2013 [Ceoi2010]A huge tower 乱搞
题意：n块砖各有宽度，A在B的上边当且仅当A不比B的宽度+D长，求放在一起方案数Sol:先排序，考虑从小到大一个个插入因为当前插入的一定最大，比她小的一定能在它上面，只需考虑她能放在谁上面显然可以放在底下，此外还有一段连续区间可以放那么可以每次二分区间左端点然后乘法原理发现左端点是单调不降的，可以维护指针扫过去，复杂度瓶颈在于排序如果采取更优秀的排序算法可以做到线性时间
2017-06-08 23:35:07
662
原创 BZOJ3451 Normal 点分治+FFT
题意：陈老师在点分治时随机选择重心然后分治，每次代价为树的大小，求期望代价nSol:这只是Normal 啊！！Lunatic要难成什么样啊TAT由期望的线性性质，我们可以算出每个点的期望代价求和即为答案。现在选定一个点，考虑其他点对她的贡献，当这个点是她到选定点路径上第一个被钦定的点时会产生1的贡献，所以贡献为1/dis(x,y) dis(i,j)表示i到j路径上的点数(包括端
2017-06-08 23:26:39
674
原创 BZOJ2741 【FOTILE模拟赛】L 可持久化Trie+分块
题意：给定长度为n的序列，m次询问区间最大连续子段异或和nSol：首先搞前缀异或和，问题变成询问区间选两个数最大异或和然后考虑暴力 设f[i][j]表示区间i - j 答案 f[i][j]=max(f[i+1][j],calc(a[i],i+1,j)) calc(x,l,r)表示x与[l,r]中数的最大异或值然后分块大法好，f[i][j]表示i块到j块的，询问时整块直接得到，两
2017-06-06 23:26:47
550
原创 BZOJ3166 [Heoi2013]Alo 可持久化Trie
题意：给定长度为n的整数序列，一个连续子段的收益为子段次大值xor子段中任意数，求最大收益子段值Sol:考虑枚举次大值是谁，则一个数作为次大值时的扩张范围是[左边第二个大于她的数+1 , 右边第一个大于她的数-1] 和 [左边第一个大于她的数+1 , 右边第二个大于她的数-1] 两个区间可以合并起来，用可持久化Trie查询最大异或值。找左右数可以将所有数从小到大排序后顺序枚举，每次
2017-06-06 23:04:38
373
原创 BZOJ 3924: [Zjoi2015]幻想乡战略游戏
题意：动态维护支持修改点权的树上带权重心Sol:看见东方就点进来了233膜拜下陈老师出的题首先考虑如何求一个点到树上其他点的带权距离和，动态点分治可以做到单词O(logn)现在考虑暴力，发现如果求出了每个点到其他点的带权距离和记为权值，那么以带权重心为根，权值从上到下递增，换句话说对于任何一条链，权值都是单峰的。暴力做法可以随便选一个点枚举出边，计算出边指向的点的权值的最小
2017-06-03 07:38:58
578
原创 BZOJ 4598: [Sdoi2016]模式字符串
题意：一棵树点上有字符，给定模式字符串，求树上两点间路径形成字符串为模式字符串重复整数次得到的点对个数Sol：显然的点分治，判断可以将模式字符串的正反版本补齐到n后Hash，对当前重心的每个儿子dfs时记录路径Hash值与之前的配对即可，注意自己与自己的配对关系时间复杂度O(nlogn)这种代码题我竟然1A了233真是感动Code：#include#define debu
2017-06-01 21:20:13
591
原创 BZOJ 2459 [BeiJing2011]神秘好人
题意：2行n列网格图，边有边权，支持1.修改边权2.询问两点间最短路Sol:身经百战之后，已经没有什么好怕的了，3行n列我也写给你看= =把Traffic的bool数组改成int维护长度就行了也是注意绕路情况，合并时耿直的讨论一下Code:#include#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#
2017-05-13 22:06:02
453
原创 BZOJ 3995 [SDOI2015]道路修建
题意:2行n列的网格图边有边权，支持1.修改一条边权值2.询问区间最小生成树Sol:又是你，2行n列网格图，线段树套路直接上两个区间的最小生成树如何合并？红边中小的那个一定会加上，考虑大的那个是否保留，如果保留上会形成环，删掉环上最大边即可怎么求形成环上最大边权？显然一个区间内最小生成树至少包括一条竖向边，不难发现一个区间最右竖向边右边所有横向边都在最小生成
2017-05-13 21:58:40
434
原创 BZOJ 4010 [HNOI2015]菜肴制作 拓扑排序
题意：给一个有向图，求一个拓扑序(可能没有)，满足编号小的尽量靠前Sol:最近太颓废了，，，写点题压压惊首先思考这样一种拓扑排序的方法：把普通BFS式拓扑排序的队列换成小顶堆，即优先放置编号小的点这样并不能保证题目条件，比如答案应该是3 1 2 而不是 2 3 1我们发现这个方法实际是保证了字典序最小再分析发现也保证了编号大的尽量靠后于是我们把原图所有边反向，可
2017-05-11 22:17:13
347
原创 BZOJ 1146 [CTSC2008]网络管理Network
题意：给一棵树点有点权，要求支持1.更改点权2.询问链上第k大n,mSol:并不能算Solution，因为我没过....先树链剖分一发，询问变成给定log个不相交区间，询问区间并的第k大带单点修改区间第k大用主席树，带单点修改就在外面套一层树状数组这样的话时间复杂度是O(n*log^3(n) ) ，空间复杂度是O(n*log^2(n) )看起来不错，写完调对交上
2017-05-03 22:13:00
484
原创 BZOJ 1018 SHOI2008 堵塞的交通traffic
题意：2*n的网格图相邻格点之间有边，一开始所有边坏掉了，要求完成以下操作：1.修复一条边2.破坏一条边3.询问两个格点是否直接或间接联通Sol：神题。。。线段树维护连通性。感觉我写了一天+一开始想线段树维护一块内四个角的连通性，开4*4的bool数组合并的时候分类讨论/传递闭包一下下bulabula然后一个点怎么到另一个点呢？显然这是可能的但是还可能这样这
2017-05-01 11:43:41
392
原创 BZOJ 3533 Sdoi2014 向量集
题意：在二维平面内，支持一下操作：1.插入一个向量2.给定一个向量x，询问第[l,r]次插入的向量中，与x向量叉积的最大值
2017-04-27 22:17:54
442
原创 BZOJ 3589 动态树
3589: 动态树Time Limit: 30 Sec Memory Limit: 1024 MBSubmit: 517 Solved: 182[Submit][Status][Discuss]Description别忘了这是一棵动态树, 每时每刻都是动态的. 小明要求你在这棵树上维护两种事件事件0:这棵树长出了一些果子, 即某个子树中的每个节点都会长出K个
2017-04-25 22:39:38
375
原创 BZOJ 4202: 石子游戏 SG定理+LCT
4202: 石子游戏Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 37 Solved: 15[Submit][Status][Discuss]Description石子游戏是大家都很喜欢玩的一类游戏，这类游戏通常与石子的移动和取舍有关，往往可以让人在游戏中获得不少的乐趣。有一类树上石子游戏的规则是这样的：在一棵有根
2017-04-17 21:43:25
695
原创 Liner_Shaker_Full
线性筛法(不)完全版求出素数，欧拉函数，莫比乌斯函数，约数个数函数，约数和函数等原理：1.线性筛法保证每个数只被最小素因子更新(这也是复杂度为线性O(N)的保证)2.大部分积性函数支持线性筛法求值 (这里包括完全积性函数和不完全积性函数)3.相关公式令 , 表示因子个数有对于下面两个函数，可以处理出每个数最小质因子的相关信息(次数
2017-04-11 13:25:45
298
原创 BZOJ 4012: [HNOI2015]开店 -- 动态树分治
4012: [HNOI2015]开店Time Limit: 70 Sec Memory Limit: 512 MBSubmit: 1463 Solved: 635[Submit][Status][Discuss]Description 风见幽香有一个好朋友叫八云紫，她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动，打算在幻想乡开一家小店来做生意赚点钱
2017-03-11 16:43:24
684
原创 POJ-3693--后缀数组求字典序最小重复次数最多子串
摘自2009年国家集训队罗穗骞论文《后缀数组-处理字符串的有力工具》因此我们只需处理出原串正反两个版本的后缀数组，然后用rmq问题的处理方法求LCP，我的处理方法是让关键点包含在r中，如果想包含在l中，只需把向前向后扩展的位置稍作处理&查询rank最小值的区间端点分别+1即可。字典序最小的处理方法摘自hzwer博客orz因为每次我们找到了合法答案，子串起点∈[i-l,i-l+(
2017-01-22 15:41:33
758
原创 最大全0子矩阵问题
题意：给定一个01矩阵，求：1.最大全0正方形面积2.最大全0子矩阵面积-----------------------------------------我是分割线-----------------------------------------对于第一问，我们有O(nm)的动态规划解法：设f[i][j]表示以i,j为右下角的最大正方形边长if(a[i][j]==0) f[
2017-01-18 23:29:31
2161
原创 经典树形DP-剪树杈
给定一棵树，点有颜色(黑/白)，将树分成若干部分，使得每一部分有且仅有一个黑点。设f[i][1]表示以i为根的子树，最上面的连通块内有一个黑点的方案总数f[i][0]表示以i为根的子树，最上面的连通块内没有黑点的方案总数#includeusing namespace std;typedef long long ll;const ll mod = 1e9+7;co
2016-11-21 14:48:43
627
原创 康托展开
给定排列，求其唯一映射的排列编号：rank[a[1]]*(n-1)!+rank[a[2]]*(n-2)!....ran[a[n]]*(n-n)!int Cantor(int a[]){ int ans=0; for(int i=1;i<=n;i++) { int cnt=0; for(int j=i+1;j<=n;j++) if(a[i]>a[j])
2016-11-17 12:24:55
313
原创 C++高精度模版
const int maxn = 10010;struct Bign{int a[maxn];int len;Bign(){memset(a,0,sizeof a);len=1;}Bign operator = (long long num){memset(a,0,sizeof a);len=0;while(num){len++;a[
2016-10-29 19:31:40
309
原创 USACO-奶牛叠罗汉--交换法贪心思想
Cow AcrobatsTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 4433 Accepted: 1704DescriptionFarmer John's N (1 <= N <= 50,000) cows (numbered 1..N) are pl
2016-09-24 23:28:52
1382
原创 乘法逆元模板
我们知道，在模意义下，加减乘运算是封闭的;例如在模17意义下，8+11=((8%17)+(11%17))%17=2，19+21=((19%17)+(21%17))=6;减法同理，但是在C++编译器中取模的意义是与数学上不同的，负数mod正数应该是非负数，但是C++却可能模出负数，所以我们要多加一些处理，对于x,可以(x%mod+mod)%mod保证其正确性，比如在模17意义下，21-19=
2016-09-23 23:34:40
2958
原创 关于树上倍增求LCA
例：BZOJ1787画图发现规律，三个点两两之间最近公共祖先点的集合最多只有两个元素，分类讨论即可。#includeusing namespace std;#define fi first#define se secondtypedef pair pii; const int maxn = 500010;int first[maxn];struct edg{ in
2016-09-22 22:21:30
980
原创 floyd求传递闭包
传递闭包问题，我的理解就是通过一些已知的连边求出点与点之间的关系设f[i][j]表示i 与 j 是否联通，f[i][j]=f[i][k]&&f[k][j]时间复杂度O(N^3)POJ-3660#include#includeusing namespace std;const int maxn = 110;int a[maxn][maxn];int n,m;int ans
2016-09-16 00:09:25
1717
1
原创 装压DP及TSP问题的学习
当n比较小的时候（其实为什么要装压呢？比如我们完全可以设计f[a][b][c][d][e][f][g][h][......]描述状态，但是这样是不是看起来很丑呢？我们完全可以设f[i]表示状态为i时的情况，是不是美观多了？TSP问题是装压DP的一种，状态常常设计成f[i][j]表示状态为i，当前在j时的最小花费。有时候我们要先做一遍floyd求出两点之间最小路径长度，然后转移，有时却不
2016-09-13 22:39:02
730
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人