2016-5-26模拟测试

T1

• description
  问([L,R])中有多少个数满足奇数位的和与偶数位的和的最大公约数(<d),(T)组询问.
  (1 leqslant L leqslant R leqslant 10^{18},T leqslant 1000)
• solution
  显然数位dp，考场上写的是(f(i,j,k))表示已经填了(i)位，剩下的和还需要(j)和(k)，边界是(f(0,0,0) = 1)，算的时候必须枚举(9^2)，算一次的复杂度就是(9^4log{n})始终不知道怎么优化常数。
  结果把状态设为填了(i)位，已经得到的和是(j,k)，这样边界就是(gcd(j,k) leqslant d)，这样就可以把d作为一维状态给记忆化下来，这样第一个(9^2)就不需要了。

T2

• description
  就是一个二分图最大权匹配，特殊之处在于有一列每个点连出去的边的权值都是一样的。
• solution
  实际上，在做匈牙利的时候是有顺序的，会按照你给定的顺序优先匹配，比如这道题就用到了这个性质，但是当时没有认真分析就跳过了。
  这道题也是，将连出去的那一列边按照(权值,字典序)排序后做匈牙利即可。

T3

• description
  一个NPC问题，考搜索剪枝QAQ.