WORIA

https://ac.nowcoder.com/acm/contest/7141/A 题意：给定一棵树，多次询问，每次询问给定一个点集，定义某点到点集的距离为它到点集中所有点距离的最大值。问树上所有点到这个点集的距离的最小值。 最重要的一点要看出来，最终这个点就在这个点集中最远点对形成的链的中心。 做法一： 我们知道找树的直径有一种贪心做法，先找任意一点，找到离他最远的点 x，再找到距离 x 最远的点 y，则 (x,y) 就是一条直径。 由这种做法不难得出，必定有一条直径经过深度最大的点（把树根作为这个“任意一点”）。这是对于一棵完整的树而言，本题对于树上的一个点集，同样有这个结论，至于原因，知道虚树的应该不难想到。所以可以遍历点集中所有点，找到深度最大的点，再遍历点集找出距离该点最远的点。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include<bits/stdc++.h> ...

https://ac.nowcoder.com/acm/contest/11169 D - 回文字D   题意：定义D型回文串：若长度小于D，则必是；否则，对于任意长度为D的连续子串，必须是回文串。给定D，串 S，要分割成 kkk 个连续子串，满足每个子串都是D型回文串，问最小的 kkk。 贪心+字符串哈希 假设用dp，则 dp[i]=min⁡j<i且S[j+1⋯i]为D型回文串(dp[j])+1dp[i]=\min\limits_{j<i且S[j+1\cdots i]为D型回文串}(dp[j])+1dp[i]=j<i且S[j+1⋯i]为D型回文串min​(dp[j])+1。 又容易发现 dp[i]dp[i]dp[i] 必是递增的，所以上面这个dp实际上就是贪心选最长的D型回文串 S[j⋯i]S[j\cdots i]S[j⋯i]。 所以直接从头开始匹配最长的D型回文串即可。 匹配固定长度D的回文串可以用字符串哈希，正着哈希值等于反着哈希值，说明是回文串。 123456789101112131415161718192021222324252627282930313233 ...

https://ac.nowcoder.com/acm/contest/11168 E - CCA的区间   题意：给定一个数列 a,1≤ai≤223a,1\le a_i\le 2^{23}a,1≤ai​≤223，每个数都是 2 的幂次，最多可以翻转一个区间，要找出一个内部不含相同元素，且区间和最大的区间，问区间和。 SOSdp 可以翻转一个区间，所以问题变为求两个不含相同元素的区间，区间和最大。 由数据范围发现可以把每个区间进行状压，遍历左端点可以得到所有不含相同元素的区间状压为数。 接下来就要找到两个and等于0的数，和最大。 dp[x]dp[x]dp[x] 表示 xxx 的所有子集的最大值。 由 FMT 的技巧可以得到转移： 设 dp[i][x]dp[i][x]dp[i][x] 表示与 xxx 只有前 iii 位可能不同的所有数字 y,(y∈x)y,(y\in x)y,(y∈x) 的最大 dpdpdp 值，则 dp[i][x]= \begin{cases} dp[i-1][x], & \text {if x&$2^i$=0} \\ \max(dp[i-1][x],dp[i-1][ ...

https://ac.nowcoder.com/acm/contest/10845 E - 牛牛数数   题意：给定 n 个数字，用其中任意一个非空子集的异或和得到数字 x，问有多少种 x 大于给定数 K。 线性基+二分 线性基求第 k 大模板。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091#include <bits/stdc++.h>#define debug(x) cout << #x << ":\t" << (x) << endl;using namespace std;#define ll long long#define ull unsigned llconst int N = 2e6 + 10;c ...

https://ac.nowcoder.com/acm/contest/10507 C - 宝石街   题意：给定一个数组，从左往右走，每次可以拿不超过 a[i]a[i]a[i] 个宝石或扔掉任意个宝石，设在某点拥有宝石总数为 kkk，则到达下一点需要时间也是 kkk，问在 ttt 时间内，最多拿多少个宝石，不需要到终点。 尺取法 如果最终停在 iii 点，则 aia_iai​ 必定都拿，ai−1a_{i-1}ai−1​ 也是尽量多拿，ai−2a_{i-2}ai−2​ 也是，以此类推。 所以对于每点，需要算出最左从哪点开始拿。可以知道这个点是随着 iii 而递增的。 所以尺取，或者双指针。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include <bits/stdc++.h>#define debug(x) cout << #x <&l ...

