爱悠闲 > 分类 >

BZOJ 第57页

BZOJ 2529 Poi2011 Sticks
题目大意:给定 n(n≤106) 根木棍,每根木棍有一个长度,求是否存在三根颜色不同的木棍能构成一个面积为正的三角形 枚举最长的那根木棍,由于能够成三角形的充要条件是两短边和大于第三边,因此短边越长越好 因此维护 [1,i] 集合中最长的三根颜色不同的木棍即可 #include <cstdio> #include <cstring> #include <iostream> #include <al
BZOJ 4127 Abs 树链剖分
题目大意:给定一棵树,每个点有一个整数权值(可以是负数),要求支持两种操作: 1.链上加 2.链上绝对值之和 由于加的数保证非负,因此一个负数变成一个正数最多有 n 次 树链剖分,在线段树中维护一下区间最大负数即可 不知道为何 写了两个线段树就TLE 把两个线段树合并成一个就7s过了 #include <cstdio> #include <cstring> #include <iostream>
BZOJ 4129 Haruna’s Breakfast 带修改树上莫队+分块
题目大意:给定一棵树,每个点有一个非负点权,支持下列操作 1.修改某个点的点权 2.查询某条链上的mex 考虑链上不带修改的版本,我们可以用莫队+分块来搞http://www.aiuxian.com/article/p-2139968.html 现在到了树上带修改,果断糖果公园 本来抱着逗比的心态写了一发结果1.4s过了 跟糖果公园的80s完全不成正比啊0.0 #include <cmath> #
codeforces 321E Ciel and Gondolas 四边形不等式
题目大意:给定 n 个人,需要分 k 次过河,两个人 i,j 如果同乘一条船就会产生 ai,j 的代价,求最终代价的最小值 这个玩应显然满足四边形不等式(虽然我并不知道这个不等式是啥 然后就是决策单调(虽然我并不知道为何满足四边形不等式一定决策单调 然后就能分治做辣。。。 定义 Solve(l,r,optl,optr) 表示当前在处理区间 [l,r] ,最优决策区间为 [optl,optr] 然后
BZOJ 1563 NOI2009 诗人小G 四边形不等式
题目大意:玩具装箱,然而指数变成了 p ( p≤10 ) 首先我们需要证明决策单调 由于数死早,还是戳这里吧 知道决策单调之后怎么办呢? 由于是1D1D,所以不能分治了 每个决策点能决策的区间一定是连续的一段 并且随着决策点的右移 这个区间也在不断右移 令 g[j] 表示决策点 j 能贡献的最左侧的位置 然后我们开一个栈来维护当前存在贡献的贡献点 那么显然 stack[i] 的贡献区间是 [g[s
BZOJ 2530 Poi2011 Party 构造
题目大意:给定一张 n 个点 m 条边的图( n≡0( mod 3) ),保证存在一个大小为 23n 的团,要求输出一个大小为 13n 的团 每次找一对没有连边的点对将其删掉 由于这对点之间没有连边,因此两个点不可能都存在于团中,也就是说我至少删掉了 1 个不在团中的点 那么不超过 13n 次操作后所有不在团中的点都会被删掉 此时最多删掉了 23n 个点 剩余的点构成了一个团,大小 ≥13n ,任
BZOJ 4145 AMPPZ2014 The Prices 状压DP
题目大意:给定n个商店和m种物品,你需要每种物品买一个,去第 i 个商店的路费是 di ,第 i 个商店出售第 j 种物品的价格是 ci,j ,求最小花销 令 fi,j 表示当前已经考虑了前 i 个商店,购买的状态为 j 的最小花销 然后每个商店内跑个背包即可 时间复杂度 O(nm2m) #include <cstdio> #include <cstring> #include <iostream
BZOJ 4147 AMPPZ2014 Euclidean Nim 博弈论+数论
题目大意:给定 n 个石子,两人轮流操作,规则如下: 轮到先手操作时:若石子数 <p ,那么只能添加 p 个石子,否则可以拿走 p 的倍数个石子 轮到后手操作时:若石子数 <q ,那么只能添加 q 个石子,否则可以拿走 q 的倍数个石子 拿走所有石子的人胜利,问先手是否必胜,或输出游戏会永远进行下去 令 d=gcd(p,q) ,那么若 d 不能整除 n ,游戏将会永远进行下去 否则将 p/=d,q
BZOJ 4128 Matrix Baby-Step-Giant-Step+矩阵求逆
题目大意:给定两个 n∗n 的矩阵 A 和 B ,求一个最小的非负整数 x 满足 Ax≡B( mod p) 保证 [0,p] 内有解 这个问题类似于离散对数问题,因此可以用BSGS来解决 但是和离散对数要求逆元一样,这个问题需要求出矩阵的逆 之前一直只会 O(n5) 的方法- - 今天特意去学了 O(n3) 做法如下: 将 A 矩阵的右侧接一个单位矩阵 I 变成一个 n∗2n 的矩阵 (A|I)
BZOJ 1124 POI2008 枪战Maf 贪心
题目大意:给定 n 个神枪手,每个神枪手瞄准一个人,以一定顺序开枪,问最少和最多死多少人 首先考虑最多 对于每个联通块: 如果这个连通块只有一个人,那么这个人自杀,死亡人数为 1 如果这个连通块是一个环,那么可以活下来一个人,死亡人数为 size−1 否则除了叶节点之外其他人都可以死,死亡人数为 size−cnt叶节点 接下来考虑最少 首先叶节点一定不能死 首先把叶节点加入队列,然后每取出一个点时