2017/04/02 训练赛题解

题解

A、Circle in Square
题目来源：lightoj1022
水题，正方形面积4r²，圆面积πr²
S=4r²-πr²

B、Discovering Permutations
题目来源：lightoj1023
求按照字典序从小到大求前K个序列
若想练习回溯法就用DFS写吧
捡方便的话还是用next_permutation这个STL函数
（详情可以百度）

C、Eid
题目来源：lightoj1024
求N个数的最小公倍数
很简单，把N个数都因式分解后，对于每个质因数，取这N个数分解结果中的最大次幂，然后相乘。
先对于每个数Ak质因数分解
A₁ = P₁^q11+P₂^q12+P₃^q13+……
A₂ = P₁^q21+P₂^q22+P₃^q23+……
A₃ = P₁^q31+P₂^q32+P₃^q33+……
A_k = P₁^qk1+P₂^qk2+P₃^qk3+……
所以答案就是每个质因数的最大次幂的乘积
Ans = P₁^max(qk1)+P₂^max(qk2)+P₃^max(qk3)+……

D、A Dangerous Maze
题目来源：lightoj1027
有N道门
门上有个数，如果是正数a就代表走这个门走a分钟就出去了
如果是负数就是走-a分钟回到了原点，问走出去的时间的期望值。
设期望值为E,Z_k为正数，F_k为负数
E=Z₁/n+Z₂/n+Z₃/n+……+Z_k/n+(-F₁+E)/n+(-F₂+E)/n+(-F₃+E)/n+……(-F_k+E)/n
也可以表示为
E=P₁ x E₁ +p₂ x (E₂+E)
其中P₁为选到正门的概率，p₂为选到负门的概率，E₁为走正门出去的时间期望，E₂为走负门回到原点的时间期望

E、Trailing Zeroes (I)
题目来源：lightoj1028
将N转换为K进制，问有多少种K使得转换后的K进制数末尾为0
只要N能整除K，转换K进制后末尾肯定是0。
所以这道题就变成了求N的约数的个数。
如果不会详情百度。

F、Civil and Evil Engineer
题目来源：lightoj1029
用kruskal或者prim算法求出最大最小生成树即可。
如果不会详情百度。

G、Discovering Gold
题目来源：lightoj1030
题意自行理解。
E_i为第i个格子时，能获得的金子的期望
E_i=E_i+1/6+E_i+2/6+E_i+3/6+E_i+4/6+E_i+5/6+E_i+6/6
E₁即为答案
（当i>n-6时需要特殊处理。）

H、Easy Game
题目来源：lightoj1031
区间DP
给一个整数序列，两个人轮流从序列某端取若干数，问先手比后手多的最大分数
dp_ij为区间i到j先手比后手都的最大得分
sum_ij为区间i到j的和
dp_ij=max(sum_ij , sum_ik-dp_k+1j , sum_k+1j-dp_ik)
(i <= k < j)

I、Generating Palindromes
题目来源：lightoj1033
给一个字符串，让你任意位置添加任意数量的字符，问最少需要添加多少次可以变成回文字符串
区间DP
dp_ij为i到j区间的字符串变成回文字符串的最小添加次数
如果s[i]==s[j]
dp_ij=dp_i+1j-1
如果s[i]!=s[j]
此时可以在头部添加一个与尾部相同的字符，也可以在尾部添加一个与头部相同的字符。取两种情况的最小值
dp_ij=min(dp_i+1j,dp_ij-1)+1

J、Intelligent Factorial Factorization
题目来源：lightoj1035
求N的阶乘
用因式分解的方式表示
因为N小于等于100
所以分解后的最大质因数肯定是小于100的
然后瞎搞吧 水题嘛