关于一些没做出来的SBCF题

这里是一些我SB没做出来的CF水题。

其实这些题思维量还不错,所以写在这里常来看看……

不一定每题代码都会写。


CF1143C Queen

其实只要注意到如果一个点开始能被删,那一直就能被删;一个点开始不能被删,那一直就不能被删就行了。然而……


CF1151B Dima and a Bad XOR

以为是个什么很难的构造题……

先考虑 $c_i=1$,也就是全选第一列。如果可以就可以。

否则如果每行上的数全都相等,那么无论如何改变 $c_i$ 都不行,输出无解。

否则随便改一个数改成不同的即可,一定是合法解。


CF1151E Number of Components

这场div2是smg……

先考虑如何求一个 $f(l,r)$。如果我们把权值在 $[l,r]$ 的数记为 $1$,其它记为 $0$,那么答案就是 $(0,1)$ 对数的个数。(第 $0$ 个数看成 $0$)

那么考虑 $(i,i+1)$ 对总答案的贡献,发现只能是 $a_i$ 不在范围内,而 $a_{i+1}$ 在范围内:

  • $a_i<a_{i+1}$ 时,只能是 $a_i<lle a_{i+1}le r$,贡献为 $(a_{i+1}-a_i)(n-a_{i+1}+1)$。
  • $a_i>a_{i+1}$ 时,只能是 $a_i>rge a_{i+1}ge l$,贡献为 $(a_i-a_{i+1})a_{i+1}$。

做完了。

upd:震惊,这题居然有 $2100$……


CF1155E Guess the Root

这种题做不出来太过分了……

由于多项式次数 $le 10$,可以用 $11$ 次询问询问 $0$ 到 $10$ 的点值,然后拉格朗日插值求出这个多项式,然后把 $11$ 到 $10^6+2$ 判断一遍。


CF1152C Neko Does Maths

先判掉 $a=b$。不妨令 $a<b$,原式相当于 $frac{(a+k)(b+k)}{gcd(a+k,b+k)}=frac{(a+k)(b+k)}{gcd(a+k,b-a)}$,然后就不会做了。

发现分母一定是 $b-a$ 的约数。可以枚举 $gcd$。设正在枚举到的是 $d$,那么 $a+k$ 必须得是 $d$ 的倍数。令 $a+k$ 为 $ge a$ 的数中是 $d$ 的倍数的最小的。

???那 $gcd(a+k,b-a)$ 可能比 $d$ 大啊?没事,那样答案只会更小,而且枚举重了也没事。


CF1179B Tolik and His Uncle

对于歪果仁来说的送分题。对于我来说的送命题……

直接 $(1,1) ightarrow(n,m) ightarrow(1,2) ightarrow(n,m-1) ightarrowdots ightarrow(1,m) ightarrow(n,1) ightarrow(2,1) ightarrow(n-1,m) ightarrowdots$ 即可。


CF1208C Magic Grid

又一道送命构造。

把数按 $lfloorfrac{x}{16} floor$ 分组,每组有 $16$ 个数。对每组按 $0$ 到 $15$ 的方法构造,把小矩阵拼起来。

原文地址:https://www.cnblogs.com/1000Suns/p/10657515.html