9月30日复盘

· · 生活·游记

上午在海亮OJ打了场提高组，发现那几道题根本是不可做的（至少对于像我这样的蒟蒻而言）。。。

悲报 29 分，0+0+0+29=29。。。

下午讲了 25 日和 27 日的作业题。

二十五日的题，第一道其实就是：给定数组 a，构造一个非负数组 b 使得 a_i+b_i 是不降序列，问 \max(b_i)在二进制下最少是几位数。可以发现这两个问题完全等价。

显然，b_1=0是最优的。对于每个 i（i \ge 2），b_i+a_i \ge b_{i-1}+a_{i-1}，根据不等式的性质（好像在 ZJ 是八年级内容？？？），b_i \ge b_{i-1}+a_{i-1}-a_i，计算每个 b_i 即可求出答案。

第二题老师说要二元一次方程？

众所周知，二元一次方程都可以转换为鸡兔同笼问题（大雾）

其实这个方程很简单，无非就是 x_i+y_i=s_i,x_i-y_i=h_i，其中x_i表示经过这个点高兴的人数，y_i表示经过这个点不高兴的人数，s_i表示经过这个点的总人数（通过预处理的方式求得），h_i表示这个节点的检测结果。

注意一些小细节。

第三题类似于这种跳法：

第四题正解还是挺妙的，一句话：请构造一个长度为 9 但输出为 0 的字符串，构造完之后你就知道正解了。

二十七号的四题全部是我补题的时候写的。

第一题，蜘蛛。

显然，直接暴力建边肯定 T。因此，我们考虑 \gcd(a,b)>1其实就是存在一个质数x使得 a \mod x=0且b \mod x=0。那么我们可以将每个 a_i 向它的所有质因数连一条权值为 1 的边，将每个 a_i 的质因数向 a_i 连一条权值为 0 的边，然后跑最短路。（感觉也可以 a_i 的质因数向 a_i 也连一条权值为 1 的边然后bfs，最后答案除以二？我没试过）

第二题看上去答案是 \frac{Σv_i}{t_j}，实则不然。可能会有些 i 满足\frac{Σ_{k=1}^{i}v_k}{i}>t_j，这时无论怎样都无解。其他情况就按之前那个公式算即可。

第三题，显然操作次数要尽可能少，每一次操作最多能加 Σ_{i=1}^{\frac{n}{k+1}}φ_i次，暴力计算即可。

第四题，考虑众数 X 在长度为 n 的区间里出现了 x个。划分的意义在于每多出一组数就可以多容纳一个 X，因此答案就是 \max(1,2x-n+1)。