第一题

城市公路某些路段路面质量下降，多多需要对这些路段进行维修。多多可进行工作的时间为1~H。同时有交通管理系统会根据不同因素发出拥堵预警:天气预报显示可能有暴雨、大型活动预计车流剧增、早晚高峰时期等。多多的维修应当在路况不繁忙的时候进行，需要注意预警时段可能存在重叠，比如雨天预警[10,20]和活动预警[15,25]同时存在，则需要避开整个[10,25]时段进行维修青你帮助多多计算可以进行公路维修的时间共有多少？

输入描述

第一行为一个整数T,表示共有T个测试数据(1 <= T<= 10)每组测试数据:

第一行为一个整数H,表示多多可进行维修的工作总时长(1<= H<= 10^9)第二行为一个整数N,表示预警时段的个数(1<= N<= 100000)接下来的N行:每行输入两个整数xi, yi, 表示区域[xi, y]被预警将有拥堵发生 (1 <= xi <= yi <= H)

输出描述

每组数据输出一个结果，每个结果占一行

解题思路

类似于 最大不相交区间问题，使用贪心的思想，将所有的 【预警时段】当作一个区间，存于一个区间数组，并且以每个区间的起始点从小到大排序，声明一个变量res用来存储结果，使用st和ed维护一个区间，然后遍历所有的区间：

• 如果当前区间的起始点 < st, 进行区间合并， ed = min(ed, 当前区间的ed)
• 否则，代表出现了新区间，那么 res += 当前区间的st - ed，然后更新区间

第二题

在一片神奇的魔法森林中，有n个魔法节点，每个节点都有一个传送门。第i个节点的传送门会把你传送到a;号节点。

多多每次可以选择坐传送门从i节点传送到a;节点，或者选择步行到相邻的节点i-1或i+1节点。当然多多是个喜欢偷懒的人，所以它能坐传送门就尽量不步行。现在多多从1号节点出发，想知道到达每个节点需要经过的最少步行次数，

输入描述

输入两行，第一行包含一个数字n(1<=n<=100000)，表示有n个节点。接下来一行n个数字，每个数字a;(1<=a;<=n)，表示i节点的传送门可以传送到a节点注意ai可能等于i

输出描述

输出一行包含n个数字，第i个数字ans;，表示从1号节点到i号节点的最少步行次数

解题思路

刚开始想使用dp，但是状态转移想不出来。。。后来想到使用BFS来做，维护一个dist数组表示每一个点到1的距离，先把1加入到队列，不断从队列中弹出元素：

• 如果它的前后元素的dist大于当前元素的dist + 1,那么把它的前后元素加入队列
• 如果它能够跳跃到的元素的dist大于当前元素的dist，那么把它的跳跃到的元素 加入队列

直到队列为空

第三题

给定两个仅包含小写字符 a和b的字符串 A和 B，长度分别为n和 m，现在根据A和 B构造一个 n“m 的字符矩阵 C，其中 C 的值由 A,和 B, 决定，具体计算方式如下:

·如果 A; 和 B; 都为 a，则 C为a;

·否则 C 为 b。

多多对字符 a情有独钟，他想知道矩阵 C 中共有多少个仅包含a的子矩形，并且其字符总数恰好为 k?

输入描述

三行，第一行三个正整数n,m,k，分别表示字符串 A和 B的长度，以及多多想知道的子知形个数。

第二行为字符串 A

第三行为字符串 B

(1<= n,m <= 1000,000,1 <= k <= n*m)

输出描述

一个整数K

解题思路

多模拟几个，可以发现一种乘法规律，也就是先处理a字符串，获得a串中连续'a'字串的长度的数组，再处理b字符串，获得b串中连续'a'字串的长度的数组，做双层遍历：

遍历a数组，得到矩形的长度 l：

遍历b数组，得到矩形的宽度 w：

枚举子矩形的长度x:

res += ( l - x + 1) * (w - k / x + 1)

第四题

不会