chty_syq-CSDN博客

原创新的独立博客

我的个人独立博客终于搭好了，欢迎诸位大佬前来访问传送门 : http://www.chty.me

2017-03-01 12:37:30 640

原创数论知识总结——史诗大作（这是一个flag）

1、快速幂计算a^b的快速算法，例如，3^5，我们把5写成二进制101，3^5=3^1*1+3^2*2+3^4*1ll fast(ll a,ll b){ll ans=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ans=mul(ans,a);return ans;}//一行快速幂 2、快速乘当模数较大时，直接乘会爆掉long long

2016-12-02 10:37:14 1987 3

原创【bzoj3295】动态逆序对 CDQ分治

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=3295【题解】这题很神。我用的是popoqqq大爷的做法。具体见http://blog.csdn.net/popoqqq/article/details/38761287感觉这种做法似乎应该称为整体二分？#include#include#include#incl

2017-02-23 21:32:52 515

原创【bzoj2683】简单题 CDQ分治+树状数组

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2683【题解】话说这题好像可以用整体二分来做（蒟蒻不会啊），CDCQ大神的整体二分比我的CDQ分治高到不知道哪里去了。说一下做法吧：首先把询问的矩形分成4部分，算一下每部分的答案，然后容斥原理即可。怎样算每部分的答案呢？我们按照时间分治，CDQ递归过程中按x排序，遇到

2017-02-23 11:55:44 371

原创【bzoj3262】陌上花开 CDQ分治+树状数组

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=3262【易错点分析】相信会写CDQ分治的人都会这道题，所以我就来讲一讲博主在做题时遇到的错误（ps：静态查错大法好）1、tb的右端点多次打成r2、排序过程中忘记定义z的优先级3、被题目所坑：考虑两个属性值相同的花，它们的美丽值可以互相超过。。。所以要把相同的花缩成权值的形

2017-02-23 09:17:52 498

