[Codeforces] Mashup 練習 2

2021-03-11

提升一下難度就不會了傷心
都要靠題解的提示了QwQ

1244E - Minimizing Difference

Link
每一步操作可以把一個數字加1或減1，問操作完全距最小是多少。

用map暴搜，
迭代器超難寫:(
AC Code

Link
有一個01字串，
每次可以選一個子序列然後順時針轉一個位置，
問做到對齊的最小次數。

這題我真的想不到:(

官解是證明每次選取010101010…的字串至少會是最佳解，
原題就變成了最大連續和
AC Code

Link
有兩個字串$a$，$b$，問有多少$a$的排列滿足字典序大於$a$小於$b$。
輸出$\mod 10^9 + 7$。

分開作小於$a$，小於$b$再相減，
用DP/排列組合就可以過。

本題時限卡很緊，需要優化。
(建議可以用階乘反元素處理)

Link
有一個空字串A，
依序把原字串S的前面放到A的頭或尾(不需要放完)，
有多少操作順序使得做出來的A有一個前綴是T。
輸出$\mod 998244353$。

令$dp[i][j]$表示已經放了$[0..i]$，開頭在$j$，滿足條件的可能，
每次就只要考慮放前或放後兩種可能就好。