原题解链接：https://ac.nowcoder.com/discuss/153563 线段树+倍增+LCA。 首先车站一定在所有铁路的经过的点的交集上，所以可以用线段树求出区间路径的交集，同时维护离路径交的两个端点最远的点。找到出了最远的两个点后，那么可以倍增求出车站的位置。 具体地，线段树每个节点维护u,v,du,dv，u,vu,v,du,dv，u,vu,v,du,dv，u,v是路径交，du,dvdu,dvdu,dv是分别是距离u,vu,vu,v最远的点。合并两个区间的过程是先对两个区间的路径求路径交，然后新的du,dvdu,dvdu,dv一定是两个区间中四个du,dvdu,dvdu,d...

原题解链接：https://ac.nowcoder.com/discuss/153563 并查集+bitset+bitset+bitset优化。 操作二可以在加边的过程中求出。即加入一条端点同色的边，并查集判断是否可以消去一个白（黑）连通块。 操作三求的是x,yx,yx,y所在的两个白连通块都连出的黑点（假设x,yx,yx,y是白色，黑色的情况是一样的）。 于是可以bitsetbitsetbitset维护每个白联通块连出的黑点，黑连通块连出的白点。每加入一条端点异色的边，在两个白、黑连通块的bitsetbitsetbitset中将一个位置设为111；加入一条端点同色的边，就是合并白（黑）连通块...

原题解链接：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} \times\left(p_{i}+P\right)+\left(1-T_{i-1}\right) \times p_{i}Ti​=Ti−1​×(pi​+P)+(1−Ti−1​)×pi​ 复杂度：加上求逆元的复杂度，O(nlogn)O(nlogn)O(nlogn) #include<cstdio&gt...

原题解链接：https://ac.nowcoder.com/discuss/153563 dfsdfsdfs序+LISLISLIS。 因为根节点的权值最小，其次是右子树的点，最后是左子树的点，所以按照先根，再右子树，再左子树的顺序dfsdfsdfs整棵树，求出dfsdfsdfs序，在dfsdfsdfs序上求最长上升子序列。 复杂度O(nlogn)O(nlogn)O(nlogn) #include<cstdio> #include<algorithm> #include<iostream> using namespace std; const int N = ...

原题解链接：https://ac.nowcoder.com/discuss/153563 找规律。 首先考虑斜着走，每走一步都会使横坐标和纵坐标的距离减111，可以持续这个操作使得两个点处在同一水平或者竖直的线上。此时每斜着走两步会使距离减222。 所以如果它们的距离为偶数，那么可以按照两步两步的走过去，否则先到达终点旁边的格子，再花费一次上下左右走的次数，到达终点。 复杂度O(1)O(1)O(1)  #include<iostream> #include<algorithm> using namespace std; int main() { long long n,...

原题解链接：https://ac.nowcoder.com/discuss/151505 按位考虑。 我们可以使用树剖线段树维护所有logVlogVlogV个位的信息，计算出这一位为0/10/10/1时，最后的结果。复杂度O(log2nlogV)O(log2 n logV)O(log2nlogV),难以通过此题。 我们可以将646464位的状态信息压在两个unsigned long longunsigned \ long \ longunsigned long long中，利用位运算O(1)O(1)O(1)维护所有位的信息。复杂度O(log2n)O(lo...

原题解链接：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的意义如下: 1.没有反转 2.正在反转 3.反转完成 转移讨论当前这一位在S′S'S′中是什么，结合kkk即可得出jjj的变化。 #include<bits/stdc++.h> #define Mod 1000000007 #define N 5005 using namespace s...

原题解链接：https://ac.nowcoder.com/discuss/151505 首先，不难发现对角线上的元素一定一样。 那么我们就可以把n×mn \times mn×m的网格看成一个n+m−1n + m- 1n+m−1长度的序列。 对于第二个valvalval价值的限制，从小到大填数就行了。 先填‘（’，DPDPDP出填了以后有多少答案;如果>K> K>K则继续，否则KKK减去这个方案数，然后填上右括号。  #include<bits/stdc++.h> #define pi pair<int,int> #define mk make_pai...

原题解链接：https://ac.nowcoder.com/discuss/151505 折半搜索。 对对角线上每个结点开一个TrieTrieTrie。前 ⌊n2⌋\left\lfloor\frac{n}{2}\right\rfloor⌊2n​⌋ 步搜出来的答案用TrieTrieTrie保存, 后 n−⌊n2⌋n-\left\lfloor\frac{n}{2}\right\rfloorn−⌊2n​⌋ 步的答案在TrieTrieTrie上寻找最大值。 时间复杂度 O(2n2log⁡A)\mathcal{O}\left(2^{\frac{n}{2}} \log A\right)O(22n​logA...

原题解链接：https://ac.nowcoder.com/discuss/151505 显然n≠1n≠1n​=1且n mod 4≠0n \,mod\, 4 ≠ 0 nmod4​=0时答案为000, n=1n=1n=1答案为111。 下面考虑 n mod 4=0n \,mod \,4 = 0 nmod4=0的情况： 假设 at=ta_{t}=tat​=t, 取 i=j=ti= j=ti=j=t 有 2t=n+12 t=n+12t=n+1 。 这时nnn是奇数,矛盾。 若 at=n+1−ta_{t}=n+1-tat​=n+1−t, 取 i=n+1−t,j=ti=n+1-t, j=ti=n+1...

原题解链接：https://ac.nowcoder.com/discuss/151505 显然，只考虑月份和日期，合法的回文日期只有"01−10”、“02−2"、“03−30∗、“10−01”、“11−11”"01-10”、“02-2"、 “03-30*、 “10-01”、 “11-11”"01−10”、“02−2"、“03−30∗、“10−01”、“11−11”和“12−21"“12-21"“12−21",共666种。 而合法的质数年份也相当有限，只有926926926种。 因此，我们可以直接打出合法年份的表,令t=k−1t= k- 1t=k−1，通过⌊t6⌋\left\lfloor\fra...

原题解链接：https://ac.nowcoder.com/discuss/151166 计算几何。 只要叉积维护一下前缀和就好了。 #include <cstdio> #include <bits/stdc++.h> #include <map> #include <cstring> #include <algorithm> using namespace std; #define mst(a,b) memset((a),(b),sizeof(a)) #define rush() int T;scanf("%d",&T);w...

原题解链接：https://ac.nowcoder.com/discuss/151166 二分 首先我们明确一点,如果要放障碍物000号方格左右最多放一个，因为只要碰到一个就不会继续走过去了，也就是说放置多个障碍物只有最靠近0号方格的是有意义的。 此外因为要保证最后一次到达没到过的地方，不可能两侧都放，因为这样的话要不就是不满足题意，要不就是其中一个障碍没有意义，所以障碍物的上限是111个。 然后如果最后一个指令为L/RL/RL/R,那么障碍物要放一定放在0 00号方格右侧/左侧。且以障碍物放在000号方格右侧为例，如果障碍物放在xxx处满足题意的话，放在x−1x-1x−1这个位置也是满足题意...

原题解链接：https://ac.nowcoder.com/discuss/151166 因为A，BA，BA，B是随机的，所以分块维护一下颜色即可。 当然用其他方法也可以，验题人表示还可以用一个set/mapset/mapset/map存下所有的相同的段，每次把[l,r][l,r][l,r]这一段分离出来，然后把这一段里面的相同段修改之后合并成一段。 #include <cstdio> #include <bits/stdc++.h> #include <map> #include <cstring> #include <algorithm...