学习方面

这个学期初的八科总分大概在 $\dfrac{725}{810}$ 左右，经过了一个学期的努力，现在快要期末考了，总分大约 $\dfrac{620}{810}$ 左右。

恭喜，你有 $80\%$ 的概率考不上普通高中！

OI 方面

今年各种比赛的 AK 次数：0

前十次数：严格小于 1。

CSP/NOIP: 200/80。

恭喜你被 ty_xyz 吊打，并且已经退役！

Day 0

反正我这么菜，NOIP 包没有 1= 的，那么趁退役之前当然要再腐一会，generals，启动！

Day 1

今年总算能来 NOIP 了，目标是完赛。

门口聚集了不少人，广大附的厕所真高级。

Day 0

学校校运会，本来得被迫报 800 和 1500，但是 1500 在 CSP 当天，而 CSP 前得好好休息，况且校运会很危险，所以 800 米自然也非常遗憾地无法参加了。于是我早上在打比赛的时候摆烂，一个位的代码都没打，自然也没有交。

到了中午，虽然我们老师上一天刚发起了“整风运动”，但既然都要结束集训了，直接开腐，熟练地安装了 HMCL 和 JRE，不熟练地上了同学的服务器。

下午快乐喝奶茶，晚上看《算法竞赛》缓解慌的心情。

题意

在范围 $\left [1, n \right ]$ 的数轴上，给定 $m$ 个子区间 $\left [l_i, r_i \right ]$，我们可以选择一个出发点 $x$，则贡献为 $\Sigma_{i = 1}^m \max(\left | l_i - x \right | ,\left | r_i - x \right |)$。求最小的贡献和其对应的 $x$，若 $x$ 有多个，输出最小的一个。

解法

假设我们有一个子区间 $\left [3, 5 \right ]$，则它对 $\forall x, x \in \left [ 1, n \right]$ 的贡献为：

题意

$n - 1$ 条主边构成一棵树，再在上面加 $m$ 条辅边，对这颗树进行若干次操作，每次操作有参数 $opt, u, k$，
若 $opt = 1$，则将点 $u$ 权值加 $k$，并对所有通过主边或辅边与 $u$ 相邻且深度比 $u$ 小的点重复此操作。
若 $opt = 2$，则将点 $u$ 权值加 $k$，并对所有通过主边或辅边与 $u$ 相邻且深度比 $u$ 大的点重复此操作。

求最后所有点的权值。

Week 1

Day 1

早上调题。

龙说 18:00 ~ 19:30 可以来，本来想 18:00 就来的，但是在家收东西，6 点才出发，到宿舍遇到了 shine，然后去机房。老师严厉谴责了我们不打比赛的做法。笑死了，我太菜了，每次都做不出来。

装了个 Fedora 和 VSCode 来码。

晚上回到宿舍，睡得挺爽。

题意

有一个长 $n$ 的序列，我们分别从 $[1, n]$ 开始遍历，每次遍历到尾就跳到头继续。遍历开始时设一个变量 $cnt$，遍历时累加序列中的数。如若整个遍历过程中一直 $cnt > 0$，那么称这次遍历是“安全的”。

每次“安全的”遍历都会生成了一个长度为 $n$ 的新序列，将这些新序列按序列开头的数在原序列的位置从小到大排序，然后将它们拼接到一起，替换原序列。

我们再执行以上操作 $k$ 次，求最后一次操作找到了几个“安全的”遍历。

阅读全文 »

Day 0

腐朽，一直腐到晚上 11 点，我觉得明天可以直接保玲了。

Day 1

台风来了，雨太大了，只好打车去，好在没有迟到，七中就是近。（怎么年年都在七中啊)

到那里遇到 Nemophery，我们一起进去了，到机房时人还很少，shiny_shine 已经到了，讨论了一下昨晚 CF 的 B，发现自己是 Joker，想出做法打不出来。

电脑开机，七中的电脑换了新的 CPU、内存和系统，唯一不变的是又老旧又勾石的 Dev-C++。打开 Chrome，受不了旧版，就下了个新 Chrome，然后打开 CF 看 shiny_shine 的代码。这时 codingcow、chili、cyt、ljd、nst、chl、K1ngsley 都来了，真是 TY 专场。shiny_shine 说他从 github 上下载了一个 Mingw-w64-13，可惜我来不及下载了。

开始比赛了，看来少年宫吸取了教训，不是 IOI，他们的机子连 Oiclass 都比不上，用着高级的 Ubuntu 16.04 配 kernel 4.4.0。

瞪眼出结论题

结论

先考虑只有一次询问的情况。

我们要构造一个序列 $b$。

1. 如果 $c_i$ 是 $1$，那么 $b_i$ 取 $2$。
2. 否则，$b_i$ 取 $1$。

这样就能做到 $\Sigma b$ 尽量小。

如果 $\Sigma b \le \Sigma c$,那么肯定是可以通过一些骚操作满足条件的。否则再怎么样也不行，毕竟 $\Sigma b$ 已经尽量小了。

思路

很容易证明这是道贪心，贪心策略是先打离自己近的。

证明（不严谨）：

有 $2$ 个怪物 $i$ 和 $j$，如果 $\left | x_i \right| < \left | x_j \right |$，且先打 $j$ 更优。

由于先打 $j$ 更优，所以我们在先打 $j$ 的情况下自己不会被怪物吃掉。

但是，不管怎样顺序，打死这两只怪物的总时间相等，所以我们先打 $i$ 和先打 $j$ 是一样的。

而且在有些情况下，先打远的会导致近的偷家，于是就没有先打近的优。