C 设 为字符集大小。 因为是排列计数，所以考虑使用 而不是 。对于一种字符，我们列出它方案数对应的 如下: 那全部卷起来就是答案的生成函数： 接下来暴力展开式子，枚举后面那个多项式选了多少个 由于只关心 的大小，于是设 为前 个字符，选取 个字符的多项式相乘的答案。转移只需要考虑第 个选不选即可。这部分时间复杂度 。 现在式子变成了： 因为 的次数最高为 ，所以暴力展开 来卷。 但是如何快速求出 的第 项系数？第 项的系数就是长为 的序列，共有 种数可以放，最后能构成的序列的方案数。也就是 。然后要除以一个 表示为 形式。也就是： 乘 是为了抵消 中的...

多校信息汇总 https://ac.nowcoder.com/discuss/944978 活动具体内容比赛结束以后-9月19日,在牛客博客写 "蔚来杯"2022牛客暑期多校训练营3 的题解,并将题解链接发到本帖下。即可获得牛币~ 发放牛币的数量取决于题目难度，题目数量，题解质量 在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~我们将在9月19日审核，并给参与活动的同学发放10-100牛币 PS：如果题解写的非常好， 将会增加其获得的牛币如果题解写的非常水， 将会减少获得其获得的牛币如果题解有抄袭行为，将会取消其获得牛币的资格 如何开通牛客博客: http...

A 只需要预处理前后缀 ，然后枚举关键点 ，用前后缀的 再求一次 即可求出剩余关键点的 ，然后比较大小贡献答案。 #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 9; int n; int read() { int f = 0, x = 0; char ch = getchar(); while (!isdigit(ch)) { f |= (ch == '-'); ch = getchar(); } ...

A 发现随着时间的增加，凸包的每个顶点都是沿着角平分线移动。当两个相邻的顶点相交时，整个凸包的形状就会改变。 每次找到最近发生变化的顶点，可以通过距离计算出移动的时间。同样就能求出其他所有点移动距离从而求得新的凸包。 对于凸包形状不变的一段时间，面积是关于时间的一个二次函数，求出这个二次函数输出答案即可。 #include <bits/stdc++.h> #define P pair<double,int> #define fi first #define se second using namespace std; const int N = 1e5 + 9; con...

A 题面等价于找到一条最长的，恰好 条边的回路。 为了简化问题，不妨找到任意两个相邻的点，把环断成链。因为最后的路径肯定会跨过这条边，所以枚举跨过这条边的两个端点更新答案即可。 此时有个暴力的做法，设 为恰好 条边，从 走到 的最长路，转移式有： 这个可以矩阵快速幂加速，时间复杂度 。 观察式子形态，唯一可优化的就是用四边形不等式。所以我们试图证明对于任意 满足 。 我们在平面上依次连接 并让 和 交于点 ，可得 。两式加起来，就有 满足四边形不等式。而两个满足四边形不等式的状态合并起来仍然满足四边形不等式，于是我们可以用决策单调性解决这个问题。时间复杂度 。 #inc...

B 首先，如果要花费 的代价知道黑球数量，那么只会在最开始的时候使用且仅使用一次。所以策略有以下两种情况： 不花费 的代价，把所有的球打开代价是 。 花费 的代价知道所有黑球数量。无论怎么开球，球的颜色都相当于事随机的。那么不妨将 从小到大排序挨着开，知道有一个后缀是同一个颜色就不需要开了。代价是 。因为一个球不开当且仅当后面颜色都和它相等。 然后两者取最小值输出。 #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 9; int n; double C, w[N], sum, f = 1; i...

多校信息汇总 https://ac.nowcoder.com/discuss/944978活动具体内容 比赛结束以后-9月19日,在牛客博客写 "蔚来杯"2022牛客暑期多校训练营2 的题解,并将题解链接发到本帖下。即可获得牛币~ 发放牛币的数量取决于题目难度，题目数量，题解质量 在牛客博客中写题解，并回复地址，如果写了多篇题解，请在回复中说明~我们将在9月19日审核，并给参与活动的同学发放10-100牛币 PS：如果题解写的非常好， 将会增加其获得的牛币如果题解写的非常水， 将会减少获得其获得的牛币如果题解有抄袭行为，将会取消其获得牛币的资格 如何开通牛客博客: http...

