emerald's blog

POJ 3126 先把所有1000~10000素数排出来 改变给出起点数a的4位,每一位9种选择(1,2,3...9), bfs,求最短路,ans[i],记录到达数字i需要多少步数. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575

数论做法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 时则平分成功, 或者我们可

HDU 1495 数论:思路1: 首先总可乐升数是奇数肯定不能被平分 设x =b杯子倒进来次数-倒出去的次数,y同理, __为什么是-不是+,因为倒出去后杯子可乐减少,统计的是最后杯子剩余的可乐,所以做的是代数上的加减 既然要平分,那么经过移动后想要满足$bx+cy=a/2$,已知扩展欧几里得$bx+cy=gcd(b,c)$,如果满足gcd(b,c) == a/2,那

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,常数无影响)模板：1234

最大公约数由$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

HDU 2612 思路: 记录出发点(Y和 M)到每一个kfc的距离, 更新ans最小距离之和坑点: 不能走对方的出发点, 更新ans时注意 有的kfc被包围了,不能走到,除去dist[][] == 0的情况 清空数组的细节问题123456789101112131415161718192021222324252627282930313233343536373839404142434445464

POJ 1426 找到一个数字X(只由1,0组成),且$ X \% n == 0 $,(数字X能够被n整除) 输出任意的一个X 还是想不到要用BFS，从1开始bfs,加入数字ncur = cur * 10 + i,保证了数字都由1 0组成,1234567891011121314151617181920212223242526272829303132333435363738394041424344

POJ 3279 点击的数组的字典序是一行一行看成字符串的(开头的0不要,从1开始)。 输出字典序的前提是step 相同,那么枚举点的操作是从0开始$ (000001)_2 $,字典序是1 , $ (11111)_2 $字典序是11111,所以我们已经默认的是按字典序枚举的,1234567891011121314151617181920212223242526272829303132333435

POJ 3278 总是想着用dfs做,不知道为什么 标记已经进入队列的点, 遇到k就存ans = step 输出 用dfs做的时候,根本没有办法控制dfs的范围,这里bfs刚好解决了x-1 x+1 2*x谁先到k的问题 体现了广度优先的思想 12345678910111213141516171819202122232425262728293031323334353637383940414243

BPOJ 2251 三维bfs求最短路径 方向从 东南西北 加入 上下 注意L是层数的意思,从下层给到上层, bfs模板 + vis三维标记 + tx ty tz 三维坐标 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960