ACGO 挑战赛 #20 全题解
> 声明:如果您阅读本题解只是学术价值,请跳过每道题的“前言”部分。
故事的开端
Link
然后有一个我们都不认识的人说了一句话
结果实在是太需要 fs 了,等不了疯癫赛,就肝一篇较长的指导性文章 Link。
可是主播的 fs 数依旧没有任何增长,然后刚好碰上了挑战赛,想着先写一篇题解。
于是就有了这篇文章。
T1 小午的222
前言
T1 可是道难题啊(((
我们的 @AAA水泥批发BaiRX哥,@复仇者_帅童,@亚洲卷王 AK IOI 等等 dalao 都被罚了一道两发(((
他们可真 FW 啊(纯恶意
题面描述
给定一个大整数 n=a×10b(1≤a<10)n=a \times 10^b(1 \le a \lt 10)n=a×10b(1≤a<10),请找出一个整数 ttt 使得 n2t\frac{n}{2^t}2tn 为正整数,求 ttt 的最大值。
题目分析
容易发现,n≤10106n \le 10^{10^6}n≤10106,显然不可使用普通变量存储,但打高精度有太麻烦了,考虑常数求值。
首先我们令 f(x)f(x)f(x) 为使得 x2t\frac{x}{2^t}2tx 为正整数的最大整数 ttt,然后考虑一个性质,即 f(x)=f(y)+f(z)(1≤y,z<x,x=yz)f(x)=f(y)+f(z)(1 \le y,z \lt x,x=yz)f(x)=f(y)+f(z)(1≤y,z<x,x=yz)(这里不做证明,留给读者自己思考),所以 f(n)=f(a)+f(10b)=f(a)+f((2×5)b)=f(a)+f(2b×5b)=f(a)+f(2b)+f(5b)=f(a)+b+0f(n)=f(a)+f(10^b)=f(a)+f((2 \times
5)^b)=f(a)+f(2^b \times 5^b)=f(a)+f(2^b)+f(5^b)=f(a)+b+0f(n)=f(a)+f(10b)=f(a)+f((2×5)b)=f(a)+f(2b×5b)=f(a)+f(2b)+f(5b)=f(a)+b+0。除了第一项,其它均为常数,而第一项又可以在短时间时间内求出。
CODE
T2 午枫的01树中心
前言
T2 也是道难题啊(((
我们的 @dream_陆军展览 dalao 也罚了一发,不过因为人数少于 T1,所以难度应该会简单点。
题面描述
给定一棵树,每个节点都有一个点权(000 或 111),求对于一个点与它相连接的所有点中满足这点与他们的点权均不相同的点的个数
题目分析
T2 其实真的不难,它没有涉及到任何算法以及思考,无脑模拟即可,而 T1 还需要进行一定的转换。
CODE
T3 午枫爱搬家2
前言
T3 确实不难,就是一道 01 背包的板子。不过 ppl 第一发还是 RE 了,大概是调了五六分钟才调出来,代码放附件了,看看你们需要多久找出来。
题面描述
01 背包板子
题目描述
无。
CODE
T4 午枫的又一个01串
前言
我个人认为 T4 可能是本场比赛的防 AK 题(大雾
题面描述
给定一个 01 串,定义“度”为整个串中的连续段数量减一,每次需找出一个区间 [l,r][l,r][l,r],满足区间合法长度大于 111 且 sl=0,sr=1s_l=0,s_r=1sl =0,sr =1,对区间内的每个元素进行取反操作。请问进行做多 mmm 次操作后“度”最小为多少。
题目分析
不妨考虑找出每个可能的左端点和右端点,然后进行配对,注意,这里的配对过程有一个小小的贪心,就是我们要对每个右端点配对最小的左端点,而不是对每个左端点配对最大的右端点,这里读者可以自己思考一下缘由。配对完之后再计算每个区间可以减少的度的数量,每次优先选择最多的,最后再处理一些细节就 AC 了。
你可能会觉得不可思议,甚至我自己都不敢相信,可能自己没有办法证明这样是正确的,但容易发现确实没有任何反例能使得这样做错。
这就是第六感。
CODE
T5 午枫的彩排
前言
T5 其实不难,主要还是要想到这是一道数据结构题。
题面描述
有 nnn 位演员,每个演员都有三个指标 wi,si,tiw_i,s_i,t_iwi ,si ,ti ,他们会在 sis_isi 时刻进入舞台,并在 ti+0.1t_i+0.1ti +0.1 时刻准时离场。我们令 f(x)f(x)f(x) 表示第 xxx 位演员入场时在场包括自己所有人的 wiw_iwi 指标(即能力值)最小值,最后对于每位演员请输出 wi−f(i)w_i-f(i)wi −f(i)。
题目分析
我们先从暴力做法入手,首先求出一个人的 f(x)f(x)f(x) 时间复杂度为 O(n)O(n)O(n),那么求出 nnn 个人即为 O(n2)O(n^2)O(n2),显然过不了。
接下来考虑优化,对于第二个 nnn 显然优化不了,那么考虑第一个 nnn,既然是只求最小值不求次小值,很容易想到优先队列 priority_queue。然后又出来一个问题,对于堆内的元素该如何进行过期删除,我个人认为最简单的方法就是存一个 pair 类,第一位存 wiw_iwi ,第二位存 tit_iti ,每次取出队头最小值时判断是否过期,如果是就再取一个直到队列为空。
CODE
T6 午枫的字符串修改
前言
我觉得 T6 还是有点难度的,但是被 @AAA水泥批发BaiRX哥 dalao 用平衡树爆切了,%%%。
这就说明了 TA 肯定用 AI 了(大雾
题面描述
给定一个长为 nnn 字符串,对其进行 qqq 次操作,求最终字符串。
题目分析
对于操作一,既然是区间循环加,果断考虑使用差分,但是由于存在操作二,所以整个字符串的下标会收到影响。
但是注意到操作二是进行循环移动,不妨维护一个变量 tmp,用于表示整个字符串经过了多少次循环移动。进行操作一时先用 tmp 计算出真实下标进行差分即可。
CODE
附件
彩蛋
#1 与 CJDST 的赌约
其实就是赌 T3 的难度,上文找不到了(((
#2 与 BAIRX 的赌约