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

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

多校信息汇总 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; int m...

补题写题解，即可得牛币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 main()...

出题人视频讲解 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[111]; ...

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

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

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

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

qwq 儿童节比赛结束啦，我们的特别奖是涂鸦T恤，这次一共涂了5件   给大家展示一下牛客竞赛带艺术家们的成果   客户1需求：希望把我们暑期多校的T恤涂了，三个工作人员分别涂一件，涂的越满越好   成果：   1.qcjj赤果果     2 兰子田鼠小埋鸭     3 植物大战网络流     反面 荷塘涟漪金鱼      客户2需求：可以画仙贝吗？    成果：      客户3需求：pljj！   成果：            对比图：

特别小活动：分享多校报名链接（https://competition.nowcoder.com/1/introduce ）   至 朋友圈/ QQ空间 / 非牛客算法群（群人数50以上），将分享截图发至本帖   即可 参与抽奖“牛可乐背包”，每满15楼抽取1人赠送！~~   中奖后我们会加QQ或者微信好友做验证，请勿截图后直接就删除或者撤回。               顶尖命题团队：国内ACM顶尖选手和IOI国家队成员命题   知名选手答疑：出题大佬视频讲解比赛题目，答疑解惑。   报名赠送T恤： 每个报名队伍将获赠3件牛客T恤。           报名&比赛时间：   报名时间：...

点击查看题解