爱悠闲 > 分类 >

BZOJ 第55页

BZOJ 4080 Wf2014 Sensor Network 随机化
题目大意:给定平面上的 n 个点,求一个最大的点集,使得两两之间距离不超过 d 爆搜T到死,加什么剪枝都没用…… 随机化大法好 每次随机一个序列,依次贪心加入,然后更新答案 据说很靠谱?反正写完直接过了 #include <bitset> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #d
BZOJ 3779 重组病毒 LCT+线段树维护DFS序
题目大意:给定一棵树,初始每个点都有一个颜色,支持三种操作: 1.将某个点到根的路径上所有点染上一种新的颜色 2.将某个点到根的路径上所有点染上一种新的颜色,然后把根设为这个点 3.定义一个点的代价为这个点到根路径上颜色的种类数,求某个点子树中所有点代价的平均值 我真是炖了狗了…… 容易发现这玩应就是个LCT,操作1就是Access,操作2就是Move_To_Root,代价就是一个点到根路径上的虚
BZOJ 4077 Wf2014 Messenger 二分答案+计算几何
题目大意:给定两条折线,Alice沿着第一条折线走,Bob沿着第二条折线走,邮递员从Alice路径上的任意一点出发,沿直线走到Bob的路径上后刚好和Bob相遇,三人的速度都是 1m/s ,求邮递员走的最短距离,无解输出impossible 二分答案,然后让Bob提前出发 mid ,然后求出Alice和Bob全程的最短距离,判断是否 ≤mid 就行了 无解比较难办,反正我是提前判断了无解的情况 #i
BZOJ 2613 Poi2003 Shuffle 数论
题目大意:给定一个长度为 n 的置换 b 和一个正整数 k , 求一个置换 a ,使得 ak=b 要做这个题首先我们需要知道 ak 是什么 想象一个长度为 L 的循环,如果我们将这个循环求 k 次方,我们将会得到 Gcd(L,k) 个长度为 LGcd(L,k) 的循环 那么现在我们将 b 分解成循环,假如现在我们得到了一个长度为 L′ 的循环,那么由之前的结论可以得到 L′=LGcd(L,k) 容
BZOJ 4073 Wf2014 Buffed Buffet 斜率优化
题目大意:给定 d 种食物,食物分两个类型:离散食物和连续食物 离散食物只能按份供应,每种食物有一个质量w 连续食物可以食用任意质量 每种食物有一个初始美味值 t 和一个美味值衰减系数 △t 对于一种离散食物,如果你吃了 N 份,那么获得的美味值为 ∑Ni=1(t−(i−1)△t) 对于一种连续食物,如果你吃的质量为 X ,那么获得的美味值为 ∫X0(t−x△t)dx 现在你必须吃总质量为 W 的
BZOJ 3456 城市规划 快速傅里叶变换
题目大意:求 n 个点的无向简单连通图个数, n≤1.3∗105 递推式: fi=2C2i−∑i−1j=1fj∗Cj−1i−1∗2C2i−j 推导http://www.aiuxian.com/article/p-2139983.html 然后两侧同除 (i−1)! 得到: fi(i−1)!=2C2i(i−1)!−∑i−1j=1fj∗2C2i−j(j−1)!∗(i−j)! ∑ij=1fj∗2C2i−
BZOJ 2287 POJ Challenge 消失之物 分治+背包
题目大意:给定n个物品,每个物品有一个体积,对于所有的 1≤i≤n,1≤j≤m 输出在不使用第 i 个物品的情况下装满大小为 j 的背包的方案数 我这傻逼居然真的去写了分治背包…… 第i个物品存在的时间为 [1,i−1] 和 [i+1,n] 两个区间 然后分治…… 时间复杂度 O(n2logn) 黄学长我仰慕您 #include <vector> #include <cstdio> #includ
BZOJ 3782 上学路线 动态规划+Lucas定理
题目大意:给定一张 N∗M 的网格图,有 T 个坏点,求左上角走到右下角的方案数对 P 取模后的值 首先把坏点和终点以 x 坐标为第一键值, y 坐标为第二键值排序 令 fi 表示从原点不经过任何坏点走到第 i 个点的个数,那么有DP方程: fi=Cxixi+yi−∑xj<=xi,yj<=yiC(xi−xj)(xi−xj)+(yi−yj)∗fj 这个相当于枚举第一个遇到的坏点是啥,然后从总方案里减
BZOJ 1982 Spoj 2021 Moving Pebbles 博弈论
题目大意:给定n堆石子,每次可以选择一堆石子,拿走任意个,然后将堆中剩余石子移动任意个到任意一些堆里,不能操作者为输,求是否先手必胜 必败状态为: n 为偶数,且将石子数相同的堆两两配对可以配成 n2 对 例如: 6 1 1 4 4 5 5  这就是一个先手必败的初始状态 证明: 首先证明这个状态是必败的 由于堆可以两两配对,因此无论先手做什么,后手都可以对另一个堆做同样的事情,故先手必败 对于一
BZOJ 4103~4105 THUSC2015 题解
T1:BZOJ 4013 xor 题目大意:给定一个长度为 n 的数列 a 和一个长度为 m 的数列 b ,给定矩阵 A ,令 Ai,j=ai⊕bj , q 次询问某个子矩形里的 k 大值 n≤1000,m≤3∗105,q≤500 刚看到这题的时候我发现我不会,看到数据范围的时候我发现出题人也不会…… 如果 n=1 ,那么我们对这 m 个数建立可持久化Trie树,每次询问的时候查询异或 a1 的