Educational Codeforces Round 86
A. Road To Zero
Solution
先把两个数减到相同,再一起减到 $0$.
Code
1 |
|
B. Binary Period
Solution
如果 $t$ 中字符全部相同那么输出 $t$ 即可;否则以 $01$ 为循环节输出。
Code
1 |
|
C. Yet Another Counting Problem
Solution
$[1,ab]$ 是一个循环节,可以先预处理出 $f[1\sim ab]$ 存储答案的前缀和,则 $1\sim U$ 的答案就是 $f[ab]\cdot\left\lfloor\frac{U}{ab}\right\rfloor+f[U\mod(ab)]$.
$[L,R]$ 的答案即是 $[1,R]$ 的答案减去 $[1,L-1]$ 的答案。
Code
1 |
|
D. Multiple Testcases
Solution
从大到小贪心放置 $m_i$,每次寻找第一个可放置 $m_i$ 的 testcase,可放置当且仅当这个 testcase 里现有元素个数严格小于 $m_i$ 允许个数。所以我们需要单点修改、查找小于某数的第一个位置,用值域线段树可解决。
Code
1 |
|
E. Placing Rooks
Solution
要使每一个格子都被攻击到,有两种情况——每一行都有且仅有一个车,或者每一列都有且仅有一个车。
只考虑每一行都有且仅有一个车的情形:如果我们想要有 $k$ 个车互相攻击,那么我们需要把 $n$ 个车放在 $n-k$ 列中——因为每把一个车放到非空的列上时,能互相攻击的车数加一。所以问题变成了把 $n$ 个车放到 $c$ 列中且每列不空的方案数。这可以容斥:总数是 $c^n$,即每个车都有 $c$ 中选择,减去有空列的方案数——至少有一个空列的方案数为 $C_c^1(c-1)^n$,至少有两个空列的方案数为 $C_c^2(c-2)^n$,……,因此答案是 $\sum\limits_{i=0}^c(-1)^iC_c^i(c-i)^n$. 乘上 $C_n^c$,即选择哪些列放车,就是每一行有且只有一个车的情形的答案。
如果 $k=0$,那么每一行有且仅有一个车和每一列有且仅有一个车情形重合;否则,答案再乘上 $2$.
Code
1 |
|
Educational Codeforces Round 86
http://xyfjason.github.io/blog-xcpc/2020/04/27/Educational-Codeforces-Round-86/