「JZOJ5053」石子游戏 - 贪心+搜索 / 数位动规 | Bill Yang's Blog

「JZOJ5053」石子游戏 - 贪心+搜索 / 数位动规

题目大意

    桌面上有$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;
}
0%