【水题合集】6.11考试

果然蒯代码是不好的。。不然可以rk1

1.又见整数拆分

大概想到了正解的思路然而没往下想了

令\(f[i]=min(j|a[j]\equiv i \pmod{a[1]})\)

那么一个数\(x\)能被表示出来当且仅当\(x>=f[x\bmod a[1]]\)

将每个\(x\bmod a[1]\)的值看作一个点,每个数数当作边,那么跑最短路可以求出\(f[i]\)

优化:取最小的\(a\)作为\(a[1]\)可以减少点数,对于所有\(a[i]\equiv k \pmod{a[1]}\)只留最小的减少边数。

2.矩阵

最大全零子矩阵。。

貌似叫悬线法?

3.盾盾的油头

【BZOJ1016】【JSOI2008】最小生成树计数

直接把之前写的代码蒯过来然后xjb改RE了。。

变量取名要谨慎。。不要总是蒯代码

4.铁路

这题我最多会\(O(边数)\)的做法

大概卡卡时就过了?

正解是强力的线段树orz

发个\(O(边数)\)的(在我机子上暴力都能跑过)

说点什么

  Subscribe  
提醒