目录

atcoder beginner contest 173

A B

考会不会语法直接略过~

C H and V

题意:给一个$n*m$得矩阵,矩阵上每一个方格都被涂成白或者黑,现进行一种操作,可以任选几行和几列将这些行列中的数抹去,给定一个数$k$,问有多少种操作的方法使操作后恰好剩余k个黑块。

题解:数据范围非常小,考虑到行列选择得任意性,可以参考状压得思想,把抹去第几行,第几列变为二进制数在第几位为1,然后就方便暴力循环了,注意位运算的细节即可。

D Chat in a circle

题意:每个人有一个友好度,每次有一个人进队,对总体友好度得和的贡献为周围(呈圆形排列)两人友好度的较小值,问一种进队顺序使总和即答案最大?

题解:由贪心的想法,将数由大到小排序,从第一个开始,每次将一个数插在较大的两者之中,不难发现,除了最大的那个数,其他数都会对答案做出两倍的该数的贡献(因为圆形排列一个数傍边会存在两个空位,而数周围都是大于它的数,所以必定成立),之后暴力统计即可。

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)$处理即可。