赤红

分类

codeforces(4) pta(1) 刷题(1) 图论(1) 差分数组(1) 思维(2) 数位dp(1) 未归档(27) 树状数组的拓展(1)

/ 注册

全部文章（共39篇）

吉首大学2019年程序设计竞赛（树状数组）

题目：https://ac.nowcoder.com/acm/contest/992/B 这道题目的思想和这一道小石的妹子感觉有点像，有兴趣的话可以去看看这一道题，这是我写的题解：https://blog.csdn.net/xiaonanxinyi/article/details/95758...

2019-07-15

0 688

牛客小白16月赛小石的妹子

题目：小石的妹子题意：給n个妹子排序，i妹子比j妹子好的需要满足ai>aj&&bi>bj，当然如果一大一小的是无法比较大小的，于是排名就相同。思路：这是个二维偏序的问题，先对一维排序（即是按a从大到小排序），之后我们考虑b，对于第...

2019-07-13

0 486

日常笔记（数学）

目录一 polya定理，Burnside引理转自：https://blog.csdn.net/whereisherofrom/article/details/79631703 一 polya定理，Burnside引理转自...

2019-07-11

0 609

莫对算法

https://ac.nowcoder.com/acm/contest/917/H 链接：https://ac.nowcoder.com/acm/contest/917/H 来源：牛客网题目背景把一张纸对折100次就和珠穆朗玛峰一样高了哦 ...

2019-06-17

0 664

日常笔记

目录一树上差分：二 tarjan算法求割边三 tarjan求割点四康托展开五后缀数组模板：六后缀自动机模板：一树上差分：对于数组来说如果我们要在区间[L,R]上增加k，那么可以在L位置上增加K，R+1位置上减小K。 ...

2019-06-17

0 590

LCA

LCA：一棵树上两个点向上最近的一个点，我们可以先对其中一个点向上标记至根节点，再对另外一个点向上标记，第一次遇到第一次标记的点就是所求。此外，我们可以采用倍增的思想记录每个点向上2^k步的父节点，首先预处理出每个点的深度，以及每个点向上2^k步的父节点。当我们查询两个点的LCA时，先把他们...

2019-06-14

0 558

扫描线

扫描线用于求解n个图形的面积的并,主要思想就是用一条线从左到右（或者从上到下）扫描整个所有图形，其实方向无所谓的。这里以一个题为例讲解亚特兰蒂斯有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。其中一些甚至包括岛屿部分地图。但不幸的是，这些地图描述了亚特兰蒂斯的不同区域。您的朋友...

2019-06-13

0 561

欧拉降幂

题目：http://acm.nuc.edu.cn/OJ/contest/show/54/1008 SHT作为实验室的第一帅哥，一直有一个梦想，希望自己不要长得这么帅，长得帅的苦恼实在是太多了。为了让自己变得没那么帅，他开始疯狂的熬夜刷题，希望通过这样的方式让自己有黑眼圈，然侯实现没那么帅的梦想。终...

2019-06-07

0 628

带权并查集

普通的并查集其实就是若干棵树构成的森林，带权的并查集即是在树中的每条边增加了一个权值，现在我们就还需要再维护一个数组的d[x]，表示节点x到父亲节点f[x]的距离；以一个题目为例：银河英雄传说描述公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为...

2019-06-05

0 518

codeforces Ehab and the Expected XOR Problem（异或前缀和）

题目：https://codeforces.com/contest/1174/problem/D D. Ehab and the Expected XOR Problem time limit per test 1 second memory limit per test 256 mega...

2019-06-04

0 669