codeforces round #607 题解

A. Suffix Three

直接判断最后一个字母

B. Azamon Web Services

直接构造出第一个字符串所能得到的字典序最大串。
方法:复制一个排个序,找到第一个和原串不相符的字符,把这两个字符交换一下。
例如原串是ABCACAB,排序后是AAABBCC,最优的选择一定是找原串里最后出现的A替换,得到AACACBB。

C. Cut and Paste

只要得到前x个序列就可以推出之后的长度,之后用dp得到最终结果。
TLE了好几次,最后发现是乘法和取模运算常数太大被卡了

D. Beingawesomeism

想象一种极端情况:全图只有一个A宗教,很显然最多只需要4步就可以了。
例如
PPPPP     PAPPP     AAPPP     AAPPP     AAAAA
PAPPP     PAPPP     AAPPP     AAPPP     AAAAA
PPPPP     PPPPP     PPPPP     AAPPP     AAAAA
所以一共只有0,1,2,3,4和不可能,共六种情况

  • 不可能:全图都是P
  • 0:全图都是A
  • 1:至少有一个边界全都是A
  • 2:有一个角上是A,或者有一个非边界的行/列全是A
  • 3:有一个A在边界上
  • 4:剩余情况

没时间做就没做了= =有空补代码

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注