CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 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)$处理即可。
CVBB ACM Team

用户工具

站点工具

页面工具
