ACM

hdu 5835 题目链接 题意：n种礼物，每种a[i]个。现在有无穷个小朋友排成一排，分给每个人一个“普通”的礼物，一个“昂贵”的礼物（哪个普通哪个昂贵是自己定的，或者说，任意的） 要求是相邻的小朋友的普通的礼物不能是同一种。现在问最多能给多少小朋友分礼物。。。

hdu 5842题目链接 题意：给一个只由小写字母组成的字符串，每个字符映射到一个数字，问映射之后的最长上升子序列的长度。。 思路：上来写nlogn的LIS是我无脑了。。。wa了之后想了下。。其实只要统计不同的字母数就好了啊。。。set一下

hdu 3374 题目链接 题意：给出一个循环字符串，问最小表示出现的位置以及次数，最大表示出现的位置以及次数。 思路：之前只写过最小表示。。最大表示其实是一样的。。。把不等式方向变号即可。。。对于出现的次数。。。其实就等同于这个字符串是由几个子串组成。。。跑一遍kmp。。答案为len-nxt[len]，1A

hdu 2609 题目链接 题意：给出n个循环字符串，问有多少种。 思路：将每个字符串换成最小表示，然后set存一下即可。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月13日 星期六 02时44分21秒 4File Name :code/hdu/2609.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <stack> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <deque> 19#include <ctime> 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E4+7; 34int n; 35char s[N][105]; 36set<string>se; 37int minRep(char *s) 38{ 39 int n = strlen(s); 40 int i = 0 ; 41 int j = 1 ; 42 int k = 0 ; 43 while (i<n&&j<n&&k<n) 44 { 45 int t = s[(i+k)%n] - s[(j+k)%n]; 46 if (t==0) k++; 47 else 48 { 49 if (t>0) 50 i+=k+1; 51 else j+=k+1; 52 if (i==j) j++; 53 k = 0 ; 54 } 55 } 56 return i<j?i:j; 57} 58int main() 59{ 60 #ifndef ONLINE_JUDGE 61 freopen("code/in.txt","r",stdin); 62 #endif 63 while (~scanf("%d",&n)) 64 { 65 ms(s,0); 66 se.clear(); 67 // cout<<"n:"<<n<<endl; 68 char tmp[105]; 69 for ( int i = 0 ; i < n; i++) 70 { 71 scanf("%s",tmp); 72// cout<<"tmp:"<<tmp<<endl; 73 int k = minRep(tmp); 74// cout<<"k:"<<k<<endl; 75 int cnt = 1; 76 int len = strlen(tmp); 77 for ( int j = k ; cnt <= len ; j++,cnt++) 78 s[i][cnt-1] = tmp[j%len]; 79 se.insert(string(s[i])); 80 } 81// for ( int i = 0 ; i < n; i++) cout<<"s[i]:"<<s[i]<<endl; 82// 83 int ans = se.size(); 84 printf("%d\n",ans); 85 } 86 #ifndef ONLINE_JUDGE 87 fclose(stdin); 88 #endif 89 return 0; 90}

hdu 4162 题意：给出一串代表8个方向的数字，求这串序列的一阶差分（the first difference）的字典序最小的表示。 思路：先做个变换，按照题意，第i位的一阶差分 s[i] = ((s[i+1]-s[i])+8)%8; 然后求出最小表示开始的位置。。输出即可。

poj 1509 题目链接 题意&思路：同uva 1314 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月12日 星期五 18时48分29秒 4File Name :code/uva/1314.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <stack> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <deque> 19#include <ctime> 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E5+7; 34int n ; 35char s[N]; 36int minRep(char *s) 37{ 38 int n = strlen(s); 39 int i = 0; 40 int j = 1; 41 int k = 0; 42 while (i<n&&j<n&&k<n) 43 { 44 int t = s[(i+k)%n]-s[(j+k)%n]; 45 if (t==0) k++; 46 else 47 { 48 if (t>0) 49 i+=k+1; 50 else j+=k+1; 51 if (i==j) j++; 52 k = 0 ; 53 } 54 } 55 return i<j?i:j; 56} 57int main() 58{ 59 #ifndef ONLINE_JUDGE 60 freopen("code/in.txt","r",stdin); 61 #endif 62 int T; 63 cin>>T; 64 while (T--) 65 { 66 scanf("%s",s); 67 printf("%d\n",minRep(s)+1); 68 } 69 #ifndef ONLINE_JUDGE 70 fclose(stdin); 71 #endif 72 return 0; 73}

