Codeforces Round #597(Div.2) 解题报告

比赛通过:ABCD

赛后补题:EF

嘛结果还是掉分了……

比赛页面(1245)

A.Good ol’ Numbers Coloring

题干真长

NOIP2017小凯的疑惑的某一引理,直接看a和b的最小公倍数,over

这个定理名字也挺好玩的…Chicken McNugget Theorem

B.Restricted RPS

不知道这题为什么把一些大佬卡住了

这题就直接先贪心选,然后剩下的空位随便补就行

(我居然一开始把&&写成了&……)

C.Constanze’s Machine

可以看出与斐波那契有关……然后瞎搞一波

Code by ZXyang

D.Shichikuji and Power Grid

Prim+方案输出……裸的

Code by ZXyang

E.Hyakugoku and Ladders

神奇的期望dp……

其实道理很简单,我们倒着dp。首先为了简化,我们把方格图弄成序列,反正路径都是那些。

设dp[i]表示到i的最小期望,然后up[i]表示从某个点爬梯子到i,之后的转移就很简单了,dp[0]就是我们需要的答案。

转移的话,到达i这个点有两种,一种是爬梯子到他,另一种是直接掷骰子到他,于是dp方程就出来了:dp[i]=1+min{dp[i+k],dp[up[i+k]]},其中k表示掷得的点数。

不过对于终点附近那6个格子,由于题干条件,会出现不能走的情况,我们就需要记录一下,再乘以当前的dp[i]就行。

F.Daniel and Spring Cleaning

数位dp…怎么这么多dp呀

随便搞搞就能发现,a+b=a xor b的条件就是a与b二进制的位数相等(或者b的位数小于等于a),并且a与b在相同位上不同时有1,这就转化成了一道组合计数的题目。

然后就数位dp瞎搞了……

 

发表评论