记录每个字母出现的位置，查找的时候用二分优化，时间复杂度nlogn #include<iostream> #include<vector> using namespace std; string str; char t[1000005]; int n; vector<int> space[150]; int binary_search(const vector<int> &arr, int k) { int l = 0, r = arr.size() - 1, middle; if(r == -1) return -1; while(l ...

把字符数组开大点,开到10000

D-小黑的区间 现在定义dp[i]表示以i位置结尾的完美区间个数，不难发现，以i位置结尾的区间可以是i位置的一个数，也可以是i-1位置到i位置两个数，也可以时i-2到i位置三个数，直到这个区间内有两个相等的数，它们之间不存在与它们相等的值且它们之间的距离大于k。假设我们已经知道了第一个发生冲突的位置j，那么dp[i] = i - j 那么现在要求的就是第一个发生冲突的位置。当然可以一个一个枚举，然后直接超时...所以现在问题就是如何快速找出从后往前数第一个发生冲突的位置 假设在计算dp[i]时我们已经知道了和i - 1位置第一个发生冲突的位置j1，现在我们再计算和i位置的值第一个发生冲突的位置...

B-小蓝的旅游 看到这题我就想起小时候玩手机，总有什么能不能一笔从左上角画到左下角，清华北大答不出，农名工给出解答这类营销号的题目，我真的是绞尽脑汁画不出。。。 言归正传，现在我们假设这个网格图中有0和1交错分布，即0的上下左右4个方向全是1，1的上下左右4个方向全是0，那么走了1所在的格子后下一个格子必定是0，走了0所在的格子后下一个格子必定是1。所以，设左上角的数字为0，当n为奇数时（有奇数行），可以得知左下角也是0，根据刚刚的分析，要走奇数次才可以走到0（一定是0->1->0->1->0这样走）,同理，当n为偶数时，可以知道左下角是1，要走偶数次才能走到1。 我们...

E-相依 定义dp[i]为第一个数到第i个数所需要合并的最少次数，可以得到动态转移方程： dp[i] = min{dp[j - 1] + 1} (1 <= j < i且 val[i] = val [j]且 dp[j - 1]存在) 但是这样做要枚举前i - 1个数，时间复杂度原地爆炸。观察动态转移方程，不难发现我们要找的是dp[j - 1]的最小值，即每个与i位置有相同的值的j位置前面一个位置的dp值的最小值。所以可以使用哈希表记录每个val值前面位置dp值的最小值，用m[val]代表这个值,那么dp[i]就可以这样计算: dp[i] = m[val[i]] + 1 现在，只需要在...