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就能达到这样的平衡状态，...
BZOJ.2639.矩形计算(二维莫队)
题目链接二维莫队，按x,y坐标一起分块.(x,y)的所属的块为 x/sq(n)*sq(m) + y/sq(m)排序时按照(左下点所在块，右上点的标号)排序排序后 先得出一个询问的答案，然后利用上一个询问的矩形与当前矩形位置关系更新答案转移真的麻烦。。为了避免算重 一定要加个vis[][]//4432...
树链剖分模板(BZOJ3083)
实现了路径修改，子树查询，及换根。换根其实很简单，分三种情况讨论，画画图就明白了。#include <cstdio>#include <algorithm>using namespace std;#define m ((L+R)>>1)#define lc o&l...
BZOJ 2302: [HAOI2011]Problem c( dp )
dp(i, j)表示从i~N中为j个人选定的方案数, 状态转移就考虑选多少人为i编号, 然后从i+1的方案数算过来就可以了. 时间复杂度O(TN^2)---------------------------------------------------------------------#inclu...
POJ 1987 BZOJ 3365 Distance Statistics 树的分治(点分治)
题目大意：（同poj1741，刷一赠一系列）CODE：#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define MAX 40010#define ...
BZOJ1047[HAOI2007]理想的正方形——二维ST表
题目描述有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。输入第一行为3个整数，分别表示a,b,n的值第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。100%的数据2<=a,b<=...