发表于 | 更新于 | 分类于 | 评论数：
牛客OI月赛12-提高组

T1 小w的进制转换

小$w$在将一个$10$进制数转换为二进制数的时候，不小心将“$0$”和“$1$”搞混了，也就是说本来该输出$1$的时候他输出了$0$，本来该输出0的时候他又输出了$1$。而他在输出答案的时候，又将输出的左右顺序搞混了。举个例子：小$w$将$6$转换为二进制，本来$6$的二进制表示为$110$，但是小$w$转换成了$001$，输出时又倒了过来变成$100$。现在假设评测姬中的评测数据是$1,2,3,4,5,6…n$也就是从$1$到$n$，问小$w$能$AC$其中的多少组测试案例？

这个东西是一个很纯的进制题，题目大意就是计数合法的串，满足各位异或1之后调转整个序列使得与原序列相同。也就是让你求“反对称01串”的个数。显然奇数长度的串是不会合法的，那么考虑偶数长度的串，推一推样例可以发现第$N$个符合长度的串就是$N$的二进制接上$N$的反对称串，熟悉位运算的话实际上就是一个模拟题，思维难度不大，就是看你能不能掌握位运算了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define Half (Len >> 1)

using namespace std ;
typedef long long LL ;
const LL MAXN = 110 ;
const LL INF = 0x7fffffff ;
LL T, N, A[MAXN], Len, Old, Ans ;

inline LL Read() {
    LL X = 0, F = 1 ; char ch = getchar() ;
    while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
    while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
    return X * F ;
}

int main() {
	T = Read() ; while (T --) {
		N = Read() ; Old = N ; Len = 0, Ans = 0 ;
		while (Old)  {
			LL X = Old % 2 ;
			if (X == 1) A[++ Len] = 1 ;
			else A[++ Len] = 0 ;
			Old >>= 1 ;
		}
		for (int i = 1 ; i <= Half ; i ++)
			swap(A[i], A[Len - i + 1]) ;
		if (Len & 1)
			for (int i = 1 ; i <= Half ; i ++)
				Ans += 1 << (i - 1) ;
		else {
			for (int i = 1 ; i <= (Half - 1) ; i ++)
				Ans += 1 << i - 1 ;
			for (int i = 2 ; i <= Half ; i ++)
				if (A[i]) Ans += 1 << (Half - i) ;
			Old = 0 ; LL Old2 = 0 ;
			for (int i = 1 ; i <= Half ; i ++)
				Old = (Old << 1) + A[i] ;
			for (int i = Half ; i >= 1 ; i --)
				Old2 = (Old2 << 1) - A[i] + 1 ;
			if ((Old << Half) + Old2 <= N)
				Ans ++ ;
		}
		printf("%lld\n", Ans) ;
	}
	return 0 ;
}

T2 小doge的快乐阳光跑

每次开始阳光跑，会在n个点里随机生成好多点位，并且需要按照点位顺序跑.

当且仅当，阳光跑随机生成的点位序列（注意顺序）是你跑步序列的一个子序列时，你完成阳光跑。

某一个序列的子序列指的是，保留该序列的顺序并删除一些元素或者不进行删除后的结果。

小$doge$是一个乐于助人的好孩子，他常常帮助别人跑步。

这天，小$doge$想要完成自己的阳光跑并且顺便帮助小$w$一起完成即一个人完成两人的任务，并且两个人的任务是独立的，小$doge$有$a$个点位，小$w$有$b$个点位。小$doge$想要最效率的跑法，所以他想知道他最少要跑多远。小$doge$可以选择任何一个点出发。

对于阳光跑的要求，我们如下定义：有$n$个有顺序的点位$a_1到a_n$，想要完成阳光跑，必须按照顺序依次经过每个点位，并且在到达前一个点位后到达下一个点位才有效。

搬过来的题解里面的题意简化：给一张图，求一个权值和路径最小的移动序列，使得移动序列包含两个给定的子序列。（早这样说多好

