NC50617. 取石子游戏
描述
输入描述
第一行为石子的堆数N。
接下来N行，每行一个数，表示每堆石子的个数，接下来一行为每次取石子个数的种类数M。
接下来M行，每行一个数，表示每次可以取的石子个数，
输入保证这M个数按照递增顺序排列。
输出描述
第一行为YES或者NO，表示小H是否有必胜策略。
若结果为YES，则第二行包含两个数，第一个数表示从哪堆石子取，第二个数表示取多少个石子，若有多种答案，取第一个数最小的答案，若仍有多种答案，取第二个数最小的答案。
示例1
输入:
4 7 6 9 3 2 1 2
输出:
YES 1 1
说明:
样例中共有四堆石子，石子个数分别为7,6,9,3，每人每次可以从任何一堆石子中取出1个或者2个石子，小H有必胜策略，事实上只要从第一堆石子中取一个石子即可。Python3 解法, 执行用时: 44ms, 内存消耗: 4732K, 提交时间: 2021-12-15 14:19:31
import sys
a = [0] * 1100
b = [0] * 1100
sg = [0] * 1100
vis = [0] * 1100
n = int(input())
for i in range(n):
a[i] = int(input())
m = int(input())
for i in range(m):
b[i] = int(input())
for i in range(1, 1005): # 暴力sg函数
vis = [0] * 1100
for j in range(m):
if b[j] <= i: # 如果可以取的数量
vis[sg[i - b[j]]] = 1 # 取后的为多少的sg的vis为1
for j in range(1006): # 遍历如果剩下的当中
if vis[j] == 0:
sg[i] = j # 相当于在找最小的没有被遍历到的数
break
ans = 0
for i in range(n):
ans ^= sg[a[i]]
if ans:
print("YES")
for i in range(n):
for j in range(m):
if b[i] <= a[i] and ((ans ^ (sg[a[i]]) ^ (sg[a[i] - b[j]])) == 0):
print("%d %d" % (i + 1, b[j]))
sys.exit(0)
else:
print("NO")
C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 376K, 提交时间: 2020-02-16 17:26:37
#include<bits/stdc++.h>
using namespace std;
int main() {
int N; cin >> N;
vector<int> A(N); for (auto &a: A) cin >> a;
int M; cin >> M;
vector<int> B(M); for (auto &b: B) cin >> b;
vector<int> sg(1024);
for (int i = 0; i < 1024; i++) {
set<int> S;
for (int b: B) if (i - b >= 0) S.insert(sg[i-b]);
while (S.count(sg[i])) sg[i]++;
}
int ans = 0;
for (auto &a: A) ans ^= sg[a];
if (ans == 0) cout << "NO" << endl;
else {
cout << "YES" << endl;
for (int i = 0; i < int(A.size()); i++) {
for (int b: B) {
if (A[i] - b >= 0 && (ans ^ sg[A[i]] ^sg[A[i]-b]) == 0) {
cout << i + 1 << " " << b << endl;
return 0;
}
}
}
}
}
C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 620K, 提交时间: 2020-06-02 20:39:42
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin>>N;
vector<int> A(N);
for(auto &a:A)
cin>>a;
int M;
cin>>M;
vector<int> B(M);
for(auto &b:B)
cin>>b;
vector<int> sg(1024);
for(int i=0;i<1024;i++)
{
set<int> S;
for(int b:B)
if(i-b>=0)
S.insert(sg[i-b]);
while(S.count(sg[i]))
sg[i]++;
}
int ans=0;
for(auto &a:A)
ans^=sg[a];
if(ans==0)
cout<<"NO"<<endl;
else
{
cout<<"YES"<<endl;
for(int i=0;i<int(A.size());i++)
{
for(int b:B)
{
if(A[i]-b>=0&&(ans^sg[A[i]]^sg[A[i]-b])==0)
{
cout<<i+1<<" "<<b<<endl;
return 0;
}
}
}
}
}