2022-2023:teams:loaf_on_contest:front_page:nowcoder4
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2022-2023:teams:loaf_on_contest:front_page:nowcoder4 [2022/08/28 13:22] toby-shi [L] |
2022-2023:teams:loaf_on_contest:front_page:nowcoder4 [2022/08/31 21:32] (当前版本) yuki |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| =====D===== | =====D===== | ||
| + | 本场的签到题之一，当一个人的三个参数 IQ、EQ、AQ 均不小于某个工作给定的值时，这个人就可以胜任这份工作，需要统计有多少个公司可以给某人提供岗位。 | ||
| + | |||
| + | 由于公司数量非常少（只有10），因此使用f[i][a][b]表示第i个公司，要求为 $IQ\geq a$，$EQ\geq b$ 的岗位的 $AQ$ 最小值。 | ||
| + | |||
| + | 显然有：\\ | ||
| + | f[i][j][k] = min(f[i][j][k], f[i][j - 1][k]);\\ | ||
| + | f[i][j][k] = min(f[i][j][k], f[i][j][k - 1]);\\ | ||
| + | f[i][j][k] = min(f[i][j][k], f[i][j - 1][k - 1]);\\ | ||
| + | |||
| + | 然后询问时，枚举所有公司统计即可。 | ||
| + | |||
| =====N===== | =====N===== | ||
| + | |||
| + | 一开始拿到题没看懂，以为是直接把那个方差算出来，然后成功的WA掉了。。。 | ||
| + | |||
| + | 在经历了半个小时的仔细读题之后，哦，原来是要任意选两个数$a,b$，变成$a\& b,a|b$，直到无法变化为止 | ||
| + | |||
| + | 那就把所有二进制位上的$1$一个个扒出来，每次把当前能填的往最大数上添，一个数的一个二进制位最多填一个$1$ | ||
| + | |||
| + | 这样出来的玩意一定是最后的结果 | ||
| + | |||
| + | 因为小的数一定被大数包含 | ||
| + | |||
| + | 最后算个方差就解决了 | ||
| + | |||
| + | 然后本stockholm制杖忘记了$gcd$。。。 | ||
| + | |||
| + | 最后还是过了 | ||
| =====A===== | =====A===== | ||
| 行 23: | 行 50: | ||
| 大意就是，选一个当前值最佳的，这个值不一定会放在这个位置，但是必然会出现在答案序列中。否则，这个数代替答案序列中这个位置的数，会使答案上升。所以这个数至少会出现在序列中。 | 大意就是，选一个当前值最佳的，这个值不一定会放在这个位置，但是必然会出现在答案序列中。否则，这个数代替答案序列中这个位置的数，会使答案上升。所以这个数至少会出现在序列中。 | ||
| =====H===== | =====H===== | ||
| + | 一个很简单的构造题，感觉条件挺宽松了，很多种方法应该都可以。 | ||
| =====L===== | =====L===== | ||
| 行 31: | 行 59: | ||
| 建系过程详见下图： | 建系过程详见下图： | ||
| - | {{ https://sm.ms/image/VqUYlhBM4of1Rwj.jpeg |p1}} \\ | + | {{https://s2.loli.net/2022/08/28/VqUYlhBM4of1Rwj.jpg|p1}} |
| - | {{ https://sm.ms/image/Ts3APj8LCSFkU1n.jpeg |p2}} | + | {{https://s2.loli.net/2022/08/28/Ts3APj8LCSFkU1n.jpg|p2}} |
2022-2023/teams/loaf_on_contest/front_page/nowcoder4.1661664162.txt.gz · 最后更改: 2022/08/28 13:22 由 toby-shi
