|
给
n
n
n个非负数，两个人轮流玩游戏，如果玩家擦出一个数后，剩下的数字异或为0，则该玩家输，也就是说当前玩家黑板上的数字异或为0，则该玩家赢，比如1，2，3，先手赢。
1
≤
n
≤
1
0
6
1 \leq n \leq 10^6
1≤n≤106
题解
注意到：一个玩家面临的初始数字个数是奇数（偶数）个的话，那么一直到游戏结束，他面临的数字个数仍然是奇数（偶数）个。 故从奇偶性角度考虑。假设先手面临的数字是偶数个，记
a
1
⊕
a
2
⊕
?
⊕
a
n
=
S
a_1 \oplus a_2 \oplus \cdots \oplus a_n = S
a1?⊕a2?⊕?⊕an?=S；如果
S
=
0
S = 0
S=0，先手赢；如果
S
≠
0
S \neq 0
S?=0，考虑先手在什么情况下必输？只有当任意擦除一个数后，剩下的数字异或为0，即擦除任意一个数
a
i
a_i
ai?，都有：
a
1
⊕
a
2
⊕
?
⊕
a
i
?
1
⊕
a
i
+
1
?
⊕
a
n
=
0
a_1 \oplus a_2 \oplus \cdots \oplus a_{i - 1} \oplus a_{i + 1} \cdots \oplus a_n = 0
a1?⊕a2?⊕?⊕ai?1?⊕ai+1??⊕an?=0用
S
S
S表示：
S
⊕
a
i
=
0
S \oplus a_i = 0
S⊕ai?=0。进一步有：
(
S
⊕
a
1
)
⊕
(
S
⊕
a
2
)
⊕
(
S
⊕
a
3
)
?
⊕
(
S
⊕
a
n
)
=
0
(1)
(S \oplus a_1) \oplus (S \oplus a_2) \oplus (S \oplus a_3) \cdots \oplus (S \oplus a_n) = 0 \tag{1}
(S⊕a1?)⊕(S⊕a2?)⊕(S⊕a3?)?⊕(S⊕an?)=0(1)而
(
S
⊕
a
1
)
⊕
(
S
⊕
a
2
)
⊕
(
S
⊕
a
3
)
?
⊕
(
S
⊕
a
n
)
=
(
S
⊕
S
⊕
?
⊕
S
)
⊕
(
a
1
⊕
a
2
⊕
?
⊕
a
n
)
=
S
(2)
(S \oplus a_1) \oplus (S \oplus a_2) \oplus (S \oplus a_3) \cdots \oplus (S \oplus a_n) = (S \oplus S \oplus \cdots \oplus S) \oplus (a_1 \oplus a_2 \oplus \cdots \oplus a_n) = S \tag{2}
(S⊕a1?)⊕(S⊕a2?)⊕(S⊕a3?)?⊕(S⊕an?)=(S⊕S⊕?⊕S)⊕(a1?⊕a2?⊕?⊕an?)=S(2) 结合(1)，(2)，有：
S
=
0
S = 0
S=0 这与
S
≠
0
S \neq 0
S?=0矛盾，故任意擦除一个数后，剩下的数字异或为0不成立，即先手面临的数字个数是偶数个时，总能找到一个数，擦除后其异或不为0。综上所述：
-
a
1
⊕
a
2
⊕
?
⊕
a
n
=
0
a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0
a1?⊕a2?⊕?⊕an?=0，先手必胜
-
n
n
n 为偶数，先手必胜
一辆车初始位置为
0
0
0，初始速度为
1
1
1，有两种指令：
- 指令
A
A
A，
p
o
s
=
p
o
s
+
s
p
e
e
d
pos = pos + speed
pos=pos+speed，
s
p
e
e
d
=
s
p
e
e
d
?
2
speed = speed * 2
speed=speed?2
- 指令
R
R
R，
p
o
s
=
p
o
s
pos = pos
pos=pos，
s
p
e
e
d
=
(
s
p
e
e
d
>
0
?
?
1
:
1
)
speed = (speed > 0 \quad ? -1 : 1)
speed=(speed>0??1:1)
给出目标地址
t
a
r
g
e
t
target
target，问到达该位置的最短指令长度？
1
≤
t
a
r
g
e
t
≤
1
0
5
1 \leq target \leq 10^5
1≤target≤105
题解
如果
t
a
r
g
e
t
=
2
k
?
1
target = 2^k - 1
target=2k?1，则最短指令长度为
k
k
k；如果不等则必然存在一个
k
k
k使得：
2
k
?
1
?
1
<
t
a
r
g
e
t
<
2
k
?
1
2 ^ {k - 1} - 1 < target < 2^k - 1
2k?1?1<target<2k?1。令
d
p
[
i
]
dp[i]
dp[i]表示从0走到
i
i
i 的最短指令长度。分为两种情况讨论：
- 一直用
A
A
A指令走到
2
k
?
1
2^k - 1
2k?1处再掉头（使用
R
R
R指令），即
d
p
[
i
]
=
m
i
n
(
d
p
[
i
]
,
k
+
1
+
d
p
[
2
k
?
1
?
i
]
)
dp[i] = min(dp[i], k + 1 + dp[2^k - 1 - i])
dp[i]=min(dp[i],k+1+dp[2k?1?i])；
- 一直用
A
A
A指令走到
2
k
?
1
?
1
2^{k - 1} - 1
2k?1?1处再掉头（使用
R
R
R指令），使用
b
a
c
k
back
back个
A
A
A指令后，再掉头（使用
R
R
R指令）向前走，即
d
p
[
i
]
=
m
i
n
(
d
p
[
i
]
,
(
k
?
1
)
+
1
+
b
a
c
k
+
1
+
d
p
[
i
?
(
2
k
?
1
?
1
)
+
(
2
b
a
c
k
?
1
)
]
)
dp[i] = min(dp[i], (k - 1) + 1 + back + 1 + dp[i - (2^{k - 1} - 1) + (2^{back} - 1)])
dp[i]=min(dp[i],(k?1)+1+back+1+dp[i?(2k?1?1)+(2back?1)])；
第二种情况需要枚举后退时使用了几个
A
A
A指令。
为什么可以复用之前的
d
p
[
]
dp[]
dp[]呢？因为每次使用
R
R
R指令后相当于初始状态
|