状压好题!!
设 d p [ i ] [ S ] dp[i][S] dp[i][S]表示考虑前 i i i列, S [ j ] = 1 S[j]=1 S[j]=1表示已经钦定了第 j j j行的最大值,已经钦定的最大值之和最大
复杂度 O ( n m 3 n ) O(nm3^n) O(nm3n)显然 t l e tle tle飞了。
那么按每一列的最大值排序,注意到只有前 n n n列会对答案产生贡献。
于是优化到 O ( n 2 3 n ) O(n^23^n) O(n23n) 。
但是枚举子集太慢了。考虑对于一种循环,往集合里面一个一个塞数,用临时数组存一下然后贡献到答案里。
复杂度 O ( n 3 2 n ) O(n^32^n) O(n32n)。可以通过。
tips:小心数据范围诈骗。
仔细想一下发现是套路题
从高到低位处理答案,预处理一下 S S S超集的最大,次大位置即可
复杂度 O ( ( n + a ) log a ) O((n+a)\log a) O((n+a)loga)
烦死了烦死了
设 d p [ S ] [ u ] dp[S][u] dp[S][u]表示以 u u u为根的方案数, S S S是一个二进制状态
转移为 d p [ S ] [ u ] = ∑ d p [ S ⊕ S 2 ] [ u ] × d p [ S 2 ] [ v ] dp[S][u]=\sum dp[S\oplus S2][u]\times dp[S2][v] dp[S][u]=∑dp[S⊕S2][u]×dp[S2][v]
为了避免算重我们强制 S 2 S2 S2包含特殊点 p p p时才能转移
考虑限制条件。事实上我们只关心 L C A LCA LCA在子树内以及边在子树内的情况。
对于 L C A LCA LCA:
1.1
1.1
1.1对于限制
(
a
,
b
,
c
)
(a,b,c)
(a,b,c),如果
c
=
u
c=u
c=u,但是
a
,
b
∈
S
2
a,b\in S2
a,b∈S2 那么
L
C
A
(
a
,
b
)
≠
c
LCA(a,b)\ne c
LCA(a,b)=c
1.2
1.2
1.2对于限制
(
a
,
b
,
c
)
(a,b,c)
(a,b,c),如果
c
∈
S
2
c\in S2
c∈S2,但是
a
∉
S
2
a\notin S2
a∈/S2或者
b
∉
S
2
b\notin S2
b∈/S2那么
L
C
A
(
a
,
b
)
≠
c
LCA(a,b)\ne c
LCA(a,b)=c
对于边:
1.1
1.1
1.1对于边
(
x
,
y
)
(x,y)
(x,y),如果
x
∈
S
2
x\in S2
x∈S2并且
y
∈
S
−
u
y\in S-u
y∈S−u或者反之,那么
(
x
,
y
)
(x,y)
(x,y)不可能在树上
1.2
1.2
1.2如果
u
u
u与
i
i
i有边并且
i
∈
S
2
i\in S2
i∈S2的
i
i
i的个数
≥
2
\ge 2
≥2,那么不可能有满足条件的树
事实上如果满足条件的 i i i的个数等于 1 1 1,那么转移时 S 2 S2 S2的根可以直接求出
复杂度 O ( n q 3 n ) O(nq3^n) O(nq3n)。
事实上可以对 L C A LCA LCA预处理,复杂度 O ( n 3 n + 2 n q ) O(n3^n+2^nq) O(n3n+2nq)。
我是傻逼
key observation : \text{key observation}: key observation:每个点权值为 [ 0 , n − 1 ] [0,n-1] [0,n−1]
把拓扑序拉出来,然后不断对一段后缀 − 1 -1 −1直到不能减为止,然后把后缀最小的那个提到前面来,不难证明每次提到前面来的值小于 n n n。
然后枚举子集把一个集合的点全部设为某一权值来转移,复杂度 O ( n 3 n ) O(n3^n) O(n3n)显然 t l e tle tle飞了。
如果当前点在第 j j j轮加进去的话贡献是 j × v [ i ] j\times v[i] j×v[i]
那么我们将贡献提前计算,复杂度 O ( 3 n ) O(3^n) O(3n)。
我是傻逼
对于炸弹可以看成价值为无穷小的宝藏。
对于每个宝藏引一条射线,如果和封闭路径边界有奇数个交点就证明在封闭路径围成的内部。
考虑状压记录每个宝藏交点个数的奇偶性,以及当前所处的位置,然后跑最短路即可。
然后射线和线段求交点那个地方比较复杂。射线的斜率取一个比较大的随机数,这样就不会穿过整点了。