A. 小葱的01串

Solution

显然为了满足染色后红色和白色的0/1数目相同，设原串中有 $ll$ 个 0，$rr$ 个 1 我们染色的区间里一定满足有 $\frac{l}{2}\backslash frac\{l\}\{2\}$ 个 0 和 $\frac{r}{2}\backslash frac\{r\}\{2\}$ 个1，那么我们枚举每个端点作为左边界，二分右边界看是否符合即可。由于是环形，只需要把字符串扩展为原来的两倍。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49460859

B. 小䓤的一些数字

Solution

注意到 $k\le 20k\; \backslash leq\; 20$，我们都知道 $k=1k\; =\; 1$ 的公式，而 $k\ge 3k\; \backslash geq\; 3$ 时，暴力计算的区间不会超过 $10^{6}10^6$，所以只需要考虑 $k=2k\; =\; 2$ 的情况，打表OEIS找规律得出 ${\sum }_{i=1}^n\lfloor \sqrt{i}\rfloor \backslash sum\backslash limits\_\{i\; =\; 1\}^\{n\}\backslash lfloor\; \backslash sqrt\{i\}\; \backslash rfloor$ 公式为 $k\cdot n-(k\cdot (2\cdot k+5)\cdot (k-1)\mathrm{/}6)k\; \backslash cdot\; n\; -\; (k\; \backslash cdot\; (2\; \backslash cdot\; k+5)\; \backslash cdot\; (k-1)/6)$，注意要用__int128。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49462912

C. 小䓤的一个数字

Solution

不难发现，每个 1 都能通过他的低位翻转再经操作 2 得到，所以只需要枚举使用 $xx$ 次操作 2，此时每个 1 的花费是 $min\{a_k\},i-x\le k\le imin\; \backslash \{a\_k\backslash \},\; i\; -\; x\; \backslash leq\; k\; \backslash leq\; i$，最后不要忘记加上 $x\cdot bx\; \backslash cdot\; b$。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49461818

D.

Solution

对于最后剩下因子 $p_{i}p\_i$ 的概率是 $probability=\frac{c_i}{{\sum }_{i=1}^n{c}_i}probability\; =\; \backslash frac\{c\_i\}\{\backslash sum\backslash limits\_\{i\; =\; 1\}^n\; c\_i\}$，最后这个因子的贡献是 $probability\cdot p_i^{{\sum }_{i=1}^n{c}_i}probability\; \backslash cdot\; p\_i^\{\backslash sum\backslash limits\_\{i\; =\; 1\}^n\; c\_i\}$，所以直接统计就好啦。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49462556