竞赛讨论区 > 【题解】牛客小白月赛68
头像
tokitsukaze
编辑于 2023-03-11 15:52 浙江
+ 关注

【题解】牛客小白月赛68

【题解】牛客小白月赛68

A. Tokitsukaze and New Operation

直接模拟即可。

代码:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=61169745

B. Tokitsukaze and Order Food Delivery

直接模拟即可。

代码:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=61169766

C. Tokitsukaze and Average of Substring

枚举区间的两个端点 llrr,在 rr 往后移动时,用一个桶维护 C(l,r)C(l,r),并计算 F(l,r)F(l,r) 更新答案。

时间复杂度 O(n2)O(n^2)

代码:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=61169785

D. Tokitsukaze and Development Task

首先观察到,这 44 种资源互相独立,所以可以分开计算答案,最后累加起来。

然后发现每种资源都是从 1010 开始,我们只需要求出 1010 到任意量的资源所需要的最小操作次数即可。这个可以用 BFS 求。

由于测试数据组数 TT 比较大,我们可以预处理出结果,对于每组测试数据直接输出答案。

代码:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=61169799

E. Tokitsukaze and Colorful Chessboard

显然棋盘越大就越能放下所有棋子,所以我们可以二分答案。

假设现在二分出的棋盘大小为 xx,我们需要求出相同颜色的棋子最多能放的个数。如果 xx 是偶数,则结果为 x(x/2)x*(x/2);如果 xx 是奇数,则结果为 x(x/2)+(x+1)/2x*(x/2)+(x+1)/2。如果这个个数 max(a,b)\ge max(a,b),并且 x2a+bx^2 \ge a+b,则该棋盘合法。

代码:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=61169808

F. Tokitsukaze and New RenKinKama

先遍历一遍处理出所有可能需要交换的素材位置(即不合法的位置)。

发现进行 11 次操作后,最多会改变 66 个素材的状态(合法/不合法)。所以最多可能有 1212 个不合法的位置。

当不合法的位置数量 >12>12,直接输出 1-1

否则:

  1. 11 个不合法的位置,然后暴力枚举跟哪个位置交换,这一步的时间复杂度是 O(n12)O(n \cdot 12)

  2. 接着再求一遍不合法的位置,如果当不合法的位置数量 >6>6,则continue。然后再选 11 个位置进行交换。这一步的时间复杂度是 O(n6)O(n \cdot 6)

  3. 最后检查当前所有不合法的位置以及第二步交换的那个位置是否都合法,如果是,即找到一个方案。这一步的时间复杂度为 O(6)O(6) (为什么需要检查 "第二步交换的那个位置" ?因为交换后可能会新增不合法的位置)

所以总时间复杂度为 O(n21262)O(n^2 \cdot 12 \cdot 6^2)

PS:由于 nn 只有 300300,有些选手写 n3n^3 级别的做法,常数小也可以通过。

代码:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=61169825

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