ResurrectionTX

分类

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

/ 注册

全部文章（共45篇）

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

2019正睿csp-s赛前冲刺

主席遗留下来的遗产~ \(Day5\) 杜爷删代码的时候找到了一个去年他不会的题，所以拿来看看觉得还挺有意思，就是\(C\)。然后切完\(C\)就顺便把\(A\)和\(B\)也补了。吐槽下奇怪的难度顺序：\(B > A > C\) \(A\) 如题每个连通子图最后只会剩下...

正睿

2020-10-12

0 436

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

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

Trie UOJ 博弈论

2020-10-09

0 481

2019洛谷csp冲刺模拟赛

难题做不动就去翻去年的洛谷csp题做，实在是水啊~ 第一次 (A) (dp_{i, j})表示使用(i)个色子得到点数为(j)的概率，这样求出(dp_x)和(dp_y)两个(dp)数组后就可以枚举(x)个色子得到的点数，(y)个色子得到的点数是一个前缀，枚举即可。 #include #includ...

Luogu

2020-10-03

0 559

9.18胡测

\(A\) 传送门用哈希表去下重即可。 #include <iostream> #include <cstdio> #include <cstring> using namespace std; #define ll long long const ...

2020-09-21

0 397