ITMO Chinese Winter Camp -Day4

ITMO Chinese Winter Camp Day4

Statements

Solutions

Slides of tutorial

Problem A

Solved by Weaver_zhu. 00:18:37(+)

温暖的签到

Problem B

Solved by Xiejiadong. 00:13:08(+1)

不怎么温暖的签到。

Problem C

Solved by Kilo. 01:57:07(+2)

题意：$n$个海盗发现了$m$枚钱币，海盗要从第一个人开始每个人提出一个分配方案，如果同意的人数没有严格大于不同意的人数，第一个人就会被推下海。每个人只有在保证自己绝对安全并且绝对可以拿到更多的钱的情况下才会同意方案，求第一个人最多可以分给自己多少钱

题解：这题看上去很像是找规律，但实际在人数太多的情况下规律会变得很复杂，因此使用朴实的方法记录贿赂每个人需要的金额。对于第$i$个人来说，贿赂第$i-1$个人需要的金额是第$i-1$个人能分给自己的钱数$+1$，如果第$i-1$个人必死就$0$元也能贿赂。第$i$个人总共需要除自己之外的$i/2$票，选出贿赂金额最少的$i/2$个人后，如果最低的没有被贿赂的人需要的金额是$k$，那么所有需要$k$以下金额的人都一定会被贿赂喔，这些人的贿赂金额$+1$，剩下的人不一定会被贿赂到，因为无法保证绝对能拿到更多的钱，给他们$1$枚钱币就能得到支持。用$O(n^2log(n))$的复杂度推到第$n$个人即可。

Problem D

Upsolved by Weaver_zhu.

自闭快2h已经枚举出来了正解的处理形式，因为没有清楚的推出式子导致没看出最后一步否掉了正解，背大锅。

题意：给一个没有重边自环的图，求最小割，其中最小割的代价定义是边权的平均值而不是总和。

思路：二分答案，小于二分值的当然选取以拉低平均值记为$\sum{neg}$，之后再求出最小割，注意这个最小割中建图的边权应该是$W_i=w_i-x$，$x$是二分值。总的来说推出式子发现只要让$\sum{W_i}+\sum{neg}$加起来小于0就算满足，这样就不用考虑边的数量了（分子小于0就小于0了不用管分母）。

Problem E

Unsolved.

Problem F

Solved by Weaver_zhu. 01:17:45(+)

题意：给出长度n，求单调序列长度（下降链或上升链）最短的n序列中最短的那一个。

思路：固定下降链的长度去想，让上升链最短，可将答案接近到$sqrt(n)$，而可以证明答案更小是不可能的，然后考虑字典序最小。场上打表找出规律，令$m=sqrt(n)$，发现$n=m^2$时是m个下降连续序列一定是最小的，不相等的话从后往前填满m+1个下降的连续长度为m+1个序列，比如10的话就是6,5,4,3和10,9,8,7，和1和2。（其实这是打表找出来的规律）。可以发现，为了保住第一个位置是1，必须从后往前尽量塞满，若2也能保住也是同理从后往前塞。再有三是不可能的，因为这样单调序列长度就不为m+1了。

Problem G

Upsolved by Xiejiadong. (-2)

题意：给出一个$0$/$1$串，用最少的操作使得$S_1$..$S_{n-m}$和$S_{m+1}$..$S_n$匹配，操作有两种选择，一种是反转单个字符，另一个是反转$S_1$..$S_{k*m}(k=const)$。

题解：

$S_1$..$S_{n-m}$和$S_{m+1}$..$S_n$匹配，我们可以很显然的得出，$S_i=S_{i+m}$。

也就是说，我们把原串按照$m$分块以后，分别对应每一块的第一位、第二位都要相等。

分两种情况讨论：

• $m<=\sqrt{n}$

这样的情况，每一块都很小，我们考虑枚举块的最终状态，$f[i][j][k]$表示，到第$i$块，每一块的最终状态为$j$，当前是否处于反转状态$k=0/1$。

这样就很好转移了，因为后面的反转状态和前面的无关，从后往前推dp即可。

• $m>\sqrt{n}$

这个每一块都很大，但是块不多。

我们可以发现，对于反转$S_1$..$S_{k*m}(k=const)$的操作，对于每一个$k$最多执行一次，因为执行多了没有意义，而且执行的先后任意。

这样，我们就可以枚举，每一个$k$时候执行，然后再暴力计算还需要的第一类操作次数即可。

Problem H

Solved by Weaver_zhu. 02:38:54(+1)

题意：给出$k(k<=10)$个$|V_i|=n_i$的简单图，求是否存在一个长度$k$，使得每个图都存在一个长度为$k$从$1$到$n_i$的通路。

思路：由于可以从终点与另一个点之间反复横跳，只需求出到终点长度为奇数的最短距离和偶数的最短距离。将每个点拆成两个点，一个表示到这个点距离为偶数的，一个表示奇数的，那么边连一定是偶数连奇数，奇数连偶数。求最短路得出每个图的奇数最短距离和偶数最短距离。一通取max（距离短的反复横跳等距离长的）后得出两种情况（长度为奇数和偶数）的解。

Problem I

Solved by Xiejiadong. 00:27:10(+)

题意：如果$S_{i-1}$的子串包含$i$，那么$S_i=S_{i-1}$，否则$S_i=S_{i-1}+i$。

题解：从$1$开始，依次计算$S_i$，用$f[i]$保存当前的子串是否已经出现了$i$，直接暴力计算即可。

Problem J

Unsolved.

Problem K

Unsolved.

Problem L

Unsolved.