T1
题目大意
题目会给出nnn个学生,每个学生必定属于两个集合当中的一员,两个集合分别为GGG与HHH。
每个学员还会有一个朋友圈的集合,范围为从自身iii开始一直到EiE_iEi 个同学为一个朋友圈。
领袖筛选资格:
1. 朋友圈包含所有同社团同学
2. 包含另一个社团的领袖。
题目要求我们求出有多少对人员可以符合这个要求。
思路分析
部分分思维
在1~10的数据范围当中,n的取值始终是小于等于3000的,这就意味着O(n2)O(n^2)O(n2)的做法可以通过这部分的数据样例点。
暴力枚举
1. 枚举出朋友圈包含G集合的所有人
2. 枚举出朋友圈包含H集合的所有人
3. 判断这些人之间是否存在着朋友关系 统计对数
但是观察到总体的NNN的范围为N≤105N \leq 10^5N≤105,因此在这里只有O(N)O(N)O(N)或者O(Nlog(N))O(Nlog(N))O(Nlog(N))才可以通过。
1. 根据题目需求,一个学生被选择为首领条件只有 包含另一个种类的领袖 包含同种类的所有同学。
在两个领袖当中最多只有一个能够满足其中第一个条件。并且满足第二个要求的从左至右的第一个某种类的学生。
*两个满足第一个条件的学生也能凑成一对
2. 找出从左到右的第一个当前种类的学生。判断他是否也满足条件2
3. 枚举所有的学生,可以去判断它是否包含另一个种类满足条件二的学生,如果有说明符合条件的对数多了一对。
T2
题目意思
在一个二维矩阵当中,题目会给出一个只包含上下左右的边连接的一个正多边形。
然后会给出qqq对起点sss与终点eee,求解每一对起点到达终点的最小步数。(可以顺时针或者逆时针进行行走)
思路分析
1. 暴力枚举
1. 记录每一个格子的前后坐标
2. 每当进行一次提问,那么就从起点正反走到终点,累计步数。
在部分数据当中X,Y≤100X,Y \LEQ 100X,Y≤100 还是可以过的
在全部数据当中,他的具体运算时间大致为⬇️
T(1000×1000×2×2×105)T(1000 \times 1000 \times 2 \times 2 \times 10^5)T(1000×1000×2×2×105)约等于
O(x×y×q)O(x \times y \times q)O(x×y×q)
具体超时的原因还是在每次查询问题的时候(x×y)(x \times y)(x×y) ,超出了时间。
我们最终要去求的还是行走的步数,有没有一种办法可以快速的算出某一段区间的总和呢?
以上核心代码的时间复杂度最多为T(105×1000∗1000)T(10^5 \times 1000 * 1000)T(105×1000∗1000),一旦出现路线覆盖整个地图,则必然超时。
但是转变思路,路线虽为竖横,正向负向行走,但是我们可以将正向的路线其视为是一条线段,其中的第iii个顶点的坐标可以视为在第iii步所能到达的位置,具体如下:
那么我们将正向的路线视为是一条线段,通过在地图mp[i][j]mp[i][j]mp[i][j]当中记录下走到当前格子的步数,每当给出起点与终点坐标时,我们就可以通过mp[sx][sy]−mp[ex][ey]mp[sx][sy] - mp[ex][ey]mp[sx][sy]−mp[ex][ey]直接得到正向行走的步数。
而负向只需要将总步数 - 正向步数即可获得。
通过这样的方式,每次回答的时间复杂度为O(1)O(1)O(1),最后时间复杂度为最高为T(1000×1000)T(1000 \times 1000)T(1000×1000)
参考代码
T3
题目大意
给出两个数字a,ba,ba,b,需要使其通过两种操作变为相等。
1. 给aaa进行+1操作
2. 当aaa为偶数,可以除2或者乘2
每次执行视为一次操作,最少几次操作让其变为一致?
思路解析
1. a>ba>ba>b
为了尽可能让a与b接近,在只能对a进行操作的情况下,我们需要不停的将其缩小,也就是通过/2与+1的操作使其变小。
a>ba > ba>b -> a=ba = ba=b or a<ba < ba<b
2. a<ba < ba<b
若出现2*a < b 的情况下,如果我们直接去累加1的话,可能会出现漏掉部分a/=2或者a+=1的操作使得次数更小的情况。
但是很麻烦的事情是,你没有办法去判断a的取值到达多少才比较合适,因为他的浮动过大,边界难以去限定。
那么我们换一个思路,我们只是为了求解最少次数,b的操作是否存在一些与a的操作等价的情况?
例如 b = 10 a = 20 ,操作为a /= 2 ;
换算成等价公式,也可以视为 b*= 2;
那么在面对2*a的情况下,我们不对a进行操作,因为边界值无法确定,但是我们可以通过等价的换算对b进行同等的价值操作。
也就是
IFIFIF $ a*2 < b$ andandand b%2==0b\%2 == 0b%2==0 : b/=2b /= 2b/=2
假如2∗a>b且a<b2*a > b 且 a<b2∗a>b且a<b:
只能执行+1的操作,使其变为b 并不正确。
这时候,a有可能通过*2的操作变为大于b的情况,在通过+1的操作变为b的倍数在除2刚好变为距离b更接近的数字,操作次数刚好比直接+1更小。
这种情况下,操作次数是没有办法确定一个方案一定可以得到最值的,我们就需要把这个范围的操作次数全部枚举出来,但是只对a进行这样的操作范围太广了,几乎无法确定具体的边界。
因此,我们可以将a*=2 和a+=1的操作 等价转换为b /=2 和 b-=1的操作,将a和b同时进行/=2的+1,-1的操作,枚举完a和b逐渐变为1的情况,最后选择出现过的操作次数。
特殊样例
answer = 15
若a=110,且b=200,count代表当前情况下通过+1和之前/2的操作次数使其相等的次数
1. a = 110 b = 200 count = 90
2. a = 55 , b = 100 , count = 47
3. a = 28 , b = 50 count = 29
4. a = 14 , b = 25 count = 18
5. a = 7 , b = 12 count = 15
6. a = 4 , b = 6 count = 15
7. a = 2 ,b = 3 count = 16
取其出现的最小值15作为答案。
3. a=ba=ba=b
直接输出
操作步骤
1. 使 a>b -> a< b
2. 使 2*a < b -> 2*a > b
3. 枚举在2*a < b范围当中a和b的所有取值求最小值操作次数
T4
给出一字符串,字符串只有字符COW。
其中任意一个字符可以转换为另外两个字符,并且排列顺序随意排列
例C -> OW
任意两个不同的字符排在一起,可以转换为另一个与这两个字符都不同的字符
例 ‘OW’ -> 'C'
然后我们就可以发现一个非常好玩的性质 逆向操作
我们可以把任意两个不同的字符排列,视为另外一个不同的字符的等价
例: 'C' ->'OW' ->'C' , 'OW'就可以视为是一个C
两个相同的字符可以对消
例:CC -> '' 删除相临相同的字符
题目目的:通过两种操作也没有可能把字符串的某一个子串变为只剩下C的情况。
思路解析
Q1:是否有可能通过无线的扩展延伸,让字符变为只剩下一个C的字符?
例:'COW' -> 'OWOW' -> 'CWWOW' ...
A1: 我们可以通过题目给出来的条件,得到等价公式 任意两个不同的字符排列 等价于 另一个完全不同的字符 因此假若这个字符串本身就是合法的,那么一定有办法,假如本身就不合法,就不可能通过无线的拓展操作变为字符串C。
问题就转换为了,如何判断这个字符串本身是合法的?难道输入这个字符串本身就决定了是否能变为字符串C。
例'COWC' 输入本身如此那么他就必然不合法吗?其实并不是。
关键性质:任意两个不同的字符可以 交换位置
例: 'OW' -> 'WCCO' -> 'WO'
也就是说,字符串本身的字符排列顺序是可以变为类似于冒泡排序的相临字符交换位置。
那么,刚才的例子‘COWC’ -> 'COCW' -> 'CCOW' -> 'OW' -> 'C' 合法!
那么,剩下来的问题,就变为统计字符WCO的个数,判断是否能够只剩下C即可
对于COW的字符个数做一个前缀和数组,在获取子串范围的时候,通过O(1)的时间复杂度计算出子串内的字符个数。