刷题记-XX

前言

以后不打 Div.3 了，会打 Div.2 和 Div. 1，因为 Div.3 太简单了(划掉)(HouZAJ这只渣渣F题WA了6遍还在这里BB)

A. Wrong Subtraction

题意

给定整数n和k，k为操作次数，一次操作为：若n结尾非0则减1,若n结尾为0则把0删除，问最后的n是什么（题目数据保证最后的n是正数）

思路

大体上只是模拟，但是要加快模拟速度，对于结尾非0的，如果k还有剩余就直接求余，不足就慢慢减1,如果结尾是0的就除10，循环到k为0

B. Two-gram

题意

求作为子串在给定字符串中出现次数最多的字母对（如AA，AB，BA之类的由两个字母组成的字符串）

思路

hash思想，把字母对当作数组下标存起来，每次扫到有这种字母对则对应位置的数组元素值++，最后扫一遍最大的出现的位置，把位置还原为字母对

C. Less or Equal

题意

给定一个数组，求一个正整数x能满足有k个数小于或等于x，无解输出-1

思路

排序之后，直接看第k位和第k+1位是否相同，相同必定无解，同时如果给定的k=0，而数组中最小的元素又为1,那也是无解的，排除这两种情况后，当k!=0的时候，x可以直接等于第k位的元素，符合要求，当k=0的时候直接输出1

D. Divide by three, multiply by two

题意

给定数组，将数组元素重新排序，使得后一个元素是前一个元素/3或*2的结果

思路

因为数组最多100个元素，所以可以直接把答案搜出来，用set来标记元素是否在数组中，直到DFS的搜索深度能够达到数组元素个数，这时把答案保存下来即可。另外，每次搜/3和*2，最后答案还得倒过来，所以可以直接搜索为*3和/2，保存之后的答案无需倒置

E. Cyclic Components

题意

给定一张图，求图中连通分量是单圈的个数

思路

其实可以想到，单圈中每个点的度数均为2，因此用并查集得出连通分量，然后再去判断连通分量中的每个点是否都是度数为2的点，最后扫一遍得到答案

F. Consecutive Subsequence

题意

求最长连续递增子序列，输出下标

思路

实际上可以边读边dp，dp状态方程为 dp[x] = dp[x - 1] + 1，由于x太大，不能用数组保存为下标，所以使用map，dp过程中还有记录x对应在数组中的下标，以及记录前驱的位置，最终找到最大值及其对应下标，并递归输出即可