做购物网站建设的公司,广州网站制作公司,黄州网站建设,台州建设公司网站环上的游戏#xff08;cycle#xff09;有一个取数的游戏。初始时#xff0c;给出一个环#xff0c;环上的每条边上都有一个非负整数。这些整数中至少有一个0。然后#xff0c;将一枚硬币放在环上的一个节点上。两个玩家就是以这个放硬币的节点为起点开始这个游戏#xf…环上的游戏cycle有一个取数的游戏。初始时给出一个环环上的每条边上都有一个非负整数。这些整数中至少有一个0。然后将一枚硬币放在环上的一个节点上。两个玩家就是以这个放硬币的节点为起点开始这个游戏两人轮流取数取数的规则如下1选择硬币左边或者右边的一条边并且边上的数非02将这条边上的数减至任意一个非负整数(至少要有所减小)3将硬币移至边的另一端。如果轮到一个玩家走这时硬币左右两边的边上的数值都是0那么这个玩家就输了。如下图描述的是Alice和Bob两人的对弈过程其中黑色节点表示硬币所在节点。结果图(d)中轮到Bob走时硬币两边的边上都是0所以Alcie获胜。 现在你的任务就是根据给出的环、边上的数值以及起点硬币所在位置判断先走方是否有必胜的策略。【输入格式】第一行一个整数NN≤20表示环上的节点数。第二行N个数数值不超过30依次表示N条边上的数值。硬币的起始位置在第一条边与最后一条边之间的节点上。【输出格式】仅一行。若存在必胜策略则输出“YES”否则输出“NO”。【样例】cycle1.in 4 2 5 3 0 cycle1.outYES cycle2.in 3 0 0 0cycle2.outNO 最后取到数的人获胜 解首先根据题意分析可得假使走过一条边那么每次将它一点点减小到0 和一次性将它减小到0是一样的那么不妨每走过一条边就将边上的数值 减为0 数据范围n20 那么我们可以搜索所有的可行路线 相当于剪枝一旦存在先手赢的做法就返回 1 #includeiostream2 #includecstdio3 #includealgorithm4 #includecmath5 #includecstring6 #includestring7 using namespace std;8 int n,a[30];9 int L(int x)
10 {
11 int p(x-1n)%n;
12 if(p0) pn;
13 return p;
14 }
15 int R(int x)
16 {
17 int p(x1n)%n;
18 if(p0) pn;
19 return p;
20 }
21 bool fg;
22 //1 Alice 2 Bob
23 void dfs(int nw,int peo)
24 {
25 // coutuu nw peoendl;
26 if(fg) return;
27 if(a[nw]0 a[L(nw)]0)
28 {
29 if(peo2) fg1;
30 return;
31 }
32 if(a[nw])
33 {
34 int tmpa[nw];a[nw]0;
35 dfs(R(nw),3-peo);
36 a[nw]tmp;
37 }
38 if(a[L(nw)])
39 {
40 int tmpa[L(nw)];a[L(nw)]0;
41 dfs(L(nw),3-peo);
42 a[L(nw)]tmp;
43 }
44 }
45 int main()
46 {
47 freopen(cycle.in,r,stdin);
48 freopen(cycle.out,w,stdout);
49 scanf(%d,n);
50 for(int i1;in;i) scanf(%d,a[i]);
51 dfs(1,1);
52 // for(int i1;in;i)
53 // couti PPP L(i) R(i)endl;
54 if(fg) printf(YES);
55 else printf(NO);
56 return 0;
57 }//数据范围小搜索 代码 转载于:https://www.cnblogs.com/adelalove/p/9096908.html
