@[toc]理论知识（1）、若面临末状态者为获胜则末状态为胜态否则末状态为必败态。（2）、一个局面是胜态的充要条件是该局面进行某种决策后会成为必败态。（3）、一个局面是必败态的充要条件是该局面无论进行何种决策均会成为胜态 斐波那契博弈 问题： 有一堆数量为n的石子，游戏双方轮流取石子，满足： （1）先手不能在第一次把所有的石子取完； （2）之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。 约定取走最后一个石子的人为赢家。求必败态 结论 当n为斐波那契数时，先手必败。 证明： 齐肯多夫(zeckendorf)定理：任何正整数都可以表示成若干个...

常见的博弈论有巴什博弈，威佐夫博弈，尼姆博弈，斐波那契博弈等等，今天暂时讲几个@[toc] 一.巴什博弈 巴什博奕：只有一堆n个物品，两个人轮流从中取物，规定每次最少取一个，最多取m个，最后取光者为胜。 证明： 显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们可以推算出：如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数...

比赛链接：@[toc] 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 codeJan 非常喜欢旅行。现在有 n 个城市排在一条线上，并且 codeJan 的位置不和任何一个城市的位置重叠。 codeJan想要游览 m个城市，同时因为时间是不断变化的，游览一个城市多次也是允许的，但是不能永远待在一个城市，否则那样太无聊了。给出这些城市的位置，codeJan想要知道游览 m 个城市至少需要走多少米？ 输入描述: 第一行是一个T≤20代表测试组数。每组第一行是三个正整数n,m,p，分别代...

原题传送器<----点我 题意：n个数字，请你给它们排个序围成一个环，满足任意一个数两边的数之和大于它本身，例如题目给的图（左图为正确答案），如果不存在这样的环就输出NO。难度★ 题解 这题主要靠思路，能想到正确的方法就很easy，码量不多。对于这组数我们可以先排升序，然后取后三位比较（为什么，往下看） ，例如后三位是a[n-2],a[n-1],a[n],然后比较a[n]>a[n-1]+a[n-2]是否成立，如果不成立就说明肯定不能成环，反手就是输出NO；如果成立，先将a[n]和a[n-1]输出，然后除了a[n-2]的其他数直接输出就行，把a[n-2]最后输出；即a[n] a[n...

比赛链接 A L1-1 I LOVE WIT 模拟，每个字母单独一行，前面的空格按规律输出。可以直接输出，也可以模拟过程 #include<bits/stdc++.h> using namespace std; int main(){ string s="I LOVE WIT"; for(int i=0;i<s.size();++i) { for(int j=1;j<=i;++j) { cout<<" "; } cout<<s[i]&l...

链接： 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 给你一个边长为 n 的用硬币摆成的实心三角形，请问把他倒过来最少需要多少步？ 例子：这是一个边长为3的硬币三角形 只要移动边上的两个硬币，就可以把它到过来（注意是倒过来，不是旋转角度），变成这样： 聪明的 Prev1ous秒切了这道题，于是他希望来考考你 Prev1ous 经过计算后发现，由于答案实在是太大了，所以他只关心答案对23333333333333333取膜的结果，顺带一提这是个质数。 输入描述: 多组数据，第一行...

链接：「火」皇家烈焰@[toc] 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 帕秋莉掌握了一种火属性魔法 由于钟爱扫雷游戏，帕秋莉把自己图书馆前的走廊看作一个一维的扫雷地图，她制造了很多烈焰，排在这条走廊内 现在帕秋莉告诉你一部分烈焰的分布情况，请你告诉她可能的情况有多少种 对于一个格子，里面会有以下几种字符： 0：这个格子没有烈焰，且其左右两个格子均没有烈焰 1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰 2：这个格子没有烈焰，且其左右两个格子中均有烈焰 *：这个格子有烈...

链接： 题目描述 windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T次，他最多能正确粉刷多少格子？ 一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。 输入描述: 输入文件paint.in第一行包含三个整数，N M T。 接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色。 输出描述: 输出文件paint.out包含一个整数，最多能正确粉刷的格子数。 示例1输入 3 6 3 111...

链接： @[toc] 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 131072K，其他语言262144K 64bit IO Format: %lld 题目描述 牛牛最近得到了一颗树，根是 1 号节点，他想要把这颗树染色。每个节点可以染成白色和黑色，牛牛认为一种染色方案是好的当且仅当任意两个黑点的 lca（最近公共祖先）的颜色也是黑色的。求一共有多少种好的染色的方案。 输入描述: 第一行一个整数 n，表示这棵树有 n个节点。 接下来 n-1行，每行两个整数 u,v 表示 u,v之间有一条边。 输出描述: 一行一个整数，表示所有合法的点的集合数量。 示例1输入 4 1 ...

比赛链接@[toc] A题 A Simple Problem about election 链接： 题目描述 n名候选人，每个人必须提名其中m个人，（也可以提名自己），候选人将按照获得的提名降序排列，如果数量相同则按照名字字典序递增排列。每个人也是按照名字依次提名m人，叫ZZZZSGW的这个人感觉自己太倒霉了，（名字这么多z，每次提名），他最后提名，问还能不能让自己获得最高地位？ 样例：输入 2 5 3 5 1 2 6 7 5 3 5 1 2 5 7 输出 3 2 题解： 自己肯定还是要给的，然后剩下的m-1个票就要尽可能与自己票数相差大的人（也就是不对自己的排名造成影响），有两种情况，一个是...