HNU:ACM校队预选寒假训练1.25-1.31-div3-杂题-题解
题解仅供参考
题外话:我得重新整个实用的大数板子了
A
题解
就是个裸的辗转相除法,没什么坑,int就能过
B
题目大意
就是求一堆数里的素数(这题貌似用最简单的判断素数方法就能过)
优化
可以对前1e7个数用筛法判断存表(不过这题确实没必要)
C
题目大意
求1-n的奇数平方和
题解
法一:用公式解决(注意n(n+1)(n+2)
会超长整数范围)
法二:预处理打表(核心代码如下)
long long pow2[100001]; |
题外话
打表被老师嘲讽了
D
题解
这题挺坑的,还要在出发点相遇(题目没讲清楚吧)
具体的解法是,假设输入的数是a/b c/d
化简 a/b 和 c/d 得到新的 a,b,c,d,答案为 lcm(a,c)/gcd(b,d)
注意分母为1的情况
E
题解
这题是个纯数学题,看平均分后有多少刀是重复的
即 a+b-gcd(a,b)
F
题目大意
求最大质因数是第几个素数
题解
显然用埃氏筛轻松解决
G
题解
显然 c 是 b 的倍数且满足 gcd(a,c)==b 即可
循环 c 累加 b,找到最小的 c 后直接 break
H
题解
根据题目可知,一共有三种形式的小数需要我们去转换成分数,分别为:
有限小数:形如 0.2,0.33
纯循环小数:形如 0.333333333…
非纯循环小数:形如 0.32477777… ,0.24367676767…
显然,无限不循环小数不可能转换为分数(中学知识),而对于上面两种循环小数,我们不妨分情况来讨论。
1、纯循环小数
0.33333… * 10 = 3.33333…
(10 - 1) * 0.33333… = 3
即 9 * 0.33333… = 3
所以 0.33333… = 3/9 = 1/3
再举一个例子
0.474747… * 100 = 47.474747…
(100 - 1) * 0.474747… = 47
即 99 * 0.474747… = 47
所以 0.474747… = 47/99
由上述两个例子我们可以发现,纯循环小数化成分数过后其分子就为所循环单元化成的数,分母则全由9组成,位数和循环数的位数相同。
2、非纯循环小数
0.4777777… * 10 = 4.7777…
0.477777… * 100 = 47.77777…
(100 - 10) * 0.4777777… = 43
所以 0.4777777… = 43/90
再举一个例子
0.323565656… * 1000 = 323.56565656…
0.323565656… * 100000= 32356.565656…
(10000 - 1000) * 0.32356565656… = 32033
所以 0.32356565656… = 32033/99000
由上述两个例子我们可以发现,非纯循环小数化成分数过后其分子为 非循环部分与第一个循环部分 组成的数减去非循环部分的数,分母则为9与0组成的数,9的位数和循环部分数的位数相同,0的位数则和非循环部分数的位数相同
PS:对于有限小数,不妨看作是非纯循环小数的一种特例子,即0.3 = 0.30000000
I
题目大意
输出[1,2,…,n]的第i个子序列
自序列的顺序按字典序排序
题解
这题就很有意思了
对 n=1 而言,子序列为
[1]
对 n=2 而言,子序列为
[1],[1,2]
[2],[2,1]
对 n=3 而言,子序列为
[1],[1,2],[1,2,3],[1,3],[1,3,2]
[2],[2,1],[2,1,3],[2,3],[2,3,1]
[3],[3,1],[3,1,2],[3,2],[3,2,1]
……
显然可以发现,长度为 n 的序列的子序列 S(n) 满足这样一个关系式:S(n)=n*(S(n-1)+1)
如果按上面的写的话,将 S(n) 个数分为 n 组,每组有 S(n-1)+1 个
那么第 i 个子序列的开头就很明显了,为 x1=i/(S(n-1)+1)+1
假如 n=3,i=9 ,求出的第9个子序列的第一个数为 x1=2
接下来对第 x1 行处理,去除第一个数,新的序列为
[1],[1,3]
[3],[3,1]
即为序列 [1,3] 的子序列
所求即为第 i%(S(n-1)+1)-1
个子序列
以此类推
代码
|
J
题目大意
其实就是最大上升子序列和
题解
DP题一道,dp[i]记录从1-i的最大子序列和,不断维护最大值即可,核心代码如下
int maxx=-1; |
K
题解
01背包问题,不过这题反向记录不被录取的最小概率会比较好算
dp[i]记录的是 i 万美元下不被录取的最小概率,核心代码如下
long long i,j; |
L
题解
数塔(数字三角形)什么的已经很老套了,这里就不讲了(不过递归会超时)
M
题目大意
求 N! 的位数
题解
求位数我们其实比较容易想到的是 log10(i)+1
log10(N!) = log10(12L*N) = log10(1) + log10(2) + L + log10(N)
最后对和取整+1即为答案
N
题目大意
就是个大数加法板子。。。
题解
略(基本上每个板子都能过吧)
O
题目大意
大数累乘求 N!
题解
10000!
足足有近36000位,所以考虑了下压位处理
这题卡了空间没卡时间,打表反而会 MLE,每次运算求解就可
核心代码如下:
memset(a,0,sizeof(a)); |
PS:注意 0! =1
P
题目大意
求每组大数和
题解
还是个大数板子题,不过注意这题有个单独的数据 0
比较恶心
Q
题目大意
求 R 的 n 次方根
题解
对整数部分和小数部分分别运算,注意最后输出格式(小数的乘法确实难搞)
R
题目大意
求区间内的菲波那契数的个数
题解
这题我采用的是先打表后查找的方式,菲波那契数的第500项位数就超过100位了
(然后大数比较我写错了,找BUG找了半天)
普通查找即可(不需要二分就可以过)
代码
|
S
题解
继续我的大数打表行为emmm
T
题解
跟大数加法没太大区别,只不过变成头尾补0了
U
题解
这题我的解法跟别人可能不太一样。。。我直接让组合出的数做为下标存到布尔数组里,再枚举数组值为 true 的下标(暴力不需要考虑重复)
太丢脸了就不放代码了
V
题目大意
已知树的前根中根遍历,求后根遍历
题解
这题也是老题了,熟悉这三种遍历方式的自然知道怎么判断树的根节点(不需要构建树)
W
题目大意
1,2是友谊数
如果 a,b (可相同)是友谊数,那么 ab+a+b 也是友谊数
求 n 是不是友谊数
题解
这是道数学题。可以发现公式
n+1 = ab+a+b+1 = (a+1)(b+1)
又因为所有友谊数都是由 1,2 衍生,可以知道 n+1 可以表示成 pow(2,x)*pow(3,y) 的形式
判断 n 是否满足上述结构即可