[学习笔记]Nim游戏 社团招新题 附加题T1 好吧我忘干净了 题目描述 有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动） 思路解析 首先考虑简单情况 只有两堆石头 一堆x 一堆y 记为（x,y） 可以得到二维表格 先确定几条定理： 无法操作 必败 对于无论所有操作都会到达必胜局面的 必败 可以到达必败局面的 必胜 必胜为1 必败为0 如图可知 两堆石子相等时为必败局面 推广到三堆 只要把其中两堆视作一个整体 就变为两堆问题 初步结论 每次操作尽可能使两堆石子数量相等 关于进阶 Nim值：当前规则下的石子数，等效于普通规则下的石子数 Nim值的计算:所有操作能到达局面的从未出现过的最小非负整数 这个我还不会 最终结论 每堆石子的异或和为0则 必败 反之 必胜
[SCOI2012]滑雪 问：景点数最大的同时 滑行总距离最小 景点数最大 即求 最大连通块 滑行总距离最小 即求 最小生成树 对于多条件问题 有限考虑硬性条件（可行性） 再考虑最优性 1.可行性 滑行必须从高到低（相等也可），即更新节点时必然是从高的点更新低的点， 所以选择节点时 优 先 考虑高的节点 结论 对所有节点从高到低排序 2.最优性 与最小生成树同理 优先选择长度最短的边 结论 对所有边从小到大排序 3.坑点 当两个点高度相等是，是双向边 既然是双向边，就要开两倍数组，否则RE 只考虑了最优性而没有考虑可行性 4.代码如下 #include<bits/stdc++.h> using namespace std; #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } const ll N = 1e5+7, M = 2 * 1e6+7, INF = 5e9+9; // 可能存在双向边 ll n,m,h[N]; ll head[N],tot; struct edge { ll ver,dis,nex; }e[M],pe[M]; void add(ll u,ll v,ll w) { e[++tot].nex = head[u]; e[tot].ver = v; e[tot].dis = w; head[u] = tot; } ll phead[N],ptot; void padd(ll u,ll v,ll w) { pe[++ptot].nex = phead[u]; pe[ptot].ver = v; pe[ptot].dis = w; phead[u] = ptot; } bool arr[N]; ll num; void bfs(ll begin) { queue<ll> q; arr[begin] = 1; num++; q.push(begin); while(q.size()) { ll now = q…