zcmimi's blog

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

avatar
zc
2020-05-05 00:18:00
查看原题

点击跳转

枚举变换情况(6!),然后kmp\Theta(n)判断即可

avatar
zc
2020-05-04 01:28:00
查看原题

点击跳转

容易发现,只要这个点与1之间存在某条路径长度(\le阶段数)+阶段数为偶数的,那1就得提供原材料

我们分别求出长度为奇数、偶数的最短路长度即可判断

avatar
zc
2020-05-03 21:39:00
查看原题

点击跳转

可以发现如果要字典序最小,那么就需要让靠前的数字变小

那么最终形成的平均数是递增的

可以用单调栈维护平均数递增

avatar
zc
2020-05-03 11:51:00
查看原题

点击跳转

交互题

我们从叶子节点开始搜索,把所有叶子节点添加到队列中

每次从队列中弹出两个叶子节点,

如果lca为其中一个,那么这个lca就是树根

否则删除这两个节点,可能会形成新的叶子节点,加入队列

因为最坏情况下每次都会删掉两个节点,那么重复\frac n2次后,也就只剩下根节点了

avatar
zc
2020-05-03 11:09:00
查看原题

点击跳转

可以发现有三种路径:

  1. a \leftrightarrow b

  2. a \leftrightarrow x \leftrightarrow y \leftrightarrow b

  3. a \leftrightarrow y \leftrightarrow x \leftrightarrow b

只需要判断这三条路径是否满足就可以了

可以发现只要dis\le k而且和k同奇偶就是符合的

(比如x\leftrightarrow y可以一直循环,变成x\leftrightarrow y \leftrightarrow x \leftrightarrow y \dots,每次长度+2)

avatar
zc
2020-05-03 01:04:00
查看原题

点击跳转

暴力枚举即可

avatar
zc
2020-05-02 23:47:00
查看原题

点击跳转

可以发现110\leftrightarrow 011相当于0前/后移动了2格,那么每个0位置的奇偶性是不变的

而且每个0无法移动到下一个0的后面

把这些0记录到一个序列里,然后通过哈希判断两个子串在序列中对应的部分是否相同

因为子序列的起点奇偶性不同,分别表示以起点为奇数和偶数为标准时哈希得的前缀0序列数组。

avatar
zc
2020-05-02 11:52:00
查看原题

点击跳转

ans={n\choose w_1}\cdot {n-w_1\choose w_2}\cdot {n-w_1-w_2\choose w_3}\cdots {n-w_1-w_2-\dots -w_{m-1}\choose w_m}

套扩展卢卡斯即可

avatar
zc
2020-05-02 11:42:00
查看原题

点击跳转

p=p_1^{k_1}p_2^{k_2}\dots p_n^{k_n}

求出每个{n\choose m} \equiv a_i \pmod {p_i^{k_i}}

得到同余方程组

\begin{cases} {n\choose m} \equiv a_1 \pmod {p_1^{k_1}} \\ {n\choose m} \equiv a_2 \pmod {p_2^{k_2}} \\ \vdots \\ {n\choose m} \equiv a_n \pmod {p_n^{k_n}} \end{cases}

使用crt即可求出n\choose m的值

p^t不是质数,那么如何求{n\choose m} \mod p^t呢?

可以计算{n\choose m}=\frac{n!}{m!(n-m)!},分别计算出n!,m!,(n-m)!在模p^t意义下的值

假设p=3,t=2,n=19,

n!=1\cdot 2\cdot 3\cdots 19 \\ =(1\cdot 2\cdot 4\cdot 5\cdot 7\cdot 8\cdot 10\cdot 11\cdot 13\cdot 14\cdot 16\cdot 17\cdot 19)\cdot (3\cdot 6\cdot 9\cdot 12\cdot 15\cdot 18) \\ =(1\cdot 2\cdot 4\cdot 5\cdot 7\cdot 8\cdot 10\cdot 11\cdot 13\cdot 14\cdot 16\cdot 17\cdot 19)\cdot 3^6\cdot(1\cdot2\cdot3\cdot4\cdot5\cdot6)

可以发现后面的部分相当于\left\lfloor \frac np \right\rfloor!,递归计算即可

前半部分以p^t为周期,即

1\cdot 2\cdot 4\cdot 5\cdot 7\cdot 8 \equiv 10\cdot 11\cdot 13\cdot 14\cdot 16\cdot 17 \pmod {3^2}

只需要计算不满足周期的数19就可以了

avatar
zc
2020-04-28 17:21:00
查看原题

点击跳转

可以发现答案是递减的

每个q_i相当于破坏掉[1,q_i]的最大值

那么我们把[1,q_i]区间-1

将最大值变为p_k的时候,相当于[1,k]的最大值都变成了p_k

那么把[1,k]区间+1

每次询问的时候,一直将当前最大值-1,应用变化,直到区间最大值大于0,输出答案

具体看代码

11/65
Search
search