Codeforces 1279A~D 题解
Codeforces 1279A New Year Garland 题解
题意
给定$r,g,b$ ($1\le r,g,b\le10^9$),表示有$r$个字符R
,$g$个字符G
,$b$个字符B
。问可不可能把这些字符排成一行,使得相邻两两字符不相同。
题解
令$r\le g\le b$,肯定要把最大的用完,$b$最大为$r+g+1$。
如果$b>r+g+1$,那么就会出现这种情况BRBGB ... BRBBBB
,不可能完成。
如果$b\le r+g+1$,用完B
后一定能使得$r=g$或$r+1=g$,可行。
程序
1 | // #pragma GCC optimize(2) |
Codeforces 1279B Verse For Santa 题解
题意
给定$n,s$ ($1\le n\le10^5$,$1\le s\le10^9$)和$n$个的数$a_1,a_2,\dots,a_n$ ($1\le n\le10^9$)。你需要从头开始连续地取一些数,使得它们的和小于等于$s$,你可以跳过仅一个数。问你应该跳过那个数,使得你取到的数的数量最多。如果你不需要跳过任何数,输出$0$。
题解
首先,如果$\sum\limits_{i=1}^{n}a_i\le s$,那么答案为$0$。
否则,设$\sum\limits_{i=1}^{k}>s$,那么跳过下标大于$k$的数是无用的。在下标小于等于$k$的数中,贪心地想,最好是跳过最大的那一个,即$\max\limits_{i=1}^{k}a_i$。
程序
1 | // #pragma GCC optimize(2) |
Codeforces 1279C Stack of Presents 题解
题意
给定$n,m$ ($1\le m\le n\le10^5$),$n$个数$a_1,a_2,\dots,a_n$和$m$个数$b_1,b_2,\dots,b_m$ ($1\le a_i,b_i\le n$,$a_i$两两互不相等且$b_i$两两互不相等)。
$a$是一个栈,栈顶是$a_1$,栈底是$a_n$。按输入顺序对于每一个$b_i$,需要从$a$中找到一个数$a_j=b_i$,把$a_j$以上的元素(假设有$k$个)拿出来,把$a_j$扔掉,然后再把那些元素放进去,总共需要$2k+1$秒。当你放进去元素时,你可以按照任意顺序放进去,且不需要时间。
问最少需要多少秒完成。
题解
因为放进去时,可以按照任意顺序,所以如果之前有一步它被放进去了,那么它一定可以作为栈顶取出来。具体操作如下:
预处理数组$p$,使得$p_{a_i}=i$。
假设现在需要计算$b_i$的答案,令$k=\max\limits_{j=1}^{i}p_{b_j}$,$k$的初始值为$-1$。
- 如果$p_{b_i}>k$,只能花费$2\times[p_{b_i}-(i-1)]+1$秒。
- 如果$p_{b_i}\le k$,$b_i$就能被当作栈顶取出来,花费$1$秒。
程序
1 | // #pragma GCC optimize(2) |
Codeforces 1279D Santa’s Bot 题解
题意
给定$n$和$k_i,a_{i,1},a_{i,2},\dots,a_{i,k_i}$ ($1\le n,a_{i,j}\le10^6$)。
有$n$个人,第$i$个人希望得到$k_i$种不同的礼物,分别为$a_{i,1},a_{i,2},\dots,a_{i,k_i}$。
三元组$(x,y,z)$是按照以下方法得到的:
- $x$:从$n$个人中等概率地选一个人。
- $y$:从第$x$个人想要的$k_x$个礼物中等概率地选一个礼物。
- $z$:从$n$个人中等概率地选一个人(与$x,y$独立)。
一个三元组$(x,y,z)$是合法的,当且仅当第$z$个人希望得到第$y$个礼物。
问三元组$(x,y,z)$有多少概率是合法的。
如果答案为$\frac{x}{y}$(最简分数),则输出$x\cdot y^{-1}\mod998244353$ ($y^{-1}$为$y$在模$998244353$意义下的逆元)。
题解
记$cnt(x)$为所有人的愿望单中礼物$x$的数量。
对于合法三元组$(x,y,z)$,选出$x$的概率为$\frac{1}{n}$,从他的愿望单中选出一个礼物$y$的概率为$\frac{1}{k_x}$,选出合法的$z$的概率为$\frac{\sum\limits_{i=1}^{k_x}cnt(a_{x,i})}{n}$,相乘就是$\frac{\sum\limits_{i=1}^{k_x}cnt(a_{x,i})}{n^2\times k_x}$。
再把所有的概率相加得$\frac{1}{n^2}\times\sum\limits_{i=1}^{n}\frac{\sum\limits_{j=1}^{k_i}cnt(a_{i,j})}{k_i}$。
注意乘法逆元。
程序
1 | // #pragma GCC optimize(2) |