NOIP集训-11.4总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
考试的时候..调了2个小时的第二题结果还是没调出来，于是交了个乱搞加暴力，哇，90分
------------------------------------------------------------------------------------------
Number:SuperOjP1002
发现第i个好数的三进制长得和i的二进制是一样的
首先把问题转化为前缀和相减
所以只需要求x之前所有数每一位1的个数，再乘以3的对应次方就好
打表发现每一位1、0是有规律的，根据这个规律就可以求出来了
------------------------------------------------------------------------------------------
DP:SuperOjP1003
数据特水
考虑二分答案DP验证：
首先二分答案得到一个最低高度mid
f[i][s]表示前i个位置的最小费用，s表示这个位置及其之前k-1个位置的选或不选（所有对这个位置有影响的位置）
状态转移:
f[i][s] = min{f[i-1][(s>>1)|(1<<(k-1))] , f[i-1][(s>>1)]} + 第i个位置的费用（如果要选的话）
其中>>表示二进制右移，|表示位或
另外还要验证一下f[i][s]这个状态下第i个位置的高度是否大于等于mid，如果不是的话就把f[i][j]设为+∞
如果存在p使得f[n][p]≤m,就表明高度mid是可行的
------------------------------------------------------------------------------------------
Change:SuperOj1004
大水题..
交换行或列，只需要交换其指针..
------------------------------------------------------------------------------------------
评论 (0)
