BZOJ4516: [Sdoi2016]生成魔咒 后缀自动机
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<cmath>#include<algorithm>#include<cs...
洛谷P1972 [SDOI2009]HH的项链（树状数组）
题目链接：https://www.luogu.org/problemnew/show/P1972题目描述：HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一...
【BZOJ】1878: [SDOI2009]HH的项链（树状数组）
http://www.lydsy.com/JudgeOnline/problem.php?id=1878我太弱了，看题解才过的。一开始看到此题，我想了想在线做法，但之后觉得这个想法可能是错的：维护一颗splay，按输入顺序建树，将相同节点缩点，维护2个值，一个是size，为节点数量，一个是size2...
[SDOi2012]吊灯
嘟嘟嘟这题想了半天，搞出了一个\(O(10 * d * n)\)（\(d\)为\(n\)的约数个数）的贪心算法，就是能在子树内匹配就在子树内匹配，否则把没匹配的都交给父亲，看父亲能否匹配。交上去开了O2才得了60分。按讨论中的方法卡常后还是A不了，就放弃了。正解需要推一个结论，就是一棵树能被分成\(...
bzoj3533: [Sdoi2014]向量集
Description维护一个向量集合，在线支持以下操作："A x y (|x|，|y| < =10^8)"：加入向量(x，y);" Q x y l r (|x|，|y| < =10^8，1 < =L < =R < =T，其中T为已经加入的向量个数)询问第L个到第R个加...
【bzoj3532】 Sdoi2014—Lis
http://www.lydsy.com/JudgeOnline/problem.php?id=3532 (题目链接)题意给出$n$个数的数列，三个值$a[i],b[i],c[i]$。将其中一些数删掉，使得序列的$a[i]$的最长上升子序列至少减少$1$，删掉的数的$b[i]$和最小，在$b[i]$...
BZOJ 4517: [Sdoi2016]排列计数 错排公式
4517: [Sdoi2016]排列计数题目连接：http://www.lydsy.com/JudgeOnline/problem.php?id=4517Description求有多少种长度为 n 的序列 A，满足以下条件：1 ~ n 这 n 个数在序列中各出现了一次若第 i 个数 A[i] 的值为...
[BZOJ 4817] [SDOI 2017] 树点涂色
DescriptionBob有一棵 \(n\) 个点的有根树，其中 \(1\) 号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：1 x：把点 \(x\) 到根节点的路径上所有的点染...
BZOJ 1975 SDOI2010 魔法猪学院 A*k短路
题目大意：给定一个值E 求起点到终点的最多条路径 使长度之和不超过Ek短路的A*算法……每一个点有一个估价函数=g[x]+h[x] 当中g[x]是从源点出发已经走了的长度 h[x]是从这个点到汇点的最短路首先先在反图上跑一遍SPFA求出每一个点的h[x]，然后将源点的g[x]+h[x]增加堆 每次取...
BZOJ 2707: [SDOI2012]走迷宫( tarjan + 高斯消元 )
数据范围太大不能直接高斯消元, tarjan缩点然后按拓扑逆序对每个强连通分量高斯消元就可以了.E(u) = 1 + Σ E(v) / degree(u)对拍时发现网上2个程序的INF判断和我不一样(他们2个的INF判断也不一样).....然而都A掉了....我觉得应该是他们写错了，我的做法应该没错...
BZOJ 2726: [SDOI2012]任务安排( dp + cdq分治 )
考虑每批任务对后面任务都有贡献, dp(i) = min( dp(j) + F(i) * (T(i) - T(j) + S) ) (i < j <= N) F, T均为后缀和. 与j有关的量只有t = dp(j) - F(i) * T(j) , 我们要最小化它. dp(j)->y...
bzoj 2241: [SDOI2011]打地鼠
#include<cstdio> #include<iostream> using namespace std; int n,m,a[][],b[][],ans,sum; void pan(int i,int j) { int su=; for(int i1...
[LuoguP2158][SDOI2008]仪仗队
[LuoguP2158][SDOI2008]仪仗队(Link)现在你有一个\(N \times N\)的矩阵，求你站在\((1,1)\)点能看到的点的总数。很简洁的题面。这道题看起来很难，但是稍加分析还是可以看出做法的。首先我们知道当一个点不能被看到，当且仅当有另外一个点的斜率与它相同且横坐标值小于...
Luogu2469 SDOI2010 星际竞速 费用流
传送门发现它的本质是求一个费用最小的路径覆盖最小路径覆盖是网络流23题中的一个比较典型的模型所以考虑相似的建边因为每一个点要恰好经过一次，是一个有上下界的网络流，故拆点，星球\(i\)拆成\(A_i,B_i\)两个点，\(S->B_i , A_i -> T\)，原图中的边\((i,j)\...
BZOJ2243——[SDOI2011]染色
1、题目大意：给个树，然后树上每个点都有颜色，然后会有路径的修改，有个询问，询问一条路径上的颜色分成了几段2、分析：首先这个修改是树剖可以做的，对吧，但是这个分成了几段怎么搞呢，我们的树剖的不是要建线段树吗我们的线段树存这样的几个值，一个是这个区间被分成了几段，另外就是这个区间的最左边的颜色和最右边...
BZOJ 1878: [SDOI2009]HH的项链 离线树状数组
1878: [SDOI2009]HH的项链Time Limit: 1 SecMemory Limit: 256 MB题目连接http://www.lydsy.com/JudgeOnline/problem.php?id=1878DescriptionHH有一串由各种漂亮的贝壳组成的项链。HH相信不同...
Luogu3297 SDOI2013逃考（半平面交+最短路）
把每个人的监视范围看成点，相邻的两个监视范围连边，那么跑一遍最短路就可以了（事实上边权都为1可以直接bfs）。显然存在最优路线没有某个时刻同时被多于两人监视，要到达另一个区域的话完全可以经过分界线而不是和其他区域的交点（若两个区域只有一个交点的话是不能直接到达的），总之就是说不用特判同时被多人监视的...
BZOJ 1923: [Sdoi2010]外星千足虫
Description给出几个异或方程组求解,\(n \leqslant 2000\)Sol高斯消元.直接消元就行,遇到自由元就直接输出,同时记录一下用到的最高行数.复杂度不科学就可以用 bitset 啊...跑的灰常快...不过他没有重载某一位的异或操作,需要人工判断一下.Code/*******...
SDOI2017 R1做题笔记
SDOI2017 R1做题笔记梦想还是要有的，万一哪天就做完了呢？也就是说现在还没做完。哈哈哈我竟然做完了-2019.3.29 20:30
BZOJ2282: [Sdoi2011]消防
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2282答案一定是在直径上的一段，然后答案一定不会小于不在直径上的点到直径的距离（要是可以的话那当前这条直径就不是直径了）然后二分一遍，当前段的最长答案只可能在s->l,r->t取到，其...