ARC058 简要题解
A
暴力枚举然后 Check 一下
B
设左上角的点坐标为 ((1, H)) , 右下角的点坐标为 ((W, 1))
补集转化之后就只用求必须经过左下角那个矩形的方案数了
考虑无论怎么走必须要从矩形右边的那一条((B, A)-(B,1))线段经过
枚举一下最后经过的哪个点即可
C
妙
补集转化之后求不存在满足题意条件的方案数
看到数据范围容易想到状压, 但是由于限制的条件是和, 并且一个合法的 X, Y, Z 的起点可以是另一个合法的 X, Y, Z 中的点
没办法写
考虑将一个数 (x) 状压成 ((1 << (x - 1))) , 即最后一个选的是 (5) 就压成 (10000) , 是 (5, 3) 就压成 (10000100)
发现 X, Y, Z 和只有 17, 显然跑得过, 然后设 (f[i][S]) 为前 (i) 个数, 后面几个数选的集合为 (S) , 发现一段后缀和要为 (k) 当且仅当在 (S) 中从右往左数第 (k) 位要是 1
随便整整就行
D
待填坑
嘿嘿嘿