2016-2017 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 2016)

acm 2017年7月 codeforces 组队训练

---

入口：2016-2017 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 2016)

rank	ac/all	A	B	C	D	E	F	G	H	I	J	K
123/257	7/11	.	Ø	O	Ø	Ø	O	.	Ø	.	.	O

.	尚未通过	O	当场通过	Ø	赛后通过

---

B. Bribing Eve

---

http://blog.csdn.net/dormousenone/article/details/75125621

优先判断 w1=0 和 w2=0 的情况，此处复杂度为 O(N)

[w1, w2] 对结果的影响与 [w1/w2, 1] 等效，故枚举产品 1 能够大于其它产品的 w1w2 的可行区间，求最大区间并的个数即可。

C. Candle Box

---

模拟。

D. Dinner Bet

---

https://www.bbsmax.com/A/l1dyqgndem/

$f[i][j][k]$表示有$i$个仅属于第一个人的数字被选中，$j$个仅属于第二个人的数字被选中，$k$个属于两个人的数字被选中的期望次数。

E. Passwords

---

AC自动机+dp。
$dp[i][j][k]表示当前长度为i，状态为j，且正处于AC自动机上的节点k时的方案数。$
考虑若c为k的下一个节点，且该节点不为end节点，那么这个c节点即可对下一位产生贡献。

$$dp[i + 1][j | state][c] = \sum dp[i][j][k]$$

F. Performance Review

---

按rank值从小到大排序，用线段树维护rank小于当前rank值的作业的和，单点更新，区间查询。

H. Pascal's Hyper-Pyramids

---

https://www.bbsmax.com/A/l1dyqgndem/

等价于找$D$个非负整数$x_1,x_2,...,x_D$，且和为$H-1$，答案为$\frac{(H-1)!}{x_1!x_2!...x_D!}$。

考虑爆搜，加上$x_i\leq x_{i+1}$以及可行性剪枝即可，计算答案可以分解质因数。

其实对于给定的n, D, H，每个num值为：

$$num=C_{x_1}^0C_{x_1+x_2}^{x_2}C_{x_1+x_2+x_3}^{x_3} \cdots C_{x_1+x_2+ \ldots +x_n}^{x_n}, \quad x_1+x_2+ \ldots +x_n=H-1$$
爆搜，加上$x_i\leq x_{i+1}$以及可行性剪枝，直接dfs也是可以做的。

K. Balls and Needles

---

两次的并查集判环。对于投影的判环注意细节。