这题很显然你应该求一个最短路，想用$Floyed$的大可不必了，数据范围对于$A$和$B$来说只有$100$，所以我们可以直接对于每一个$A$和$B$中的点为起点跑一遍$SPFA$，时间上是没有问题的。现在有了$D[i][j]$之后我们就可以进行$Dp$了，设$Dp[i][j][0/1]$，表示当前完成了$A$的第$i$位和$B$的第$j$位，然后$0$为停留在$A$路径上，$1$为停留在$B$路径上。转移方程还是需要推一推的。

1
2
3
4
Dp[i][j][0] = min(Dp[i][j][0], Dp[i - 1][j][0] + D[La[i - 1]][La[i]]) ;
Dp[i][j][0] = min(Dp[i][j][0], Dp[i - 1][j][1] + D[Lb[j]][La[i]]) ;
Dp[i][j][1] = min(Dp[i][j][1], Dp[i][j - 1][1] + D[Lb[j - 1]][Lb[j]]) ;
Dp[i][j][1] = min(Dp[i][j][1], Dp[i][j - 1][0] + D[La[i]][Lb[j]]) ;

看起来非常的整齐（嗯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std ;
typedef long long LL ;
const LL MAXN = 1010 ;
const LL MAXM = 10010 ;
const LL MAXA = 110 ;
const LL INF = 0x7fffffff ;
LL N, M, H[MAXN], Tot, A, B, Dp[MAXA][MAXN][2] ;
LL La[MAXN], Lb[MAXN], D[MAXN][MAXN], Ans = 0 ;
struct Node {
	LL F, T, L, Next ;
}	E[MAXM << 1 << 1] ;
bool Vis[MAXN] ;

inline LL Read() {
    LL X = 0, F = 1 ; char ch = getchar() ;
    while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
    while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
    return X * F ;
}

inline void Add(LL F, LL T, LL L) {
	E[++ Tot].F = F ; E[Tot].T = T ; E[Tot].L = L ;
	E[Tot].Next = H[F] ; H[F] = Tot ;
}

inline void Spfa(LL F) {
	queue <LL> Q ;
	memset(Vis, 0, sizeof (Vis)) ;
	D[F][F] = 0 ; Vis[F] = 1 ; Q.push(F) ;
	while (! Q.empty()) {
		LL Now = Q.front() ; Q.pop() ; Vis[Now] = 0 ;
		for (LL i = H[Now] ; i ; i = E[i].Next)
			if (D[F][E[i].T] > D[F][Now] + E[i].L) {
				D[F][E[i].T] = D[F][Now] + E[i].L ;
				if (! Vis[E[i].T])
					Q.push(E[i].T), Vis[E[i].T] = 1 ;
			}
	}
}

int main() {
	N = Read() ; M = Read() ;
	for (LL i = 1 ; i <= M ; i ++) {
		LL X = Read(), Y = Read(), Z = Read() ;
		Add(X, Y, Z) ; Add(Y, X, Z) ;
	}	
	memset(D, 127, sizeof (D)) ;
	A = Read() ;
	for (LL i = 1 ; i <= A ; i ++)  La[i] = Read(), Spfa(La[i]) ;
	B = Read() ;
	for (LL i = 1 ; i <= B ; i ++)  Lb[i] = Read(), Spfa(Lb[i]) ;
	memset(Dp, 127, sizeof (Dp)) ;
	Dp[0][0][0] = Dp[0][0][1] = 0 ;
	for (LL i = 1 ; i <= N ; i ++) D[0][i] = 0 ;
	for (LL i = 1 ; i <= A ; i ++)	
		Dp[i][0][0] = Dp[i - 1][0][0] + D[La[i - 1]][La[i]] ;
	for (LL i = 1 ; i <= B ; i ++)
		Dp[0][i][1] = Dp[0][i - 1][1] + D[Lb[i - 1]][Lb[i]] ;
	for (LL i = 1 ; i <= A ; i ++)
	for (LL j = 1 ; j <= B ; j ++) {
		Dp[i][j][0] = min(Dp[i][j][0], Dp[i - 1][j][0] + D[La[i - 1]][La[i]]) ;
		Dp[i][j][0] = min(Dp[i][j][0], Dp[i - 1][j][1] + D[Lb[j]][La[i]]) ;
		Dp[i][j][1] = min(Dp[i][j][1], Dp[i][j - 1][1] + D[Lb[j - 1]][Lb[j]]) ;
		Dp[i][j][1] = min(Dp[i][j][1], Dp[i][j - 1][0] + D[La[i]][Lb[j]]) ;
	}
	printf("%lld\n", min(Dp[A][B][0], Dp[A][B][1])) ;
	return 0 ;
}

