Codeforces Round # 555 (Div3)

2023-11-09 17:31:58

1157A. Reachable Numbers

给一个数n，每次可以给n加1，得到去除末尾0之后的数，输出总共可以到达多少个数。

按题意直接模拟（出题人说最多答案只有91个）。

给一个仅含$1 \sim 9$的数字串，与映射$f(x) = a_x, (1 \leq x,a_x \leq 9)$，可以连续的对这个序列操作任意次，输出可得的最大的序列。

按题意直接模拟，只能更改变大的第一个块。

C1，C2只有构造条件不同。

给$n$个数，每次只能取头尾，构造出一个符合要求的严格递增序列，输出序列长度和每次操作是$L$（从左端取数）或是$R$（从右端取数）。

每次选左端和右端中小的那个数必是最优的。

依旧每次选左端和右端中较小的，当左右相同时，之后都只能选择一个方向的数，因此选择选左端和选右端两中方案中更优的答案。

https://codeforces.com/contest/1157/submission/53429184（我写了个DFS，其实相当于没有，可以看看别人的代码）

给一个数$n$和天数$k$，每天有一个值$a_i$且$a_i \neq 0$，要求$\sum_{i=1}^k a_i = n$。对每天的值，第一天可以是任意的，其后$a_{i-1} \leq a_i \leq 2a_{i-1}, (1 \leq i \leq k)$。

因为第一天可以是任意的，那么$k$天的下限值就等于$1+2+3+...+k$，如果$n$小于下限值一定不能构造，此时的上限值是$2^(k) - 1$。然后第一天的值会影响上限值和下限值，我们只要找到下限值小于$n$，上限值大于$n$的第一天的值，按题意暴力构造即可。

给两个长度为$n$的数字序列$a$和$b$，你可以使用$b$中第$j$位与$a$中第$i$位配对，$a$中该位数字变为$a_i = (a_i + b_j) % n$，$b$中每个数字只能使用一次，输出可得的字典序最小的$a$。

我们只要对$a$中每一位都配上$b$中当前剩下数的求和取模后最小的那个数，使用multiset维护即可。

PS：set和multiset的二分查找请用stl方法 .lower_bound 和 .upper_bound，否则$O(n)$。

给$n$个数，用其中若干个数构成一个序列，要求相邻的数相差不超过1，其中头尾视为相邻。

对原序列排序，然后双指针找出合法的最长的部分，对这部分进行构造，唯一的难度在于找出最长的起尾。

给一个$n \times m$的01矩阵，要求在行列各进行任意次操作后，得到一个非递减矩阵，这个矩阵拉平后是前一部分全0，后面全1的，输出是否可以得到这样的矩阵，行的操作序列，列的操作序列（反转用1表示，否则为0）。

暴力对矩阵的每一个位置枚举，这个位置之前的全为0，其他为1，检测是否可以操作得到这样的非递减矩阵。

（还没有搞皮肤，先黑白过渡一下）