我认为的编程能力:
其中非常重要的一个就是算法。 一个算法浓缩了程序员对一个问题的解读、分析、思考、推论、实现。 工作之后遇到的所有问题,难度都不如之前遇到过的算法题目。 那么,这些问题也会被我迎刃而解。
看完题目大意,先思考,再看解析;觉得题目大意不清晰,点击题目链接看原文。
本篇因为篇幅,不贴代码实现。
题目大意:输入三个整数t, s, x。问输入的整数x等于 t, t + s, t + s + 1, t + 2s, t + 2s + 1... 中的一个。
题目解析:
分类讨论
偏移量:ret = x - t。
如果 ret < s, 只有 ret = 0;
如果 ret >= s, 满足 ret % s = 0或者1 即可。
是否觉得题目过于简单?
题目大意:输入一个科学计数法的数字,输出一个十进制计数的数字。
比如
输入8.549e2,输出854.9;
输入8.549e3,输出8549;
题目解析:
科学计数法的e,如果不为零,那么会对小数点的位置造成影响,比如:整数部分存在前导零、小数部分全部为零、整数小数部分全部为零的情况;
对着多种情况进行分类讨论即可。
有另外一种的方式,
scanf("%[^e]%ne%d",d,&l,&b);
,利用scanf直接读取整数部分、小数部分的值,然后分类讨论。 可能这个才是正解。
题目大意:在自然数中,数i到数2i存在一条边,数i到数2i+1存在一条边。
输入有两类型:
1、在u到v的最短路径上每条边的费用都加w;
2、求u到v的最短距离;
当输入为类型2的时候,输出u到v的最短距离。
题目解析:
对于每个自然数i,会和比自己小的自然数构成一条边,比自己大的自然数构成两边条,那么可以把边的费用存在中较大数。
对于u到v的最短路径,必然存在的k,路径为(u, k) + (k, v),k=lca(u,v)。(lca是最近公共祖先)
在此题目中,每次对u、v中的较大值/2,即可得到lca(u, v)。
题目大意:n个点形成一棵树,根节点为1。以1为起点,对树进行dfs遍历,current_time为访问到的时间。
求每个点的current_time期望值。
样例输入:
7
1 2 1 1 4 4
样例输出:
1.0 4.0 5.0 3.5 4.5 5.0 5.0
样例输入:
12
1 1 2 2 4 4 3 3 1 10 8
样例输出:
1.0 5.0 5.5 6.5 7.5 8.0 8.0 7.0 7.5 6.5 7.5 8.0
DFS算法实现
let starting_time be an array of length n
current_time = 0
dfs(v):
current_time = current_time + 1
starting_time[v] = current_time
shuffle children[v] randomly (each permutation with equal possibility)
// children[v] is vector of children cities of city v
for u in children[v]:
dfs(u)
题目解析:
对于点u有的若干个子节点,有:
如果v是u的子节点,那么starting_timev = 所有其他子树的和/2 + starting_timeu + 1。
推论:
如果u只有一个子树,那么starting_timev = starting_timeu + 1;
如果u有多个子树,如果先遍历其他子树,再遍历v所在子树,starting_time会加上其他子树的节点和;
由题目可知,遍历是随机的,那么相对子树v,先遍历某个子树的概率为1/2;
(如果难以理解,可以枚举abc、abcd的全排列,b在a前面的概率为1/2。
题目大意:有三个一模一样盒子从左到右排列。中间的盒子有一个特殊物品,每次操作随机选择左右两边的盒子和中间交换。
问n次操作后,中间盒子有特殊物品的概率。答案按照最简分数化简后,分子分母再mod值10E9+7。
题目解析:
给盒子编号1、2、3,那么盒子的排列有:
123、132、213、231、312、321;其中123、321是中间有特殊物品。
假设di是第i次操作后,盒子排列为j的次数。
di = di-1 + di-1;
di = di-1 + di-1;
di + di + di + di + di + di = 2 ^ i。(每次操作产生2种可能)
令fi = di + di。
fi = di-1 + di-1 + di-1 + di-1
= 2 ^ (i - 1) - di-1 - di-1
= 2 ^ (i - 1) -fi-1.
其中f0 = 1;
当i=2k的时候,f2k = 2^(2k-1) - 2^(2k-2) + 2^(2k-3) ... + 2^1 - 2^0 + 1;
f2k+1 = 2^(2k) - 2^(2k-1) + 2^(2k-2) ... - 2^1 + 2^0 - 1;
等比数列求和,化简后有:
f2k = (2^(2k)+2)/3;
f2k+1 = (2^(2k+1)-2)/3;
最终的答案为: ans = fn / 2^n.
当n=2k的时候,ans = f2k / 2^(2k) = (2(2k-1)+1)/(2(2k-1)*3);
当n=2k+1的时候,ans = f2k+1 / 2^(2k+1) = (2(2k)-1)/(2(2k)*3);
ans = x / y;
统一下,当n为奇数,x = (2^(n-1)+1) / 3, y = 2^(n-1);
当n为偶数, y = (2^(n-1)-1) / 3, y = 2^(n-1);
性质:如p是质数,且gcd(a,m)=1,那么 a^(m-1)≡1(mod m)。 (费马小定理)
推论:(a/b) % m = (a/b * 1) % m
= (a/b * b^(m-1)) % m
= (a * b^(m-2)) % m
= a%m * b^(m-2)%m
2^(n-1) % m = (2^n / 2) % m
= 2^n % m * 2^(m-2)%m
备注:感谢胡浩大神提供最后推论的思路。
有思考,才会有收获。多次的苦思冥想,最后解决问题的那一刻,很刺激。
E题推论出公式很快,最后在化简卡住了很久,演算了多张草稿纸都没有思路,最后猜测应该是数论的知识,询问了数学系的一个朋友,最后得到了费马小定理可以用来化简分数的mod。