zcmimi's blog

categories/刷题记录/共659篇文章

avatar
zc
2020-01-21 10:36:00
查看原题

点击跳转

设当前区间为[l,r]

res=\sum_{i=l}^r p_i\times[\prod_{j=l,j!=i}^r(1-p_j)]

s_{[l,r]}表示\prod_{i=l}^r(1-p_i)

res=s_{[l,r]}\sum_{i=l}^r \frac{p_i}{1-p_i}

a_i=1-p_i,b_i=\frac{p_i}{1-p_i}

res=\prod_{i=l}^ra_i\sum_{i=l}^rb_i

假设现在区间变成了[l,r+1]

A=\prod_{i=l}^ra_i,B=\sum_{i=l}^rb_i

res'=A\times a_{r+1}(B+b_{r+1})

=A(a_{r+1}B+a_{r+1}b_{r+1})

=A(a_{r+1}B+p_{r+1})

res'>res,那么a_{r+1}B+p_{r+1}>B

1-p_{r+1}+\frac{p_{r+1}}B>1

\therefore B<1

那么对于每个l,只需要找到最远的r使\sum_{i=l}^rb_i<1

而这又具有单调性,那么\mathcal{O(n)}就可以解决了

avatar
zc
2020-01-20 23:48:00
查看原题

点击跳转

按斜率建图

然后跑背包

avatar
zc
2020-01-20 22:35:00
查看原题

点击跳转

A,B总和不相同,显然是-1

由于元素都大于0,可以使用类似双指针的方法

两个指针在A,B数组中移动,若找到A,B中和相同的两端,答案就+1

avatar
zc
2020-01-20 21:57:00
查看原题

点击跳转

结论:

x^{\frac14}内的因子筛掉,剩下的x一定是完全立方数或者不可化简

证明:

若存在p>x^{\frac14}b\times p^3=x,那么b>x^{\frac14}b=1

\because b>x^{\frac14} \therefore b\times p^3 >x,不符合

\therefore b=1,x为完全立方数

实现:

  1. 先筛出(10^{18})^{\frac14}(\approx31650)内的质数

  2. 筛掉x^{\frac14}内的因子,筛的过程中统计有没有立方

  3. 判断x是不是完全立方数(pow(x,1.0/3)^3+eps==x四舍五入)

avatar
zc
2020-01-20 10:19:00
查看原题

点击跳转

先排序

从小到大添加

如果有以a_i-1的组,那么a_i必然添加在目前以a_i-1结尾的组的末尾

否则新建一个组

可以使用 桶+堆 实现

avatar
zc
2020-01-20 07:57:00
查看原题

点击跳转

最短路松弛的比较方式变为d_x+w\le d_{to}

记得long long

avatar
zc
2020-01-19 23:55:00
查看原题

点击跳转

avatar
zc
2020-01-19 21:11:00
查看原题

点击跳转

f[k][i][j]表示前k种面值,Ai元,Bj元最少交换几张

avatar
zc
2020-01-19 14:13:00
查看原题

点击跳转

我们可以把每对x,y都看成边

如果当前x,y已经连通,那么当前客人一定会悲伤(相当于加上x\leftrightarrow y后形成了环,显然没法实现)

那么答案+1

可以用并查集实现

avatar
zc
2020-01-19 12:25:00
查看原题

点击跳转

直接按照规则建图后跑最短路

26/66
Search
search