计划

1.顺序刷完PAT 甲级 155题
2.看完算法笔记
3.考前做几次真题

在这里记录自己遇到的难题

题目

1068 Find More Coins (30 分) 01背包问题
1069 The Black Hole of Numbers (20 分) 题目不难,需要多注意边界条件,多尝试几个测试用例
1070 Mooncake (25 分) 测试点2需要注意float除以int 和float除以float有可能结果不同
1072 Gas Station (30 分)
图论 单源最短路径 之前用Dijkstar算法超时,改用Bellman-Ford算法还是超时,最后用SPFA算法过
1074 Reversing Linked List (25 分)每K个一组反转链表,第一次做用map超时,开了一整个数组hash了所有地址后不超时了
1076 Forwards on Weibo起初用DFS没过,改成BFS就通过了,这题计算传播的层数,用DFS会导致有些点的层数计算出错导致有些点被认为层数过高被排除
1077 Kuchiguse (20 分)测试点3卡了很久,一个字符串有256个字符应该声明char str[257] 最后一个字符为/0 ,改了才通过
1085 Perfect Sequence (25 分)用two pointers思想解,两个指针都是从0开始到n-1,最后一个测试点需要注意p x m<=10^18 超出了int的范围,需要用long long来防止溢出(p<=10^9,m<=10^9)

1091 Acute Stroke (30 分)
一开始的思路是用着色做,最后一个测试点没有办法过,计算量大,最后后查了网络,用BFS做,就通过了