- 博客(93)
- 收藏
- 关注
RSS订阅转载 将博客搬至CSDN
http://blog.csdn.net/gjghfd转载于:https://www.cnblogs.com/gjghfd/p/6906054.html
2017-05-25 21:28:00
80
转载 codeforces801E Vulnerable Kerbals
题目大意：给定n个数，构造一个序列，满足所有前缀积模m互不相等且不与n个数中任意一个相等。最大化序列长度。将1~m-1每个数作为一个点，如果存在a，使得 i*a=j (mod m)，那么从i向j连一条有向边。那么答案就是图中的最长路径。又因为如果 i*a=j (mod m)，则gcd(i,m)|gcd(j,m)，所以可以将gcd(i,m)相等的所有点缩成一个点，每个点向...
2017-05-25 21:02:00
134
转载 codeforces805F Expected diameter of a tree
题目大意：给定一个森林，有若干个询问，每次询问在第i棵树中随机选一个点，在第j棵树中随机选一个点并将它们相连后树的直径的期望值。对每棵树求出它的直径d，对每个点求出它到树上最远点的距离f，那么选择x、y点时树的直径就是：max(d[i],d[j],f[x]+f[y]+1)对每棵树中点的f排序。枚举一棵树中每个点，再二分另一棵树的f就能统计答案了。具体看代码。...
2017-05-25 20:45:00
119
转载 bzoj1857 [ SCOI2010 ] -- 三分套三分
显然我们一定是先走到AB上一点X，然后走到CD上一点Y，最后到D。那么答案就是|AX|/P+|XY|/R+|YD|/Q假设我们已经确定了X，那么目标就是在CD上找一点Y，使|XY|/R+|YD|/Q最小。显然这是个单峰函数。那么三分套三分就可以了。代码：#include<iostream>#include<cstdio>...
2017-05-19 17:02:00
91
转载 bzoj3626 [ LNOI2014 ] -- 树链剖分
直接复制gconeice的题解吧显然，暴力求解的复杂度是无法承受的。考虑这样的一种暴力，我们把 z 到根上的点全部打标记，对于 l 到 r 之间的点，向上搜索到第一个有标记的点求出它的深度统计答案。观察到，深度其实就是上面有几个已标记了的点（包括自身）。所以，我们不妨把 z 到根的路径上的点全部 +1，对于 l 到 r 之间的点询问他们到根路径上的点权和。仔细观察上面的暴力不难发现...
2017-05-13 09:34:00
60
转载 bzoj2165 -- 倍增floyd
题意：给定一张有向图，求图中从1开始长度>=m且边数最少的路径经过的边数。考虑倍增floyd。令f[p][i][j]表示经过2p条边从i到j的最大长度。那么f[p][i][j]=max{f[p-1][i][k]+f[p-1][k][j]}令g[i][j]表示当前答案从i到j的最大长度。求答案时从大到小枚举每个二进制位，更新g，若不存在从1开始长度>=...
2017-05-09 11:22:00
168
转载 bzoj4881 [ Lydsy2017年5月月赛 ] -- 二分图染色+线段树
以下是Claris的题解：若线段 i 和 j 相交，那么在它们之间连一条边。若这个图不是二分图，那么无解，否则令cnt 为连通块个数，那么 ans = 2cnt。在二分图染色的过程中，每个点只需要被访问一次。对于当前所在的点 x，它可以一步走到 [1, x) 里 p[i] > p[x] 的所有 i，以及 (x, n] 里 p[j] < p[x] 的所有 j。用线段...
2017-05-07 11:40:00
70
转载 bzoj2588 -- 树链剖分+主席树
先将权值离散。显然可以对于每个结点建一棵权值线段树存这个点到根结点的路径上的点权，询问时在线段树上二分，但这样时间是O(n2log2n)的。然后想到用主席树优化，时间复杂度O(n*log2n)。代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring&g...
2017-05-04 17:36:00
107
转载 bzoj4712 -- 树链剖分
题解：http://www.cnblogs.com/clrs97/p/6006305.html代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<...
2017-04-24 18:22:00
76
转载 bzoj4546 -- 可持久化字典树
可持久化字典树模板题。。。把每个数转换成二进制建立字典树，按照下标建立可持久化字典树，存一下子树中点的个数就行了。代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using...
2017-04-24 11:22:00
96
转载 bzoj2120&&2453 -- 带修改莫队
待修改莫队裸题。。。当莫队有修改操作时，只要记录每个询问的时间，在两次询问之间修改就可以了。可以证明时间复杂度是O(n^(5/3))的具体看代码。代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<alg...
2017-04-21 10:21:00
82
转载 bzoj4726 [ POI2017 ] -- 树形DP
显然：1、最坏情况下最初的叛徒一定是叶子。2、若x不是叛徒，那么x的父亲也不是叛徒。令f[i]表示i不是叛徒的最小x，s[i]表示i的子树大小，那么答案就是所有s[i]>k的f[i]的最大值。接下来考虑怎么求f[i]。当i是叶子节点时，因为每个叶子节点都有可能是叛徒，所以f[i]应是1，表示只有f[i]>1时可行。当i不是叶子节点时，枚举每个子节点j。...
2017-04-21 08:46:00
58
转载 bzoj2809 [ APIO2012 ] -- 主席树
先求出dfs序，然后枚举管理者。由于只要求数量最多，所以薪水一定从小到大取，用主席树维护，每次在主席树上二分就可以了。具体看代码。代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm>...
2017-04-20 20:02:00
100
转载 bzoj4216 -- 分块
如果没有内存限制，显然树状数组就可以了。有了内存限制，我们使用分块。因为没有修改操作，所以可以每16个数分一个块。时间复杂度O(16*n)注意不要用using namespace std，会占用1M不到的内存代码： 1 #include<cstdio> 2 #include<cstring> 3 #include<...
2017-04-19 09:14:00
81
转载 bzoj4173 -- 欧拉函数
题解：http://blog.csdn.net/PoPoQQQ/article/details/46820313代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #includ...
2017-04-19 07:52:00
52
转载 bzoj2982 -- Lucas定理
Lucas定理裸题。。Lucas定理:C(n,m)=C(n%p,m%p)*C(n/p,m/p)%p预处理出阶乘、逆元的阶乘就可以了。代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm>...
2017-04-18 18:16:00
39
转载 bzoj2653 -- 二分+主席树
对于每一个询问二分答案。设当前答案为x，将>=x的数的权值设为1，<x的数的权值设为-1。当 [b+1,c-1]的权值和+[a,b]权值和最大的后缀+[c,d]权值和最大的前缀>=0时x可行。先对每个数离散，然后以每个值建立主席树记录区间和、最大前缀、最大后缀就可以了。时间复杂度：O(n*log3n)代码： 1 #include&l...
2017-04-18 17:54:00
59
转载 bzoj3289 -- 莫队+树状数组
离线。将大小离散，然后用莫队更新树状数组和答案就可以了。代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namesp...
2017-04-15 10:10:00
114
转载 bzoj2599 [ IOI2011 ] -- 点分治
令ans[i]表示权值和等于k的路径条数，然后点分治就可以了。具体看代码。代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<vector> 6 u...
2017-04-09 20:44:00
58
转载 bzoj1077 -- 并查集
看这位大佬的题解就可以了。http://blog.csdn.net/Fuxey/article/details/50573495代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #...
2017-04-07 15:24:00
43
转载 bzoj4807 -- 组合数
容易看出答案就是C(n,m)。。。然后高精乘一下就可以了。对n!分解质因数时，质数p的出现次数是n/p+n/p^2+n/p^3+...代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm&g...
2017-04-02 08:53:00
91
转载 bzoj2957 -- 线段树
考虑线段树。对于一段区间，记录它的最大斜率和只考虑区间内约束的答案。合并时一段区间的答案就是左子区间的答案加上右子区间考虑左子区间约束之和的答案。求一个区间约束为h的答案时，判断左子区间与h的关系。如果不大于h，答案就是右子区间约束为h的答案，否则递归左子区间。时间复杂度O(nlog2n)代码： 1 #include<iostream> 2 #...
2017-03-29 21:20:00
99
转载 bzoj2209 [ JSOI2011 ] -- splay
将左括号记为1，右括号记为-1，则一个合法的括号序列满足所有的前缀和非负。用splay维护。代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespac...
2017-03-28 20:40:00
78
转载 bzoj3874 [ AHOI2014 ] -- 爬山算法
不知道为什么，用模拟退火就WA了。。。显然如果知道了总共购买几次，就可以贪心地求出答案。那么套个爬山就行了。代码： 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<cstring> 5 #include&l...
2017-03-28 17:38:00
143
转载 bzoj1038 [ ZJOI2008 ] -- 模拟退火+二分
这题正解是半平面交，但可以用模拟退火水过。。。用模拟退火求x的值，然后二分求y的值就可以了。当所有端点到这个点的直线按逆时针顺序时这个点可以看到任何位置。代码： 1 #include<iostream> 2 #include<cstdlib> 3 #include<cstring> 4 #include<...
2017-03-27 21:02:00
79
转载 bzoj2428 [ HAOI2006 ] -- 模拟退火
题目大意：已知N个正整数：A1、A2、……、An。今要将它们分成M组，使得各组数据的数值和最平均，即各组的均方差最小。思路：考虑模拟退火。每次先对每个数随机分在哪个组，然后每次退火随机一个数x，将其换到组y，取y时按温度分类：若温度高，则此时不稳定，y取温度最小的组。若温度低，则此时已经接近稳定，随机选一个y。只做一次显然有很大概率错误，所以要做至少100...
2017-03-27 19:01:00
61
转载 bzoj3680 -- 模拟退火
模拟退火裸题（输出"nan nan"可以AC）代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 using namespace std;...
2017-03-27 17:34:00
56
转载 bzoj4500 -- 差分约束
令a[i]表示第i行总共加了a[i],a[j]表示第j列总共加了a[j]，得到k个方程：a[i1]+a[j1]=c1a[i2]+a[j2]=c2...a[ik]+a[jk]=ck将i,j看成点，一遍dfs求出a并判断是否合法即可。代码： 1 #include<iostream> 2 #include<cstdio>...
2017-03-26 17:41:00
76
转载 bzoj3527 -- FFT
代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 #define N 800010...
2017-03-26 13:31:00
49
转载 bzoj1013 [ JSOI2008 ] -- 高斯消元
得到n+1个方程：(a1 1-x1)2+(a1 2-x2)2+..+(a1 n-xn)2=r2(a2 1-x1)2+(a2 2-x2)2+..+(a2 n-xn)2=r2...(an+1 1-x1)2+(an+12-x2)2+..+(an+1 n-xn)2=r2将后n个方程减去第一个方程就能到得到n个n个未知数的线性方程，高斯消元即可。代码： 1 #...
2017-03-19 09:49:00
44
转载 bzoj3732 -- 最小生成树+倍增
显然使A到B的最长边最小的路径一定在最小生成树上，否则一定可以使生成树更小。求出原图的最小生成树，然后用倍增求路径上最大值就可以了。代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 usi...
2017-03-19 08:49:00
83
转载 bzoj2821 -- 分块
将序列分块。令f[i][j]表示第i块到第j块的答案，可以O(n*sqrt(n))统计出来。令sum[i][j]表示前i块值为j的数出现了几次。每次询问暴力统计零散的数对答案的贡献就可以了。具体见代码代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring...
2017-03-18 08:39:00
120
转载 bzoj2956 -- 数论分块
直接分块就行了。注意要求出2和6的逆元。代码： 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 #define M 19940417 7 i...
2017-03-17 18:56:00
51
转载 bzoj1009 [ HNOI2008 ] -- KMP+矩阵乘法加速DP
令f[i][j]表示前i个字符，匹配到不吉利数字的第j位的方案数。枚举第i+1位，通过KMP求出前i+1个字符可以匹配到不吉利数字的第几位，递推。但由于n<=109，要用矩阵乘法加速。f[i][j]=a[j][0]*f[i-1][0]+a[j][1]*f[i-1][1]+...+a[j][m-1]*f[i-1][m-1]那么f[n]就是 an×f[0]用快速幂，...
2017-03-16 10:22:00
90
转载 bzoj2631 -- LCT
包含了link、cut、update、query操作。更新时类似线段树就可以了。代码：#include<cstdio>#include<iostream>#include<cstring>using namespace std;#define N 100010#define M 51061#define ll...
2017-03-16 08:49:00
59
转载 bzoj2117 [ 2010国家集训队 ] -- 点分树+二分答案
考虑点分树。求出每个重心所管辖的范围内的每个点到它的距离，建成点分树。查询时二分答案，然后问题就转化为求到x的距离<=d的点的个数。在点分树上暴力往上跑就行了，注意去重。时间复杂度：O(nlog3n)代码： 1 #include<cstdio> 2 #include<cstring> 3 #include<...
2017-03-15 17:53:00
95
转载 bzoj3175 [ TJOI2013 ] -- 二分图最大点独立集
画个图自己走一走，容易看出这是一个二分图。那么答案就是二分图的最大点独立集。二分图的最大点独立集=|V|-最大匹配数最大匹配数用匈牙利算法求。代码： 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std;...
2017-03-15 09:14:00
62
转载 bzoj1856 [ SCOI2010 ] -- 卡特兰数
其实就是卡特兰数的定义。。。将放置一个1视为(1,1)，放置一个0视为(1,-1)则答案就是从(0,0)出发到(n+m,n-m)且不经过y=-1的方案数。从(0,0)出发到(n+m,n-m)的总方案数是C(n+m,n)。若一条路径经过y=-1，那么将其从(0,0)到y=-1的一段路径以y=-1作对称，就变成了一条从(0,-2)到(n+m,n-m)的路径。设走了x步(1...
2017-03-15 08:25:00
83
转载 bzoj2712 -- 类欧几里得算法
与bzoj2187类似，不过是要先将小数转化成四舍五入前的分数代码： 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<cmath> 5 using namespace std; 6 #define ll long...
2017-03-15 07:42:00
78
转载 bzoj2187 -- 类欧几里得算法
用类欧不断缩小规模，就能在O(T*log2n)时间内求出答案。题解：http://blog.csdn.net/coldef/article/details/62035919代码： 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using nam...
2017-03-15 07:39:00
58
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人