简单计算
题解
$sumlimits_{i=0}^{i<=p}large lfloor frac {i*q}{p} floor$
$sumlimits_{i=0}^{i<=p}large lfloor frac {i*q}{p} floor$*2可转化
$lfloor frac {i*q}{p} floor lfloor frac {(n-i)*q}{p} floor$
考虑转化,本来是两部分加和完整的,=q,现在拆成两部分如果i*q不能整除那么最终贡献就是q-1,否则贡献就是q
那么考虑容斥,先不考虑整除答案就是q*(p+1)先把所有贡献-p-1,最后再加上可以整除就是gcd(p,q),再算上0的情况+1
所以答案就是$frac{q*(p+1)-p+gcd(p,q)}{2}$
格式化
题解
考虑贪心,如果a<=b那么按照a从小到大排序,如果a>b按照b从大到小排序
证明第一个,因为都是做正贡献所以越小越好,因为买大的可能会需要多花钱买,
例如2 3
3 4
先买3 4需要3代价,再买2 3,多出来贡献浪费了
先买2 3 再买3 4可以只花2
证明第二个,因为肯定是做副贡献,但是还是有贡献的,因为所有必须都要选,如果最后选相对贡献大的,多出来的贡献会造成浪费
分组配对
题解
倍增+二分
倍增减少二分次数
因为check时间复杂度过于大(n*log(n))
一个一个区间拓展极限情况就每一个点是一段这样二分次数logn,check(n*logn),然后每个点进行上述操作$n^2*{log}^2$
倍增一点一点前进减少次数,第一次不符合情况下在最后一次符合-第一次不符合之间二分
复杂度正确(不是优化复杂度是避免了最差复杂度)