July 28th 近期练习题总结

这周多校联合训练正式开始了,第一周的成绩并不能让大家满意,很多该做的题没有做出来,在这里继续对本周的比赛进行总结,希望下周能发挥出更好的水平。

BC第九场

 

拓展欧几里得的复仇

A题水题。读题时注意题目要求的是整数对即可简单通过列举所有整数对得到ac结果。

尼姆博弈的复仇

B题为一道简单的博弈,规则为每次只能拿最前面一堆的任意数量的石子。

考虑最终情况,如果只剩最后一堆石子,那么先手必胜。继续往前推,如果剩两堆石子的话,谁能让对方拿完这堆石子,谁就能最后胜利。此时如果石子大于一个,先手可以直接把石子拿到只剩一个。那么先手必胜,如果此时石子只剩一个,那么获胜状态会发生改变。先手可以在上一步直接全部拿完使自己处于必胜态。如果石子只剩一个,此时又是第一步,那又怎么样呢?

简单思考,我们可以知道只需求出开头连续1的数量,模2得到结果,如果一直到结尾都是1,那恐怕我们要进行一下特殊判定了。

KNN的复仇

这是一道暴力,先进行排序,然后求出每个数的最近k个数的平均值赋给这个数,最后输出最大值即可。

 

BC第十场

 

斐波那契的复仇

暴力搜索即可,时间复杂度够。

GCD的复仇

这道题可是复仇成功了,卡根号的复杂度。依然暴力,只是我们算出一个因数的时候可以通过用整数除以这个因数得到与它“对称”的另一个因数。循环以根号结束即可ac。

Collinearity的复仇

题目的数据量很小,所以我们依然可以进行暴力。对于每一个点做一个map,用它来储存它与其他点所构成的相同斜率大小的点的数量。然后遍历map,对于所有的斜率数量取一个C (n,2) 结果加和即可。这里要注意的一点是,一开始自己为每个点建了一个map,就一个map数组,结果mle了,最后发现每一个点的map之间没什么联系,并且在遍历过后就没什么用了,所以可以对其进行重复利用,只建一个map,把统计斜率和计算数量放到同一个循环里,就顺利ac了。

 

BC第十一场

 

A题签到题,判断点是否在矩形中间,直接判断就好。

B题题意是给n个在0到9之间的数字,我们需要用这n个数字组成一个数,这个数需要是一个整数,其次不能有前导零。我们需要找到符合条件的最大的一个数。

思路还是很简单的,统计每个数字的数量,把最小的一个奇数挪到开头。然后按顺序输出每个数字。需要注意前导零的处理,只有一种情况就是当只有一个奇数和很多个零的时候,处理过程中就会出现前导零,这时候直接判No就好,这种情况判断的时候还要处理一个只有一个奇数没有零的问题,因为这个还Wrong answer了一次。

C题的题意是找出一个字符串的相同字母不多于k的子串数量。我们用一个队列维护一个最长子串,每次如果当前字母合法就直接入队列,否则将队尾元素出队列直到当前字母合法,循环到结束找最大值即可。

D题待补

 

2017多校第一场

A题题意是输出不大于2m-1的最大10k的k值。因为lg(2m-1)向下取整和lg(2m)向下取整是相等的,所以直接输出就好。

B题待补。这道题很气,做了半天发现排序出了问题,明天好好再补一遍。

F题题意不太好描述,它给出了一个映射,要求求有多少种符合要求的匹配。由于两个数列都是0到n-1的排列,我们可以把它看作一个图。用第二个图中的环将第一个图中的环全部填满,只有当第一个图中环的size是第二个环的size的整数倍是才能够填入。判环的工作可以通过并察集来完成。

K题可以通过模拟过程可以直接找到循环规律。

2017多校第二场

A题给出两个人的选择题答案和两份成绩单,判断是否有矛盾,选择题答案只有ABC三种。所以对于两道两人答案不同的题,有一人对一人错和两人都选错三种情况,对于这几种情况分别列出不等式。最终解不等式即可。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注