Pre
本弱实在是太弱了,身边的大佬们切题如喝水,而我昨天A+B做了快一个小时。。。
写一下简要的题意和收获,暂时只打算改ABCD,也许能力强一点(根本不会发生的事)之后会改EF。
#Round 740
A
纯模拟
B
算出一个人需要反转几次才能赢,然后枚举他赢得次数。
因为每次赢都可以和一次输反转加两次break
C
二分答案,先二分计算出来进入每个山洞需要的最小体力。
然后在二分答案,优先选择最小体力最小的山洞进入。
D
貌似这题还行,大佬都说是水题。
D1 可以差分处理第一种+整除分块处理第二种(\(n \sqrt n\))
D2 比较巧妙不用这个点去刷新别人,而是对于每个点看他从谁转移过来,配合一个前缀和,枚举调和级数。(\(n ln n\))
\(\lfloor \frac{a}{b} \rfloor=c\)的数对,对于每一个\(c\),可以直接枚举\(b\)。
这样,最后一个 \(\lfloor \frac{a}{b} \rfloor !=c\)的\(a\)必定是 \((c+1)*b\)。
所以,直接把 \([c*b,(c+1)*b-1]\)的前缀和加到答案就行了。
整除分块变调和枚举。
#Round 741
A
假设模数是\(x\) ,答案就是 \(min(r-x,x-1)\)。
发现是两个一次函数取min,是个单峰且单调段都线性变化。
所以直接看峰点是否在范围内,否则直接把左/右端点当成x
B
看起来很唬人,然而不难。
如果个位中出现了1/4/6/8/9,那么直接输出就是合法方案。
否则,如果有一个位上面的数出现了两次或以上,我们可以11乘这个数。
如果都没判走,那么这个k<=4,直接状压就行了。
推性质带走合法状态从而枚举。
C
考场太困没想出来(菜)
够造一种合法方案,首先如果序列里面有0,那可以操作。
他在前半段,我们可以连上后半段输出两个相等的数(加前导0)
他在后半段,可以构造出两个数为二倍关系。
所以序列里全剩1了,这样也有很多种构造
直接输出两个全等的串(1~(n-1),2~n)。
或者构造(x*(x+2))也可以。
第二种就是先把和他一样长的一段0复制在后面,在加上他自己
111-> 111000 -> 111111
D
太菜还不会做,太废还不想看题解。