一个高级 trick。考虑 \(+1\) 操作，他会把最低连续一段 \(1\) 改成 \(0\)，把原来第一个 \(0\) 改成 \(1\)。注意到此时最低若干位全被覆盖为了 \(0\)，所以可以考虑从高位到低位划分子问题。
具体的，对于第 \(k\) 位，\(+1\) 操作对其有影响，当且仅当这一位原来是 \(1\) 且 \(0\sim k - 1\) 位向该位进了 \(1\)。
当进了 \(1\) 后，此时 \(0\sim k - 1\) 位上全部都是 \(0\)，划分为子问题。
设 \(f_{i, p, q, S}\) 表示考虑了 \(0\sim i - 1\) 位，将 \(st\) 变为 \(ed\) 并且使用的 XOR 操作集合为 \(S\) 的答案，其中若 \(p = 0\) 则 \(st\) 为起始数字，否则 \(st = 0\) 且操作中没有向下一位进 \(1\)；若 \(q = 0\) 则 \(ed\) 为目标数字，否则 \(ed = 0\) 且操作中恰好一次向下一位进了 \(1\)。
转移可以考虑第 \(i - 1\) 位的变化，若 \(q\) 次进位后 \(st\) 和 \(ed\) 在 \(0\sim i - 1\) 位恰好匹配了，那么 \(f_{i, p, q, S} \gets f_{i - 1, p, q, S}\)。
否则 \(0\sim i - 2\) 位可能经过了多次向第 \(i - 1\) 位进 \(1\) 的操作，每进一次 \(0\sim i - 2\) 位都会清零，所以整个转移应为 \(f_{i, p, q, S_1 \oplus S_2 \oplus \dots \oplus S_k} \gets f_{i - 1, p, 1, S_1} + f_{i - 1, 1, 1, S_2} + \dots + f_{i - 1, 1, q, S_k}\)，可以最短路解决，注意判断一下转移路径的合法性。
时间复杂度 \(\mathcal O(2^{2n} \log V)\)。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mkp make_pair
#define pir pair <ll, ll>
#define pb emplace_back
#define i128 __int128
using namespace std;
const ll inf = 1e18, M = 40;
template <class T>
void rd(T &x) {
char ch; ll f = 0;
while(!isdigit(ch = getchar()))
if(ch == '-') f = 1;
x = ch - '0';
while(isdigit(ch = getchar()))
x = (x << 1) + (x << 3) + ch - '0';
if(f) x = -x;
}
ll n, st, ed, w, a[15], b[15], f[41][2][2][1 << 8], dis[1 << 8];
ll _xor[1 << 8], sum[1 << 8], vis[1 << 8];
void chkmin(ll &x, const ll y) { x = x < y? x : y; }
int main() {
rd(n), rd(st), rd(ed), rd(w);
for(ll i = 1; i <= n; i++) rd(a[i]), rd(b[i]);
memset(f, 0x3f, sizeof f);
for(ll S = 0; S < (1 << n); S++) {
for(ll i = 1; i <= n; i++)
if(S & (1 << i - 1))
_xor[S] ^= a[i], sum[S] += b[i];
f[0][0][0][S] = f[0][1][0][S] = sum[S];
f[0][0][1][S] = f[0][1][1][S] = sum[S] + w;
}
for(ll i = 1; i <= M; i++) {
for(ll p = 0; p < 2; p++) {
for(ll S = 0; S < (1 << n); S++) {
if((((p? 0 : st) ^ ed ^ _xor[S]) >> i - 1) & 1 ^ 1)
chkmin(f[i][p][0][S], f[i - 1][p][0][S]);
if((((p? 0 : st) ^ _xor[S]) >> i - 1) & 1)
chkmin(f[i][p][1][S], f[i - 1][p][1][S]);
}
memset(vis, 0, sizeof vis);
for(ll S = 0; S < (1 << n); S++)
if((((p? 0 : st) ^ _xor[S]) >> i - 1) & 1 ^ 1)
dis[S] = f[i - 1][p][1][S];
else dis[S] = inf;
for(ll o = 0; o < (1 << n); o++) {
ll S = -1;
for(ll T = 0; T < (1 << n); T++)
if(!vis[T] && (S == -1
|| dis[S] > dis[T])) S = T;
vis[S] = 1;
for(ll T = 0; T < (1 << n); T++)
if((_xor[T] >> i - 1) & 1)
chkmin(dis[S ^ T], dis[S] + f[i - 1][1][1][T]);
}
for(ll S = 0; S < (1 << n); S++)
for(ll T = 0; T < (1 << n); T++) {
if(((_xor[T] ^ ed) >> i - 1) & 1)
chkmin(f[i][p][0][S ^ T], dis[S] + f[i - 1][1][0][T]);
if((_xor[T] >> i - 1) & 1 ^ 1)
chkmin(f[i][p][1][S ^ T], dis[S] + f[i - 1][1][1][T]);
}
}
} ll ans = inf;
for(ll S = 0; S < (1 << n); S++)
ans = min(ans, f[M][0][0][S]);
if(ans >= inf) ans = -1;
printf("%lld", ans);
return 0;
}