10.24 闲话

祝所有程序员 加班节 程序员节快乐（虽然我不是）。

日寄

上午阿巴阿巴，切了一堆随的题，讲究就是一个随到会的就做，随到不会的一眼过。

感觉机房里乐子越来越少，emo 越来越多了。

中午阔别了一天的某人回机房拿走了他的所有物品。

为啥我感觉考完 CSP 就跑路的那几个人都是比我强的 /kk。或许命运如此吧，whk 又将是新的天地，祝好。

想起我学 whk 的日子了，那时虽然老是觉得作业多，考试砸，还得惦记 OI，但那会儿每天还能发自真心地笑出来。

下午阿巴阿巴，找 wangk 谈了谈，想每个晚自习回去学文化课，wangk 说 noip 后会统一安排。行，就这样吧。

过得好恍惚。

等 HE 迷惑行为赏。

我推の歌

没听歌，但还有库存。

In Hell We Live, Lament

In this inferno (Inferno)

We built for ourselves

Reviving each other in this hell

World execute(me);

Though you're free I'm still trapped in love.

口题解

AT_arc128_e K Different Values

一个位置一个位置添加元素，记 \(m\) 为需要构造的序列长度，即 \(\sum A_i\)，把序列划分，每段长 \(k\)（还可能有一个剩余段），记划分段数（包括剩余段）即 \(\left \lceil \frac{m}{k} \right \rceil\) 为 \(t\)，若有 \(A_i>t\) 直接无解；若有 \(A_i=t\)，说明该元素必须出现在每一段，包括剩余段，选择其中最小的 \(i\) 填到第一个位置；若所有 \(A_i\) 均小于 \(t\)，选择最小的 \(i\) 填到第一个位置。这时我们将问题递归为了要构造一个长 \(m-1\) 的序列，以此类推。

UVA1347 旅行 Tour

首先将原问题进行转化，转化为两个人从左向右走，都是从 \(1\) 到 \(n\) 但途径的点不能重合，求最小路程。设 \(f_{i,j}\) 表示前 \(\max(i,j)\) 个点已经被走过，第一个人走到 \(i\)，第二个人走到 \(j\) 的最小路程。不妨强制使 \(i>j\)，倒序转移，记两点间距离为 \(d(i,j)\)，得到方程：

\(f_{i,j}=\min(f_{i+1,j}+d(i,i+1),f_{i+1,i}+d(j,i+1))\)

初始化所有 \(f_{n-1,i}\) 为 \(d(n-1,n)+d(i,n)\)，最终答案为 \(f_{2,1}+d(1,2)\)。