Rewinner

分类

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

/ 注册

全部文章（共136篇）

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

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

2019-07-19

0 624

2019 西安邀请赛 J And And And【树形DP】

传送门思路：如果要求异或为0的路径的个数，这就是一个***题。但是他要求的集合的个数。可以从刚才那个问题扩展开来，问有多少条路径的子路径的异或值为0。这是一个计数的问题，我们知道异或有一个性质 x^x=0 1为树的根节点，xor[i] 表示i到根节点路径上的的异或值我们可以发现当两个点(s...

2019-07-17

0 573

点分治【模板】

推荐学习博客：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

CLion 编辑器的各种问题【转载】

Clion设置编译器MinGW、Clion设置字体大小、Clion设置tab进四格、解决CLion输出中文乱码、解决CLion输入EOF且输出中断、错误：cannot open output file CLion 是一款专为开发C及C++所设计的跨平台IDE。它是以In...

2019-07-15

0 4361

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

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

2019-07-14

0 565

Floyd算法(多源最短路)

Floyd 如果你有挑战程序设计竞赛第二版(群文件里面有PDF版本)，你可以看P103讲解的很好。如果要用到 Floyd 算法建边方式基本都是邻接矩阵，因为时间复杂度为O(n^3)，所以说n通常都不会很大。 Floyd 可以求解多源最短路，传递闭包(POJ3660)，求最小环。代码： ...

2019-07-14

0 514

邻接表（链式向前星）

邻接表（链式向前星）链式向前星：用来储存边的信息的以中方法。优点：速度快，节省空间，很常用如果我们用 Vector 来建边，相当于开的是一个动态的二维数组，较数组模拟来说比较慢。有时候还卡空间(被某一道题卡崩的YMF学长：我再用Vector建边我是🐶)。我先把基本代码贴出来。 #...

2019-07-14

0 689

Codeforces 669E Little Artem and Time Machine 【CDQ分治+map】

传送门废话：读错题了，写了半天结果发现写了一道假题。题意：三种操作：操作①：在时间戳为T的多重集合中加入一个数字x。操作②：在时间戳为T的多重集合中加入一个数字x。操作③：询问在时间戳为T的多重集合中包好多少个数字x。解题思路: 基础的二维偏序：对于操作时间 q1 和 q2，时间戳 ...

2019-07-14

0 549

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