CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^
|  +  |  +  |  +  |  +  |  +  |  O  |
rank:394
 
=====ABC=====
  * 题意:过水已摸。

  * 题解:过水已摸。

=====D=====
  * 题意:对于一个字符串$t$，定义数组$b$，$b_i$的值是所有$>t_i$字符串位置到$i$距离之和。现在给出$b$数组和每个字母最多出现次数，要求构造出一个可行的字符串$t$，保证有解。

  * 题解:从$z$考虑到$a$，每次找出空的且$b_i=0$的位置，如果可用字母数$\ge$位置数，则全部填这个字母，然后将所有未填位置减去对应的距离；否则不填字母。继续考虑下一个字母，直到全部填完。

=====E=====
  * 题意:从长度为$n$的字符串中挑出一些字符随意排列后组成一个环形项链，要求旋转$k$次后不变，求项链最长长度。$(1 \le n, k \le 2000)$

  * 题解:显然目标串的循环节长度必是$k$的因数，数据范围很小枚举因数全验证一遍即可。

=====F=====
  * 题意:给出一个长度为$n$的序列，每次可以将一个数字移动到头部或尾部，将序列变为不降的序列，求最少次数。$(1 \le n \le 2 \cdot 10^5)$

  * 题解:<del>打了一万年fhqtreap发现想错了。</del>首先离散化。可以发现对于每个元素最多动一次，因此我们考虑最多可以让哪些元素不动。因为这些元素不动，相当于它们中间的其它元素最后都会被拿出去，这些元素最后会挨到一起，因此所以它们组成的子序列一定要单调不降，而且要形如$1,...,1,2,...2,...$，而且如果$x$不在这个子序列的头和尾，那么必须有全部的$x$。因此我们设$f_{i,0/1/2}$分别表示以$i$结尾此时是子序列**开头/中间/结尾**时最长的子序列，转移时符合上述所说即可。最后答案为$n-最长子序列长度$。
CVBB ACM Team

用户工具

站点工具

页面工具
