CF1554

B Cobb

题目大意

给定一个长度为 nn 的序列 {a1,a2,,an}\{a_1,a_2,\cdots ,a_n\}kk,当 1i<jn1\leqslant i < j \leqslant n 时,求最大的 ijk(aiaj)i\cdot j-k\cdot(a_i|a_j) 的值,也就是求

max{ijk(aiaj):1i<jn}max\{i\cdot j - k\cdot (a_i|a_j):1\leqslant i < j \leqslant n\} \\

取值范围:2n105,1kmin(n,100)2 \leqslant n\leqslant 10^5, 1\leqslant k \leqslant min(n, 100)

思考

注意到 k100k\leqslant 100 这个奇葩取值范围,就肯定猜到和暴力枚举 kk 这个范围有关,比赛时往这方向想了,但没有从最值条件上考虑导致没有弄出来。

f(i,j)=ijk(aiaj)f(i,j)=i\cdot j-k\cdot(a_i|a_j)

观察式子 ijk(aiaj)i\cdot j-k\cdot(a_i|a_j)

第一项 max{ij}=(n1)nmax\{i\cdot j\}=(n-1)\cdot n,第二项 max{k(aiaj)}=k2nmax\{k\cdot(a_i|a_j)\}=k\cdot 2n,发现第一项大小远超第二项

所以我们直接考虑最大的第一项,也就是 i=n1,j=ni=n-1,j=n

f(n1,n)(n1)nk2n=n22knnf(n-1,n)\geqslant (n-1)\cdot n-k\cdot 2n=n^2-2kn-n

考虑当 j=nj=n 时,如果 i,f(i,n)>f(n1,n)\exists i,f(i,n) > f(n-1,n),考虑 ii 的最大取值范围

max{f(i,n)}>min{f(n1,n)}max\{f(i,n)\} > min\{f(n-1,n)\}

in>n22knni>n2k1in2ki\cdot n > n^2-2kn-n \Rightarrow i > n-2k-1 \Rightarrow i \geqslant n-2k

i[n2k,n]i\in[n-2k,n],也就是说 ii 的取值只有 2k2k 种,那么我们只需要在区间 [n2k,n][n-2k,n] 中枚举 i,ji,j 即可,复杂度 O(k2)O(k^2)

C Mikasa

题目大意

给定 n,m(0n,m109)n,m(0\leqslant n, m \leqslant 10^9) 求出在集合 S={n0,n1,,nm}S=\{n\oplus 0, n\oplus 1, \cdots, n\oplus m\} 中没有出现过的最小的非负整数,数学化表达就是求

min{kN:kS}min\{k\in \mathbb{N} : k \notin S\}

思路

考试是死磕了一个半小时还没弄出来,结束后又弄了半个小时才做出来,主要原因是想直接分类讨论出来,但其实可以通过转换问题从而简化问题,所以并没有必要去讨论

先分析问题

kSk\in S,则 xm\exists x \leqslant m,使 nx=k    nk=xn\oplus x=k \iff n\oplus k=x,于是有 0nkm0\leqslant n\oplus k\leqslant m,所以问题转换为求最小的 kk 使得 nkm+1n\oplus k\geqslant m+1,也就是求

min{kN:nkm+1}min\{k\in \mathbb{N}:n\oplus k\geqslant m+1\}

注意这里取 \geqslant 而不是 >>,因为我们容易修改 kk 使得式子两边值相等,所以取等时可以减少讨论。

这里问题就变得很简单了。。。可以自己思考下

我们从二进制上来分析问题,令 M=m+1M=m+1, ni,Mi,kin_i, M_i, k_i 表示 n,M,kn, M, k 二进制下的第 ii 位值

下面从高位到低位讨论 n,Mn, M 在第 ii 位不同取值时,kk 对应的取值:

  1. ni=Miki=0n_i=M_i\Rightarrow k_i=0
  2. ni=0 and Mi=1ki=1n_i=0\ and\ M_i=1\Rightarrow k_i=1
  3. ni=1 and Mi=0ji,kj=0n_i=1\ and\ M_i=0\Rightarrow \forall j\leqslant i,k_j=0,不用再对低位进行讨论了

抓住要求 kk 尽可能小这个性质,原因不难解释,可以自己手玩一下。

D Diane

题目大意

要求构造一个长度为 nn 的字符串S,满足他的任意子串s在原串S中出现次数为奇数

思路

考验构造能力

先手玩一下aaaaaa的每个子串出现次数:a=6,aa=5,aaa=4,aaaa=3,aaaaa=2,aaaaaa=1,容易发现奇偶性是一偶一奇

再玩一下aaaaaa=5,aa=4,aaa=3,aaaa=2,aaaaa=1,发现奇偶性是一奇一偶

我们又知道:奇+偶=奇

那么如果我们把他们联合起来是什么效果,中间有一个其他字符截断

aaaaaabaaaaaa=11,aa=9,aaa=7,aaaa=5,aaaaa=3,aaaaaa=1,这样不就满足条件了?

aa...a串长度为 ll,如果令 l1=n2,l2=l11l_1=\left\lfloor\frac{n}{2}\right\rfloor, l_2=l_1-1

那么构造为 aaabaaal1   l2\begin{matrix}\underbrace{aa\ldots a}b\underbrace{aa\ldots a}\\l_1\qquad\ \ \ l_2\end{matrix} (n为偶) 或 aaabcaaal1 l2\begin{matrix}\underbrace{aa\ldots a}bc\underbrace{aa\ldots a}\\l_1\qquad\quad\ l_2\end{matrix} (n为奇)


CF1554
https://wty-yy.github.io/posts/18831/
作者
wty
发布于
2021年7月30日
许可协议