ResurrectionTX

题解

比赛(7) 笔记(6)

/ 注册

全部文章 / 题解（共32篇）

2020牛客NOIP赛前集训营-提高组（第六场）A 袜子分配

这种期望题一般要不就是对每个点单独计算贡献要不就是算形如的东西。那么这题是对每个点单独算贡献。一共有2n只袜子，所以就有2n！种拿法。将每对袜子拆成两个不一样的，那么他们在一起当且仅当在n个组的同一组内即为种，因为拆成了两个不一样的，所以要乘2。然后每个袜子对期望的贡献是独立的，所以剩下...

概率期望数论组合数学

2020-10-29

5 660

2020牛客NOIP赛前集训营-提高组（第六场）B 艰难睡眠

什么泄出题人比赛开始了两个小时才改好题面。首先枚举连续睡觉时间的开始，则可以算出在这一段时间内吵闹的人转移到的可行区间。这样问题就变成每次有一段可行区间求区间最小值。直接st表肯定是不行的，但是注意到每次睡觉时间只会往后移动1，那么吵闹的人转移到的可行区间的l和r也只会变化1。这样我们可以用...

单调队列

2020-10-29

4 589

2020牛客NOIP赛前集训营-提高组（第六场）C 路径难题

wdnmd真就自闭了，上次数组开小1扣了15分痛失阿珂，这次一样扣了15分。对于出租车类型为1的边，连边方式同普通无向图。对于公交车连类型为2的边，建两个虚点1和2，先把所有站点向虚点1连边权为0的单向边，再从虚点1向虚点2连边权为c的单向变，再从虚点2向所有站点连边权为c的单向边。这样每次就...

最短路网络流

2020-10-29

3 590

2020牛客NOIP赛前集训营-提高组（第四场）

要是早点写这题就能赛时调过了，就能Rank2了(痛哭看到题目先来化一波式子：为了简化式子，令，，发现长得都很像，所以其实只要求出形如的东西就行了。考虑每个位置的权值对这个式子上面的指数的贡献，我们可以得知这个式子就等于。组合意义是每个位置选或者不选的所有情况，最后再减...

线段树数论

2020-10-25

13 836

2020牛客NOIP赛前集训营-提高组（第三场）B 牛半仙的妹子图

首先因为能走过的边的边权是递增的，那么经典套路是枚举最大的边的长度然后用并查集合并图上点的连通性。按照题意，当困难度为的时候的答案就是将所有边权的边加进去之后起点所在的连通块中不同类型点的数量。注意类型数量比较少只有种，所以可以直接对每个并查集用维护并查集里出现的点的类型情况。发现有多次询问，...

并查集 bitset

2020-10-22

4 603

2020牛客NOIP赛前集训营-提高组（第三场）C 牛半仙的妹子Tree

先吐槽一波出题人( 数据强度属实不行，同学写的暴力竟然拿了。读完题发现可以点分树做掉，但是不大会写，所以写了对操作序列分块的做法。考虑朴素判断某个点是否染色，遍历上次清零操作之后的所有插入操作，如果，那么现在的点可以被染色。这样考虑对操作序列分块，块大小为，插入操作对某个询问操作的影响分为两种...

分块

2020-10-22

6 744

UOJ #266.【清华集训2016】Alice和Bob又在玩游戏

Description 传送门 Solution 首先每个连通块之间是独立的，也就是说算出每个连通块的\(sg\)值异或起来就行。那么每个连通块单独考虑，进行一次题目中的操作后，会产生一些新的连通块，假设当前节点为\(x\)，它能到达的所有点的\(sg\)值都已经算出来了，那么如果选择...

Trie UOJ 博弈论

2020-10-09

0 481

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