https://ac.nowcoder.com/acm/contest/8282 C - brz的序列   题意：给定一个数列，每次操作选择一个数变成左右两个数的平均数，可以进行任意次操作，问数列总和最小是多少？ 单调栈 当一个数列是等差数列时，操作不会改变任何数，否则一定可以继续变小。 所以就是要把原数列变成一些等差数列。 以 (i,ai)(i,a_i)(i,ai​) 为点，在同一个等差数列中表示在同一条直线上。 画图能发现就是要找到一个下凸包。 这样把等差数列变成凸包，再用单调栈维护也算是套路了，要记住。 12345678910111213141516171819202122232425262728293031#include <bits/stdc++.h>#define debug(x) cout << #x << ":\t" << (x) << endl;using namespace std;#define ll long longconst int N = 2e6 + 10;const int ...

https://ac.nowcoder.com/acm/contest/7329 E. 子串   题意：给出一个长度为 nnn 排列 pip_ipi​，规定一个区间 [l,r](l<=r)[l,r] (l<=r)[l,r](l<=r) 是 fair 的，当且仅当区间中最小值等于 lll 并且最大值等于 rrr，求 fair 区间的个数。 单调栈+二分+扫描线+树状数组 fair区间可以理解为一堆连续的数打乱后放在这个区间里。 对于一对 (x,pos[x])(x,pos[x])(x,pos[x])，如果一个区间的一端在该范围内，另一端不在，那么这个区间一定不合法。因为这个区间就不能够包含等于下标的所有数。 对于每个左端点，合法的右端点必须满足区间范围内的最小值不能小于左端点位置的下标。 对于每个右端点，合法的左端点必须满足区间范围内的最大值不能大于右端点位置的下标。 以对每个右端点求合法左端点范围为例：从小到大遍历作为右端点，因为我们需要的是恰好不合法的点，所以单调栈中维护从大到小，在单调栈里二分，得到位于边界的位置。 对于一个合法区间，等价于满足左端点在右端点的合法范 ...

https://ac.nowcoder.com/acm/contest/7079 D - 牛牛的粉丝   题意：环上 n 个位置，每个位置有 x[i]x[i]x[i] 个人，每个人独立，有 p1p_1p1​ 的概率顺时针移动，p2p_2p2​ 概率逆时针移动，p3p_3p3​ 概率不动。问移动 kkk 轮后，每个位置上的人数的期望。3≤n≤500,0≤k≤1018,xi≤1063≤n≤500,0≤k≤10^{18},x_i≤10^63≤n≤500,0≤k≤1018,xi​≤106 矩阵快速幂+循环矩阵 每个人都是独立的，所以可以分别考虑每个人最终移动到各个位置上的概率。 假设 一个人初始在位置 0 ，f[i][j]f[i][j]f[i][j] 表示第 iii 轮后这个人在位置 jjj 的概率。 转移方程为 f[i][j]=p1f[i−1][j−1]+p2f[i−1][j+1]+p3f[i−1][j]f[i][j]=p_1f[i-1][j-1]+p_2f[i-1][j+1]+p_3f[i-1][j]f[i][j]=p1​f[i−1][j−1]+p2​f[i−1][j+1]+p3​f[i− ...

https://ac.nowcoder.com/acm/contest/6885 D - 牛妹爱数列   题意：给定一个01序列，两种操作：翻转某一位；翻转第一位到某一位所有位。问最少几次操作使得变为全 0. dp 做法一：翻转某一个区间需要 2 次操作。考虑枚举翻转的块的大小，则需要枚举所有 1 到 i-1，需要再化简dp式子，用一个 mn 记录前面的值。 123456789101112131415161718192021222324#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const int N = 2e6 + 10;const ll mod = 1e9 + 7;int n;int dp[N], a[N], s[N];int main() { scanf("%d", &n); for (int i = 1; i <= n; ...

https://ac.nowcoder.com/acm/contest/6112 E - 骚区间   题意：定义一个区间是骚的，当且仅当区间左端点是次小值，右端点是次大值。给定一个排列，问有几个骚区间。 权值线段树+树状数组 虽然这里线段树完全没必要。。 假设已经知道了每个点右边最近的两个比它小的数，以及左边最近的比它大的数。则可以一遍遍历左端点，一遍更新右端点同时统计可行区间。 具体方法为遍历每一位作为区间左端点，并且找到满足当前位置在右端点的两个左边比它大的数之间的右端点，这可以通过树状数组求得两个前缀的差得到一个区间的右端点个数。在移动到下一个左端点前更新满足条件的右端点。 再考虑求每个点右边最近的两个比它小的数，以及左边最近的比它大的数。这可以通过一边遍历一边插入权值线段树实现，并改变一次值来获得第二近的位置。 但是实际上可以用set实现，通过遍历权值，可以保证已经存在set里的位置上都是小于当前的数，只要upperbound找最近的大于的位置即可，再指针++就是第二近的位置。找左边较小的可以存负值类似实现。 1234567891011121314151617181920212 ...