ACM-ICPC 2018 徐州赛区网络预赛 B BE, GE or NE 【模拟+博弈】
2024-09-03 22:31:13
题目：戳这里
题意：A和B博弈，三种操作分别是x:加a，y:减b，z:取相反数。当x或y或z为0，说明该操作不可取，数据保证至少有一个操作可取，给定一个区间（l,k)和原始数字m，如果A和B在n次操作以后使m小于等于l，则B赢，大于等于k则A赢。如果A或B实在赢不了，就会尽量让对方也没法赢。
解题思路：因为数据范围始终在[-100,100]，我们就有了逆推的想法。思路是假如n=3且A必赢。因为我们假设的是A必赢，那么第三步之后的m一定在nu3:[k,100]之间，又因为第三步是A的操作，A肯定是哪步操作可以赢，就使用哪步操作，所以第三步以前的范围nu2是根据第三步以后的范围nu3：[k,100]对所有操作逆推出来的集合求并。据此从nu3逆推出nu2。
第三步之间就是第二步，第二步是B的操作，B如果有任何机会肯定是不会让A赢的，所以第二步之前的范围nu1是第二步以后nu2对所有操作逆推出来的集合求交。
nu1同nu3的推法。
第二种情况就是B必赢。也是和上面的思路一样推，如果A必赢和B必赢都无法满足，那一定是在(l,k)之间了。
看代码更好理解。
附ac代码：
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn = 1e3 + 10;
4 typedef long long ll;
5 int nu[maxn][11];
6 int ans[2][555];
7 int main()
8 {
9 int n, now ,l ,k;
10 scanf("%d %d %d %d", &n, &now, &k, &l);
11 for(int i = 1; i <= n; ++i)
12 {
13 scanf("%d %d %d", &nu[i][1], &nu[i][2], &nu[i][3]);
14 }
15 //B win
16 for(int j = -100; j <= 100; ++j)
17 {
18 if(j <= l)
19 ans[n & 1][j + 200] = 1;
20 else
21 ans[n & 1][j + 200] = 0;
22 }
23 for(int i = n; i >= 1; --i)
24 {
25 memset(ans[(i&1)^1], 0, sizeof(ans[(i&1)^1]));
26 for(int j = -100; j <= 100; ++j)
27 {
28 if(i&1)
29 {
30 int flag = 0;
31 if(nu[i][1])
32 {
33 int u = min(j + nu[i][1], 100);
34 if(!ans[i&1][u + 200]) flag++;
35 }
36 if(nu[i][2])
37 {
38 int u = max(j - nu[i][2], -100);
39 if(!ans[i&1][u + 200]) flag++;
40 }
41 if(nu[i][3])
42 {
43 int u = j * -1;
44 if(!ans[i&1][u + 200]) flag++;
45 }
46 // printf("%d %d %d %d\n", i, j, flag, ans[i&1][j + 200]);
47 if(!flag) ans[(i&1) ^ 1][j + 200] = 1;
48 }
49 else
50 {
51 int flag = 0, v = 0;
52 if(nu[i][1])
53 {
54 ++v;
55 int u = min(j + nu[i][1], 100);
56 if(!ans[i&1][u + 200]) flag++;
57 }
58 if(nu[i][2])
59 {
60 ++v;
61 int u = max(j - nu[i][2], -100);
62 if(!ans[i&1][u + 200]) flag++;
63 }
64 if(nu[i][3])
65 {
66 ++v;
67 int u = j * -1;
68 if(!ans[i&1][u + 200]) flag++;
69
70 }
71 // printf("%d %d %d u %d\n", i, j, flag == v, l);
72 if(flag != v) ans[(i&1) ^ 1][j + 200] = 1;
73
74 }
75 }
76 }
77 int bwin = 0;
78 for(int i = -100; i <= 100; ++i)
79 {
80 // printf("%d %d\n", i, ans[0][i + 200]);
81 if(ans[0][i + 200] && i == now)
82 {
83 ++bwin;
84 break;
85 }
86 }
87 for(int i = -100; i <= 100; ++i)
88 {
89 if(i >= k)
90 ans[n & 1][i + 200] = 1;
91 else
92 ans[n & 1][i + 200] = 0;
93 }
94
95 for(int i = n; i >= 1; --i)//a win
96 {
97 memset(ans[(i&1)^1], 0, sizeof(ans[(i&1)^1]));
98 for(int j = -100; j <= 100; ++j)
99 {
100 if(i & 1)
101 {
102 int flag = 0 ,v = 0;
103 if(nu[i][1])
104 {
105 ++v;
106 int u = min(j + nu[i][1], 100);
107 if(!ans[i&1][u + 200]) flag++;
108 }
109 if(nu[i][2])
110 {
111 ++v;
112 int u = max(j - nu[i][2], -100);
113 if(!ans[i&1][u + 200]) flag++;
114 }
115 if(nu[i][3])
116 {
117 ++v;
118 int u = j * -1;
119 if(!ans[i&1][u + 200]) flag++;
120 }
121 // printf("%d %d %d v %d\n", i, j, flag == v, ans[i&1][j + 200]);
122 if(flag != v) ans[(i&1) ^ 1][j + 200] = 1;
123 }
124 else
125 {
126 int flag = 0;
127 if(nu[i][1])
128 {
129 int u = min(j + nu[i][1], 100);
130 if(!ans[i&1][u + 200]) flag++;
131 }
132 if(nu[i][2])
133 {
134 int u = max(j - nu[i][2], -100);
135 if(!ans[i&1][u + 200]) flag++;
136 }
137 if(nu[i][3])
138 {
139 int u = j * -1;
140 if(!ans[i&1][u + 200]) flag++;
141 }
142 // printf("%d %d %d %d\n", i, j, flag, ans[i&1][j + 200]);
143 if(!flag) ans[(i&1) ^ 1][j + 200] = 1;
144 }
145 }
146 }
147 int awin = 0;
148 for(int i = -100; i <= 100; ++i)
149 {
150 if(ans[0][i + 200] && i == now)
151 {
152 ++awin;
153 break;
154 }
155 }
156 //printf("%d %d\n", awin, bwin);
157 if(!awin && !bwin) puts("Normal Ending");
158 if(awin) puts("Good Ending");
159 if(bwin) puts("Bad Ending");
160 return 0;
161 }
最新文章
- linux中通配符和常用特殊符号
- Time crumbles things; everything grows old under the power of Time and is forgotten through the lapse of Time
- 9、FTP封杀用户、限制传输速率、限制访问目录、为匿名用户提供下载资源
- mnsday1t1
- ASP.NET Page对象各事件执行顺序（转）
- 判断DataSet是否有数据
- Java基础——字符串构建器
- 关于国际化时报org.springframework.context.NoSuchMessageException错，具体到No message found under code '你的键名' for locale 'zh_CN'.的解决方案
- spring cloud 入门系列六：使用Zuul 实现API网关服务
- 中科曙光I620-G15服务器登录密码破解
- Image Widget 的几种加入形式
- Spring Boot到底是怎么运行的，你知道吗？
- 一个AI产品经理怎么看AI的发展
- [LeetCode] 607. Sales Person_Easy tag: SQL
- mysql索引注意事项
- Linux ftp软件安装、配置和启动
- SqlServer 自动化分区方案
- Python——eventlet.hubs
- 使用Ant搭建Android开发环境入门
- ecstore关于smarty语法调用