算法竞赛备忘录

有些坑要记一下，应该不会忘，但是随便写写

---

ceil(a/b) with int

如果a,b均为int/long long，那么直接使用ceil(a/b)不行，因为a/b作为中间过程是int，会被trunc。

但是使用ceil((double)a / (double)b)还是不行，因为浮点数精度不行，总有你意想不到的奇怪意外。

用(a+b-1)/b来代替ceil()。原理是$$a=x*b+y$$，那么$\lceil\frac{a}{b}\rceil = \lfloor\frac{a+b-1}{b}\rfloor$，而int除法的floor是正确的。

Overflow

long long tp = a*a + b*b如果a,b均为int，是有可能溢出的，要保证a,b也是long long（至少 a*b时，a是long long）

Lambda

使用传值时会发生拷贝，因此[=](){}十有八九会导致TLE，要用[&](){}

使用lambda进行sort by index，并且不改变原本数组的排列

vector<int> dp(n);//dp有一些random value
vector<int> idx(n);
iota(idx.begin(),idx.end(),0);//equal to rep(i,0,idx.size())idx[i]=i;
sort(idx.begin(),idx.end(),[&](int a, int b){
	return dp[a]<dp[b];
});//使idx的内容变成dp从小到大的index值，即dp[idx[0]] <= dp[idx[1]] <= dp[idx[2]] <= ...

这样可以不修改原本的列，同等的写法需要：

vector<pair<int,int>> dp(n);//pair<index, value>
sort(dp.begin(),dp.end(),[](pair<int,int> a, pair<int,int> b){
	return a.second < b.second;
});//sort后会改变原本的数组