FDOM-CSDN博客

原创 Good Luck in CET-4 Everybody! HDU - 1847（巴什博弈）

#include <iostream>using namespace std;//博弈就是找每步都让对方必败的点//必败点0 3 6 9 12。。。，发现都是3的倍数，因为每两个必败点之间只有两个数，且这两个数都可以一步转化为必败点，所以n是三的倍数先手必败，否则必胜int main(){ int n; while(cin>>n) { if(...

2018-04-20 10:52:21 187

原创取石子游戏 HDU - 2516（斐波那契博弈）

斐波那契博弈有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜。结论是：先手胜当且仅当n不是斐波那契数（n为物品总数）#include <iostream>using namespace std;int main(){ long long n; int a[1001...

2018-04-19 21:40:17 182

原创 Being a Good Boy in Spring Festival HDU - 1850(尼姆博弈)

根据尼姆博弈性质，如果面对奇异局势，则先手必败，否则必胜判断是否是奇异局势，只需将所有的数异或起来，如果为0，则为奇异局势此题可以先判断是否为奇异局势，如果是奇异局势直接输出0。如果不是奇异局势，则需把非奇异局势转化为奇异局势，这样下一个人必败，自己必胜。假设一个非奇异局势(a,b,c)，若想转化为奇异局势，只需让a=b^c或者b=a^c或者c=a^b,因为a^b^(a^b)=(a^a)^(b^b...

2018-04-19 21:20:06 134

原创尼姆博弈整理

尼姆博弈有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。这种情况最有意思，它与二进制有密切关系，我们用（a，b，c）表示某种局势，首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3）也是奇异局势，无论对手如何拿，接...

2018-04-19 20:29:00 192

转载树状数组

int lowbit(int t){return t&(-t);}void add(int x,int y){for(int i=x;i<=n;i+=lowbit(i))tree[i]+=y;}int getsum(int x){int ans=0;for(int i=x;i>0;i-=lowbit(i))ans+=tree[i];return ans;} 这篇笔记会...

2018-04-19 19:56:31 115

转载威佐夫博弈详解

威佐夫博弈是博弈中的另一个经典模型。问题：首先有两堆石子，博弈双方每次可以取一堆石子中的任意个，不能不取，或者取两堆石子中的相同个。先取完者赢。分析：首先我们根据条件来分析博弈中的奇异局势第一个（0 ， 0），先手输，当游戏某一方面对（ 0 ， 0）时，他没有办法取了，那么肯定是先手在上一局取完了，那么输。第二个（ 1 ， 2 ），先手输，先手只有四种取法，1）取 1 中的一个，...

2018-04-19 19:54:17 3317

原创取(2堆)石子游戏 HDU - 2177 (威佐夫博弈)

根据威佐夫博弈的性质：如果先手面对奇异局势，则必败。可采用适当方法把非奇异局势转变为奇异局势，则下一个必败。此题可先判断是否是奇异局势，即a和(b-a)*(sqrt(5.0)+1.0)/2.0是否相等（最好不要直接让(b-a)*1.618，会有精度损失），如果相等直接输出0，如果不等，则需把非奇异局势转化为奇异局势。有两种可能的途径，一种是从两堆里拿出相同的石子且剩下的两堆石子是奇异局势，另一种是...

2018-04-19 19:50:34 182

转载几种博弈论及分析

原博地址：https://blog.csdn.net/ac_gibson/article/details/41624623一. 巴什博奕（Bash Game）： A和B一块报数，每人每次报最少1个，最多报4个，看谁先报到30。这应该是最古老的关于巴什博奕的游戏了吧。其实如果知道原理，这游戏一点运气成分都没有，只和先手后手有关，比如第一次报数，A报k个数，那么B报5-k个数，那么B报数之后问题就...

2018-04-19 17:57:46 2210

原创 (HDU - 4764) Stone（巴什博弈）

Tang and Jiang are good friends. To decide whose treat it is for dinner, they are playing a game. Specifically, Tang and Jiang will alternatively write numbers (integers) on a white board. Tang writes...

2018-04-19 17:36:41 191

原创最大的算式（动态规划）

先抽象出状态dp(i,j)，表示前i个数中有j个乘号的最大值。假设j个乘号中最后一个乘号的位置是第t个数和第t+1个数之间，则若要取最大值，须把第t个数之后的数加在一起再乘上dp(t,j-1),由此得出状态转移方程dp(i,j)=max(dp(t,j-1)*(sum[i]-sum[t]))，sum[x]表示前x数的和，用记忆化搜索求解，解是dp(n,k)#include <iostream&...

2018-04-19 15:29:43 803

转载 sscanf用法

C语言函数sscanf()的用法sscanf() - 从一个字符串中读进与指定格式相符的数据.　　函数原型:　　int sscanf( string str, string fmt, mixed var1, mixed var2 ... );　　int scanf( const char *format [,argument]... );　　说明：　　sscanf与scanf类似，都是用于输入的...

2018-04-15 09:59:59 221

原创字符串之strtok

和java里的split功能差不多，用于分割字符串原理就不赘述了，这里直接说明用法，并举例。strtok(x,y)用来分割字符串，每次截下来一部分，第一个参数是指针（第一次分割时第一个参数是字符串首地址，以后再分割第一个参数是NULL），第二个参数是分割符(比如*、#等等),头文件是string.h一个简单的例子#include <iostream>#include <cstri...

2018-04-12 21:01:21 123

原创小朋友排队（树状数组）详细注释

#include <iostream>#include <algorithm>#include <cstring>using namespace std;//分析可知每个小朋友的交换次数即每个数左边更大和右边更小的数的个数和，即左边与其形成的逆序对数 + 右边与其形成的逆序对数//则此问题转换为求逆序对数，如果直接暴力求解时间复杂度o（n^2）会超限，则利用树状...

2018-04-12 20:46:14 197

原创矩阵连乘（dp）

给定一个有n个矩阵的矩阵链A1A2A3…An，其中矩阵Ai(i=1,2,3…n)的维度为pi-1*pi。我们知道，两个维度分别为m*r和r*n的矩阵用一般的矩阵乘法相乘，所需的运算次数为m*r*n，最后得到一个维度为m*n的结果矩阵。对于矩阵链问题，因为矩阵乘法具有结合律，其运算顺序有很多中选择。换句话说，不论如何括号其乘积，最后结果都会是一样的。例如，若有四个矩阵A、B、C和D，将可以有：(AB...

2018-04-12 20:34:50 633

原创 Cutting Sticks uva 10003(dp)

属于线性结构上的动态规划，区间划分类型，典型题目如最优矩阵链乘，不断分割区间直到边界#include <iostream>#include <cstring>using namespace std;//d(i,j)=min(d(i,p[x])+d(p[x],j))+j-i表示i,j之间切割的最小开销;(i,j)之间没有p[x]时结束，注意是开区间，答案是d(0,len)in...

2018-04-12 19:16:51 98

原创 uva 437 The Tower of Babylon (动态规划)

#include <iostream>#include <cstring>using namespace std;//d(x,y)以第x个立方体的第y条边做高能达到的最高高度,递推方程d(x,y)=max(d(i,j))+h[x][y],1<=i<=n,1<=j<=3,记忆化搜索求解int h[101][101];int n;int d[101][1...

2018-04-10 21:45:36 152

原创 memset为什么只能把整型数组的值设置为0或-1

memset是按字节一个一个的设置，比如把整型数a设置为1，int是32位的共四个字节，每个字节设置为1，则为00000001 00000001 00000001 00000001转为十进制数是1+1*2^8+1*2^16+1*2^24=16843009，而不是1。对于0和-1，0为 00000000 00000000 00000000 00000000，转化为十进制为0，-1为 11111111...

2018-04-10 19:02:23 1791

原创劲歌金曲（dp）

两层动态规划，需要满足在数量最多的情况下时间最长第一层数量最多: 和01背包相似，状态d(i,j)是在面对第i首歌还剩j时间时所能唱的最多歌曲数，得出状态递推方程d(i,j)=max(d(i+1,j),d(i+1,j-len[i])),用递推法得出答案d(1,t)第二层时间最多 :注意是在数量最多的情况下，递推方程和数量差不多#include <iostream>using names...

2018-04-10 18:29:24 530

原创畅通工程之局部最小花费问题（并查集）

7-1 畅通工程之局部最小花费问题（35 分）某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标：使整个地区任何两个城镇间都可以实现快速交通（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建快速路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全地区畅通需要的最低成本

2017-10-31 19:52:36 1174

smithstf的博客