sg函数的简单入门

博弈论之sg函数

前言

最近打atcoder的abc368的F题（如下图），完全就是一个裸的sg函数博弈论的知识，这一块要是学过相关内容的同学应该能够速通这个题目

相关知识点总结图

推荐大家看一下董晓算法的讲解

此题AC代码

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <functional>
#include <stack>
#define x first
#define y secondusing namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int N = 1e5 + 10;int main() {int n;cin >> n;vector<int> a(n);for(int i = 0; i < n; i ++ ) {cin >> a[i];}vector<int> sg(N, 0);vector<set<int>> S(N);for(int i = 1; i < N; i ++ ) {for(int j = 0; j < N; j ++ ) {if(S[i].count(j)) sg[i] ++ ;else {break;}}for(int j = i + i; j < N; j += i) {S[j].insert(sg[i]);}}int res = 0;for(int i = 0; i < n; i ++ ) {res ^= sg[a[i]];}if(res == 0) {cout << "Bruno" << endl;}else cout << "Anna" << endl;return 0;
}

更多sg函数模版题

1. Nim游戏
2. 台阶-Nim游戏
3. 集合-Nim游戏