比较考思维的一道斜率优化。 Description 农夫 John 准备扩大他的农场,他正在考虑 $N (1\le N\le 50\ 000)$ 块长方形的土地。每块土地的长宽满足 $(1\le$ 宽 $\le 1\ 000\ 000, 1\le$ 长 $\le 1\ 000\ ...
解题报告
洛谷 P3195 [HNOI2008]玩具装箱 题解【斜率优化】【DP】【单调队列】
斜率优化..感觉没学过 题目描述 P 教授要去看奥运,但是他舍不得他的玩具,于是他决定把所有的玩具运到北京。 他使用自己的压缩器进行压缩。这个压缩器可以将任意物品变成一维,再放到一种特殊的一...
洛谷 P4382 / loj 2477 [九省联考2018] 劈配 题解【网络流】【贪心】【二分答案】
一道灵活的网络流题目。 题目背景 一年一度的综艺节目《中国新代码》又开始了。 Zayid 从小就梦想成为一名程序员,他觉得这是一个展示自己的舞台,于是他毫不犹豫地报名了。 题目描述 轻车熟...
CF1139E Maximize Mex 题解【二分图】【匈牙利算法】
我发现我有道叫[SCOI2010]连续攻击游戏的题白写了.. Description There are $n$ students and $m$ clubs in a college. The clubs are numbered from $1$ to $m$. Each student has a potential $p_i$ a...
CF1139D Steps to One 题解【莫比乌斯反演】【DP】【枚举】
反演套 DP 的好题(不用反演貌似也能做 但是我不会啊 Description Vivek initially has an empty array $a$ and some integer constant $m$. He performs the following algorithm: Select...
洛谷 P2480 [SDOI2010]古代猪文 题解【CRT】【欧拉定理】【Lucas定理】
数论综合题。 题目背景 题目背景与题目无关因此省略。题目链接 题目描述 猪王国的文明源远流长,博大精深。 iPig 在大肥猪学校图书馆中查阅资料,得知远古时期猪文文字总个数为 $N$。当...
loj 6433 「PKUSC2018」最大前缀和 题解【DP】【枚举】【二进制】【组合数学】
这是个什么集合DP啊… 想过枚举断点但是不会处理接下来的问题了… 我好菜啊 题目描述 小 C 是一个算法竞赛爱好者,有一天小 C 遇到了一个非常难的问题:求一个序列的最大子段和。 但是小 C 并不会...
CF1012C Hills 题解【DP】
思路还是比较简单的 dp 吧,但是就是想不出来…甚至类似的方程都被自己推翻了 Description Welcome to Innopolis city. Throughout the whole year, Innopolis citizens suffer from everlasting city co...
洛谷 P4774 / loj 2721 [NOI2018] 屠龙勇士 题解【同余】【exgcd】【exCRT】
推导过程存在漏洞+exCRT板子没打熟于是期望得分÷实际得分=∞? 题目描述 小 D 最近在网上发现了一款小游戏。游戏的规则如下: 游戏的目标是按照编号 $latex 1\sim n$ 顺序杀掉 $latex n$ 条巨龙...
51nod 1943 联通期望 题解【二进制】【枚举】【概率期望】【DP】
集合统计类期望题目。 题目描述 在一片大海上有 $latex n$ 个岛屿,规划建设 $latex m$ 座桥,第i座桥的成本为 $latex z_i$,但由于海怪的存在,第 $latex i$ 座桥有 $latex p_i$ 的概率不能建造。 ...