A 考虑如何快速计算 f(x)f(x)f(x) ，若把 xxx 差分一下，则需要最后序列全 111 。而每次修改相当于改变两个或一个地方的值。 令 w=∑i=1k−1[xi=xi+1]w=\sum_{i=1}^{k-1}[x_i=x_{i+1}]w=∑i=1k−1​[xi​=xi+1​]，则 f(x)=⌈w2⌉f(x)=\lceil\frac{w}{2}\rceilf(x)=⌈2w​⌉。 把上取整换成 12(w+w mod 2)\frac{1}{2}(w+w\ \rm mod\ 2)21​(w+w mod 2) ，分开计算。 对于前者，枚举子序列中的一对...

A 考虑容斥。如果把每对不合法的相邻的 au,ava_u,a_vau​,av​ 连起来的话，发现是若干个连通块。 那么设 f(x,i)f(x,i)f(x,i) 表示 xxx 子树内，xxx 所在联通块 bib_ibi​ 最小值为 iii 。（这样的话，这个连通块有 iii 种取值可以连起来）。 转移考虑子树合并。 不把儿子 yyy 并上来，有 f′(x,i)=f(x,i)×∑j×f(y,j)f'(x,i)=f(x,i)\times \sum j\times f(y,j)f′(x,i)=f(x,i)×∑j×f(y,j) 把儿子 yyy 并上来 儿子 yyy 所在连通块最小值大于 xxx 所在...

A 若最终序列长为 mmm ，对于数字 iii ，至少填 ⌈mai⌉\lceil\frac{m}{a_i}\rceil⌈ai​m​⌉ 次 。那么理论上只需满足 ∑i=1n⌈mai⌉≤m\sum_{i=1}^n \lceil \frac{m}{a_i}\rceil\leq m∑i=1n​⌈ai​m​⌉≤m 即 ∑i=1n1ai≤1\sum_{i=1}^n \frac{1}{a_i}\leq 1∑i=1n​ai​1​≤1 即可有解。而题目保证 ∑i=1n1ai≤12\sum_{i=1}^n \frac{1}{a_i}\leq \frac{1}{2}∑i=1n​ai​1​≤21​ 。所以考虑把 a...

 代码可以把id加到这个链接后面查看https://ac.nowcoder.com/acm/contest/view-submission?submissionId=后提交昵称题目标题先提交昵称后提交代码先提交代码鹿少年World Final? World Cup! (I)无敌暴龙6039159860281614独特的托尼在刷代码World Final? World Cup! (I)Hojstyer6041040060302170靓魄World Final? World Cup! (I)妈咪妈咪哄~6037007060369892XzyyicWorld Final? World Cup! (I...

出题人发成了博客，我在这边重新发一遍 原博客链接：https://blog.nowcoder.net/n/899c42c0093340da806279bc1ecc8cb6 A 本题数据范围较小，可以直接枚举每一天每一棵树的变化。 坑点：求第 mmm 天中午的状态实际上是进行了 m−1m - 1m−1 次变化（生长和剪切）。 时间复杂度：O(T×n×m)O(T \times n\times m)O(T×n×m)。 B 注意到 xxx 的取值不超过区间中数的个数，这说明区间中的数模 xxx 的余数必然可以得到：0,1,…,x−10,1,…,x-10,1,…,x−1 ，中的任意一个，这意味着答案只...

点击查看题解 增加字数增加字数增加字数增加字数 增加字数增加字数增加字数增加字数 增加字数增加字数增加字数增加字数 增加字数增加字数增加字数增加字数

邀请函：点击下载报名地址：点击查看总榜及各场比赛榜单：https://docs.qq.com/sheet/DTElPY2tDeG1FYVhP?tab=xiaz4q总排名规则：单场得分 = 100*(解题数/第一名的解题数)* (2*本场参赛队伍数-2)/(本场参赛队伍数+名次-2) 总排名积分取最高得分的5场之和，参赛不足5场的队伍，按所有参赛场次的得分之和计算。场次链接比赛时间文字题解视频题解第一场1月16日13:00-18:00出题人题解视频题解第二场1月18日13:00-18:00出题人题解视频题解第三场1月20日13:00-18:00出题人题解视频题解出题人讲题第四场1月30日13:0...

A 令 表示以 为左端点，最小的合法右端点。那么有 。考虑反证法，若 ，那么区间 包含 。所以 也合法，那么不满足 是最小的合法右端点。 于是双指针扫描，用 数组记录每个数字出现次数。时间复杂度 。 #include <bits/stdc++.h> using namespace std; long long n, m, s[100100], v[100100], cnt, ans; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >&gt...

本场模拟没有生硬的多合一，或者是坑人的套路题，有较强的思维性，基本是对照 noip2021 的难度出的。 对题面的一些问题影响了选手的参赛体验表示歉意。 另外 D 题数据似乎造水了qwq A. 博弈 xor-hashing 可能最近普及开来了，记得 PKUSC 和 ABC 都有考过啊。 另外，参考学习资料：link。 Part1 我们先来研究，在数组 确定的情况下，先手必胜的条件。 首先，当 的最小值只有 个的时候，显然先手必胜。 我们发现，只要 的最小值出现奇数次，那么先手就会必胜。 当 的最小值出现偶数次的时候，先手就不能第一个取最小值了，那么就可以把所有的最小值去掉，然后继续研...

A 由于答案是关于 的多项式。于是暴力搜索出 的解然后拉格朗日插值。具体地：$$ #include <bits/stdc++.h> #define ll long long using namespace std; const int P = 998244353; ll n, m, k, inv[5]; ll C(ll x, int t) { ll res = 1; for (int i = 0; i != t; i++) res = 1ll * res * (x - i) % P * inv[i + 1] % P; return res; } int ...

集训营简介 牛客OI赛前集训营，是牛客网为即将参加CSP、NOIP考生举办的赛前特训营。集合多名ICPC、APIO金牌选手联合出题，更全面的帮助选手提升能力，冲破短板。 高分命题团联合出题： ICPC、APIO金牌选手联合出题 比赛时间 2022年10月4日-10月15日 每周二、四、六，晚上普及组18:30-22:00，提高组18:00-22:00，各6场比赛，共12场比赛。 比赛难度 普及组 4题，提高组4题 参考正式赛难度 报名方式 1、普及组(六场比赛) 报名费用：100元/账号 ...

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

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

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