SSL-OI夏日合宿 2020.08.21 A组

这两天花了好多钱买键盘和键帽, 因为喝多了? F60竟然删减了蓝牙模块(虽然平时也不怎么用), 粉色F60配上纯白键帽感觉还是可以的. 今天试着打了打部分分, 不是很顺利, 但是还算是一次可以的尝试.

A 决战

一道小水题, 但我还是没有想正解去打了部分分.

题意

给一张$n$个点$m$条边的图, 问: 删哪个点可以使剩余的图变成一棵树. 保证至少存在一个点可以成为答案.

故事

选择了一档$m=n-1$的部分分和一档$m=n$的部分分, 最后只有树那一档打出来了, 20pts.

题解

首先, 被删去的这个点必须不是割点, 这个用tarjan求出. 对于一个非割点$x$, 若删去这个点所剩下的图是一棵树, 必有$m-Due_x=n-2$. $Due$表示这个点的度.

然而强连通我不会, 所以判图也不会

B 终焉

C 解读

很显然这是一道贪心题, 但我贪错了. 果然平时不贪心的人, 考场也不会贪心.

题意

给一个长为$n$的数组$a$, 以$a_i+2\times a_i$的方式合并两个数. 有$q$组查询, 每组查询询问$[l,r]$内合并的最大值.

$n,q\leq10^5$, 答案对$10^9+7$取模.

故事

很明显, 求最大又要取模, 只能是贪心. 考场打了第一档$n\leq10$的区间DP, 尝试打了一个$n^2$的暴力(但是错了).

正解

感性理解题解可以发现, 如果对于一给子段$b$有$f(b)<0$,

容易发现, 这道题是对于每个值乘上一个$2^k$的系数然后求和. 若是连续的一段(从后往前)合并, 一段中的系数指数$k$是递增的. 如: $$a_{i}^{2^0}+a_{i+1}^{2^1}+a_{i+2}^{2^2}+a_{i+3}^{2^3}$$

若要合并两个连续的段, 将两个段的和依次设为$s_1$和$s_2$, 合并后有$s=s_1+2\times s_2$.(如题)

考虑$l=1$(Sub5)的情况. 显然$a_1$的系数为$1$, 其他数的系数至少为$2$. (至少会跟$a_1$合并一次) 若加入的值小于$0$, 我们希望它的指数尽量小, 则将指数设为$2$. 若加入的值大于$0$, 它肯定能做正贡献, 我们将它的系数指数设为它前一个的系数指数$+1$. (并入上一个块)如: $$(a_i\geq0)$$