2020-2021:teams:manespace:atcoder_beginner_contest_173
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:atcoder_beginner_contest_173 [2020/07/14 23:19] iuiou |
2020-2021:teams:manespace:atcoder_beginner_contest_173 [2020/07/15 14:56] (当前版本) iuiou |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| 考会不会语法直接略过~ | 考会不会语法直接略过~ | ||
| =====C H and V===== | =====C H and V===== | ||
| - | 题意：给一个n*m得矩阵，矩阵上每一个方格都被涂成白或者黑，现进行一种操作，可以任选几行和几列将这些行列中的数抹去，给定一个数k，问有多少种操作的方法使操作后恰好剩余k个黑块。 | + | 题意：给一个$n*m$得矩阵，矩阵上每一个方格都被涂成白或者黑，现进行一种操作，可以任选几行和几列将这些行列中的数抹去，给定一个数$k$，问有多少种操作的方法使操作后恰好剩余k个黑块。 |
| 题解：数据范围非常小，考虑到行列选择得任意性，可以参考状压得思想，把抹去第几行，第几列变为二进制数在第几位为1，然后就方便暴力循环了，注意位运算的细节即可。 | 题解：数据范围非常小，考虑到行列选择得任意性，可以参考状压得思想，把抹去第几行，第几列变为二进制数在第几位为1，然后就方便暴力循环了，注意位运算的细节即可。 | ||
| 行 11: | 行 11: | ||
| 题解：由贪心的想法，将数由大到小排序，从第一个开始，每次将一个数插在较大的两者之中，不难发现，除了最大的那个数，其他数都会对答案做出两倍的该数的贡献（因为圆形排列一个数傍边会存在两个空位，而数周围都是大于它的数，所以必定成立），之后暴力统计即可。 | 题解：由贪心的想法，将数由大到小排序，从第一个开始，每次将一个数插在较大的两者之中，不难发现，除了最大的那个数，其他数都会对答案做出两倍的该数的贡献（因为圆形排列一个数傍边会存在两个空位，而数周围都是大于它的数，所以必定成立），之后暴力统计即可。 | ||
| + | |||
| + | =====E Multiplication 4===== | ||
| + | 题意：有n个数，给定k，问取k个数乘起来最大是多少? | ||
| + | |||
| + | 题解：首先有个直观的想法，一定要避免出现负数，正数一定比负数大，有两种情况结果一定是负数，一种是全部是负数而要求选的个数为奇数，这种只要按照绝对值从小到大选即可，还有一种就是选全部的数，而负数的个数正好为奇数个，这样也好解决，全部乘起来就好了。其余情况我们一定可以找到一种方法方法，选出偶数个负数使答案成立。降所有数按照真实大小排序，设置两个指针，一个头一个尾，向中间合拢，每次选择两个数，计算最大值即可。 | ||
| + | |||
| + | =====F Intervals on Tree===== | ||
| + | 题意：给定一棵树，定义$f(l,r)(l<r)$为$l$节点到$r$节点中所有点在在树中组成的子图中连通块的个数。求$\sum_{l=1}^{l=n}\sum_{r=l}^{r=n}f(l,r)$ | ||
| + | |||
| + | 题解：其实就是让我们求连通块的个数，有个比较显然的结论，加一条边会让连通块的数量$+1$，而初始的情况一个点就是一个连通块，所以我们可以还原建树的过程来解决这道题。通过找规律，比较容易发现，在l到r建一条边会使总答案减少$l*(n-r+1)$个,之后$O(n)$处理即可。 | ||
2020-2021/teams/manespace/atcoder_beginner_contest_173.1594739940.txt.gz · 最后更改: 2020/07/14 23:19 由 iuiou
