# Codeforces Round 927 (Div. 3)
<https://codeforces.com/contest/1932>
# A
遍历，连续两个荆棘出现之前的所有金币都会吃到
----------------------
# B
比last大的最小的k的倍数为：$(\lfloor last/k\rfloor+1)\cdot k$
----------------------
# C
步骤如下：
- ①统计LR操作分别的数量（LR操作序列要保留），容易知道结束位置的下标恰为L的个数
- ②从结束位置开始，将操作序列反向遍历，把新数字乘进来，根据剩余定理计算每次的余数，得到结果
比如以样例为示范，明显看出将$O(n^2)$优化为了$O(n)$：
```txt
跟操作序列倒着来，依次乘新数来计算：
1 % m => res[3]
1*4 % m = 4*res[3] % m => res[2]
1*4*2 % m = 2*res[2] % m => res[1]
3*1*4*2 % m = 3*res[1] % m => res[0]
直接��拟计算每一步：
3*1*4*2 % m => res[0]
1*4*2 % m => res[1]
1*4 % m => res[2]
1 % m => res[3]
```
-------------------------
# D
本来是在邻接矩阵上对符合约束的不相容卡牌对<先手,后手>做dfs搜索，AC了。
```txt
3C 4C 9S 7S 3S 6D
3C 0 1 1 1 1 0
4C 0 0 1 1 1 0
9S 0 0 0 0 0 0
7S 0 0 1 0 0 0
3S 0 0 1 1 0 0
6D 0 0 1 1 1 0
```
后来看了tourist的解法，才知道比搜索更好的方法是**自定义规则的升序排序后贪心**，类似红心大战的解法：
- ①最小的牌只能作先手牌，
- ②以能beat它的最小的牌作为后手牌，
- ③这样不断配对，没配对的最小的牌都会重复步骤①，直到最后遍历到结尾并查询是否得到了恰好n对（即每张牌恰好使用一次，即问题有解）。
不难推出，这样得到的一定是最优解。复杂度为排序的复杂度。
-------------------------
# E
规律：个位数x要变x次；十位数xy的十位变x次，个位变xy次，总共x+xy次；同理百位数xyz要变x+xy+xyz次……所以求出和就行了。
但是！必须要用大整数加法，手工模拟竖式及进位！
根据上面的规律可以推出竖式解法，以百位数xyz为例，每一位都会对个位贡献一次，即竖式中个位为x+y+z，十位为x+y，百位为x，形式如下��
```txt
x
xy
+ xyz
--------
(result)
```
参考tourist的模板：
```cpp
int n;
cin >> n;
string s;
cin >> s;
reverse(s.begin(), s.end());
vector<int> a(n); // 使用vector由低到高存储每一位
// 本题解法，最高位不变，接下来每低一位，都加之前所有位一次。注意这里不处理进位。
int k = 0;
for (int i = n - 1; i >= 0; i--) {
k += int(s[i] - '0');
a[i] = k;
}
// ----------------------
// 大整数进位处理模板！
// ----------------------
// 从低位到高位传递进位，确保处理过的位为<10的正整数
int carry = 0;
for (int i = 0; i < n; i++) {
a[i] += carry;
carry = a[i] / 10;
a[i] %= 10;
}
// 若传递到最高位后仍需进位，则进到超越位，直至不再进位为止
while (carry > 0) {
a.push_back(carry % 10);
carry /= 10;
}
// 去除前导0
while (a.size() > 1 && a.back() == 0) {
a.pop_back();
}
// 输出
for (int i = a.size() - 1; i >= 0; i--) {
cout << a[i]; // 由高到低输出，由低到高存储（便于处理进位和前导零）
}
cout << '\n';
// ----------------------
```
![]()