南昌市公司网站建设,沈阳市和平区建设局网站,深圳注册公司条件,口碑营销有哪些方式容斥原理、博弈论 容斥原理890. 能被整除的数#xff08;二进制状态压缩版本#xff0c;复杂度多一个Om#xff09;890. 能被整除的数#xff08;dfs版本#xff09; 博弈论无限制nim游戏AcWing 891. Nim游戏AcWing 892. 台阶-Nim游戏#xff08;待补#xff09; 集合版… 容斥原理、博弈论 容斥原理890. 能被整除的数二进制状态压缩版本复杂度多一个Om890. 能被整除的数dfs版本 博弈论无限制nim游戏AcWing 891. Nim游戏AcWing 892. 台阶-Nim游戏待补 集合版本Nim游戏AcWing 893. 集合-Nim游戏AcWing 894. 拆分-Nim游戏待补 容斥原理 容斥原理可以画一个韦恩图来看各个集合的关系
890. 能被整除的数二进制状态压缩版本复杂度多一个Om
#include iostream
#include algorithm
#include cmathusing namespace std;
typedef long long LL;
const int N 17;
int p[N];
void solve()
{int n, m;cin n m;for (int i 0; i m; i) cin p[i];int res 0;for (int i 1; i 1 m; i)//枚举2的n次方-1个集合{int t 1, cnt 0;for (int j 0; j m; j)//判断是否乘上p[j]{if (i j 1){if ((LL)t * p[j] n){t -1;break;}t * p[j];cnt ;}}if (t ! -1){if (cnt 1) res n / t;//奇数就加上偶数就减去else res - n / t;}}cout res;
}
int32_t main()
{ios::sync_with_stdio(0);cin.tie(0);int T 1;//cin T;while (T --) solve();return 0;
}890. 能被整除的数dfs版本
本题本质上就是一个枚举所有答案的过程那么我们当然可以用dfs搜索到所有可能的方案
#include iostream
#include algorithm
#include cmathusing namespace std;
typedef long long LL;
const int N 17;
int p[N];
int n, m;
int res 0;
void dfs(int u, int t, bool add)
{if (u m){if (t 1) return ;else {if (add) res n / t;else res - n / t;return;} }dfs(u 1, t, add);//m个质数中不选择p[i]if ((LL)t * p[u] n)//m个质数中不选择p[i]{dfs(u 1, t * p[u], !add);//本层选了一个数的话下一层枚举的集合的add就要取反因为容斥原理公式就是1个的2个的-3个的每多选一个数字加减号相反}
}
void solve()
{cin n m;for (int i 0; i m; i) cin p[i];dfs(0, 1, false);cout res;
}
int32_t main()
{ios::sync_with_stdio(0);cin.tie(0);int T 1;//cin T;while (T --) solve();return 0;
}博弈论 为什么异或值0先手必败这个我没搞懂我主要是记住这个结论为什么异或值!0先手必胜 因为它可以转化为对手先手必败的状态异或值为0推导如下
无限制nim游戏
AcWing 891. Nim游戏
#include iostream
#include algorithm
#include cmathusing namespace std;
const int N 1e5 10;
int a[N];
void solve()
{int n;cin n;for (int i 0; i n; i) cin a[i];int t 0;//异或运算里面的0相当于加法里面的0乘法里面的1for (int i 0; i n; i) {t ^ a[i];}if (t) cout Yes endl;else cout No endl;
}
int32_t main()
{ios::sync_with_stdio(0);cin.tie(0);int T 1;//cin T;while (T --) solve();return 0;
}AcWing 892. 台阶-Nim游戏待补
集合版本Nim游戏
AcWing 893. 集合-Nim游戏
集合版本Nim游戏的每一步有多种选择但多种选择是被限制在一个选择集合中的而不是随意拿多少个。sg(起点) ! 0说明 我经过若干步一定可以到达 sg 0的点即我还是可以操作的如果sg(起点) 0那我没有任何操作空间直接判负即先手必败。推荐看这个博客
#include iostream
#include algorithm
#include cmath
#include cstring
#include set
using namespace std;
const int N 1e4 10;
int s[N], f[N];//f可以不用但可以起到剪枝的效果
int n, k;int sg(int x)
{if (f[x] ! -1) return f[x];setint S;for (int i 0; i k; i)if(x s[i]) S.insert(sg(x - s[i]));//这里如果不判断xs[i]的话会影响后续路线的赋值//本来下一层应该是12但是因为负数变成了0 1//那么本层本来是0的递归回来的时候现在也会被影响变成了2for (int i 0; i k; i){if (S.count(i) 0) return f[x] i;}
}void solve()
{memset(f, -1, sizeof f);cin k;for (int i 0; i k; i) cin s[i];cin n;int x;int res 0;while(n --){cin x;res ^ sg(x);}if (res) cout Yes endl;else cout No endl; }
int32_t main()
{ios::sync_with_stdio(0);cin.tie(0);int T 1;//cin T;while (T --) solve();return 0;
}AcWing 894. 拆分-Nim游戏待补
