爱悠闲 > 分类 >

BZOJ 第50页

Codeforces#167E Wizards and Bets 高斯消元
题目大意:给定一张有向无环图,有恰好k个无入度的点和k个无出度的点,对于一个边集如果这个边集恰好形成了从每个无入度的点到每个无出度的点的k条不相交的路径,那么这k对点就会对答案有一个贡献;如果对应关系如果是一个奇排列,对答案的贡献为-1,否则为+1。求所有贡献的和 首先不考虑路径是否相交 令f[i][j]为从第i个无入度的点走到第j个无出度的点的方案数,那么这个矩阵的行列式的值就是答案 那么考虑路
BZOJ 1941 Sdoi2010 Hide and Seek K-Dimensional-Tree
题目大意:给定平面上的n个点,定义距离为曼哈顿距离,求一个点到其他所有点的最大距离与最小距离之差最小 KDTree……这东西好神啊 注意计算最小距离的时候不能把自己也算进去= = #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 500500 #define INF 0x3
BZOJ 2648 SJY摆棋子 K-Dimensional-Tree
题目大意:给定平面上的n个点,定义距离为曼哈顿距离,支持下列操作: 1.插入一个点 2.查询离一个点最近的点的距离 Hint说KDTree【可以】过,那么不写KDT还能写啥= = 我的CDQ分治可是T掉了啊= = 记住KDT发生TLE事件的时候不一定是常数问题 有可能写挂了= =(这不和莫队一样么233 #include <cstdio> #include <cstring> #include <
BZOJ 3812 主旋律 状压DP+容斥原理
题目大意:给定一张无向图,求这张无向图的生成子图中有多少强连通图 正着做不好做,我们考虑容斥原理 如果一个图不连通,那么这张图缩点之后一定会形成一个点数>=2的DAG 一个DAG中一定会有一些入度为0的点,我们枚举这些点的点集进行容斥 具体DP方程和细节见代码 注释写的还是比较详细的我就不多说了= = #include <cstdio> #include <cstring> #include <i
BZOJ 3992 Sdoi2015 序列统计 快速数论变换
题目大意:给定n(n<=10^9),质数m(3<=m<=8000),1<=x=m,以及一个[0,m-1]区间内的集合S,求有多少长度为n的数列满足每个元素都属于集合S且所有元素的乘积mod m后=x 求原根,对S集合内每个元素取指标,然后搞出生成函数f(x) 那么答案就是(f(x))^n (mod x^(m-1),mod 1004535809) 上NTT用多项式快速幂搞一搞就好了 #include
BZOJ 3991 Sdoi2015 寻宝游戏 树链的并
题目大意:给定一棵树,多次将某个点设为关键点或取消关键点,求虚树中边长总和的二倍 Orz wyfcyx 首先我们考虑树链的并(每个点到根节点的链的并集)怎么求 将虚树中的所有点按照DFS序排序,将每个点的深度统计入答案,将相邻两个点之间的LCA的深度从答案中扣除,就是所有点到根的链的并集的长度 但是我们要求的是虚树中的边长总和,因此我们还要减掉所有点LCA的深度 现在要求动态维护,因此我们用set
BZOJ 3990 Sdoi2015 排序 DFS
题目大意:给定一个长度为2^n的排列,有n个操作,第i个操作为【将序列分成2^(n-i+1)段,每段长2^(i-1),然后任选两段交换】,每个操作最多用一次,求有多少操作序列能把序列排出来 Orz dzy 首先我们很容易发现一个操作序列是否合法与序列的顺序是无关的 因此我们只需要确定某个操作序列中每个操作选不选就行了 那么这类操作序列对答案的贡献就是选择的操作数的阶乘 我们从小到大DFS,对于第i
BZOJ 3993 Sdoi2015 星际战争 二分答案+最大流
题目大意:有n个机器人和m个激光武器,每个武器有一个威力和能打的集合,同一时刻只能打一个机器人,问最少多久可以全灭 二分答案+网络流= = 注意二分上界 #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> #define M 110 #define S 0
BZOJ 3994 Sdoi2015 约数个数和 莫比乌斯反演
题目大意:求 ∑ni=1∑mj=1d(ij) 首先我们有一个很神的结论: ∑ni=1∑mj=1d(ij)=∑ni=1∑mj=1⌊ni⌋⌊mj⌋[gcd(i,j)==1] 这个结论是怎么来的呢?我们可以先证明这个: d(nm)=∑i|n∑j|m1∗1[gcd(i,j)==1] 显然这个式子的前缀和就是上面的式子 现在我们来证明这个式子是对的 我们分开讨论每一个质数 p 对答案的贡献 不妨设 n=n′
BZOJ 3995 Sdoi2015 道路修建 线段树
题目大意:给定一个2*n的网格图,多次改变某条边的权值或询问y坐标在[l,r]中的2*(r-l+1)个点的MST 这真是一道好题= = 我们用线段树维护每个区间内的MST 然后考虑合并 合并两个区间 我们会加入两条边 这样一定会形成一个环 切掉环上最大边 这题没了 然后就是一坨乱七八糟的细节讨论= = 首先最大边一定在图中的彩色部分内 绿色部分可以O(1)求 我们需要维护的是红色和蓝色部分 然后如