耕云种月

分类

格式整理(10) 题解(107)

/ 注册

全部文章（共117篇）

出题人题解 | #异或树#

原题解链接：https://ac.nowcoder.com/discuss/153563 按位处理+线段树合并。首先按位处理，那么问题转化为求一个子树内，权值大于xxx的，111（或000）的个数。可以对每棵子树建立一棵权值线段树，每个叶子节点维护两个值sizesizesize和cnt[]cnt...

2022-01-25

0 318

出题人题解 | #车站#

原题解链接：https://ac.nowcoder.com/discuss/153563 线段树+倍增+LCA。首先车站一定在所有铁路的经过的点的交集上，所以可以用线段树求出区间路径的交集，同时维护离路径交的两个端点最远的点。找到出了最远的两个点后，那么可以倍增求出车站的位置。具体地，线段树每个...

2022-01-25

1 297

出题人题解 | #动态连通块#

原题解链接：https://ac.nowcoder.com/discuss/153563 并查集+bitset+bitset+bitset优化。操作二可以在加边的过程中求出。即加入一条端点同色的边，并查集判断是否可以消去一个白（黑）连通块。操作三求的是x,yx,yx,y所在的两个白连通块都连出的...

2022-01-25

0 499

出题人题解 | #流星雨#

原题解链接：https://ac.nowcoder.com/discuss/153563 概率dpdpdp。设TiT_iTi为第iii天下雨的真正概率，由于第i天的概率只与第i−1i-1i−1天有关，所以有 Ti=Ti−1×(pi+P)+(1−Ti−1)×piT_{i}=T_{i-1} \tim...

2022-01-25

0 396

出题人题解 | #选点#

原题解链接：https://ac.nowcoder.com/discuss/153563 dfsdfsdfs序+LISLISLIS。因为根节点的权值最小，其次是右子树的点，最后是左子树的点，所以按照先根，再右子树，再左子树的顺序dfsdfsdfs整棵树，求出dfsdfsdfs序，在dfsdfsdf...

2022-01-25

0 232

出题人题解 | #走方格#

原题解链接：https://ac.nowcoder.com/discuss/153563 找规律。首先考虑斜着走，每走一步都会使横坐标和纵坐标的距离减111，可以持续这个操作使得两个点处在同一水平或者竖直的线上。此时每斜着走两步会使距离减222。所以如果它们的距离为偶数，那么可以按照两步两步的走...

2022-01-24

0 386

出题人题解 | #筱玛的D球#

原题解链接：https://ac.nowcoder.com/discuss/151505 按位考虑。我们可以使用树剖线段树维护所有logVlogVlogV个位的信息，计算出这一位为0/10/10/1时，最后的结果。复杂度O(log2nlogV)O(log2 n logV)O(log2nlogV),...

2022-01-24

0 366

出题人题解 | #筱玛的字符串#

原题解链接：https://ac.nowcoder.com/discuss/151505 使用DPDPDP，设f[i][j][k]f[i][j][k]f[i][j][k]因表示当前处理到S′′S''S′′的第iii位，在最终的S中左括号比右括号多jjj个，当前S′S'S′的状态为kkk，其中kkk的...

2022-01-24

0 283

出题人题解 | #筱玛的网格#

原题解链接：https://ac.nowcoder.com/discuss/151505 首先，不难发现对角线上的元素一定一样。那么我们就可以把n×mn \times mn×m的网格看成一个n+m−1n + m- 1n+m−1长度的序列。对于第二个valvalval价值的限制，从小到大填数就行了...

2022-01-24

0 410

出题人题解 | #筱玛的迷阵探险#

原题解链接：https://ac.nowcoder.com/discuss/151505 折半搜索。对对角线上每个结点开一个TrieTrieTrie。前 ⌊n2⌋\left\lfloor\frac{n}{2}\right\rfloor⌊2n⌋ 步搜出来的答案用TrieTrieTrie保存, 后 ...

2022-01-24

0 295