本菜鸟又在CF Div2水了一次，这次的5道题只做出了两道，Div2的C,D（Div1的A,B），不错的题目，可惜当时只想到了一半半，要继续修炼呀。
Newspaper Headline题意是这样的，给定两个串s1,s2，s1可以使用多次，拼成s1s1s1…s1这种串，然后去掉任意多个字母能变成s2，问说最少用多少个s1。
暴力的思路比较好想，在s1,s2上设立两个指针，都是单向的，相应进行匹配，如果s1处的指针走满后，就另起一个，但这样的复杂度是O(ans*|s1|)，主要的开销在于s1上的指针每次都要走来走去的，因为字典就a…z这26种，每次找过的a，又得重新再找一遍，太冗余了，可以用dp(i, j)记录从i…len(s1)这个串中，最左边的字母j的位置，这样就可以快速定位i指针的位置了。预处理dp(i, j)的时间复杂度是O(26*|s1|)，总的复杂度为O(26*|s1| + |s2|)，这样的复杂度就可以AC了，也可以这样优化，建立26个有序表，然后二分快速定位相应的位置，这样的话可以把复杂度降为O(|s1| + |s2| * log|s2|)，补充一句，题解说可以用B树优化。代码如下：
#include <iostream> #include <algorithm> #include <string> #include <set> #include <vector> #include <map> using namespace std; const int MAX = 1e4 + 5; string s1, s2; int d[MAX][26]; //d[i][j]表示从s1[i],s1[i+1],...,s1[len(s1)]中最左边的i在哪里 int main() { cin >> s1 >> s2; int i; int len1 = s1.length(); int len2 = s2.length(); memset(d, -1, sizeof(d)); for(i = len1 - 1; i >= 0; i--) { for(int j = 0; j < 26; j++) d[i][j] = d[i + 1][j]; d[i][s1[i] - 'a'] = i; } i = 0; int ans = 0, j = 0; while(j < len2) { if(d[i][s2[j] - 'a'] != -1) { i = d[i][s2[j] - 'a'] + 1; j++; } else { if(i == 0) break; ans++; i = 0; } } if(j < len2) cout << "-1"; else cout << ans + 1; } Queue题意是这样的，N个整数组成一个序列，用a1, a2, …, an表示，对于每个每个位置i，求出i右边，最远的j使得aj < ai。题解的方法很巧妙，建立数组m[]，m[i]表示从ai到an中的最小值，则m[i]是个递减数组，然后枚举的时候，二分逼近那个最远的边界就可以了，复杂度是O(N*logN)，有人提到先对数组排序后，然后枚举，并保存最远的位置，也是个不错的方法，但要注意数组中的值可能相等，复杂度也是O(N*logN)。前者方法的代码如下：
#include <iostream> #include <string> #include <set> #include <vector> #include <map> using namespace std; const int MAX = 1e5 + 5; int v[MAX], r[MAX], m[MAX], n; int main() { cin >> n; for(int i = 1; i <= n; i++) cin >> v[i]; r[n] = n; m[n] = v[n]; for(int i = n - 1; i >= 1; i--) { m[i] = min(m[i + 1], v[i]); int low = i, high = n; while(low <= high) { int mid = (low + high) / 2; if(m[mid] < v[i]) low = mid + 1; else high = mid - 1; } if(high >= i) r[i] = high; else r[i] = i; } for(int i = 1; i <= n; i++) cout << r[i] - i - 1 << " "; }转载于:https://www.cnblogs.com/litstrong/archive/2011/06/23/2088424.html