uva 1314 题目链接 题意：给定一个循环字符串，问字典序最小的串的开始位置。最小表示法裸题。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月12日 星期五 18时48分29秒 4File Name :code/uva/1314.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <stack> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <deque> 19#include <ctime> 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E5+7; 34int n ; 35char s[N]; 36int minRep(char *s) 37{ 38 int n = strlen(s); 39 int i = 0; 40 int j = 1; 41 int k = 0; 42 while (i<n&&j<n&&k<n) 43 { 44 int t = s[(i+k)%n]-s[(j+k)%n]; 45 if (t==0) k++; 46 else 47 { 48 if (t>0) 49 i+=k+1; 50 else j+=k+1; 51 if (i==j) j++; 52 k = 0 ; 53 } 54 } 55 return i<j?i:j; 56} 57int main() 58{ 59 #ifndef ONLINE_JUDGE 60 freopen("code/in.txt","r",stdin); 61 #endif 62 int T; 63 cin>>T; 64 while (T--) 65 { 66 scanf("%d\n%s",&n,s); 67 printf("%d\n",minRep(s)); 68 } 69 #ifndef ONLINE_JUDGE 70 fclose(stdin); 71 #endif 72 return 0; 73}

首先放一波资料： 参考博客 对于字符串循环同构的最小表示法，其问题实质是求S串的一个位置，从这个位置开始循环输出S，得到的S’字典序最小。 一种朴素的方法是设计i,j两个指针。其中i指向最小表示的位置，j作为比较指针。

hdu 4300题目链接 吐槽：题意难懂的一逼，关键的地方根本没有说清好么。。。竟然还是多校题。。。。出题人英语是体育老师教的吧。。？本来挺傻逼一道题。。被这完全没有说清楚的题意搞得很不爽。。。

hdu 3336 题目链接 题意：给一个字符串，问这个字符串的所有前缀的出现次数的和。 思路：这道题需要完全理解 nxt 函数是干嘛的。nxt[i] 表示的是字符串的 0..i-1 位中，前缀和后缀相等的串的最长长度为 nxt[i]。

hdu 2594 题目链接 题意：given string s1,s2, find the longest prefix of s1 that is a suffix of s2. 思路：kmp。。。懒得说了。注意边界。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月12日 星期五 01时12分51秒 4File Name :code/hdu/2594.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <stack> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <deque> 19#include <ctime> 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=5E5+7; 34char a[N],b[N]; 35int nxt[N]; 36void getnxt( char *s) 37{ 38 int n = strlen(s); 39 int i = 0 ; 40 int j = -1; 41 nxt[0] = -1; 42 while (i<n) 43 if (j==-1||s[i]==s[j]) nxt[++i]=++j; 44 else j = nxt[j]; 45} 46int kmp(char *a,char *b) 47{ 48 int n = strlen(a); 49 int m = strlen(b); 50 getnxt(b); 51 int i = 0; 52 int j = 0; 53 while (i<n) 54 { 55 if (j==-1||a[i]==b[j]) i++,j++; 56 else j = nxt[j]; 57 } 58 if (i==n) return j; 59 return 0; 60} 61int main() 62{ 63 #ifndef ONLINE_JUDGE 64 freopen("code/in.txt","r",stdin); 65 #endif 66 while (~scanf("%s %s",a,b)) 67 { 68// cout<<"a:"<<a<<" b:"<<b<<endl; 69 int k = kmp(b,a); 70 if (k==0) 71 puts("0"); 72 else printf("%s %d\n",b+(strlen(b)-k),k); 73 74 ms(a,0); 75 ms(b,0); 76 } 77 #ifndef ONLINE_JUDGE 78 fclose(stdin); 79 #endif 80 return 0; 81}

hdu 2203 题目链接 题意：给定字符串A（一个环），和字符串B，问B是否在A中出现过。 思路：环的问题。。复制一遍到末尾就好了。。出于严谨的考虑。。我们只复制n-1个字符。 以及要记得判断文本串的长度是否大于等于模板串，如果小于，直接判断no//然而题目数据太水，没判也过了

