51nod 1007 正整数分组

想到两组数都接近所有数和的一半的话差是最小的,那么01背包一下就好了。

51nod 1009 数字1的数量

从低位到高低逐位统计对1的贡献。

  • 如果当前位是0, 这一位对答案的贡献和高位相关,比如12034,那么百位上出现1的情况有100~199,1100~1199,2100~2199,…,11100~11199,一共有12*100个。
  • 如果当前位是1,这一位对答案的贡献和高位、低位都相关,比如2134,那么百位上出现1的情况有100~199,1100~1199,2100~2134,一共有2*100+34+1个。
  • 否则,这一位对答案的贡献和高位相关,比如2234,那么百位上出现1的情况有100~199,1100~1199,2100~2199,一有3*100个。

Codeforces Round #450 C.Remove Extra One

大意就是给一个排列,必须要删除一个数,使得这个序列中满足某一条件的数尽可能多,可以删除的数多个的话删最小的那个。
某一条件:$a_i$比它前面所有数都大。
例,5 1 2 3 4, 把5删了 1 2 3 4这个序列的4个数都满足某一条件。
再例,3 2 6 1 4 5 把6删了可以让满足某一条件数最多。
从左到右扫,维护扫到目前为止的最大数和第二大数,枚举删除当前这个数,计算它被移除对结果产生的贡献c[a[i]],

  • 如果这个数是当前最大的那么c[a[i]]–;
  • 如果这个数是当前第二大的,那么c[max]++;

51nod 1522 上下序列

完全没想到是个区间DP。
每次把两个相同的数字填入已有的[l, r]序列中。
因为题意是先增后减的也就是中间比两边大,那么从大到小的把数填进去,同时判断是否满足给出的条件。
从大到小填的好处体现在已填的位置上的数比现在正要填的位置上的数大,那么只要判断当前填的位置的数是否’=’, ‘>=’, ‘>’已填好的位置上的数,而且两个数不可以’<’, ‘>’的条件。
状态表示及转移方程:
dp[i][j]表示[i, j]区间的方案数。
两个数都填左侧,check(i, i + 1, i + 2, j) dp[i][j] += dp[i][j - 2]
两个数都填右侧,check(j - 1, j, i, j - 2) dp[i][j] += dp[i + 2][j]
两个数填两侧,check(i, j, i + 1, j - 1) dp[i][j] += dp[i + 1][j - 1]

51nod 1623 完美消除

先考虑如何计算一个数的最小操作数,只要维护一个栈,每次把比当前栈大的数弹出,如果栈中没有这个数就把操作数+1。
实际上可以用一个int来状压这个栈,然后需要注意的就是初始state = (1 << 0),因为0是不会增加操作数的,剩下就是数位DP的套路了。

hackerrank-sam-and-sub-strings

给一个很长的数字字符串,求这个串所有子串加起来的值。

状态表示: $dp[i]$以i结尾字符串的贡献
转移方程: $dp[i]=dp[i-1] 10+(i+1) s[i]$

HackerRank-Euqal

给一些数字,每次操作可以选一个数不变,其余所有数都加上1、2、5。
要求最少的次数使得所有的数都相同。

逆向想一下,每次操作一个数,让这个数减1、2、5, 最后使得每个数相同。
自然就想到了所有数都减到min{a[i]}
每个数的操作次数是 $k=(x-min)/5+((x-m)\%5)/2+((x-m)\%5)\&1$
答案就是每个数操作次数之和

trick:
但是并不一定是减到min{a[i]}是最优的,也有可能是min{a[i]}-1, min{a[i]}-2, min{a[i]}-3, min{a[i]}-4,但不可能比最小值小5,这说明每个数都需要减一个5。