[原创]山东省第六届ACM大学生程序设计竞赛训练总结 [(7+1)/12] 待补

2017-04-29 21:20:32 Tabris_ 阅读数：422

博客爬取于2020-06-14 22:40:48
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/70990783

这套题 ,难度并不高,水题很多,中期题不少
但是发挥并不是特别理想,
一部分是训练态度不够,中间一段时间在聊天,并没有全力出题,
还有队友赶紧回来啊 ,两个人磕还是不行啊,罚时爆表.

最后40分钟搞的G却没有及时出,足足晚了12分钟才AC.

封榜时间出题也应该是一个强队的标志,很明显,我队距离强队差距很远,水平差很多.

个人的话卡题时间比较长,还是对解题的正确方法思考慢,越接近正解的时候越容易乱.越乱越容易出差错.
还有就是不常用算法要及时复习,平时一直写线性筛,训练的时候一个埃斯托尼筛法硬是写了好久才调对.
还有就是思路要清晰, 其实大部分题的编码时间并不长,10~15分钟够用了,除了模拟题,非小规模数据结构题,等…

Problem A SDUT 3251 Nias and Tug-of-War

————————————————————————————————————————————
水签到题，结构体排序加和比较输出即可

Problem B SDUT 3252 Lowest Unique Price

————————————————————————————————————————————
有三种操作，
1.b x 插入一个x
2.c x 删除一个x
3.q 查询当前仅有一个的最小的数

其实这种题一般都是用STL做但是渣渣并不会STL

所以每次都是用树状数组+二分来搞。

但是这题我们有一个限制，就是只在当前仅有一个的数中找？

所以我们可以定义一个数组，标记每个数出现的次数，将数组中的不是1的数拿下去，是一的数放到树状数组中，然后通过二分找到第一个有数的位置就好了

复杂度虽然是 $O(nlog_2^{2}(1e6))$ 但是没有STL的大常数。所以还是可以的。

Problem C SDUT 3253 Game!

————————————————————————————————————————————
算是个博弈吧
但考虑对称性，除了1,2之外不论先手拿1个还是2个，后手都能将局面变成对称的，先手必败

Problem D SDUT 3254 Stars

————————————————————————————————————————————
在一个二维坐标系上，给你 $n(\leq 400)$ 个点，问你找一个面积最小的矩形，使得这个矩形内有k个点
点坐标的范围在[0,400]

一看到这400个点我就觉得可以做,然后发现坐标就在[0,400]内连离散化都不用了

我们要的是最小面积,首先想的是二分,但是发现面积又涉及长又涉及宽,我无法再O(n^2)内处理出,所以放弃

然后发现我可以固定一个长,然后找长为定值的时候的面积最小值,然后维护最小值就好了

发现这样在加上一个尺取法和每行的前缀和的复杂度能做到O(n^3),可以做,

然后就A了

Problem E SDUT 3255 BIGZHUGOD and His Friends I

————————————————————————————————————————————

Problem F SDUT 3256 BIGZHUGOD and His Friends II

————————————————————————————————————————————

Problem G SDUT 3257 Cube Number

————————————————————————————————————————————
给你一个序列，问你两个数的乘积是立方数的数对有多少个？

其实和H题差不多，但是又差了很多，

假如ab是立方数，那么ab*(k^3)也是立方数,那么所有的形如ab(k^3)的数都能划归为a*b的形式,
那也就是说如果数x = (k^3)*b 那么k^3这部分就没有意义，消掉就好了。

这个时候考虑a*b在什么时候成立，显然 $a*b = p_1^{a_1}*p_2^{a_2}*...*p_n^{a_n},a_i = 0\ or\ 3$
那么对
$a = p_1^{a_1}*p_2^{a_2}*...*p_n^{a_n}$
$b = p_1^{b_1}*p_2^{b_2}*...*p_n^{b_n}$
那么对于所有的 $a_1+b_1 = 3\ or\ 0$
那么对于每一个数，我都能找到与其相乘为立方数的数了

只要找这个数的素因子的指数与其对应的就好了

这个部分我们仍然可以预处理，先把每个数划归成没有(k^3)这样的因子的数.然后对其素因子分解就好了,
但是发现如果直接这样的话预处理部分会超时,
所以我们仍然利用埃斯托尼筛法,在过程中找到每个数的因子,用一个vector存就好了,素因子个数小于log
然后对每个数找到其对应的能乘出立方数的数

然后O(n)统计就好了

注意LL

Problem H SDUT 3258 Square Number

————————————————————————————————————————————
给你一个序列，问你两个数的乘积是平方数的数对有多少个？

然后发现如果ab,ac是平方数那么b*c也是平方数. 其是具有传递性的,
那么我们就可以记录每个堆得数有多少个,然后统计就好了

考虑a*b是平方数 $(a\leq b)$ ,
那么对于定值a,
b一定是a的倍数.

这点很好发现因为ab要是平方数的话那么其开根号一定是aa*k(k也是可平方)的,

所以我们依据这个分堆就好了
分堆的方法是预处理. 预处理出每个数在那一堆,
因为在一堆的一定是某个数的倍数,那么我们可以通过埃斯托尼筛法的过程计算每个数是属于那一堆的,
标记的数组变成指向那个堆得映射就好了,

然后在统计答案的时候就可以在O(n)下统计了，

注意LL

Problem I SDUT 3259 Routing Table

————————————————————————————————————————————

Problem J SDUT 3260 Single Round Math

————————————————————————————————————————————
问你有N个男的，M个女的，分成11组，每组的男女都是成对的。问你成不成立。

水，
就是比较下N,M相不相等，相等的话男女才都能成对。
但是要分成11组，所以对数要是11的倍数，

判断一个大数是不是11的倍数，其实并不用高精度，只要for一遍就好了。

Problem K SDUT 3261 Last Hit

————————————————————————————————————————————

Problem L SDUT 3262 Circle of Friends

————————————————————————————————————————————
图论题，队友出的，我不会图论。