B 首先，如果要花费 的代价知道黑球数量，那么只会在最开始的时候使用且仅使用一次。所以策略有以下两种情况： 不花费 的代价，把所有的球打开代价是 。 花费 的代价知道所有黑球数量。无论怎么开球，球的颜色都相当于事随机的。那么不妨将 从小到大排序挨着开，知道有一个后缀是同一个颜色就不需要开了。代价是 。因为一个球不开当且仅当后面颜色都和它相等。 然后两者取最小值输出。 #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 9; int n; double C, w[N], sum, f = 1; i...

补题写题解，即可得牛币https://ac.nowcoder.com/discuss/988926 A 首先简化一下题意，等价于有 个区间 ，定义两个区间连通当且仅当它们交集非空，你可以任意添加区间，求使得 个区间连通需要添加的最小区间长度和。 将所有区间按 排序，然后每个合并小区间得到的大区间可以表示为下标的一个连续段，填补大区间之间的空隙即可。 时间复杂度 。 #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 9; int ans, id[N], n, r[N], x[N]; int mai...

出题人视频讲解 https://ac.nowcoder.com/study/live/633点击下载 十场比赛标程与题解点击下载 题解集 以及 笔记（包含民间中文题面）  感谢 @欣君  整理与分享点击下载 十场比赛总排名 第一场 题解征集欣君视频讲解 第二场题解征集欣君视频讲解 第三场题解征集欣君视频讲解 第四场题解征集欣君视频讲解 第五场题解征集欣君视频讲解 第六场 题解征集欣君视频讲解 第七场 题解征集 欣君咕了（没有了） 第八场 题解征集欣君咕了（没有了） 第九场 题解征集欣君...

A 对于一个重量为 的物品，他的生成函数为 。 对于以 为根的子树，设答案的生成函数为 。那么如果要更新一个点的答案，先把他所有儿子的生成函数乘起来，求出前 项，然后直接剪掉即可。最后得到 ，用线性递推算第 项即可。 时间复杂度 #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 9; const int P = 998244353; int X[555], Y[555]; int len = 1, rev[N], ans[N]; vector<int> dp[111], e[1...

A 如果 问是不是大于 ， 回答是，就把 的数覆盖一遍，否则把 的数覆盖一遍，否则把 的覆盖一遍。 如果一个数被覆盖大于一次，就不可能是他 赢当且仅当只有一个数覆盖次数小于等于 发现大于 的可以舍去，有效状态只有一段 ，一段 ，再一段 . 设 表示依次有 个 ， 个 ， 个 。决策单调性可以优化到 。 发现答案是 级别，而且关于第三维单调。就可以把第三维和答案交换，优化到 。 #include <bits/stdc++.h> using namespace std; const int N = 2e3 + 9; int n, dp[24][N][N]...

A 先考虑怎么判断区间 排序后是否能构成等差数列。 假设最后构成等差为 的等差数列 ，充要条件就是： 。 如果最后能构成等差数列，就可以将数列 中每个元素减去 （这样仍是等差数列），然后除以次小值（最小值一定是 ），得到的一定是 的排列。否则，一定不能构成等差数列。 考虑第二个条件，可以用辗转相除法变成 ，设答案为 , 则两两的差一定是 的倍数。 问题就转化为 。 因为 ，所以用线段树维护这个值的最小值以及最小值个数。 每次移动右端点，可以用单调栈来维护极值，每个数只会弹出一次。若固定某个点为区间左端点，那么随着右端点的移动， 最多只会变化 次，因为每次减至少除以 。...

A 设 表示两堆石头数量分别为 时是必胜态（ ） 还是必败态（）。初始有 。因为能到达一种必败态的状态是必胜的，所以对于 的状态，暴力枚举 ，令 。这样的时间复杂度是 ，是过不了的！ 这里有一个结论，对于一个 ，只存在至多一个 使得 是必败态，证明如下： 若 都是必败态，因为 可以通过选择 转移到 ，所以 是必胜态，与假设矛盾。 这样时间复杂度就是 ，需要略微卡常。 #include <bits/stdc++.h> using namespace std; const int N = 5003; bool f[N][N]; signed main() ...