长安大学ACM协会

主讲人：段英鹏时间：7.17 简单博弈论 本次简单博弈论讲解六个知识点： 1：bash博弈；2：nim博弈；3：威佐夫博弈；5：Fibonacci博弈；6：sg函数； 首先介绍博弈论问题有如下几个特点 1：博弈模型为两人轮流决策的博弈。并且两人都使用最优策略来取得胜利。 两个玩家，都会采取最优的决策，那么如果存在一个局面为必胜局面，某玩家位于此局面。只要自己无失误，则必胜。那么同样又一个局面为必败局面，某玩家位于此局面。只要对手无失误，则必败。 那也就是说，针对这样的游戏，我们关注点应该在局面上。 2：博弈是有限的。即无论两人如何决策，都会在有限步决出胜负。 3：博弈是公平的。即两人进行决策的规则相同。 相关概念： 先手必胜状态：先手可以从这个状态走到某一个必败状态。 先手必败状态：先手走不到任何一个必败状态。 也就是说先手必胜状态，那么先手一定能采取某些操作，让后手面对必败态。如果是先手必败态，无论先手怎么操作，都无法让后手面对必败态。 bash博弈 假设一堆石子有n个，每次最多取m个，甲乙两个玩家轮流取石子，最后把石子取完的人获胜，保证甲乙每一步的决策都是最优的， ...

课表 [注意事项]一、日程相关1．明远二区大门开门时间 时间段 时间 早上 8:00 - 9:00 中午 11:00 - 13:00 下午 17:30 - 18:00 2．集训地点为2501，2506 （2506 教室7.15~8.6 可用） 二、训练内容相关1.介于部分同学无法在15号开始集训，第一次课安排在17号，15，16号会安排两次比赛（3h） 2.杭电多校和牛客多校的比赛时间为（12:00~17:00），该成绩会为下半年打比赛名额选取做一定参考 3.一次课时间为 9:00~11:00（按具体情况加时，无比赛时可在下午3:00~5:00加时），按需求挂专题（挂题网址：https://vjudge.net/group/chd2019summerCamp） 4.2018学年的算法讲堂课件见爆肝群文件，每次挂的题目见https://vjudge.net/group/chdacm 5.上面提到的牛客和杭电多校分别是牛客网和HDU组织的线上比赛，题目一般比区域赛题目略难，已报名的集训队队员参加。 三、讲课相关 专题 节数 授课人 博弈论 ...

授课人 : 段英鹏 授课时间 : 6月1日 19:00 授课地点 : wx3304 授课内容 : 状压DP 倍增DP 数据结构优化DP 点击下载课件

授课人 : 韩耀东 授课时间 : 5月23日 19:00 授课地点 : wx3304 授课内容 : 区间DP 树形DP 点击下载课件 DP第一讲基础概念三要素：”状态“ ”阶段“ ”决策“ 三个基本条件：子问题重叠性，无后效性，最优子结构性质 把原问题视作若干个重叠子问题进行求解，每个子问题求解的过程就是一个“阶段”。 LIS(最长上升子序列)$d[i] = max_{0\leq j < i, a[j]<a[i]}{d[j]+1}$ LCS（最长公共子序列） d[i,j] = max \begin{cases} d[i-1][j] & \\ d[i][j-1] & \\ d[i-1][j-1] + 1 & \text{if a[i] = b[i]}\\ \end{cases}数字三角形 d[i][j] = a[i][j] + max \begin{cases} d[i-1][j] &\\ d[i-1][j-1] & \text{if j>1}\\ \end{cases}背包0/1背包问题模型：给定N个物品，其中第 i 个物品的体积为$V_i$ 价值为$W_i$ 。有一容积 ...

授课人 : 方尧 授课时间 : 5月18日 19:00 授课地点 : wx3304 授课内容 : 并查集 树状数组 线段树 点击下载课件

授课人 : 陈南曦 授课时间 : 5月4日 19:00 授课地点 : wx3304 授课内容 : 组合计数，容斥，概率dp，博弈 点击下载课件

授课人 : 韩耀东 授课时间 : 4月27日 19:00 授课地点 : wx3304 授课内容 : 数论初步：质数，约数，同余(筛法，exgcd，欧拉函数，欧拉定理，中国剩余定理) 点击下载课件

授课人 : 方尧 授课时间 : 4月11日 19:00 授课地点 : wx3304 点击下载课件

授课人 : 陈南曦 授课时间 : 3月23日 19:00 授课地点 : wx3304 点击下载课件

报名链接 时间：3月9日14：00-17：00地点：wx3203，wx3202 需要自备电脑，不可以携带任何纸质资料（草稿纸自备），请诚信参赛。