acm吧 关注：26,506贴子：48,306
- 8回复贴，共1页
剩下的交给qrz吧 F. 平面图求域（最左转边，参考 http://blog.miskcoo.com/2015/05/planar-graph-dual-and-point-locate）之后可以求出对偶图，删去无限域之后会得到一棵树，对区域的染色转化成对树的染色，这实际上就是这个题 http://codeforces.com/contest/321/problem/C，利用树分治递归染色即可，然后对每个区域的权值排序，相当于对 n 个长为 m 的 01 串排字典序，但是总共只有 n+m 个 1，那么只需要把这些 1 的位置抓出来，得到 n 个 vector，sort 一下即可，因为两个 vector 比较大小的代价是两个 size 的较小值，且每个 vector 只会和 log 个 vector 比较大小，所以复杂度是对的
G. 显然 0 不满足要求，考虑计算 [1,n] 中有多少个满足要求的数，注意到 x xor sum 和 x 的大小关系只取决于 sum 的最高位（这一位一定是 1）对应 x 所在位是 0 还是 1，如果是 1 那么 x xor sum < x ，记 sum 的最高位是第 k 位，这说明 x 的十六进制表示中最大的数字是 k，于是枚举 k，dp[i][0/1][0/1] 表示已经填了最高 i 位，是否出现数字 k，是否等于 n 的长为 i 的前缀时的方案数，直接枚举下一个数字转移，单次询问的复杂度是 O(16*(logn)^2)，已经可以通过，但是观察到只有第 k 位限制是 1，也就是从低到高的第 k/4 个数字的第 k%4 位受到限制，在这一位转移时进行枚举，在其他位转移时直接分情况讨论转移即可，这样单次询问的复杂度是 O(16*logn)
