文章

水博客真开心 1. 题目 传送门=￣ω￣= 2. 题解 先二分答案，然后 $2 ^ n$枚举怎么切割行，然后再扫描列的切割。 扫描列的切割有些小细节需要注意一下。 代码： #include <bits/stdc++.h> #define NS (20) using namespace s 阅读更多…

随机到一道普及组题目，不容易啊（水博客真开心系列）1. 题目 传送门=￣ω￣= 2. 题解 把所有的 1 位置丢到队列里 Bfs 就行啦=￣ω￣=（这题我还 WA 了一次 T 了一次）#include <bits/stdc++.h> #define NS (1005) using 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 我随机到了这道傻逼题我有什么办法啊。。。 $k = 1$，序列全取中位数 $k = 2$，同 bzoj1367 sequence，只不过把问题中的上升改成不降（以及不升）$k = 3$，预处理 $1 -> i$的不降（以及不升）的最小代价，还有 $i -> 阅读更多…

最小圆覆盖 luoguP1742 给定 $n$个点，求一个最小的圆包围所有的点。 随机增量法 定理 1：如果点 $p$不在集合 $S$的最小覆盖圆内，则 $p$一定在 $S\cup{p}$的最小覆盖圆上。 根据这个定理，我们可以分三次确定前 $i$个点的最小覆盖圆。 1. 令前 阅读更多…

定睛一看，感觉跟选课貌似差不了太多诶…… 可是当我直接把我的 树形 DP+Tarjan 缩点 搞上去的时候却 WA 了一片 结果最后居然是数组大小的问题 QvQ…. 那么我们正式进入主题。 上文已经说了，正解就是 Tarjan+树形 DP。 为什么要 Tarjan 阅读更多…

题目分析 先将网格图红白染色（你问为什么不是黑白？因为我在草稿纸上画图时发现把黑色格子改成红色是不可能的……）。 然后将与蓝色线相邻的红色格子改成黑色，相邻的白色格子改成蓝色。 大概长这样（灵魂画手 litble 再现江湖！）这样你会发现： 1. 整张图黑格子与红格不相邻，蓝格子和白格子不相邻。 阅读更多…

水博客真开心 1. 题目 传送门=￣ω￣= 2. 题解 枚举第一行状态，后面的状态就都知道了。 理论上高斯消元也能做，但是我并不知道怎么找又要 1 的个数最少又要字典序最小。。。 代码： #include <bits/stdc++.h> #define NS (20) using nam 阅读更多…

1. 题目 传送门=￣ω￣= 或者也可以去 Luogu 看 2. 题解 设 $f[x]$表示从 $1$号点一直游走，游走到点 $x$都一直没有爆炸的概率。 $f[x]=(1 – \frac P Q) \sum {\frac {f[v]} {degree[v]}} + [u == 1]$ 阅读更多…

吐槽 这么简单的算法我为啥学会 $splay$之后等了好久才学 $QAQ$，大概 qhy 对码力要求高的算法总有一种抗拒心理，然而这个东西比后缀自动机好理解多了所以读者们请放心食用。 为了能更方便看懂我的代码，我在把我的代码中的宏定义放这里: #define fo(i, a, b) for (int 阅读更多…

1. 题目 传送门=￣ω￣= 翻译： 给你一个串 $S$以及一个字符串数组 $T[1..m]$，$q$次询问，每次问 $S$的子串 $S[p_l..p_r]$在 $T[l..r]$中的哪个串里的出现次数最多，并输出出现次数。 如有多解输出最靠前的那一个。 $|S| \leq 5 \times 10 阅读更多…