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) |