本文目录
acm竞赛的算法总共有那些范围 求大牛概括
初级:
一.基本算法:
(1)枚举. (poj1753,poj2965)
(2)贪心(poj1328,poj2109,poj2586)
(3)递归和分治法.
(4)递推.
(5)构造法.(poj3295)
(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.图算法:
(1)图的深度优先遍历和广度优先遍历.
(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓扑排序 (poj1094)
(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)
(6)最大流的增广路算法(KM算法). (poj1459,poj3436)
三.数据结构.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)
(3)简单并查集的应用.
(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼树(poj3253)
(6)堆
(7)trie树(静态建树、动态建树) (poj2513)
四.简单搜索
(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.动态规划
(1)背包问题. (poj1837,poj1276)
(2)型如下表的简单DP(可参考lrj的书 page149):
1.E+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E+zij} (最长公共子序列)
(poj3176,poj1080,poj1159)
3.C}.(最优二分检索树问题)
六.数学
(1)组合数学:
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
(2)数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635, poj3292,poj1845,poj2115)
(3)计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.
(1)几何公式.
(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)
(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)
分图题是什么
分图题指的就是以二分图作为基础的一种题型，在这种题型里面绘画几种二分图的一种特殊模型，然后他作为一个无向图，然后去定义为一个二分图的时候是能够出相关的一些题目的。
然后在这种题目里面对于二分图，也就是对于分图是需要有一个具体的了解的，先了解它的定义是什么，才能够在题目里面去解决里面给出的一些问题，然后在二分图里面，这些一般是用到计算机的算法里面。
就是说编程的算法里面代码的一些算法里面就有可能用到分图的这种题型，也就是二分图的这种题型，然后像这种题目的话一般是出在数据结构这样子的一个科目。
二层博弈树怎么画
1）绘制决策树图。从左到右的顺序画决策树，此过程本身就是对决策问题的再分析过程。
（2）按从右到左的顺序计算各方案的期望 值，并将结果写在相应方案节点上方。
期望值的计算是从右到左沿着决策树的反方向进行计算的。
（3）对比各方案的期望值的大小，进行剪枝优选。在舍去备选方案枝上，用“=”记号隔断。
二分图的最短圈的长度
girth。根据查询二分图模型相关信息得知，二分图的最短圈的长度为girth。二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
算法笔记之博弈问题——猫和老鼠
博弈问题，需要注意，对于每个玩家，都会争取：
LeetCode913. 猫和老鼠
两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。
图的形式是：graph 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。
老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。
在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph 中的任一节点。
此外，猫无法移动到洞中（节点 0）。
然后，游戏在出现以下三种情形之一时结束：
如果猫和老鼠出现在同一个节点，猫获胜。
如果老鼠到达洞中，老鼠获胜。
如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。
给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：
如果老鼠获胜，则返回 1；
如果猫获胜，则返回 2；
如果平局，则返回 0 。
题目描述比较长，但其实还是很好理解的。需要注意，每个玩家都会争取自己获胜。本题就是简单的深度优先搜素+记忆化问题了。
这里考虑的是怎么才能算平局，我们采取的方法是，如果有n个节点，到2n轮如果还没出结果，就认为可以平局了。
需要注意的是记忆化，memo 代表猫在i，老鼠在j，在第k轮的结果。
参加ACM大赛应该准备哪些课程
课程：
（1）基本算法: 二分,分治，贪心
（2） 离散数学离散数学动态规划
（3） 搜索算法：深度优先 搜索，广度优先搜 A*算法 ，阿尔法贝塔剪枝
（4）数据结构: 线段树, 树状数组，并查集,Trie图
（5）图论问题：最小生成树 最短路 强连通分量、桥和割点
（6）网络流算法：基本的网络流算法，Dinic算法，带上下界的网络流，最小费用流
（7）计算几何：线与线求交，线与面求交，求凸包，半平面求交等
（8） 离散数学，高等数学，线性代数，初等数论，计算几何
（9）计算机专业英语
（10）C++；基础的递归、枚举算法
扩展资料：
1.参赛队伍最多由三名参赛队员组成。
2.竞赛中命题10题左右，试题描述为英文，比赛时间为5个小时，前四个小时可以实时看到排名，最后一小时封榜，无法看到排名。
3.竞赛可以使用的语言：Java, C, C++, Kotlin 和 Python。
4.重点考察选手的算法和程序设计能力，不考察实际工程中常用的系统编程，多线程编程等等；
5.选手可携带任何非电子类资料，包括书籍和打印出来的程序等，部分赛区会对选手携带的纸质资料做限制。
6.评委负责将结果（正确或出错的类型）通过网络尽快返回给选手，除此之外不提供任何额外帮助；
7.每个题目对应一种颜色的气球，通过该题目的队伍会得到对应颜色气球。每道题目第一支解决掉它的队还会额外获得一个“FIRST PROBLEM SOLVED”的气球。
百度百科-ACM国际大学生程序设计竞赛
分时博弈走势图怎么看
分时博弈中有四根走势线：红线，特大单净买入占成交量比例的走势线；黄线，大单净买入占成交量比例的走势线；灰线，中单净买入占成交量比例的走势线；绿线，小单净买入占成交量走势的比例线。经过长期的观察和实践这四根走势线中以大单线即黄线和小单线即绿线这两个走势线的表现为主，特大单线即红线和中单线即灰线的表现为辅。
步骤/方法
一、开盘后黄线就在绿线上方并且一直保持良好的距离，红线和灰线没太大表现，那么说明该股当天主力以多方为主，可以继续的持有；
二、开盘后绿线一直保持在黄线上方运行，红线和灰线没有太大表现，说明当天该股主力以空方为主，那么尽量不要介入；
三、如一开始绿线保持在黄线上方运行，但随着时间的推移，黄线在不断上移，说明多空双方开始有所变动，一旦黄线上穿绿线在其上方运行，那么也就多方占有优势了，那么上穿的那个位置也是当天的比较好的买点，然后再结合当然的均价线走势，临近均价线买入就更稳了。
四、同样如一开始黄线保持在绿线上方运行，但随着时间的推移，绿线在不断上移，说明空方开始出击，一旦绿线上穿黄线在其上方运行，那么也就空方有优势了，这个上穿的位置也就是当天比较好的卖点。
五、如遇到盘中特大单线也就红线拉升速度非常快，或者非常高时，说明主力当天动作是比较明显的了，一般情况随之股价就会拉升，如上午红线向上拉升后股价随之上涨并且维持在高位盘整，那么只要大单线黄线一直保持在绿线上方运行，一般情况下之后还会有一波拉升幅度，及时没有该股也是有主力十足参与的，应积极关注。
六、如当天几根走势线没有太大波动，并且间距比较小来回胶着的，说明多空方意图还没有明朗，如当时股价也是处于震荡中，那么还建议有待观察。
