牛客CSP-J入门组赛前集训营6 题解

T1 隐瞒成绩

利用if判断和是否可行，可以获得分。

继续利用if判断是否可行，可以获得分。

有一部分数据，故可以直接倒过来算。

显然枚举答案即可。

当然，直接倒着计算也是可以的。

T2 光亮

直接暴力枚举两两的影响取最大值可以获得分。

注意到可以预处理答案，利用来回两次类似差分扫描获得所有位置的结果。

具体是先考虑每个灯对右边的影响，按坐标顺序扫过去。扫到一个灯则考虑从之前的灯向右的影响有没有大于这个灯对右边的影响，如果这个灯更大则替换。每移动一个位置，先前的灯光强度影响减一。

同样的再考虑每个灯对左边的影响，按坐标顺序倒着扫过去。

然后得出所有点的结果之后直接回答询问即可，时间复杂度。

注意到一些同学利用类似分治的方法也可以通过。

Extra: 用同样的做法通过一些方式也可以完成的范围。

T3 虚实桥梁

直接考虑如何处理一条链（一直往前走）可以获得分。

考虑如何在小数据下完成本题。注意到每个点可以拆分成两个点，按下按钮奇数次和按下按钮偶数次，故直接跑floyd可以获得额外的分。

利用上面的思路，直接跑一遍bfs即可获得满分，时间复杂度。

p.s: 怎么看这也不应该用dfs猛冲，dfs视水平高低获得了不同的分数。

T4 勾股定理

对于

移项得，

令 有 , 且

由于 为完全平方数，所以 和 为完全平方数

令

则

所以 为 的因数，枚举， 因数，再在 的范围里枚举 , 计算 是否为完全平方数，如果是则记录答案。

时间复杂度 小于

std

A: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41725418
B: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41725392
C: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41725404
D: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41725289