[原创]山东省第六届ACM大学生程序设计竞赛 训练总结 [(7+1)/12] 待补
[原创]山东省第六届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的数拿下去,是一的数放到树状数组中,然后通过二分找到第一个有数的位置就好了
复杂度虽然是但是没有STL的大常数。所以还是可以的。
Problem C SDUT 3253 Game!
————————————————————————————————————————————
算是个博弈吧
但考虑对称性, 除了1,2之外不论先手拿1个还是2个,后手都能将局面变成对称的,先手必败
Problem D SDUT 3254 Stars
————————————————————————————————————————————
在一个二维坐标系上,给你个点,问你找一个面积最小的矩形,使得这个矩形内有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在什么时候成立,显然
那么对
那么对于所有的
那么对于每一个数,我都能找到与其相乘为立方数的数了
只要找这个数的素因子的指数与其对应的就好了
这个部分我们仍然可以预处理,先把每个数划归成没有(k^3)这样的因子的数.然后对其素因子分解就好了,
但是发现如果直接这样的话预处理部分会超时,
所以我们仍然利用埃斯托尼筛法,在过程中找到每个数的因子,用一个vector存就好了,素因子个数小于log
然后对每个数找到其对应的能乘出立方数的数
然后O(n)统计就好了
注意LL
Problem H SDUT 3258 Square Number
————————————————————————————————————————————
给你一个序列,问你两个数的乘积是平方数的数对有多少个?
然后发现如果ab,ac是平方数那么b*c也是平方数. 其是具有传递性的,
那么我们就可以记录每个堆得数有多少个,然后统计就好了
考虑a*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
————————————————————————————————————————————
图论题,队友出的,我不会图论。