这期单从技术不好讲，来些例题吧。
本帖含有三个例题，均为入门题，第二，三题有扩展。
【例1】计算e的值
题面
很多人萌新看到这一题都会不假思索地写一个双重循环。
如下：
for(int i=0;i<=n;i++){
int f=1;
for(int j=1;j<=i;j++){
f*=j;
}
e+=1.0/f;
}
但这是错的。
为什么呢？运行结果没错，但不够快。
因为每次不用都计算一遍阶乘。
可以发现：(n+1)!=n!*(n+1)。
也就是说，每一轮的阶乘值可以由上一轮更新而来。
代码很容易就出来了。
核心代码：
for(int i=1;i<=n;i++){
e+=1.0/f;
f*=i;
}
注意：f要赋初值为1。
降低循环次数，减少循环层数是优化代码的常用方法。
【例2】百鸡问题
题面
很多萌新看到这题都会直接敲一个三重循环，但三重循环的效率太低了，于是可以考虑减少循环次数。
简化
可以发现，当知道公鸡和母鸡的数量时，也就可以算出小鸡的数量。
核心代码：
for(long long i=0;i<=m;i++){
for(long long j=0;j<=m-i;j++){
if((m-i-j)%z==0&&i*x+j*y+(m-i-j)/z==n) cnt++;
}
}
再简化
有没有效率更高的方法？
有的，那就是数学。
（我 LaTeX 中的大括号不会打，请大佬见谅）
解：设公鸡数量为 x ，母鸡数量为 y ，小鸡数量为 z 。
ax+by+\dfrac{z}{c}=n 1.
x+y+z=m 2.
由2.得： z=m-x-y 3.
将3.带入1.得： ax+by+\dfrac{m-x-y}{c}=n
由1.去分母得： c(ax+by)+m-x-y=cn
由1.化简得： y=\dfrac{cn-m-(ac-1)x}{bc-1}
很明显，这是一个二元一次不定方程。
枚举 x ,判断 y 是否符合条件。
判断方法：
判断 bc-1 是否能被 cn-m-(ac-1)x 整除。
注： a,b,c 在程序中的输入为 x,y,z ，为符合数学习惯，将系数命名为 a,b,c 。
代码：if((z*n-m-(x*z-1))%(y*z-1)==0) cnt++;
若 bc-1=0 则程序会发生 \color{red}{Runtime\,\,error} ，需要特判。
特别的，若 bc-1=0 ，则，
b=1,c=1
ax+y+z=n 1.
x+y+z=m 2.
解：将1.减去2.得 (a-1)x=n-m
∴x=\dfrac{n-m}{a-1} （若除不尽直接输出 0 ）
再用一重循环枚举 y,z 。
你若告诉我 a-1=0 的话……
先列出方程。
x+y+z=n
x+y+z=m
若 n≠m 直接输出 0 。
否则，
直接上排列组合。
排列组合——隔板法
将 n 个数分成 m 份共有多少种方案（每份个数为正整数）？
可以把这 n 个数排成一排：
1\,\,2\,\,3\,\,4\,\,5
插入 m-1 个板子将它们分成 m 份，
共有 n-1 处插入板子。
根据组合数，有 C_{m-1}^{n-1} 种选法。
很明显，这个问题与就是隔板法当 m=3 的时候的特殊情况：
但 x,y,z 都有可能为 0 。
所以还要把这种情况加上去：
当其中之二为 0 时：
cnt=3 （分别为 x=n,y=n,z=n 三种情况。）
当其中之一为 0 时：
cnt=3C_1^{n-1}=3(n-1)
当所有数都不为 0 时：
cnt=C_2^{n-1}=\dfrac{(n-1)(n-2)}{2}
所有情况：
cnt=3+3(n-1)+\dfrac{(n-1)(n-2)}{2}=\dfrac{n^2+3n+2}{2}
最后的完整代码不想写了
完整代码估计有三十几行（这么多行的代码当然算不上什么，但这是入门题啊）。
【例3】原材料加工
题面
这道题萌新一般用两重循环，而大佬直接套背包模版。
我来说一道萌新能理解，且不会太慢的方法。
优化
这个问题可以用动态规划解决（背包也是动态规划的一种）。
dp 由边界条件，状态转移方程两部分组成。
动态规划关键在于状态转移方程。
看看 dp_i 能等于什么？
可以等于 dp_{i-1}+1 ，
也可以等于 dp_{i-a} ，
还能等于 dp_{i-b} 。
而我们要选择哪个呢？
题目中让我们求最小的，所以我们选取的当然要是最小的。
代码：
for(int i=1;i<=n;i++){
dp[i]=min(min(dp[i-1]+1,dp[i-a]),dp[i-b]);
}
其实这道题用动态规划在某些时候还是不如两重循环的，当 n 与 a,b 差距不大的时候。
其实这道题用不上 dp ，可以直接优化成一重循环。
for(int i=0;i<=n;i+=a){
ans=min((n-i)%b,ans);
}
效率还远高于 dp .
所以我讲 dp 是干嘛？
背包
因为这道题太像背包了。
https://www.luogu.com.cn/problem/P1048
背包模版题。
核心代码：
for(int i=1;i<=m;i++){
for(int j=1;j<=t;j++){
if(a[i]<=j) dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+b[i]);
else dp[i][j]=dp[i-1][j];
}
}
分析：
有两种转移方式
- dp_{i,j}=dp_{i-1,j} 直接转移
- dp_{i,j}=dp_{i-1,j-a_i}+b_i 在前 a_i 秒采摘第 i 株草药，价值增加 b_i 。
而我们要取最大值，所以状态转移方程是：
dp_{i,j}=max(dp_{i-1,j},dp_{i-1,j-a_i}+b_i)
敲到代码里就行了。
写完了，终于写完了。
