Kattis练习

Published: by Creative Commons Licence

  • Tags:

aplusb

题目

https://open.kattis.com/problems/aplusb

翻译

给定一个序列$a_1,\ldots,a_n$,问存在多少不同的互异下标$i,j,k$,满足$a_i+a_j=a_k$。这里$(i,j,k)$认为和$(j,i,k)$是不同的。这里$|a_i|\leq 5\cdot 10^4,1\leq n\leq 2\cdot 10^5$

题解

记$C(i)$表示值为$i$的元素在序列中出现次数。

首先下标要求不同太麻烦了,我们用容斥去除这个条件。记$A_{i,j}$表示所有满足$a_i+a_j=a_k$的下标组满足$i=j$的元素组成的子集,同理定义$A_{j,k}$和$A_{i,k}$。接下来我们要统计的实际上是:

\[\|\overline{A_{i,j}} \cap \overline{A_{i,k}} \cap \overline{A_{j,k}}\|\]

这个用容斥展开后,就很好算了。这里特别提一个就是全集怎么计算,即存在多少下标$i,j,k$,不要求互不相同,满足$a_i+a_j=a_k$。我们可以通过统计对于每个数$x$,存在多少不同的下标$i,j$,满足$a_i+a_j=x$(这个可以通过生成函数+FFT计算),之后将$f(x)C(x)$贡献到结果中。

总的时间复杂度为$O(n+M\log_2M)$。其中$M=10^5$。

airportcoffee

题目

https://open.kattis.com/problems/airportcoffee

题解

时限挺大的,可以直接上李超线段树。记$dp(i)$表示抵达第$i$个咖啡店最少费时。之后我们发现在这喝完咖啡后,会有速度会出现两段变化,找出这两段变化的区间,各插入一个线性函数即可。

时间复杂度为$O(n(\log_2n)^2)$。