题目大意
桌面上有$n$堆石子，第$i$堆中有$a[i]$个石子，你和你的好朋友准备玩NIM游戏。
你很绅士地让你好朋友先手。但是，为了展示自己的聪明才智，你想确保自己能够胜利。
于是，趁你好朋友不在的时候，你悄悄地从口袋里摸出一些石子，并决定在桌面上若干个石子堆中放入一些新石子，并从若干个石子堆中拿走一些石子（可以取完石子堆，但是不能创造新的石子堆）。
你希望在新的游戏局面中确保自己必胜；同时，为了避免被发现，你对现有局面不能改动过大。因此，我们定义，对取走和放入的每个石子，你需要支付一点代价。
你想知道，要得到一个让自己必胜的游戏局面，最少需要支付多少代价。
题目分析
不是很懂标解的数位dp。
我觉得贪心+搜索非常优秀。
贪心策略是：
从高位到低位考虑，若当前位的异或和为$1$，我需要抹掉一个$1$或者添加一个$1$。
若当前位值为$1$，那么找到一个后面位最小的位置，将其变成$0$的代价最小。
当前位为$0$同理。
正确性是很显然的，因为每一位必须更改。
时间复杂度$O(2^{30})$，剪个枝再特判一下$n=2$即可通过。
其实可以随便构数据卡。
代码
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
| #include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int K=30;
int n,a[18],ans=INT_MAX;
void Dfs(int Now,int sum) {
if(sum>=ans)return;
if(Now<0) {ans=sum;return;}
int sum1=0;
for(int i=1; i<=n; i++)if(a[i]&(1<<Now))sum1++;
if(sum1%2==0) {Dfs(Now-1,sum);return;}
int Min=INT_MAX,Max=INT_MIN,posmin=0,posmax=0;
for(int i=1; i<=n; i++)
if(a[i]&(1<<Now)) {if((a[i]&((1<<(Now+1))-1))<Min)Min=(a[i]&((1<<(Now+1))-1)),posmin=i;}
else {if((a[i]&((1<<(Now+1))-1))>Max)Max=(a[i]&((1<<(Now+1))-1)),posmax=i;}
if(posmax) {
int tmp=a[posmax];
a[posmax]=0;
Dfs(Now-1,sum+(1<<Now)-(tmp&((1<<Now)-1)));
a[posmax]=tmp;
}
if(posmin) {
int tmp=a[posmin];
a[posmin]=(1<<Now)-1;
Dfs(Now-1,sum+(tmp&((1<<(Now+1))-1))-a[posmin]);
a[posmin]=tmp;
}
}
int main() {
int t=Get_Int();
while(t--) {
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
if(n==2) {printf("%d\n",abs(a[1]-a[2]));continue;}
ans=INT_MAX;
Dfs(K-1,0);
printf("%d\n",ans);
}
return 0;
}
|
