工作室寒假题单部分思路

写在前边：以下思路都是我的个人思路，当然每个题目都有多种解法，每个人的思路也不尽相同，我的思路肯定也不是最优，如果大家有更好的思路欢迎来评论区与我交流0.0

ID22数组

首先根据题目描述很容易求出原始数组，我们只需将原数组中的第一位暂时设置为0即可根据两个数组之间的关系求出原数组。求出原数组之后，最重要的一点就是去判断该数组是否为优美数组。优美数组（题目定义）：该数组恰好包含从1~n（数组长度）的数字，不多不少。
我的思路是将原数组排序，对比a[i+1]与a[i]之间的差是否都为1，如果都为1的话，即满足优美数组定义，否则不满足。知其为优美数组之后，只需将数组中的每一项都加1-a[0]即可将数字全部还原为1~n。

ID23图形

其实就是推导函数：输入为n的话，输出的行数为2*n+1。从零还是遍历每一行，记该行为i行，则第i行输出的空格数为|2(i-n)|。星星的个数自己写一个变量记录就行，当i<=n时每次加一输出，当i>n时每次减一输出即可。

ID24重复

很经典的贪心问题，和安排电影院那个题目一模一样。每次去寻找右端点最靠前的即可，然后再去判断是否和前边的线段有冲突，有冲突继续向后遍历，无冲突res+1，再继续向后遍历。

ID25寻宝

经典bfs，用dfs行不通，会超时。用结构体去存储每个已经遍历过的点的位置和步长，使用bfs跑一遍即可。

ID26拍卖

巴什博弈问题，与取石子有异曲同工之妙。当n<m时候，如果m%(n+1)为0则先手必输，否则就投价m%(n+1)，是剩余价钱为（n+1）的倍数，让对手必输。如果n>=m，先手只要出价在[m，n]这个区间之内就必胜，输出这些数即可。

ID27胜利

搜索类问题，主要使用dfs算法，不过题目要保证按照字典序输出，因此首先要对数据进行排序。然后从0开始dfs即可，对于去重问题，我这里没多想直接丢进set容器中进行处理（ps：set容器可以自动去重，详情自行百度），构造如下set<vector< int> > st 容器对vector进行去重。

ID28反转

其实可以把圆的左右两个端点存下来就行，然后对左端点进行排序。如果我要求第i个圆与多少个圆没有交集，那么只需向后遍历到第一个出现与它没有交集的圆，之后的圆都与他没交集。但是这样的算法时间复杂度为O(n^2)，直接暴力会超时。用二分优化一下寻找第一个与它无交集圆的过程即可。

ID29要刷人了

贪心问题，主要是对最优解的构造。想一下一串数字如果去除一个数怎么让他最小。这一串数字的构成我们可以分成一下这几种情况：
1、单调递增：这种情况直接删除最后一个数字即可
2、单调递减：删除第一个数字
3、先增后减：删除向减少方向转折的那个数（即第一个极大值点）
4、先减后增：删除第一个数字
其实上边这四种情况我们可以做一个整合，就是每次去寻找这串数字的第一个极大值点即可，然后删除，这里的删除可以是一个逻辑的删除比如做一个记号记它为一个符号(eq: char ch = ‘0’-1)。了解了删除一个数最小，那么删除n个数就是一样的道理，不过要进行n次遍历即可(当然直接遍历n次估计也会超时，我就提示到这里，剩下的你们自己想想)。

本文地址：https://blog.csdn.net/weixin_44047927/article/details/113871135