爱悠闲 > 分类 >

BZOJ 第59页

BZOJ 2667 cqoi2012 模拟工厂 贪心
题目大意:现在你有一个工厂,初始生产力为 1 ,每一时刻你可以进行如下操作: 1.将生产力提高1 2.生产一些产品,数量等于当前生产力的数值 现在你有 n 个订单,每一份有一个交易时间 t ,一个商品数量 g 和一个价格 m ,可以接或者不接,如果接就要在 t 时刻操作之前减少 g 的商品数量,然后得到 m 的钱 求最大收益 跪shanest大爷。。。 由于 n≤15 ,爆枚接受哪些订单 每次Ch
BZOJ 2969 矩形粉刷 期望
题目大意:给定一个 W∗H 的矩阵, k 次选择两个点并粉刷中间矩形区域,求最终刷到的格子数的期望 无论独立与否期望都是可加的,我们可以一个一个格子计算期望,最后加和 然后我们可以计算出一个格子一次被涂到的概率 p ,那么 1−(1−p)k 就是这个格子 k 次后被刷到的概率 不知为何跑得奇慢无比。。。。其他人写的都不是 O(WH) 的么- - #include <cmath> #include
BZOJ 4173 数学 数论
题目大意:给定 n,m ,求 φ(n)∗φ(m)∗∑n%k+m%k≥kφ(k) mod 998244353 n,m≤1015 我是傻逼。。。 n%k+m%k≥k 等价于 ⌊n+mk⌋−⌊nk⌋−⌊mk⌋=1 无视掉前面的 φ(n)∗φ(m) 的话答案就是 ∑n%k+m%k≥kφ(k) =∑n+mk=1φ(k)∗⌊n+mk⌋−∑nk=1φ(k)∗⌊nk⌋−∑mk=1φ(k)∗⌊mk⌋ 那么 ∑nk=
BZOJ 4174 tty的求助 莫比乌斯反演
题目大意:求 ∑Nn=1∑Mm=1∑m−1k=0⌊nk+xm⌋ mod 998244353 假设 n 和 m 都已经确定了,现在要求这坨玩应: ∑m−1k=0⌊nk+xm⌋ =∑m−1k=0(⌊nk%m+xm⌋+nk−nk%mm) =∑m−1k=0(⌊nk%m+xm⌋+nkm−nk%mm) 我们一项一项考虑 令 d=gcd(n,m) ,那么有 ∑m−1k=0⌊nk%m+xm⌋ =d∗∑md−1k=
BZOJ 3864 Hero meet devil DP套DP
题目大意:给定一个长度为 n(n≤15) 的基因序列 S ,求对于每个 i(0≤i≤n) 有多少长度为 m(m≤1000) 的基因串 T 满足 S 与 T 的 LCS 为 i 考虑 LCS 怎么求 fi,j 表示 T 的前 i 位和 S 的前 j 位的 LCS 我们发现每一行之和上一行的状态有关 那么在这个问题中,我们令 fi,j 表示 T 的前 i 位与 S 的 LCS 状态的第 i 行为 j
BZOJ 3899 仙人掌树的同构 仙人掌同构+KMP算法
题目大意:给定一棵仙人掌,求有多少自同构 仙人掌同构问题= = 曾经出过一个判断两个仙人掌是否同构的题,感觉和这个题很类似 首先假设这是一棵树,考虑怎么做 我们首先找到树的重心(如果有两个就在中间加一个点变成一个) 然后把树Hash 对于一棵树 如果某一哈希值的子树有 k 个 就把答案乘上一个 k! 现在变成了仙人掌,那么我把每个环变成一个红点连向环上的所有点,然后把原先环上的边拆除,可以得到一棵
BZOJ 4176 Lucas的数论 莫比乌斯反演
题目大意:给定 n(n≤109) ,求 ∑ni=1∑nj=1d(ij) 推错式子害死人。。。 由 d|ij 等价于 dgcd(i,d)|j 可得 ∑ni=1∑nj=1d(ij) =∑ni=1∑n2d=1⌊n∗gcd(i,d)d⌋ =∑nd=1∑⌊nd⌋i=1∑⌊n2d⌋j=1⌊nj⌋[gcd(i,j)=1] =∑nd=1∑⌊nd⌋i=1∑nj=1⌊nj⌋[gcd(i,j)=1] =∑nd=1∑⌊n
BZOJ 2927 POI1999 多边形之战 博弈论
题目大意:给定一个凸多边形的三角剖分,其中一个三角形被涂成了黑色,每次可以割一刀割下一个三角形,割下黑色三角形的人胜利,求是否先手必胜 这傻逼题我想了50min。。。50min! 把这个图转对偶图之后会变成一棵树。。。 问题转化成了给定一棵树有一个黑色节点每次删除一个叶节点,删除黑色节点的人胜利 如果黑色节点初始就是一个叶节点,那么先手必胜 否则当一个人面临一个黑色节点连接两个白色节点的状态时必败
BZOJ 4184 shallot 分治+高斯消元
题目大意:给定一个可重集合,每个时刻加入一个数或删除一个数,每次操作后询问子集的最大异或和 每个数存在的时间都是一些区间 按照时间分治,维护线性基,时间复杂度 O(nlognlogai) 然而数据范围是50W,出题人在想什么。。。。 #include <map> #include <vector> #include <cstdio> #include <cstring> #include <ios
BZOJ 4116 Wf2015 Tours Tarjan
题目大意:给定一张 n 个点 m 条边的无向图,你需要选择一个颜色种类数 k ,然后用这 k 种颜色给每条边染色,要求对于图中任意一个简单环,每种颜色的边的数量都相同,求所有可行的 k 考虑将边集 E 拆成一些子集 {E1,E2,E3,..} ,满足任意一个简单环可以被拆成一些子集的和,且不存在两个子集合并后仍满足条件,那么答案就是 gcd{|E1|,|E2|,|E3|,..} 的所有约数 那么如