HDU_1495(BFS) 数论做法HDU 1495 BFS: 剪枝:奇数可乐肯定不能被平分 枚举6种操作a->c a->b b->a b->c c->a c->b 将每个杯子有多少可乐作为状态保存下来 在a == b && c == 0 或者a == c && b == 0 或者 b == c && a == 0 时则平分成功, 或者我 2019-05-23 算法
HDU_1495(数论) HDU 1495 数论:思路1: 首先总可乐升数是奇数肯定不能被平分 设x =b杯子倒进来次数-倒出去的次数,y同理, __为什么是-不是+,因为倒出去后杯子可乐减少,统计的是最后杯子剩余的可乐,所以做的是代数上的加减 既然要平分,那么经过移动后想要满足$bx+cy=a/2$,已知扩展欧几里得$bx+cy=gcd(b,c)$,如果满足gcd(b,c) == a/2,那么就能平分. 2019-05-22 算法 扩展欧几里得
扩展欧几里得例题(luogu_1082) luo gu 由$a*x \equiv1 (\mod b)$ 推导为扩展欧几里得 ->$a*x \mod b == 1 \mod b$ ->$a*x \mod b =1$ 即-> $ax = nb+1$(n是常数) -> $ax-nb=1$ ->$ax+yb=1$ (y = -n,常数无影响)模板：1234567891011121 2019-05-22 算法
扩展欧几里得算法 最大公约数由$gcd(a,b) = gcd(b,a%b)$ 辗转相除法得到, 贝祖定理存在整数a,b ,那么一定存在整数x,y,使得 $ax+by = gcd(a,b)$ 可以判断$ax + by = gcd(a,b)$是否有解,或者$ax + by = m$ 且 $m = k * gcd(a,b)$ 通过求gcd时 推x,y 首先是一组特解x = 1 y = 0 假设在辗转求gcd时满 2019-05-22 算法
HDU_2612_(BFS) HDU 2612 思路: 记录出发点(Y和 M)到每一个kfc的距离, 更新ans最小距离之和坑点: 不能走对方的出发点, 更新ans时注意 有的kfc被包围了,不能走到,除去dist[][] == 0的情况 清空数组的细节问题1234567891011121314151617181920212223242526272829303132333435363738394041424344454 2019-05-21 算法 BFS
POJ_1426_(BFS) POJ 1426 找到一个数字X(只由1,0组成),且$ X \% n == 0 $,(数字X能够被n整除) 输出任意的一个X 还是想不到要用BFS，从1开始bfs,加入数字ncur = cur * 10 + i,保证了数字都由1 0组成,12345678910111213141516171819202122232425262728293031323334353637383940414243 2019-05-20 算法
POJ_3279_(枚举) POJ 3279 点击的数组的字典序是一行一行看成字符串的(开头的0不要,从1开始)。 输出字典序的前提是step 相同,那么枚举点的操作是从0开始$ (000001)_2 $,字典序是1 , $ (11111)_2 $字典序是11111,所以我们已经默认的是按字典序枚举的,12345678910111213141516171819202122232425262728293031323334 2019-05-20 算法
POJ_3278_(BFS) POJ 3278 总是想着用dfs做,不知道为什么 标记已经进入队列的点, 遇到k就存ans = step 输出 用dfs做的时候,根本没有办法控制dfs的范围,这里bfs刚好解决了x-1 x+1 2*x谁先到k的问题 体现了广度优先的思想 123456789101112131415161718192021222324252627282930313233343536373839404142 2019-05-19 算法 BFS
POJ_2251_(BFS) BPOJ 2251 三维bfs求最短路径 方向从 东南西北 加入 上下 注意L是层数的意思,从下层给到上层, bfs模板 + vis三维标记 + tx ty tz 三维坐标 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 2019-05-19 算法 BFS
2017.瓷砖样式.dfs 我也没想到怎么做,看别人题解看懂了 dfs()枚举所有的点,我看长方形瓷砖是2格的就莫名不知道该怎么枚举 要求用2种颜色瓷砖铺满3*10的格子,且瓷砖能横着铺 竖着铺, 遍历所有的点,dfs去铺,判断每个点是否铺过,标记第一个颜色为0,第二个颜色为1 判断每个点铺了瓷砖没,没铺就铺瓷砖,铺了之后就判断该行是否铺完,否则换行或者接着下一个点继续铺, 没有铺,判断是否到了最有一个点,没有就,判断 2019-05-19 算法