精彩打脸合集

日常三题选手…

中国场！莫名的激动。题目的风格真的和出题人有关，虽然我只做了三题

可能是到目前为止最成功的一次 cf 了，下次要做到没人带我也这么强。

区间$\text{DP}$比线性$\text{DP}$好想一些。

update on 2020.4.26 新增糖果代码

浅谈差分约束

差分约束系统 是一种特殊的 $n$ 元一次不等式组，它包含 $n$ 个变量 $x_1,x_2,\cdots x_n$ 以及 $m$ 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 $x_i-x_j \leq c_k$，其中 $c_k$ 是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解 ，使得所有的约束条件得到满足，否则判断出无解。

A Divisibility Problem

题目描述

给定两个正整数 $a$ 和 $b$，你可以在一步操作中将 $a$ 加上 $1$。你需要找到最少需要多少步操作可以使得 $a \mid b $。存在最开始就满足 $a \mid b$ 的可能从而只需要 $0$ 步操作。

原题链接

题目描述

幼儿园的小孩们收到了一个有 $m$ 颗糖果的大包裹，现在要把这些糖果分给 $n$ 个小孩。

每一个小孩都给出了一个期望的糖果数，如果没有达到他的期望值 $a_i$，小孩就会生气。每差一个糖果，小孩的生气指数就会增加，可以认为他生气的程度等于他少得到的糖果数的平方。

比如，Mirko 想要得到 $32$ 个糖果，但是只得到了 $29$ 个。他少了 $3$ 个，所以他的生气指数是 $9$。不幸的是，糖果数不足以满足所有小孩的期望。所以我们应该采取最优的分配方法，使得最后小孩们的生气指数的和最小。

CF上的题目确实值得一做，打比赛是提升代码水平的好方法。

前言

在P6180 【[USACO15DEC]Breed Counting S】这篇文章中，我介绍并使用了前缀和的方法来通过该题，这次来讲前缀和的扩展——二维前缀和。