【10.28】【VP】Codeforces Round #742 (Div. 2)

ALL：6
AC：4
补题：1
Rank：375

---

C. Carrying Conundrum

题意：略。见此。

思路：注意到，数字进位其实是奇数位进位，偶数位进位，是各自独立的。考虑单独的奇数位（偶数位同理），其实非负数对的方案个数就是奇数位上的数位组合起来的数字 + 1。例如 $1234$ ，奇数位数位为 $2,4$ ，那么组合方案数为 $(2\cdot 10+4)+1$ 。乘起来减去两个有 $0$ 的方案。

AC代码：https://codeforces.com/contest/1567/submission/178183070

---

D. Expression Evaluation Error

题意：

Bob 在黑板上写下了 $n$ 个十进制正整数，已知它们在十进制下的和为 $s$。Alice 求出了这些数在 $11$ 进制下的和。

请求出任意一组使得 Alice 求得的 $11$ 进制下的和最大的 $n$ 个数。

• $1⩽s⩽10^9$， 1 ⩽ n ⩽ min ⁡ { s , 100 } 1\leqslant n\leqslant \min\{s,100\} 1⩽n⩽min{s,100}。

题解：（VP）Codeforces Round #742 (Div. 2)(A-D)

思路：手玩几组数据，容易知道，分解出来的数字，在 $11$ 进制下进行加法，如果出现了进位，那么转为 $10$ 进制是有损失的，因此分解要尽量避免进位，即比如 $1301$ ，最多拆为 $1000,100,100,100,1$ ，这样是没有损失的，再拆就有损失了。如果要拆，要拆最大的数，而且按照 十分之一去拆，比如 $1000$ 拆为 $100,900$ 。

AC代码：https://codeforces.com/contest/1567/submission/178213177

---

E. Non-Decreasing Dilemma

题意：单点修改，区间查询不降子区间数量。

思路：线段树裸题。

AC代码：https://codeforces.com/contest/1567/submission/178184918