今天的题都还比较简单,反正 AK 了(,但是几乎所有人都 AK 了,所以没啥可高兴的(
大概题目难度都是 普及- 吧
T1:级数求和
本题模拟就行。
定义一个变量 $sum$,表示当前的和,然后一直循环,当 $sum>k$ 时,退出循环。
while(1){
if(sum > k)break;
tmp++;
sum = sum+((double)1/(double)tmp);
}
T2:过河卒
做法:递推
首先先定义一个 $map$ 存储这个棋盘,然后把马的控制点标记一下,再递推即可。
注意 $ans_{0,0}$ 为 $1$,还要考虑出界,马的控制点。
if(map[i-1][j] == 0 && (i-1) >= 0)ans[i][j]=ans[i-1][j];
if(map[i][j-1] == 0 && (j-1) >= 0)ans[i][j]+=ans[i][j-1];
T3:数的计算
做法:递推
我们定义 $f_i$ 表示初始数为 $i$ 的方案总数。
因为 $i$ 后面可以接上任意一个不大于它一半的数,当然,它自己本身也符合要求。
for(int i=1; i<=1001; i++){
for(int j=1; j<=i/2; j++){
f[i]+=f[j];
}
f[i]++;
}
T4:最大公约数和最小公倍数问题
做法:有些数学题(?)
$x0\timesy0=P\timesQ$
然后知道了上面那个式子,再去枚举 $P,Q$ 即可。注意恰好平方情况!还有我特判了一下 $x0=y0$(
T5:求先序排列
做法:递归
我做了挺长时间的wtcl/kk,然后还想试一下英文注释(,但是英文单词不知道,还想百度英文单词,最后放弃了
就是递归,也没啥别的可以说的吧,然后调了半天,一些细节问题
T6:装箱问题
做法:很简单的背包(?)
就是定义 $f_{i,j}$ 表示容量为j的箱子,对于前i个物品来说,能装的最大体积
然后:
for(int i=1; i<=n; i++){//前i个物品
for(int j=1; j<=V; j++){//容量为j的箱子
if(j >= a[i]){
f[i][j] = a[i]+f[i-1][j-a[i]];
}
f[i][j] = max(f[i][j],f[i-1][j]);
}
}
然后就完了,六道题就完了,挺水的(