hdu 3746题目链接 题意：给定一个字符串，是一个环（首尾相连），问至少再添加多少个珠子才能使得整个串是循环的。。。 思路：一下子想到了最小覆盖子串的模型。。。我求出最小覆盖子串的长度（n-nxt[n]）。然后特判下最小覆盖子串的长度等于字符串长度的情况。。。试着叫了一发。。。竟然就A了2333.。。大概是所谓的题感吧（逃

hdu 5763 题目链接 题意：给定两个字符串A和B，每个出现在A中的B(可以overlap)都有两种含义，问A串一共可能有多少种含义。 思路：kmp+dp. 考虑dp[i]为前i个字符（也就是从开始长度为i，注意不是字符串的下标为i）的含义数。

hdu 1867 题意 题意：给两个字符串，将两个字符串首尾拼接之后得到一个长度最短的字符串，求这个最短的字符串（一个串的前缀可能是另一个串的后缀，这样的话只出现一次就行了） 思路：kmp。。注意和hdu 1841区分。那道题是只要得到一个串包含两个串即可。这道题是首尾拼接得到。

hdu 1841题目链接 题意：给两个字符串，问包含这两个字符串的最小的字符串的长度（最小是因为，一个串的子串可能是另一个串的后缀，这样出现一次就可以了） 思路：其实这道题最关键的思想部分是和kmp没有关系的。。。

hdu 1358 题目链接 题意：给一个字符串，求这个字符串的每个前缀（包括本身）的能否由k个子串组成（K>1） 思路：和poj 2406 比较类似。。 结论：字符编号从0开始，如果又i%(i-next[i])==0，则i前面的 串为一个轮回串，其中轮回子串出现i/(i-next[i])次。

hdu 2087 题目链接 题意：问模式串在文本串中出现的次数，不允许重叠。 思路：kmp，关键在于不允许重叠。。。 其实只要每次找到的时候j=0一下就好咯。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月11日 星期四 02时52分44秒 4File Name :code/hdu/2087.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <stack> 14#include <set> 15#include <map> 16#include <string> 17#include <cmath> 18#include <cstdlib> 19#include <deque> 20#include <ctime> 21#define fst first 22#define sec second 23#define lson l,m,rt<<1 24#define rson m+1,r,rt<<1|1 25#define ms(a,x) memset(a,x,sizeof(a)) 26typedef long long LL; 27#define pi pair < int ,int > 28#define MP make_pair 29 30using namespace std; 31const double eps = 1E-8; 32const int dx4[4]={1,0,0,-1}; 33const int dy4[4]={0,-1,1,0}; 34const int inf = 0x3f3f3f3f; 35const int N=1E3+7; 36char a[N],b[N]; 37int nxt[N]; 38 39void getnxt(char *s) 40{ 41 int i = 0; 42 int j = -1; 43 nxt[0] = -1; 44 int n = strlen(s); 45 while (i<n) 46 if (j==-1||s[i]==s[j]) nxt[++i]=++j; 47 else j = nxt[j]; 48} 49int kmp(char *a,char *b) 50{ 51 int n = strlen(a); 52 int m = strlen(b); 53 getnxt(b); 54 int i = 0; 55 int j = 0; 56 int cnt = 0 ; 57 while (i<n) 58 { 59 if (j==-1||a[i]==b[j]) i++,j++; 60 else j=nxt[j]; 61 if (j==m) 62 { 63 cnt++; 64 j=0; //不允许重叠 65 } 66 } 67 return cnt; 68 69} 70int main() 71{ 72 #ifndef ONLINE_JUDGE 73 freopen("code/in.txt","r",stdin); 74 #endif 75 76 while (~scanf("%s",a)) 77 { 78 if (a[0]=='#') break; 79 scanf("%s",b); 80 int ans = kmp(a,b); 81 printf("%d\n",ans); 82 } 83 84 #ifndef ONLINE_JUDGE 85 fclose(stdin); 86 #endif 87 return 0; 88}

hdu 1711 题目链接 题意：给定两个数列，问第二个数列在第一个数列中出现的位置（第一个元素对应的位置） 思路：数列也可以看成字符串，然后左kmp，返回的答案是i+1-m。。。1A

poj 3080 题目链接 题意：给出n个字符串（n<=10），字符串长度不超过70，问出现在全部n个字符串中的最长并且字典序最小的长度大于等于3的子串。 思路：数据范围很小。。。直接暴力枚举+kmp匹配一下。。。