HauntedProgrammer's Blog

A said strange person

SRM645 Div1题解

HauntedProgrammer posted @ 2015年4月06日 20:35 in 未分类 with tags TopCoder , 544 阅读

250:

贪心即可。每次找到所有没有被覆盖的区间的右端点的最大值,然后找到所有能够覆盖这个点的区间中右端点最右边的区间,干掉它。

500:

先检查所有点是否有对应位置,算出平移向量,然后判断一个三元一次方程有没有整数解。要做两种情况,分别是正的和负的。

900:

容斥+状压。先枚举st,表示st里的没有访问两次,别的不管。然后用[tex]O(B_{popcount(st)})[/tex]暴力枚举拆分,计算对答案的贡献。首先预处理满足包含[tex]i[/tex]且被[tex]j[/tex]包含的方案数目[tex]pre[i][j][/tex],这一步竟然是[tex]O(4^n)[/tex]的……


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter