Codeforces Round #427 (Div. 2)

acm 2017年7月 codeforces

---

入口：Codeforces Round #427 (Div. 2)

rank	ac/all	A	B	C	D	E	F
158	4/6	O	O	O	O	.	.

.	尚未通过	O	当场通过	Ø	赛后通过

---

A. Key races

---

• 比较$vs+2t$的大小即可。
  
  
  

B. The number on the board

---

• 考虑若当前已经满足$sum \geq k$，则$init=n$
• 否则，则尽量取数字小的，变成9,直到满足题意。
  
  
  

C. Star sky

---

• 注意到$1 \leq c \leq 10$
• 所以我们可以预处理出所有情况（0~c）的矩阵，求一个前缀和
• 询问的时候直接，$t=t\%(c+1)$，然后取对应的矩阵运算即可。

D. Palindromic characteristics

---

• 首先由题意可以想到，如果子串$[i, j]$是一个$k$重回文串，那么他肯定也是一个$k-1$重回文，...，1重回文
• 考虑 $dp[i][j]$：表示区间$[i, j]$的子串最大可以为$dp[i][j]$重回文
• 转移：

$$dp[i][j]= \begin{cases} dp[i][mid]+1 \qquad &\mbox{当 $[i,j]$ 是回文，且 $[i,mid],[mid+1,j]$ 是回文}\\ 1 \qquad &\mbox{当 $[i,j]$ 是回文，且 $[i,mid],[mid+1,j]$ 不是回文}\\ 0 \qquad &\mbox{当 $[i,j]$ 不是回文} \end{cases}$$