NOIP集训-11.4总结

考试的时候..调了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
大水题..
交换行或列,只需要交换其指针..
------------------------------------------------------------------------------------------