数学应用
P1348 Couple number
这里给大家演示一下平方差公式化简的步骤
(a+b)(a-b) =a(a-b)+b(a-b) =a^2-ab+ab-b^2 =a^2-b^2
∴ 由此式反推回去
a^2-b^2=(a+b)(a-b)
a+b与a-b奇偶性一定相同
证明：
a+b-(a-b)=a+b-a+b=2b
∵b是整数，∴2b一定是偶数
∴a+b与a-b奇偶性相同
那么，出现Couple number数有两种情况：a+b为奇数或a+b为偶数
如果a+b是奇数，奇数乘奇数一定还得奇数，这是情况①
如果a+b是偶数，偶数乘偶数一定是4的倍数，这是情况②
综上所述，Couple number必须符合是4的倍数或是奇数中的一种
那么只需要枚举Couple number,时间复杂度为O(n1-n2)
题目保证n1-n2<1e7,所以不用担心TLE
----by 洛谷 张文奕
https://www.luogu.com.cn/problem/P1348模拟
P2628 冒险岛
在windows和linux系统中，getline的表现是不一样的。虽然模糊的知道这个知识点，但不求甚解的结果跟完全不知道也没有什么不同。smallC233这位洛谷用户在题解中提到： getline 是遇到 \n 停止，而洛谷生成的输入数据中，换行是 \r\n 。在 Windows 系统下， \r\n 被读取的时候，会被系统自动换化成 \n 。也就是说，在输入文件中的 \r\n 被 getline 到 string 之后，其实就只有一个 \n 了。但评测机使用的是 Linux 系统，\r\n 不会被处理，所以 \r 会被读入字符串当中，字符串长度因此会多一位，导致出错。因此我们需要特判一下：
getline(cin,s);
int len=s.size()-1; //len是字符串总长度
if(s[len]=='\r'){len--;} //如果最后一位是'\r'就把它砍掉另外，题目中的奖励制度明确了需要连续3个箭头(含当前格)，但惩罚制度并没有明确这个要求，实际上，也是需要连续3个星号(含当前格)时，才触发惩罚。
https://www.luogu.com.cn/problem/P2628递推
P1358 扑克牌
自己用递推的时候错了两个点，最后参考题解，利用杨辉三角形解决的，初中的知识在几十年后终于派上了用场。也是有始有终~
https://www.luogu.com.cn/problem/P1358但题目中的有一部分没怎么看懂，虽然题解也对剩余纸牌进行了判断，数量不足就break，但并没有对sum重新进行赋值，而输出答案却变成了0，而不是中途半端的值。打印了数组看了一下，发现问题的答案在数组里，当坐标x小于y的时候，数组中的值都是“0”，乘上之后，答案就自然变为了“0”，非常的巧妙。
#include<iostream>
using namespace std;
int n,m,tmp,sum=1;
int res[10005][105];
int main(){
res[0][0]=1;
cin >> n >> m;
for(int i=1;i<=10001;i++){
for(int j=0;j<=101;j++){
res[i][j]=(res[i-1][j-1]+res[i-1][j])%10007;
}
}
//杨辉三角形输出演示
for(int i=0;i<20;i++){
for(int j=0;j<20;j++){
cout << " " << res[i][j];
}
cout << endl;
}
//演示结束
for(int i=0;i<m;i++){
cin >> tmp;
sum=sum*res[n][tmp]%10007;
n-=tmp;
if(n<0)break;
}
cout << sum;
}前缀和
https://www.luogu.com.cn/problem/P1599动态规划
P1115 最大子段和
https://www.luogu.com.cn/problem/P1115 P1164 小A点菜
https://www.luogu.com.cn/problem/P11641359 租用游艇
https://www.luogu.com.cn/problem/P1359