为保证比赛公平公正，营造健康积极的竞赛环境，我们采取以下措施： 1.赛后对代码系统查重+人工查重，不同账号相似度100%的提交直接算违规处理，不区分提交先后。某些简单的签到题视情况处理。相似度80%以上进行人工核对。赛后提交代码全部公开，接受用户投诉。（相似度非文本比较） 2.同一用户使用多账号提交相同代码也按违规处理。 3.比赛期间在互联网寻求题目答案按违规处理，接受用户举报。（包括向gpt等AI工具求助答案） 4.比赛结束前公开答案按违规处理 5.其它影响到比赛公平的行为按违规处理 对于违规用户： 第一次违规：取消本场比赛获得奖品的资格，扣除rating200分，公开违规用户名单在比赛说明...

2023牛客OI赛前集训营-普及组（第一场）题解.pdf

2023牛客OI赛前集训营-提高组第一场题解.pdf

提高组题解普及组题解

提高组题解 普及组题解

先读题。最小建设费用最大，有点绕。不会做。 那我们先试着简化一下题目，然后看能不能从简化后的题目中，分析出一些有用的结论，再利用这些结论去解决原来的题目。 如果已经确定了这 m 个公司，那么怎么建基站，才能使建设费用最小？ 一眼 O(m^2) 的 DP。想法太简单，以致于没什么用。再仔细分析一下下。 如果只有两家公司，那么我们应该建一个还是两个？位置记为 x1, x2，那么建一个的代价是 A+B(x2-x1)/2，建两个的代价是 2A。那么如果 (x2-x1)>2B/A，建两个的代价更小；反之建一个的代价更小。 再考虑更通常的情况下：我们现在有两个基站，覆盖范围分别为 [l1, r1] ...

岗位要求：1、必须线下工作，地址：北京市朝阳区北苑路北美国际商务中心K2座一层-牛客网。2、技能要求：有出题经验（校赛或牛客等系列赛均可）优先，区域赛铜以上或cf/atcoder/牛客rating1600+。3、认真负责，可以按质按量完成任务。4、实习至少2个月,且最近两周内就可以来线下。工作内容：编程题出题、录题、验题。解答客户/销售有关编程题的提问。笔试编程题答疑。岗位待遇：工作时间为周一至周五，早10点至晚七点半，中午管午饭，12:30-14:00午休。外地实习生有房补。薪资待遇面试过后与主管沟通。有意向的同学可以发送简历至 wangxuan@nowcoder.com。简历内尽量包含 牛...

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 出题人写的 https://blog.nowcoder.net/n/b977a248521446a48d17081c47a9a6d5 B 非常非常不好意思的是，个数指的是点数而不是最大团个数（ 于是 n=0 的时候答案为 0 n=1 的时候答案为 1 n>=2 的时候答案为 2 C 观察题目 很容易根据第 888 项是 16.0016.0016.00 想到乘二，但是又发现第 111111 项是 22.9922.9922.99，四舍五入是 232323，这就重温了当年学化学的疑惑，所以学过化学的应该很快就可以反应过来，查的是元素周期表。然后通过题目给定的年限 199919991999 ...

总榜：https://docs.qq.com/sheet/DY0pRc3VkRkRaUnpZ?tab=3np5k4证书：暑期多校排名证书已于9月11日发放至报名时填写的邮件。如果证书上的信息有误，或未收到邮件，请于2023年9月18日前提交申请。2023年9月18日后不再接受申请报名地址点击查看比赛相关的资料信息出题人题解打包下载：点此下载新手向题解打包下载：点此下载标程打包下载：点此下载萌新讲题录播合集 链接出题人讲题录播合集 链接本次训练营的所有讲解都有录播：大概比赛结束后三个工作日内上传至牛客竞赛b站账号（关注牛客竞赛b站账号，第一时间收取讲题视频~牛客竞赛b站账号）关于std：std可...

测试用链接：https://ac.nowcoder.com/acm/contest/52831/B 来源：牛客网 Two integers a,b are given. Please determine which one is bigger (or report that they are equal). Hint one : this problem can be a problem of Nowcodet April Fools Contest, but can't be a problem of Codeforces April Fools Contest for some reaso...

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​ 。所以考虑把 ai...