T1

题意：问从1到n有多少个数字在二进制表示下是“反对称01串”，反对称意为对称相反。

10pts

能过样例就是10pts

30pts

写了个大暴力，每次输入n都暴力求

60pts

暴力打了一张1~100000的表，预处理输入直接输出

100pts

显然的是，如果一个数字二进制表示的字符串长度为奇数，一定不符合条件。

我们观察一下前几个符合条件的数字，既然题目与二进制有关，不妨换个视角

10

1010

1100

100110

101010

110100

111000

看出来了嘛？没看出来，没关系，我们把这些数字切一半

1

10

11

100

101

110

111

转换成对应的十进制就是1,2,3,4,5,6,7...

其实很好理解，因为“反对称”嘛就如同回文数一样，前半决定后半。第k个符合条件的数在二进制表示下就是KK'，K表示k的二进制表示字符串,K'为反对称串，可以用位运算O(1)构造。有个这个性质之后，你既可以找规律统计，又可以二分一个最大的k使得KK'小于给定的n，则此时的k就为答案。

std使用的是直接按位构造的方式。

T2

题意：给一张图，求一个权值和路径最小的移动序列，使得移动序列包含两个给定的子序列。

10pts

使用了floyd求最短路emmm....除非n<=300，不然还是别轻易用floyd了。

特殊测试点信息：

对于测试点1,4,5，只要最短路求的是对的即可AC，如果这几个测试点通过而其他WA掉考虑是DP部分写错了。

对于测试点2,3。可以枚举路过序列的全排（dfs一下）瞎搞搞。

对于测试点6,7,10，这三个点的答案大于1e9，请注意是否使用long long或者inf是否足够大。

对于测试点6，是可以枚举一下在哪里拐弯来特判掉的。

100pts

首先肯定要预处理一波最短路，由于图是相对比较稀疏的稀疏图，所以其实spfa或者dij区别不太大（n太小了，故意卡spfa效果并不好）但是注意一下啊，现在spfa人人喊打，尽量少用或者别用。

对于a和b中的点，预处理这些点为起点的最短路。

然后接下来就是一个非常简单的dp，dp[i][j][01]表示已经完成了第一个人的i个点位和第二个人的第j个点位，低三个维度的0表示最后停在了第一个人的点位，1表示最后停在了第二个人的点位。

然后转移方程如下：

dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][0] + dis[a[i]][a[i + 1]]);

dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][1] + dis[b[j]][a[i + 1]]);

dp[i][j + 1][1] = min(dp[i][j + 1][1], dp[i][j][1] + dis[b[j]][b[j + 1]]);

dp[i][j + 1][1] = min(dp[i][j + 1][1], dp[i][j][0] + dis[a[i]][b[j + 1]]);

T3

emmm...首先说一点，WA1的都是存在边界问题的代码。

30pts

按照题目模拟即可，俩for暴力

特殊测试点信息：

对于测试点4，只要有1个1就是1，不然就是0。当然这个后台数据是有1的，所以你可以直接puts("1");

对于测试点5,6，由于数组有序，所以亦或掉的就是两个边界，然后就是一个经典套路01字典树储存前缀亦或，每次查询最大值，当然5,6并没有卡边界，所以没判的话能水水过去。

所以理论上即使本题没有思路，操作好一点的话60pts是可以骗到手的。

100pts

首先想到可以暴力枚举子区间，但是很明显暴力会TLE。

考虑分治枚举子区间，这个套路如果不会的话建议先去学习线段树以及折半搜索(meet in the middle)。

简单介绍一下分治统计子区间的套路：

类似线段树，首先取整个数组的中点mid，我们考虑所有从左侧一直延伸越过mid线的区间。

这些区间有一个共性，就是它们一定是由一个从mid线开始向左延伸的区间与一个从mid先开始向右侧延伸的区间拼接得到。

如果你学过折半搜索，那么你要做的事情就很好解释了，用一个可以快速插入以及查询的数据结构来储存从mid线开始向左延伸的区间信息，然后遍历mid先开始向右侧延伸的区间时从这种数据结构中快速查询筛选到需要的信息进行合并。

做完这两步，你就统计完了当前的[l,r]中所有越过mid线的区间。那么接下来就跟线段树一样继续递归[l,mid],[mid+1,r]咯。

那么本题中使用一个可持久化01字典树或者可插入删除的01字典树，将异或和放入字典树中储存然后分成以下四种情况进行讨论：

1、左侧区间提供最大值最小值。

2、右侧区间提供最大值最小值。

3、左侧区间提供最大值，右侧区间提供最小值。

4、左侧区间提供最小值，右侧区间提供最大值。

由于分治使得区间信息从mid线开始，我们发现从mid线开始往两侧延伸的区间最大值单调递增，区间最小值单调递减。

所以在我们枚举极值的时候呈双单调，一个单调想二分，双单调自然就想到划窗尺取咯。

然后分情况讨论，用双指针划窗尺取即可。

std: