layout: post
title: Codeforces Round 272(Div. 2)
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces
- DP
A - Dreamoon and Stairs (暴力枚举两步的数量)
B - Dreamoon and WiFi (dfs)
思路
因为长度只有十所以直接暴力dfs选择,复杂度(2^{10})
思路
[frac{div(x,b)}{mod(x,b)}=k\ o div(x,b)=k imes mod(x,b)\ o x=k imes mod(x,b) imes b+mod(x,b) \ o x= mod(x,b)(k imes b+1)
]
然后因为(b,)已知(mod(x,b))在(0->b-1)之间 (k)在(1->a)之间
D - Dreamoon and Sets (找规律)
思路
发现需要满足条件需要最近的四个互质的数枚举发现1,2,3,5符合
下一组应该是7,8,9,11,
13,14,15,17
以此类推
E - Dreamoon and String (Dp)
思路
(dp[i][j]表示前i个删除了j个的最优值)
(dp[i][j]=dp[i-1][j] 不删除)
(dp[i][j]=dp[i-1][j-1]删除了自己)
(dp[i][j]=dp[i-ned-lenb][j-ned]删除了一些)