[bzoj 2431][HAOI2009]逆序对数列（递推+连续和优化）
题目：http://www.lydsy.com:808/JudgeOnline/problem.php?id=2431分析：f(i,j)表示前i个数字逆序对数目为j时候的方案数那么有f(i,j)=∑f(i-1,k) j-i+1<=k<=j看似是n*k*k的，但是注意对于每一个i，当j=
【bzoj4154】[Ipsc2015]Generating Synergy KD-tree
题目描述给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色输入第一行一个数T,表示数据组数接下来每组数据的第一行三个数n,c,q表示结点个数,颜色数和操作数接下来一行n-1个数描述2..n的父节点接下来q行每行三个数a,l,c若c为0,表示询...
BZOJ4154: [Ipsc2015]Generating Synergy
Description给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色Input第一行一个数T,表示数据组数接下来每组数据的第一行三个数n,c,q表示结点个数,颜色数和操作数接下来一行n-1个数描述2..n的父节点接下来q行每行三个数a,l...
【BZOJ4154】Generating Synergy【kd树】
题意给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色分析我们以dfs序为横坐标，深度为纵坐标，建kd树。我们每次更新，都是在kd树中更新一个矩形，横坐标为[st[a],en[a]],纵坐标[depth[a],depth[a]+l]。那么就相...
【bzoj 4154】[Ipsc2015]Generating Synergy
题目大概已经掌握熟练码出\(kdt\)的技能了发现距离子树根节点\(x\)不超过\(l\)的点可以用两种方式来限制，首先\(dfs\)序在\([dfn_x,dfn_x+sum_x)\)中，深度自然也要满足\([deep_x,deep_x+l]\)发现这变成了对一个子矩形染色同时询问单点颜色的题目我们...
BZOJ4154：[IPSC2015]Generating Synergy
浅谈\(K-D\) \(Tree\)：https://www.cnblogs.com/AKMer/p/10387266.html题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=4154每个节点看做是点\((dfn_i,dep_i)\)，然后对于距...
【BZOJ4154】[Ipsc2015]Generating Synergy KDtree
【BZOJ4154】[Ipsc2015]Generating SynergyDescription给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色Input第一行一个数T,表示数据组数接下来每组数据的第一行三个数n,c,q表示结点个数,颜色...
[bzoj1997][Hnoi2010]Planar(2-sat||括号序列)
开始填连通分量的大坑了= =然后平面图有个性质m<=3*n-6.....由平面图的欧拉定理n-m+r=2（r为平面图的面的个数），在极大平面图的情况可以代入得到m=3*n-6。网上的证明（雾？）：http://blog.chinaunix.net/uid-26510579-id-3183558...
【bzoj1037】 ZJOI2008—生日聚会Party
http://www.lydsy.com/JudgeOnline/problem.php?id=1037 (题目链接)题意有n个boy和m个girl排成一排，求使得任意一段的boy个数girl个数的差不超过k的方案数。Solutiondp。对于一段确定的人，设为A，那么只有A的后缀中男孩与女孩个数之...
[bzoj1854][SCOI2010]游戏
Description一个装备有两个属性，一个装备只能被使用一次，一次使用一种属性。攻击boss时需按属性1、属性2、属性3...属性k的顺序使用，问k最大为多少。Input输入的第一行是一个整数N，表示有N种装备。接下来N行，是对这N种装备的描述，每行2个数字，表示第i种装备的2个属性值。Outp...
【BZOJ1007】【HNOI2008】水平可见直线（斜率排序+单调栈）
1007: [HNOI2008]水平可见直线Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 2605 Solved: 914[Submit][Status]DescriptionInput第一行为N(0 < N < 50000),接下来的N...
BZOJ_1342_[Baltic2007]Sound静音问题_单调队列
BZOJ_1342_[Baltic2007]Sound静音问题_单调队列题意：给出n个数，求∑[ max{a[i]~a[i+m-1]} - min{a[i]~a[i+m-1]} <= c ]分析：滑动窗口我们维护两个单调队列，分别存最大，最小值代码：#include <cstdio>...
BZOJ2961: 共点圆
好久没发了CDQ分治，具体做法见XHR的论文… /************************************************************** Problem: 2961 User: zhuohan123 Language: C++ R...
【线段树/区间开平方】BZOJ3211-花神游历各国
【题目大意】给出一些数，有两种操作。(1)将区间内每一个数开方(2)查询每一段区间的和【思路】普通的线段树保留修改+开方优化。可以知道当一个数为0或1时，无论开方几次，答案仍然相同。所以设置flag=1。如果一个节点的左右孩子flag均为1，那么它的flag也是1。 #include<iost...
bzoj1355: [Baltic2009]Radio Transmission
将原串看成是循环节的后缀加上若干个循环节，那么考虑每种情况都会发现n-next[n]就是最小循环节。（一开始总输出n。。。然后发现build_next连调用都没有，%%%#include<cstdio>#include<cstring>#include<iostream...
BZOJ 1006 【HNOI2008】 神奇的国度
题目链接：神奇的国度一篇论文题……神奇的弦图，神奇的MCS……感觉我没有什么需要多说的，这里简单介绍一下MCS：我们给每个点记录一个权值，从后往前依次确定完美消除序列中的点，每次选择权值最大的一个点(相同的话随意选一个)放到当前完美消除序列中的位置，然后把相邻的所有点权值加\(1\)。一路到底即可得...
bzoj1113: [Poi2008]海报PLA
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define maxn 250005 usin...
BZOJ1237: [SCOI2008]配对
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1237题目大意：你有n 个整数Ai和n 个整数Bi。你需要把它们配对，即每个Ai恰好对应一 个Bp[i]。要求所有配对的整数差的绝对值之和尽量小，但不允许两个相同的数配 对。例如A= ...
BZOJ_2679_[Usaco2012 Open]Balanced Cow Subsets _meet in middle+双指针
BZOJ_2679_[Usaco2012 Open]Balanced Cow Subsets _meet in middle+双指针DescriptionFarmer John's owns N cows (2 <= N <= 20), where cow i produces M(i)...
Luogu P1852 BZOJ 2144 [国家集训队]跳跳棋
qwq这题一看就不会，如果不是gg让做我是坚决不会做的画图模拟，因为一次只能跳过一个棋子，所以对于一种情况只有三种移动方式:中间向左跳中间向右跳左或右（距中间近的那个）向中间跳发现，除了跳到边界，当左右到中间的距离相等的时候就不能再向中间跳了，而任意一种情况只要一直重复方式3就能达到这样的平衡状态，...