B Cobb
题目大意
给定一个长度为 n 的序列 {a1,a2,⋯,an} 和 k,当 1⩽i<j⩽n 时,求最大的 i⋅j−k⋅(ai∣aj) 的值,也就是求
max{i⋅j−k⋅(ai∣aj):1⩽i<j⩽n}
取值范围:2⩽n⩽105,1⩽k⩽min(n,100)
思考
注意到 k⩽100 这个奇葩取值范围,就肯定猜到和暴力枚举 k 这个范围有关,比赛时往这方向想了,但没有从最值条件上考虑导致没有弄出来。
令 f(i,j)=i⋅j−k⋅(ai∣aj)
观察式子 i⋅j−k⋅(ai∣aj)
第一项 max{i⋅j}=(n−1)⋅n,第二项 max{k⋅(ai∣aj)}=k⋅2n,发现第一项大小远超第二项
所以我们直接考虑最大的第一项,也就是 i=n−1,j=n 时
f(n−1,n)⩾(n−1)⋅n−k⋅2n=n2−2kn−n
考虑当 j=n 时,如果 ∃i,f(i,n)>f(n−1,n),考虑 i 的最大取值范围
即 max{f(i,n)}>min{f(n−1,n)}
有 i⋅n>n2−2kn−n⇒i>n−2k−1⇒i⩾n−2k
故 i∈[n−2k,n],也就是说 i 的取值只有 2k 种,那么我们只需要在区间 [n−2k,n] 中枚举 i,j 即可,复杂度 O(k2)
点击显/隐代码
C Mikasa
题目大意
给定 n,m(0⩽n,m⩽109) 求出在集合 S={n⊕0,n⊕1,⋯,n⊕m} 中没有出现过的最小的非负整数,数学化表达就是求
min{k∈N:k∈/S}
思路
考试是死磕了一个半小时还没弄出来,结束后又弄了半个小时才做出来,主要原因是想直接分类讨论出来,但其实可以通过转换问题从而简化问题,所以并没有必要去讨论
先分析问题
若 k∈S,则 ∃x⩽m,使 n⊕x=k⟺n⊕k=x,于是有 0⩽n⊕k⩽m,所以问题转换为求最小的 k 使得 n⊕k⩾m+1,也就是求
min{k∈N:n⊕k⩾m+1}
注意这里取 ⩾ 而不是 >,因为我们容易修改 k 使得式子两边值相等,所以取等时可以减少讨论。
这里问题就变得很简单了。。。可以自己思考下
我们从二进制上来分析问题,令 M=m+1, ni,Mi,ki 表示 n,M,k 二进制下的第 i 位值
下面从高位到低位讨论 n,M 在第 i 位不同取值时,k 对应的取值:
- ni=Mi⇒ki=0
- ni=0 and Mi=1⇒ki=1
- ni=1 and Mi=0⇒∀j⩽i,kj=0,不用再对低位进行讨论了
抓住要求 k 尽可能小这个性质,原因不难解释,可以自己手玩一下。
点击显/隐代码
D Diane
题目大意
要求构造一个长度为 n 的字符串S,满足他的任意子串s在原串S中出现次数为奇数
思路
考验构造能力
先手玩一下aaaaaa
的每个子串出现次数:a=6,aa=5,aaa=4,aaaa=3,aaaaa=2,aaaaaa=1
,容易发现奇偶性是一偶一奇
再玩一下aaaaa
:a=5,aa=4,aaa=3,aaaa=2,aaaaa=1
,发现奇偶性是一奇一偶
我们又知道:奇+偶=奇
那么如果我们把他们联合起来是什么效果,中间有一个其他字符截断
aaaaaabaaaaa
:a=11,aa=9,aaa=7,aaaa=5,aaaaa=3,aaaaaa=1
,这样不就满足条件了?
令aa...a
串长度为 l,如果令 l1=⌊2n⌋,l2=l1−1
那么构造为 aa…abaa…al1 l2 (n为偶) 或 aa…abcaa…al1 l2 (n为奇)
点击显/隐代码