赋闲第一周结题报告

7.27周二

	杭电ACM-LCY算法入门培训班-专题训练复现（3）		题解
A	HDU 1232	畅通工程	简单并查集，统计合并所有集合以后的集合数量，然后道路数量-1-集合数量就是答案
B	HDU 1233	还是畅通工程	需要构造最小生成树，利用结构体储存数据，按照距离从小到大排序，然后遍历，进行合并，最后输出结果
C	HDU 1863	畅通工程	与B题不同的是还需要判断是否能够畅通，此时只需要随意记录一个已被畅通的道路的老大编号，最后遍历的时候判断这条道路的老大编号是否与被记录的老大编号一致，如果全都一致则输出结果，否则认为不能畅通，输出？
D	HDU 1874	畅通工程续	冥思苦想了半天，最终觉得不能用并查集写，网上搜这道题发现是用最短路径，于是去学习迪杰斯特拉算法，最终独立写出这题。有几个比较坑的地方：一、要注意道路是双向的。二、两个点之间可能会有多条道路。三、某一个到自己的距离要初始化为0。因为这三个点WA了好几发。

7.28周三

B	HDU2066	一个人的旅行	有多个起点和终点的最短路问题，需要输出某个起点到终点的最短路径，可以设置虚拟起点和虚拟终点，虚拟起点到每个起点的距离为0，虚拟终点到每个终点的距离为0

7.29周四

暑期大作业（思维-贪心、数学

A题：用辗转相除法求得所有数字的最大公约数，然后再求这个最大公约数的约数数目就行。

B题：先排序，然后找相等的对，比如找到两个1，那么就把一个1加入另外一个数组，如果这时候对数达到矩形数目的两倍，那么进行下一步判断，否则输出NO，下一步判断即持续首尾相乘，若每一对都相等则输出YES，否则输出NO。

7.30周五

D	Remove the Substring (hard version)	先从左往右依次记录子串中的字符在模式串中的位置，再从右往左记录，最后求左边第i个和右边第i+1个的差值最大值，注意要考虑边界，即右边第一个与开头的距离和左边最后一个与结尾的距离，同时要注意是否-1的问题。
C	Remove the Substring (easy version)	与C题解法一样，改个数据就行。

7.31周六

摸鱼

8.1周日

摸鱼