天津大学生专业做网站,网络架构和现实架构的差异,代码素材网站哪个好,wordpress充值金币P2148 [SDOI2009]ED
题意#xff1a;
有2n堆石子#xff0c;第2k-1堆和第2k堆是一组#xff0c;现在两个人轮流操作#xff0c;每次操作任选一组石子#xff0c;然后将改组中的一堆石子移走#xff0c;将另一堆式子分割成两堆#xff0c;形成新的两堆石子#x…P2148 [SDOI2009]ED
题意
有2n堆石子第2k-1堆和第2k堆是一组现在两个人轮流操作每次操作任选一组石子然后将改组中的一堆石子移走将另一堆式子分割成两堆形成新的两堆石子要求每堆石子数必须大于0谁先不能操作谁输掉游戏
题解
我一开始先打表利用sg的性质打表但是没有发现啥规律然后看了题解题解里都是打表不过人均一眼看出规律。。还是我太菜了
std::mappii, int sg;int calc(pii c) {if (sg.count(c)) return sg[c];std::vectorint s;for(int i1;ic.first-1;i) s.push_back(calc({i, c.first - i}));for(int i1;ic.second-1;i) s.push_back(calc({i, c.second - i}));std::sort(s.begin(), s.end());s.erase(std::unique(s.begin(), s.end()), s.end());int lst -1;for (auto i : s) {if (i ! lst 1) return sg[c] lst 1;lst i;}return sg[c] lst 1;
}
int main()
{//rd_test();pii a{50,50};calc(a);for(int i1;i50;i){for(int j1;j50;j){printf(i%d j%d sg%d\n,i,j,sg[{i,j}]);}}//Time_test();
}
有人将打表结果制图得到 选自博客 然后根据规律得到sg函数
#define c(x, p) (x % p ? x % p : p) // 0 % p p
int sg(ui x, ui y) {for (ui i 0, p 2; i 31; i, p * 2) {if ((c(x, p) p / 2) (c(y, p) p / 2)) return i;}return 31;
}额我是没发现。。后来一艘发现这个图的样子有学名阿达马矩阵 对于某一个矩阵H[t]递归定义为 H[1] [1] H[t] [0] H[t-1] H[t-1] H[t-1]
还有一个结论 f(x):表示x的二进制末尾首个0的出现位置(下标从0开始)比如f(5)f(101)2f(101)_{2}f(101)21 sg(x,y)为一组分别有x1y1个石子的sg值 SzS_{z}Sz表示满足xy1z的sg(x,y)构成的自然数几集合 根据sg性质可知 sg(x,y)mex(SxS_{x}SxUSyS_{y}Sy) 结论 SzS_{z}Sz等同于 z 二进制下 1 的位置集合。例如 S5S_{5}S5 {0,2} sgx,yf(x|y),例如sg(1,4)f(5)1 证明 具体证明
代码
// Problem: P2148 [SDOI2009]ED
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2148
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Data:2021-08-13 20:35:05
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
template typename T inline void read(T x)
{T f 1;x 0;char ch getchar();while (0 isdigit(ch)) {if (ch -)f -1;ch getchar();}while (0 ! isdigit(ch))x (x 1) (x 3) ch - 0, ch getchar();x* f;
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
#define c(x, p) (x % p ? x % p : p) // 0 % p p
int sg(int x, int y)
{for (int i 0, p 2; i 31; i, p* 2) {if ((c(x, p) p / 2) (c(y, p) p / 2))return i;}return 31;
}
int main()
{//rd_test();int t;cin t;while (t--) {ll sum 0;int n;cin n;for (int i 1; i n; i 2) {int x, y;cin x y;sum^ sg(x, y);}if (sum)puts(YES);elseputs(NO);}return 0;//Time_test();
}