原创【bzoj3238】差异后缀自动机

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=3238【题解】题上所给公式可以化为\sum_{1其中：\sum_{1=1×(n-1)+2×(n-2)+3×(n-3)+……+(n-1)×1+2×1+3×2+……+n×(n-1)=(n+1)+2×(n+1)+3×(n+1)+……+(n-1)(n+1)=(1+2+

2017-02-23 07:33:16 433

原创【bzoj4566】找相同字符后缀自动机

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=4566【题解】我们还是先把A串建成SAM，然后让B串在SAM上跑因为相同子串数=不同长度的子串数*出现次数所以每个结点对答案的贡献就是Right[x]*(len-Min(x)+1)我们知道SAM的一个性质：Min(x)-1=Max(parent(x))所以贡献就是Ri

2017-02-22 20:33:29 371

原创【bzoj1224】彩票 dfs

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=1224【题解】裸的爆搜相信大家都会，这里我们主要来谈一谈剪枝。此题使用上下界剪枝：对于当前状态，如果后面的数都选最大的仍不能到达目标状态，则当前状态为不合法状态，直接return，此为上界剪枝，下界剪枝同理。最后膜一发popoqqq大爷，参考他的代码，我省略掉了一个for循环

2017-02-22 16:17:35 436

原创【bzoj2555】SubString 后缀自动机+LCT

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2555【题解】我们把模板串建成SAM，那么一个串的出现次数就是在对应状态上的Right集的大小。那么我们如何在线维护Right集的大小呢？可以用LCT/平衡树+dfs序反正我用的是LCT，毕竟好写。我们用LCT维护parent树，对于新加入的点，连一条通向parent的边

2017-02-22 16:09:32 413

原创【spoj8222】Substrings 后缀自动机

AC通道：http://www.spoj.com/problems/NSUBSTR/【题解】我们知道，在SAM上对于一个结点s,Max(s)的出现次数就是right(s)那么问题就是我们如何求出每个点的right集的大小。我们知道，一个点的right集为它的儿子的right集的并集，所以我们按照拓扑序遍历每个点，同时更新它父亲的答案。#include#include#inc

2017-02-21 21:35:52 306

原创【spoj1812】Longest Common Substring II 后缀自动机

AC通道：https://vjudge.net/problem/SPOJ-LCS2【题解】我们先把其中一个串建成SAM，然后让其它的串在SAM上跑，同时更新每个结点的最大匹配数。每个结点的答案就是所有串在该结点的最大匹配数的最小值。注意：在更新一个结点时，它的父亲必定已经到达过了，要返回去更新父亲的答案。#include#include#include#include#in

2017-02-21 19:00:05 317

原创最长公共子串后缀自动机

【题目描述】给定两个字符串A和B，求它们的最长公共子串【分析】我们考虑将A串建成后缀自动机令当前状态为s，同时最大匹配长度为len我们读入字符x。如果s有标号为x的边，那么s=trans(s,x),len = len+1否则我们找到s的第一个祖先a，它有标号为x的边，令 s=trans(a,x),len=Max(a)+1。如果没有这样的祖先，那么令s=root,len

2017-02-21 10:10:14 473

原创【CF#498C】Array and Operations 网络流

AC通道：http://codeforces.com/problemset/problem/498/C【题目大意】给你一个二分图，左边点的编号为奇数，右边为偶数，给出每个点的权值，每次操作可将图中有边相连的两个点的权值除以他们的一个公因数（不能是1），问最多可以执行多少次这样的操作。【题解】为了得到了最多的操作次数，每次操作一定是除以两个数的公共的质因数。所以我们对于每一个

2017-02-21 08:27:27 268

原创【bzoj3514】GERALD07加强版 LCT+主席树

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=3514【题解】来自wulala大神的题解：葱娘说这是一个很巧妙的题。。有一个比较猎奇的做法：首先把边依次加到图中，若当前这条边与图中的边形成了环，那么把这个环中最早加进来的边弹出去并将每条边把哪条边弹了出去记录下来：ntr[i] = j，特别地，要是没有弹出边，ntr[i

2017-02-20 19:21:13 327

原创 0219考试总结

T1【题目大意】n个人，每个人都有一枚邮票和一些喜欢的邮票。每次可以把任意个人的邮票进行一次轮换，并且轮换后每个人必须拿着一枚喜欢的邮票，求最终能否让每个人都拿到一枚喜欢的邮票。【吐槽】这题出得神坑，直把人往tarjan上带。正解如下：其实那个交换方式只是吓唬人的。对于每一种分配方案，我们都可以构造出一种交换方案达到这样的效果。所以就是判断能不能给每个人分配一枚

2017-02-19 21:57:14 250

原创【CF#715C】Digit Tree 点分治+乘法逆元

AC通道：http://codeforces.com/problemset/problem/715/C【题目大意】给定一个有N个点的树，问其中有多少条路径满足他们的边权连成的数对M取余为0。其中gcd(M,10)=1。【题解】首先是点分治的套路，然后这题的主要难点在如何统计连通块中的答案。对于x→y的路径，也就是x→root→y，我们可以处理出dis[x]和dis[y]

2017-02-19 21:45:42 1401

原创【bzoj2084】Antisymmetry manacher

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2084【题解】我们要求反对称的子串个数，只需要定义'#'='#'，'0'='1'，'0'≠'1'，'1'≠'0'，然后求回文子串个数即可。直接上manacher，时间复杂度O(n)#include#include#include#include#include#in

2017-02-19 20:19:33 295

原创【bzoj3697】采药人的路径点分治

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=3697【题解】来自出题人hta的题解：本题可以考虑树的点分治。问题就变成求过根满足条件的路径数。路径上的休息站一定是在起点到根的路径上，或者根到终点的路径上。如何判断一条从根出发的路径是否包含休息站？只要在dfs中记录下这条路径的和x，同时用个标志数组判断这条路径是否存在

2017-02-18 11:12:13 334

原创【bzoj2599】Race 点分治

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2599【题解】直接调用黄学长的题解：开一个100W的数组t,t[i]表示权值为i的路径最少边数找到重心分成若干子树后，得出一棵子树的所有点到根的权值和x，到根a条边，用t[k-x]+a更新答案，全部查询完后然后再用所有a更新t[x]这样可以保证不

2017-02-18 09:01:15 361

原创【bzoj2152】聪聪可可点分治

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2152【题解】还是点分治的板子。统计答案的方法值得一学：用t数组记录连通块中所有点的距离对3取模后的结果，然后当前的答案就是t[0]*t[0]+t[1]*t[2]*2，为什么要乘2呢？——因为同一个点对（u，v）聪聪选u可可选v与聪聪选v可可选u是不一样的。#include

2017-02-18 08:05:33 249

原创【poj1741】tree 点分治

【题目大意】给一颗n个节点的树，每条边上有一个距离v（v定义d(u,v)为u到v的最小距离；给定k值，求有多少点对（u，v）使u到v的距离小于等于k。其中n【题解】蒟蒻发现很久以前学的点分治已经忘得差不多了，于是恶补一发所谓点分治，就是枚举每一个点为根的情况，计算当前根对答案的贡献。具体可以参考http://www.cnblogs.com/chty/p/5912

2017-02-18 07:20:08 320

原创 0217考试总结

今天做了一套奇奇怪怪的题。T1【题目大意】规定将一个序列的权值为将其进行冒泡排序的最少交换次数，给定一个序列P，求字典序不大于P的序列的权值之和。【吐槽】我在场上写了一个和标算时间复杂度同阶的数位dp+线段树做法，然后。。。就爆栈空间了，50分gg修改之后是70，后三组丧心病狂卡线段树的常数，蒟蒻只好去膜拜松爷的卡常技巧，硬是从3700ms卡到了1082ms，然而还是超时。

2017-02-17 19:30:28 546 1

原创【bzoj3282】Tree LCT

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=3282【题解】模板题，xor什么的跟求和是一样的。#include#include#include#include#include#include#includeusing namespace std;#define FILE "read"#define MAX

2017-02-17 19:09:33 215

原创【bzoj2157】旅游 LCT

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2157【题解】很模板的题目。首先还是把边建成点（这是一种套路），然后上LCT维护就行了。这题还有一个启示：在打标记时要直接下传一次，否则会出现查询时还没有下传标记的情况。#include#include#include#include#include#inclu

2017-02-17 17:26:12 338

原创【bzoj1180】OTOCI LCT

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=1180【吐槽】马上就要回宿舍了，于是蒟蒻在此水一道模板题。#include#include#include#include#include#include#includeusing namespace std;#define FILE "read"#define

2017-02-16 21:49:34 226

原创【bzoj1146】网络管理主席树+树状数组+树链剖分

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=1146【题解】这题真神，蒟蒻只好参考cydiater大神的代码，然后调了整整一下午和一晚上。做法是这样的：先把树剖掉，按时间戳建立主席树，这里有一个技巧，在[n+1,n+n]区间上建主席树，而不是直接按树状数组的初始值来建，可节省nlogn的空间。修改操作很简单，在查询时先求

2017-02-16 20:30:46 549

原创【bzoj2588】Count on a tree 主席树

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2588【题解】我们用主席树维护每一个结点到根的路径（按dfs序建主席树即可），然后有一个优美的性质：x到y的路径可以表示为T(x)+T(y)-T(t)-T(f[t])，其中t为lca(x,y)这样在回答询问时处理这4个版本的线段树就行了。经此题实测：手写hash离散比st

2017-02-16 11:38:45 245

原创【bzoj2809】dispatching 主席树+dfs序

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2809【题解】对于题上给的树，我们在它的dfs序上瞎搞。我们按照dfs序建主席树，主席树中以花费的离散值为权，并维护总花费。然后查询答案的时候，枚举每个点为管理者的情况，计算答案。这样问题就转化为了在子树内找到最多的点，使得这些点的花费小于m，用主席树就能完美解决这个问题

2017-02-16 10:24:54 438

原创【bzoj1901】带修改的区间第k大主席树+树状数组

【题目大意】给定一段序列，要求一个数据结构，支持两个操作。1.修改某个数。2，查询某段区间的第K大。【题解】我们知道如果没有修改操作，那么直接将两个版本的线段树差分即可。其实这个差分用的就是前缀和的思想，如果带修改操作的话，可以考虑用树状数组维护。我们可以在树状数组中插入线段树（想想都是exciting），每次修改权值也是在树状数组中对应的线段树修改，查询时用树状数组查找根的编

2017-02-15 20:35:30 852

原创【bzoj3524】Couriers 主席树

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=3524【题解】用主席树直接查找就行了，如果左子树sum[son[x][0]]-sum[son[last][0]]就去左子树找，右子树同理，如果都没有，那就返回0.#include#include#include#include#include#include#incl

2017-02-15 17:07:23 269

原创【bzoj2243】染色树链剖分+线段树

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2243【题解】神坑题目，今天一天都在调这道题了。首先asksum函数中忘记判断区间合并时出现相同颜色的情况，导致wa不断。然后要到了数据，查出了这个错误。然而忘记了deep[1]=1,导致在求lca的过程中访问到0号结点，然后又开始RE然后我的一整天都在二分出错位置了

2017-02-15 16:48:48 244 1

原创【poj2104】不带修改的区间第k大主席树

【题目大意】给定一个长为N的序列，每个序列的权值为Ai.有M个询问，每个询问为(L,R,K),分别代表[L,R]的第K大的数。期中n=100000，m=5000【题解】用主席树解决，那么什么是主席树呢？首先我们先明确一下权值线段树的概念。平常我们用的线段树都是区间线段树，而权值线段树和平衡树中树的结点意义是类似的。权值线段树中（下文所说线段树均值权值线段树），每个结

2017-02-15 15:33:15 300

原创【bzoj2631】tree LCT

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2631【题解】参考黄学长的代码，学到了同时传递加法和乘法标记的方法。注意如果在传递乘法标记的同时传递了加法标记，那么加法标记也要乘上这个数。#include#include#include#include#include#include#includeusing

2017-02-15 14:01:56 219

原创【bzoj1500】维修数列 splay

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=1500【题解】这是一道很恶心的题，虽然差不多是splay的板子。我们用mx[x]表示以x为根的子树内最大子串和，lx[x]表示以x为根的子树中以左端点为起点向右延伸的最大子串和，rx[x]表示从右端点向左延伸的最大子串和。维护rx和lx的过程中要注意单个结点的情况：如果v[x

2017-02-15 09:18:30 298

原创【bzoj3669】魔法森林 LCT+并查集

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=3669【题解】据说spfa可以说过。。。。。。LCT做法：将边权按其中一个值排序，往里面加边，用并查集维护图的连通性，当1与n联通时更新答案。用LCT维护图中的另一边权的最大值，如果边的两端不连通直接加入，否则说明构成了环，删去环上最大的边。小技巧：边可以建成点，向边的两

2017-02-14 21:41:43 322

原创【bzoj1036】树的统计树链剖分/LCT

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=1036【题解】看到题目，发现是树剖一眼题，所以就秒掉了。#include#include#include#include#include#include#includeusing namespace std;typedef long long ll;#defin

2017-02-14 20:21:08 378 1

原创【bzoj2002】弹飞绵羊 LCT

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2002【题解】LCT的模板题。从点i向i+ki连边，构成一颗树，询问等价于求x结点的深度，修改就是删去原边，加入新边。这些都是LCT的基本操作。#include#include#include#include#include#include#includeu

2017-02-14 13:52:08 318

原创【bzoj2049】Cave洞穴勘测 LCT

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2049【吐槽】模板题，用来练习LCT。今天晚上啃了一下LCT，感谢柳志轩大神，我已经完全理解了LCT一些细节的说明在代码中有注释#include#include#include#include#include#include#includeusing nam

2017-02-13 21:48:37 269

原创【bzoj1103】大都市meg 树链剖分+线段树

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=1103【题解】直接上树剖就好了，然而我的树剖本地测试5.2s，交到bzoj上却超时了，可能是蒟蒻自带大常数吧。#include#include#include#include#include#include#includeusing namespace std;t

2017-02-13 15:03:12 291

原创【bzoj4034】树上操作树链剖分+线段树

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=4034【题解】用树剖来做的话，做法很显然，比模板题还简单。不过，据说可以用dfs序搞一搞。#include#include#include#include#include#include#includeusing namespace std;typedef l

2017-02-13 10:50:57 291

MultiCPU.rar

18条指令单周期CPU设计

空空如也