ECNU第四届程序设计竞赛解题报告

本文主要是介绍ECNU第四届程序设计竞赛解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A rxms喜欢玩耍

占坑。。。

B rxms爱吃糖

给定序列A[]，1e5个元素求 $min\left( max_ { 1\le i \le N) } x \ast A[i] \right)$

构建字典树，构建完了之后，对于根节点，假如0,1都有，说明x的这一位取0，则以1为根节点的子树肯定小于以0为根节点的子树；x的这一位取1，则以0为根节点的子树肯定小于以1为根节点的子树，这时候比较两种方式取较小的就可以，并递推下去

C rxms很闲

$n \le 1e9$ 求 $\sum_{i=1}^{n-1}\lfloor \frac{n}{\sqrt{i(n-i)}}\rfloor$

考虑到i=1时元素取最大值，所以 $\lfloor\frac{n}{\sqrt{i(n-i)}}\rfloor$ 最大不超过 $\sqrt{n}$ ，因此枚举k= $\lfloor\frac{n}{\sqrt{i(n-i)}}\rfloor$ ，最后转化为求二次方程就得到了答案。

D rxms写摘要

tfidf排序水题

E rxms的愿望

给n个点 $n \le 100$ ，求七点共圆的可能数

三点确定一个圆，由此 $n^3$ 计算所有圆的可能数，枚举排序后计数就可以得到，这时候，每个圆相当于算了 $C_n^3$ 次，因此反推可以得到n，再就算 $C_n^7即可得到答案$

F Fast & Furious 7

n座城市，m条路，k个人， $n \le 50, m \le n*(n-1)/2 , k \le 10$ 对k个人部署使得这k个人到任何一个城市的最大距离最小。

二分一下距离重新构造图，然后检查一下k个点能不能支配整张图，DLX即可求解

G rxms换气球

本场最坑的一道。现有三种颜色的气球各r,g,b个， $r,g,b \le 100$ 。现在两个不同颜色的气球可以换两个第三种颜色的气球。求最后最多能换多少个同一颜色的气球。

假设r,g来换b，不妨设 $r\lt g$ ，那么{r,g,b}换成{0,g-r,b+r}，接下去考虑第二种和第三种。对于{0,3,1}这种情况，我们可以换成{2,2,0}，再换成{0,0,4}，因此假如{0,g-r,b+r}首先可以把3的倍数全部换掉{0，(g-r)%3,b+r+g-r-(g-r)%3}。对于{0,2,1}这种情况，可以换成{2,1,0}，最后变成{1,0,2}。但是{0,1,1}则已经没办法换了。

H 简单的矩形计数

求 $n*m\left( n,m \le 100 \right)$ 的矩阵中，四个顶点都是1的矩形个数。

两行元素做点击，最后得到的向量中的1的个数n， $C_n^2$ 就是这两行中所有的个数

I 简单的数学问题

求set( $a^b$ ), $2 \le a \le 100, 2 \le b \le n$ ,给定n。
1、python写个暴力拍过去了
2、hash数组，取余拍过去了，对数也可以
3、a= $c^d$ 这时候 $a^m$ 变等价于 $c^{dm}$ 这样只要看 $c^{dm}$ 有没有出现就可以了