250pt
給一個長度不超過50的01串S,問最少可以分割成多少個由5的冪組成的二進制數。
算法分析:
高精預處理出5的冪的二進制數就是個沙茶動態(tài)規(guī)劃了...
500pt
有一個n*m的01矩陣,支持兩種操作,操作1是選擇1行將其所有的0變成1,1變成0。操作2是選擇1列。
現在整個矩陣都是0,問恰好進行R次操作1和C次操作2以后,恰好有S個1的不同操作有多少種。
不同操作與順序無關。至于某行/列的操作次數有關。
算法分析:
我們先要計算出“有效操作”有多少。因為對一行操作兩次和沒操作沒有區(qū)別...
設有效操作1的次數是r,有效操作2的次數是c,那么一定有r*m+c*n-2*r*c == s
r和c通過枚舉求得,對哪些行/列進行有效操作可以通過組合數來求...
無效操作相當于將b個無差別的球放到a個有差別的格子里,有
f(a,b) = f(a-1,0) + ... + f(a-1,b)
預處理出來就可以了...
明天放代碼,pratice room 開不了題了...