Rewinner

未归档

ACM(1) dfsdd(1) DP(6) hash(1) STL(1) 图论(24) 小技巧(4) 思维(6) 搜索(2) 数学(5) 数据结构(16)

/ 注册

全部文章 / 未归档（共69篇）

2018CCPC吉林赛区 The Moon【期望DP】

传送门 DP 递推公式表示到达最终状态的期望表示从 i 转移到 j 的概率表示从 i 转移到 j 对花费期望DP通常倒推，有这道题我们可以知道当 q=100%的时候，当前情况按照二项式分布，期望为 p/100；需要注意题目存在1.5%，我们需要将概率乘以2再计算，然后按照...

2019-07-19

0 625

点分治【模板】

推荐学习博客：https://blog.csdn.net/a_forever_dream/article/details/81778649https://www.cnblogs.com/bztMinamoto/p/9489473.htmlhttps://www.luogu.org/blog/user...

2019-07-16

0 561

[CQOI2011]动态逆序对【CDQ分治】

传送门主席树题解传送门：https://blog.csdn.net/qq_42211531/article/details/90034520 这篇博客也算是填了以前的坑，学会了CDQ分治来做这一道题。以前做这一道题的时候，思路是对的，但是我不知道维护我想要的信息，学会了CDQ分治，这就是一...

2019-07-14

0 565

P3674 小清新人渣的本愿【莫队+ bitset】

传送门 bitset 大法好啊！！！ bitset 用法：https://blog.csdn.net/vocaloid01/article/details/82798450 解题思路：用 bitset 的每一位代表每一个数字是否出现，s1记录每一个数x出现的位置，s2记录 maxn -x 出...

2019-06-06

0 571

P4113 [HEOI2012]采花【树状数组 AC】【莫队/主席树 TLE】

传送门题意简述：给定一个长度为 n 的序列，有 m 次询问，每次询问一段区间，求区间中有多少个数出现次数超过 1 次这道题真的有点恶心。。。在洛谷上属于莫队，但是莫队会T，数据居然有2e6。莫队的想法很简单就不多提了。主席树：这道题和 HH的项链有异曲同工之妙，后者这道题：将每个数右靠，保...

2019-06-06

0 610

P4137 Rmq Problem / mex 【莫队】【主席树+思维】

传送门题目上给的 ai <= 1e9，第一反应就是离散化，细想一下区间一共就2e5，答案最大不就是2e5吗，大于2e5的数我们可以忽略，这样就可以减去离散化的步骤。莫队解题思路：莫队的就是优雅的暴力，我们可以直接暴力去找答案（稍微优雅一下），我们记录当前区间中每个数出现的位置，当我们的...

2019-06-05

0 507

Codeforces 633H. Fibonacci-ish II【莫队+线段树+公式】

传送门参看博客：https://blog.csdn.net/zearot/article/details/50850792 题意：将询问区间中[ l , r ]中的数排序去重，然后求 d 为排序去重后的长度。解题思路：正解就是莫队算法，但是这道题的 add 操作和 del 操作很不好实现。...

2019-06-04

0 548

第五届新疆省ACM-ICPC程序设计竞赛

A.Good 的集合三角形重心的公式：我们只需要记录每个点坐标 mod 3 的个数，然后我们可以知道这样就只存在 9 种点集 (0-2)*(0-2) 我们可以二进制枚举每种点集是否存在，然后去check。十分需要注意的一点：同一个点集的点，最多选取两个，如果选取了两个以上是不满足good...

2019-06-02

0 545

2019西安邀请赛部分题解

题库链接 D. Miku and Generals 解题思路：按照题意可知给出的冲突关系肯定能够构成二分图，我们可以直接染色，存在冲突的关系可以看作一个连通块，每个联通块我们看作存在三种事件①选择染色为1 ②选择染色为0 ③什么都不选择然后我们可以把问题转换为背包问题，约束条件：每个联通块里...

2019-05-28

0 503

POJ - 3481 Double Queue 【Splay 模板题】

传送门最基本的Splay模板题，没有任何花里胡哨的操作，可以用于加深理解模板中每个函数。 Splay学习博客：https://baijiahao.baidu.com/s?id=1613228134219334653&wfr=spider&for=pchttps://www.cnb...

2019-05-27

0 540