Phecda_

未归档

/ 注册

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

LuoGu P1083 借教室

题目传送门借教室这个题有两种做法，差分+前缀和或者是线段树线段树维护区间最小值，因为能不能借教室使用是由这几天中可用教室最少的一天决定的其实这题是个很裸的线段树维护区间最小值，但有一点需要注意，区间最小值在进行加减修改时不能乘以区间长度很简单，不论区间长度怎么样，你整个区间-x，最小...

二分答案线段树差分前缀和

2018-09-06

0 468

USACO15DEC最大流MaxFlow

传送门这是个假的最大流,其实是一个用树剖+线段树就能解决的事情题目中的道路会对路径上的造成压力,最后询问最大的压力其实就等价于对每条路径上的点加上 1 的权值,并且最后询问整个树中的最大值然后树剖+最大值线段树裸题,完事,莫得别的问题了. \(Updated:\) 其实,可以树上差...

树链剖分线段树差分

2019-04-28

0 486

CodeForces1000C

CodeForces1000C 本来以为是道水题,然后我看到了数据范围,当时就有点方,觉得这题难死了然鹅,我冷静了一会儿发现,离散化一下好像就变成了真水题,但是...排序离散化我搞了半天不知道哪里有毛病...于是.... 抱着试试的心态我试了试 \(map\) , 然后就一帆风顺地 \(AC\)...

差分前缀和离散化 STL CodeForces

2019-08-22

0 330

TLS 9.2 A & B

TLS 9.2A 这其实是[HNOI2006]鬼谷子的钱袋对叭... 然后你就考虑二进制是咋做到完美表示任意一个十进制数字的. 你看看它二进制下有多少位就行了. TLS 9.2B 由于\(T1\)太水了,所以我决定把它和\(T2\)放一起. 这题水的不行...我们当场想出了一堆做...

二进制 nature 差分线段树并查集

2019-09-02

0 478

ZROI#987

ZROI#987 差分+简单数学即可. 首先有个性质: 两条链相交等价于其中一条链的\(LCA\)在另一条链上. 于是我们就对每一条链的\(LCA\)都加\(1\). 最后查询每一条链的区间和即可.树剖实现. 但这样我们会算重复,就是说\((a,b)\)两条链相交我们会算\((a,b)\)一次,\...

nature 差分树链剖分线段树容斥原理

2019-09-15

0 495

LibreOJ#2359天天爱跑步

天天爱跑步这或许现在不是\(NOIP\)最毒瘤的题了叭. (当然你说是,我还可以肛你说\(NOIP\)没了) 嗯...一个很显然的暴力思路是: 对于每一个玩家,暴力跟着跑,走到\(w_i\)等于当前时间的点就统计. 这显然是对的...但它太慢了,完全跑不过去. 我们发现题目里给的条件其实是个...

差分桶 dfs 线段树合并 LCA

2019-10-08

0 416

ZROI普转提10.13

ZROI普转提10.13 不爽,连掉两场了... 还是我太菜了啊... A.控制人偶 \(SB\)题,如果 \(T\le n\) 就直接暴力跑 \(n\le 5000\). 否则,就把一整个命令串压成一个矢量,从起点 \((0,0)\) 加 \(T/n\) 次. 以这个终点作为起点再暴...

打表 brute 树状数组前缀和差分简单变换

2019-10-13

0 451