题意描述

洛谷链接

LibreOJ 链接

幼儿园里有 \(N\) 个小朋友，lxhgww 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww 需要满足小朋友们的 \(K\) 个要求。幼儿园的糖果总是有限的，lxhgww 想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

概念

差分约束指的是一种 \(n\) 元一次不等式组。令有 \(n\) 个未知数 \(x_1, x_2, \cdots, x_n\)，\(m\) 个形如 \(x_i - x_j \leq c_k\) 不等式，利用差分约束我们可以求出满足条件的解，或判断无解。

概念

最近公共祖先（英文 Lowest Common Ancestor，简称 LCA）定义为树种两个点的公共祖先里面，离根最远的一个。

概念

树状数组是一种维护线性数组前缀和的特殊方法，使用了类似于快速幂等的二进制分组的优势，对数组进行分段，从而可以快速求出该数组的前缀和的树形数据结构。

这一点与线段树类似。树状数组能干的事情线段树都能干，线段树能干的事情树状数组不一定能干。但树状数组相对线段树代码更短更好写，故在只涉及单点修改的时候树状数组更常用。

学完 wxk 的康复训练

学 wxk 学久了感觉 wxk 有意思，学 OI 学久了感觉 OI 有意思。 ——huaruoji

题意描述

洛谷链接

给定一个长度为 \(n\) 的整形数列 \(A_{1 \sim n}\)，先将其分为 \(m\) 段，并要求每段连续，目前需要一种分法，使得分出的每段和的最大值最小。

又滚来记流水账了。。。

Day -???

CSP-S 2021 第二轮成绩出来了，72 分，稳过。

我们学校的 NOIP 名单也出来了，全校参赛不到 10 个人。。。

Day -2

成功申请停课。。。

顺带在昨天过了 单源最短路径（弱化版）。调了 2 天的 bug，我太蒻了 QWQ。

看了一下图论基础，准备刷一下 DP 题。

考点也出来了，在天府七中（离家好远啊，开车将近一个小时），不过还好终于在成都考了。

爆零了？

没爆零！

Day 0

简单的准备了一下，下午在机房摸了一小会儿鱼，看了一下考试技巧，在洛谷上写了一下单源最短路找一下手感，顺便再和 "Isoheptane" "huaruoji" 聊一下天。

Day 1

CCF 迷惑操作，把考点设置在了绵阳

开了一个上午的车，终于到了绵阳东辰国际学校。来到考场后，发现考场环境比想象中的要好，九代标压 i7 加上 8G 内存完全够用。

《<算法竞赛进阶指南> 0x01 位运算》读后感

补码

计算机中的整数均使用补码存储，位运算时也不例外。

故十六进制中大于 0x7FFFFFFF 时就为负数。

在 memset(src, val, len) 中是将 val 不停循环地填入 src，且 0x00 < val < 0xFF。

故可以将 0x3F 定义为一个很大的数，即为 INF。

总觉得应该写些什么……

Day 0

今天周六，中午日常去机房，该复习的都复习过了，已经无心复习初赛，只是看了一下图论。

考场设在石室文庙，又勾起了中考考砸的不美好的回忆 QWQ

早上老师正常讲了一下课，中午竞赛来时强调了一些重要事项，下午又上了一些课。

晚上回家已经很晚，最后上床前复习了一下图论和卡特兰数。

概念

前缀和为一种预处理，可理解为数列前 \(n\) 项的和。可降低查询某些信息的所需时间。

1
2
3
4
5
6

// 前缀和示例
int sum[MAXN];
sum[0] = a[0];
for (int i = 1; i < n; i++) {
    sum[i] = sum[i - 1] + a[i];
}