T3 区间异或和异或区间最大值异或区间最小值

小$w$学会了$RMQ$算法，他现在可以求出一个给定数组某一段子区间的最大值，最小值。在这之前，他也学会了前缀和，并且他知道前缀和可以扩展到位运算求出区间异或和。 现在你给了他一个长度大小为$n$的数组，为了考察小$w$写$RMQ$以及前缀异或和的正确性，你要求他求出该数组的某一个子区间，记该子区间的异或和为$xorsum$，记该子区间的最大值为$max$，记该子区间的最小值为$min$，你要求使得$xorsum⊕max⊕min$最大。其中$⊕$为位运算异或操作。

看起来就是一道很毒瘤的数据结构题，（从题目名字就看得出来好嘛

先考虑考虑部分分吧。首先我们得知道一个原理$A⊕B⊕B =A$，相当于一个数两次异或另一个数答案是不变的。那么对于答案所求就是去掉最大值和最小值之后的区间异或和。对于区间最大值和区间最小值我们可以使用$RMQ$进行维护，对于$Sumxor$我们可以使用前缀和进行维护，于是对于确定区间的求值就只$O(1)$的，我们枚举区间的左右端点，时间复杂度就是$O(N^2)$的。

但是出题人十分毒瘤，导致$O(N^2)$只能过$30\%$的点，这就有些不良心了。。

接下来想正解，发现这个序列实际上是可以用分治瞎搞进行维护的，对于该区间取中点$Mid$，然后考虑从左端点在$Mid$左侧，右端点在$Mid$右侧的所有子区间，它们有一个共性就是一定是由一个从$Mid$开始往左延伸的区间和从$Mid$开始往右延伸的区间拼接得到的（意会），对于这两个区间我们需要找到一个支持快速插入以及查询的数据结构来进行维护从$Mid$向左延伸的区间的贡献，之后再遍历往右的区间。

这样我们就处理完了所有左端点在$Mid$左侧，右端点在$Mid$右侧的子区间，那么之后直接递归计算$[L, Mid]和[Mid +1, R]$就可以了。

回想这个数据结构，我们发现字典树可以较好地解决这个问题，我们只需要将异或和放入字典树中，然后分类讨论：

  1. 左侧区间提供最大值最小值
  2. 右侧区间提供最大值最小值
  3. 左侧区间提供最大值，右侧区间提供最小值
  4. 左侧区间提供最小值，右侧区间提供最大值

并且，由于显而易见的是随着区间延伸最大值单调不减，最小值单调不升，所以我们枚举极值的时候有一个双单调性，因此可以考虑尺取法，之中对于以上四种情况分类讨论即可。

思维难度颇大，鄙人在考场上大致也只能想出来$O(N^2)$暴力做法。（没准还可以水一水特殊数据点？

本文标题:

文章作者:Sue Shallow

发布时间:2019年09月27日 - 21:30:00

最后更新:2019年11月11日 - 19:52:34

原始链接:http://Yeasion.github.io/2019/09/27/Contest Nowcoder1090 - TG Months 12/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。