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$ 是一样的。

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

思路

在不考虑能否构成三角形的情况下，三角形有这几种情况：

1. 三条边的长度各不相等；
2. 等腰，其中腰比底长；
3. 等腰，其中底比腰长；
4. 等边三角形。

题目中木棍的长度都是 $2$ 的幂，我们再对上述几种情况作进一步分析：

1. 无法构成三角形。为了构成三角形，我们要让较短的 $2$ 条木棍尽量长，则三个木棍的长度为 $2^x,2^{x+1},2^{x+2}$，明显构不成三角形。
2. 很明显可以构成三角形。
3. 无法构成三角形。两条腰长度之和最大也只能等于底。
4. 很明显可以构成三角形。

Day 0

早上语文模拟考要写作文，核心画面忘背了，只好省略 ，只有开头和结尾也挺好。我和 ty_xyz 是同个语文老师，但他们班的语文课在下午，所以他就可以逃掉模拟考，可恶！

中午吃完午饭回到教室，黑板上说我的数学报纸在老师那，老师让我去办公室改。没门的啦，我背上书包就直接去机房集合了。

到了机房，阔别已久的 nisuiting 也来了（他淦爆电脑屏幕被停训了）。他一来，机房就炸开了锅，以至于陈老师定义了机房的两种状态：有 nisuiting 的机房和没有 nisuiting 的机房。

在车上颠了两个小时在车上观了两个小时的腐，终于到了东莞。看到了小学悦教育的同学，拿了主办方给的袋子（埋下伏笔），看了看参赛情况，我们学校居然总人数第一，中山纪中以一人的优势落后于我们。饭堂和 ty 有得一比，我们应该吃的是他们老师吃的东西。

回到酒店，和 ty_xyz 住在一起，回到房间，拿出英语作业，WHK，启动！$5$ 分钟后，傻逼 WHK，拿出电脑，腐朽，启动。Nemophery 也来和我们一起腐朽。酒店的网络是要短信验证码登陆的，然而我并没有手机，但是却莫名奇妙的可以上网。我 $2$ 个月没打 MC 了，因为打开存档不知道该干嘛。感谢 GDKOI 给了我开腐 MC 的契机。我赶紧下载好 1.18.2 和 1.8.9。 ty_xyz 说要和我联机，然而要消除正版验证太难了，于是放弃。我去一个 起床服 van 了。