1.判重可以用bool数组来实现,对每个元素进行标记
2.二分一定排序!二分一定排序!(昨天就因为排序错了)
3.任何判断质数都可以优化,也可以直接使用合数为质数成对出现这一结论
3.例子
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
int res = 0;
for(int i = 2; i <= n; i ++)
{
if (n % i == 0)
{
printf("%d", n / i);
break;
}
}
return 0;
}
4.max函数中如果两数一样大则返回两数随机值,因此需要注意
5.对于相邻交换求次数可以根据冒泡排序的思路,前面有几个数比X小则有几次交换
5.EG
#include <iostream>
using namespace std;
int n, sum;
int main()
{
cin >> n;
int a[n];
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n; ++i)
for (int j = 0; j < i; ++j)
if (a[j] > a[i])
++sum;
cout << sum;
return 0;
}
6.抽屉原理的使用,抽屉原理:n+1 个苹果放在 n 个抽屉里,那么至少有一个抽屉中会放两个苹果。
6.eg https://www.acwing.com/problem/content/submission/code_detail/23278900/
7.火车问题的整理相遇问题:路程和=时间×速度 和 火车过桥问题:总路程=车长+桥长
8.倍增思想
让我们需要一次次循环增加时,因为我们每次都会加一个数,当数据范围过大就会拖慢时间,此时就可以使用倍增优化。比如我们要找到第一个>=1e9的数,每次加5,显然太慢,此时我们就可以倍增每次*10,之后再减去多余的
8.eg https://www.luogu.com.cn/problem/P1909
9.线性筛法
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
三角形速判:在一个三角形中,如果较短的两条边的平方和大于最长边的平方,那么这个三角形是锐角三角形,否则它是钝角三角形。