重庆邮电大学第十九届ACM程序设计大赛（网络赛）回顾
重庆邮电大学第十九届ACM程序设计大赛（网络赛）回顾前言上周末参加校赛网络赛ac五道题，成功进入线下赛。但是近来有些烦躁不知从何学起，遂作此篇回顾赛场心境，也算作补题的记录。 赛场回顾签到部分开赛后迅速切掉第一道签到，但第二道签到因为在输入数据时漏掉多组数据的t导致错误，自己没有调试而是卡在那里红温浪费了时间。 D. 海鲜八爪鱼VS小猴7题目链接：D. 海鲜八爪鱼VS小猴7大意：通过一定次数的区间修改，找最后一次的数组最大值与已有数值进行操作后比较。数据范围：元素个数2e5，元素大小1e9，修改次数2e5，修改大小1e9。思路1：可以使用差分数组,记录数组中相邻元素的差值，通过对差值的修改得到最后一次的原数组元素值。相较于朴素算法n^2的时间复杂度，这种方法通过增加一个数组的空间使得时间复杂度优化为O（n）。ac代码： 123456789101112131415161718192021222324252627282930313233343536373839404142#include <bits/stdc++.h>using namespace...
二分查找与二分答案
二分思想前言：二分法是一种应用广泛的基础算法，可以在二分查找与二分答案的问题中得到应用。因其O（logn）的时间复杂度，在处理较大数据有着较高的效率。 基本原理：二分法通过将一个有序数组从中间分成两半，比较中间值与目标值的大小，从而将范围缩小，在左半部分或右半部分继续查找，直至找到目标值或者确定目标值不存在。 时间复杂度：O（logn）。其中n是数组长度。因为每次操作将范围缩小一半，是将n除以2^x得到最后的一个结果，所以最多logn次即可找到结果。 二分查找c++代码实现： 1234567891011121314int binarySearch(const vector<int>& arr, int target) { int l = 0, r = arr.size() - 1; while (l <= r) { int mid = l + (r - l) / 2; if (arr[mid] == target) { return mid; ...
