zcmimi's blog

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

avatar
zc
2020-01-23 12:40:00
查看原题

点击跳转

f[i]=\max{f[t-r]+p}

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

点击跳转

f_n表示n个节点可以构成的二叉树的个数,g_n表示n个节点可以构成的二叉树的叶子节点的总数

打表: 可以发现g_n=nf_{n-1}

证明: 对于每棵有n个节点的二叉树,若它有k个叶子节点,删去后可以得到kn-1个节点的二叉树,而这kn-1个节点的二叉树每棵都有n个位置可以放置新的叶子节点

f_1=1\\ f_n=\sum_{i=1}^{n-1}f_if_{n-i-1}

f其实就是卡特兰数

代入ans=\frac{g_n}{f_n}得到\frac{n(n+1)}{2(2n-1)}

avatar
zc
2020-01-22 17:49:00
查看原题

点击跳转

g(x)=(1+x+x^2+x^3+...+x^{num_1})(1+x^2+x^4+...+x^{2num_2})(1+x^5+x^{10}+x^{15}+...+x^{5num_3})

avatar
zc
2020-01-22 17:05:00
查看原题

点击跳转

g(x)=(1+x+x^2+x^3+...)(1+x^2+x^4+x^6+...)(1+x^3+x^6+x^9+...)...

模拟一下

\Theta(n^2)

avatar
zc
2020-01-22 09:44:00
查看原题

点击跳转

直接模拟,把平衡树当做可以\Theta(\log n)访问并删除任意位置的链表

avatar
zc
2020-01-21 16:39:00
查看原题

点击跳转

排序后动态规划

f[i][j]表示前i个女生,至少有j个比男生高

f[i][j]=(f[i-1][j]+f[i-1][j-1]\times(p-j+1))\times(n-i)!(p表示有p个男生比前i个女生矮)

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四舍五入)

24/65
Search
search