Codeforces Round #728 (Div. 2)C. Great Graphs
这题说给一个数组, 任意两个数字都可以建一个路, 求路的负数最大是多少. 这题就画一画, 比如 0 2 5 7 10, 那么可以建立任何两个数字之间的路, 和是0. 那么5->0, 7->(0,2,), 10->(0,2,5), 都是答案要的负数路. 很简单的模式.
这题说给一个数组, 任意两个数字都可以建一个路, 求路的负数最大是多少. 这题就画一画, 比如 0 2 5 7 10, 那么可以建立任何两个数字之间的路, 和是0. 那么5->0, 7->(0,2,), 10->(0,2,5), 都是答案要的负数路. 很简单的模式.
给一个数组, 求两个数字相乘等于index想加的pair的个数. 因为是index想加, 所以已知index的大小是从3(1+2)到2*n. 我们就按个找每个数, 看看有多少pair. 因为A[i]*A[j]=[1,2*n], 那么就知道其中一个是的范围肯定是[1, sqrt(n)]. 所以只要是i能整除j的, 都是答案的可能性.
给n个数字, 从1开始到n, 求距离最小的每个数都不在自己位置上的数组. 因为要距离最小, 所有前后swap一下即可. 注意如果是奇数,要多swap一下.
给一个string, 求最大的是奇数的substring. 这题就是从后往前找, 如果看到一个奇数就停止就行了.
给N个pairs, 里面第一个数字是需要买几个, 第二个数字是买多少个后可以有优惠价格. 问花多少钱能买够所有需要买的物品. 因为每个物品价格都是一样的,相当于二元店, 买够第一个数字就变成了一元店. 那么我们想花最少钱, 肯定要买最多的打折物品, 但是打折物品需要买够两元的物品才能买, 所以我们按照从小到大的顺序排序好打折物品需要买多少才能买. 然后我们设买够n个物品后, 可以开始买打折物品, 因为我们知道如果买n个可以, 那么买n+1也可以, 所以问题转化成为如何找到n的lower_bound. 这里用二分查找, 方法check就是验证是否存在n个打折物品的可能. 验证方法如下, 假设total是一共要买的物品, 我们知道total-n, 就是没有当前状态下没有打折的物品的数量. 那么我们从最少的需要物品数量就可以买打折物品的物品开始, 如果当前物品的需要购买数量已经大于total-n, 就证明当前这个不能拿了, 于是我们因为拿不到n个物品, 所以return false. 如果当前物品的需要购买数量小于等于total-n, 就证明当前这个可以拿, 我们把它加进来变成total-n+A[i].first, 然后n -= A[i].first, 这样一直找下去, 直到n==0.
给一个数组, 求加入n个数字(大小不限)后, 使得数组中两个的差不大于k. 求n是多少. 这题贪心, 就是每次都取加入最大的数字.
给一个string,和一些query, 求每个query中, string展开后的长度. 这题就是pre sum. 秒了
设计一个比赛, 一共n个人, 每个人是固定时间间隔后开始比赛, 然后比赛的总长度是k, 求每个人的比赛的时候, 有多少人还没有完成比赛. 这题画画图就明白了, 但是要注意几个corner cases. 比如间隔给的长度小于比赛的长度等.
给一个2d矩阵, 一个人的位置, 求矩阵上的两个点, 让这个人走的最远. 这题啥了, 最远的两个点, 当然是对角线. 哎….贴个比赛的code吧.
给一个数组, 可以加n个非负数数字, 让他的算术平均数等于项数. 问n是几? 这题题中给了已知永远有答案, 所以想了想就知道, 是比较sum和项数. 因为我们加的是非负数,所以可以加0来在不增加算术平均数的情况下, 增加项数.