ResurrectionTX

分类

比赛(7) 笔记(6) 题解(32)

/ 注册

全部文章（共45篇）

2018 国庆雅礼 NOIP 培训 Day3

\(U\) 传送门矩阵的范围比较小只有\(5000\)，但是操作次数比较多有\(3e5\)，最后只需要查询一次。操作次数多查询少，我们首先就会想到差分。那么由于操作的图形不是传统的正方形而是三角形，所以需要在原本的二维差分上进行膜改。考虑二维差分的意义，因为最后每个点的值是他左上方...

2020-09-15

0 503

2020正睿普转提七连测

\(Day2\) \(A\) 概率期望经典入门题，根据期望的线性性，答案就是每个点被选到的期望之和，每个点的贡献为一，所以只需要求每个点被选到的概率即可，每个点必须在它的子树中的点被选之前选，所以概率是\(\frac{1}{size_i}\)。 #include <iostream>...

正睿

2020-09-13

0 391

2020提高组正睿十连测

\(Day2\) \(A\) 注意到排序后每次是选一个前缀，所以可以在线段树上二分，每次全局加上可以拿的物品，选了的清零即可。 #include <iostream> #include <cstdio> #include <cstring> #include...

正睿

2020-09-06

0 529

信奥题库8月提高组线上模拟赛题解

\(A\) \(10pts\) 暴力即可。 \(50pts\) 发现这就是一条链的情况，也就相当于本题搬到了序列上。根据后缀最大值的定义，不难发现序列上的后缀最大值的权值是递减的，而且后缀最大值的位置是递增的，这启发我们用单调栈维护所有后缀最大值。具体的，单调栈内按权值递减的维护元素...

2020-09-02

0 454

Codeforces做题记录

\(About\) 感觉做题思维很差，很多题算法都会但就是想不到（捂脸。滚来做\(CF\)题锻炼思维力。 \(Codeforces\ Round\ \#665\ (Div.\ 2)\) \(A\) 分两种情况讨论。若\(k >= n\)，那么将\(A\)移动到\((k, 0)\...

Codeforces

2020-08-24

0 494

Luogu P5948 【[POI2003]Chocolate】

Description 传送门 Solution 每次选择花费最大的地方切，然后按照题意(O(n))模拟即可。证明如下： (1.)若两次切割都是横向或竖向，且花费小的比花费大的先切割。设花费小的切割的时候需要切割(a)次，花费大的切割的时候需要切割(b)次，因为中间可能切割了任意次另外一个方向...

贪心 Luogu

2020-08-04

0 469

Luogu P4585 【[FJOI2015]火星商店问题】

Description 传送门 Solution 其实这题是没有必要使用可持久化\(Trie\)的。首先建立一颗线段树，每个节点维护它所代表的那些商店的商品的标价所构成的\(Trie\)。这样如果没有时间上的限制，我们可以将每次的询问拆成对于\(log(n)\)个线段树上的节点的询...

线段树 Trie 树套树 Luogu

2020-07-30

0 346

Topcoder SRM713 DFSCount

Description 传送门 Solution 注意到\(DFS\)的时候每次选择一个\(DFS\)树的子树后必然会走所有子树中的节点，所以原问题变成所有子树内的顺序乘子树外的顺序。这样可以将还没有经过的节点状压，进行记忆化搜索。\(DFS\)树的子树个数就是去掉当前点之后的连通块个...

Topcoder 状压DP

2020-07-07

0 420

动态规划

树形\(dp\) P6419 [COCI2014-2015#1] Kamp 换根\(dp\)，先以\(1\)为根，记\(f_x\)表示\(x\)的子树中的关键点到\(x\)的距离之和，\(dis_{x, 1}\)和\(dis_{x, 0}\)表示\(x\)的子树中关键点到\(x\)的最远和次远距...

树形DP 状压DP

2020-07-06

0 431

Luogu P3714 【[BJOI2017]树的难题】

Description 传送门 Solution 设点\(i\)到根的第一条边的颜色为\(col_i\)，根到点\(i\)的路径上的颜色和是\(sum_i\)，经过观察发现\(col_i\)相同的不在同一个子树里的两个点之间的简单路径拼接后的答案是\(sum_i + sum_j - w_{...

点分治单调队列 Luogu

2020-06-17

0 322