不知为何起了一个如此贴近小学课文标题的名字233 THUSC 2016 补退选 Trie上标记一下就行了,这题好像去年写的,最大的收获是让我知道了指针不是默认NULL的( https://loj.ac […]
「勇気100%」と私の勇気
虽然我知道在美好的上午不做题打开网易云音乐不太好,但是,我知道我与这首歌的相遇一定是命运的安排所以这些都不重要了(x 我记得第一次听这个歌大概是初三的寒假。 那个时候,我大概还有每周看一看《看天下》的 […]
[HNOI 2019] JOJO
LOJ #3055. 首先考虑一个暴力的做法……我们很显然可以把一个二元组$(x, c)$看成一个字符,然后快乐地去跑 kpm kmp,在跳next的过程中,每个跳到的位置是$x$个$c$中的一段区间 […]
[TJOI 2019] 唱、跳、rap 和篮球
LOJ #3106. 挺套路一题 首先感觉可以无脑套容斥……那么就可以来容斥一发…… 设$f_{m, t_1, t_2, t_3, t_4}$为有$m$个学生,喜欢唱跳RAP篮球的分别有$t_1, t […]
[ZJOI 2019] 语言
LOJ #3046. 考虑一下对于一个$u$,所有的$v$的集合是什么。很显然,就是所有经过$u$的链的链并。 因为这些链都经过同一个点$u$,所以链并就是一个联通块。设所有链的端点组成的点集为$S$ […]
[SDOI 2019] 快速查询
Vijos 2051 把所有单独进行1操作的位置用std::unordered_map维护一下,另外把所有std::unordered_map里的元素之和和其他元素之和维护一下即可
[HNOI 2019] 白兔之舞
LOJ #3058. 看着这个题感觉就有点不可做……所以我们先看$n = 1$的情况 设$c_i$为走$i$步,从$(0, x)$走到一个坐标第二维为$y$的顶点的方案数,那么显然有 $$c_i = […]
[CTSC 2010] 珠宝商
Luogu P4218 将长度为$M$的串称作$s$,将点$i$上的字母称作$c_i$ 我们很显然可以有一种$O(n^2)$的方法来统计 对于串$s$建出一个SAM,然后枚举路径$u, v$的$u$, […]
一只$O(m\log n)$的最小方差生成树
给定$n$个点$m$条边的无向图,求一棵所有边权的方差最小的生成树 $n, m\leq 10^5$ 首先有一个很noip的思路,我们可以枚举所有可能的$\overline{x}$的取值,对于每种取值跑 […]
论如何在很快的时间中求解最小树形图
前言 学到了这种很神奇的 Trick ,于是来写一下 好吧其实感觉是正常智商水平算法竞赛选手能想到的,可能我太菜了 另外本来标题想叫「论如何在$O(xxx)$的时间中求解最小树形图」,但是发现好像不太 […]