ACM

poj 2185 题目链接 题意：给出一个字符矩形，问一个面积最小的矩形，覆盖掉整个矩形。大概就是二维的最小覆盖子串。 思路：对于每一行做最小覆盖子串，然后求lcm，每一列也是如此。最后记得判断不能超过原有的n,m。

参考资料（本文大部分是参考这篇博客，附带一些证明步骤的解释） 首先明确一些概念： 最小覆盖子串：对于某个字符串s，它的最小覆盖子串指的是长度最小的子串p，p满足通过自身的多次连接得到q，最后能够使s成为q的子串。 比如： 对于s=“abcab”，它的最小覆盖子串p=“abc”，因为p通过在它后面再接上一个p（即重叠0个字符），可以得到q=“abcabc”，此时s是q的子串。 对于s=“ababab”，它的最小覆盖子串为p=“ab”。

poj 2752题目链接 题意：求出所有的前缀和后缀相同的子串的长度。 思路：求出nxt函数，观察发现，从从len递归向前就是答案。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月10日 星期三 21时05分52秒 4File Name :code/poj/2752.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=4E6+7; 36int n; 37string a; 38int nxt[N]; 39void getnxt( int n) 40{ 41 int i = 0 ; 42 int j = -1 ; 43 nxt[0] = -1; 44 while (i<n) 45 if (j==-1||a[i]==a[j]) nxt[++i]=++j; 46 else j = nxt[j]; 47} 48void print( int x) 49{ 50 if (nxt[x]!=-1) 51 { 52 print(nxt[x]); 53 printf("%d ",x); 54 } 55} 56int main() 57{ 58 #ifndef ONLINE_JUDGE 59 freopen("code/in.txt","r",stdin); 60 #endif 61// ios::sync_with_stdio(false); 62 while (cin>>a) 63 { 64 int len = a.length(); 65 getnxt(len); 66 // for ( int i = 0 ; i < len ; i++) cout<<i<<" nxt[i]:"<<nxt[i]<<endl; 67 print(nxt[len]); 68 printf("%d\n",len); 69 70 } 71 72 #ifndef ONLINE_JUDGE 73 fclose(stdin); 74 #endif 75 return 0; 76}

hdu1686 题意：给出模式串和文本串，问模式串在文本串中出现了多少次，可以overlap. 思路：思考naive的匹配过程。nxt函数不过是改进了当失配发生时，不是移动1位，而是移动多位。nxt函数的含义是当失配发生时，移动到的位置….所以有的教程管这个叫失配函数吧，也不是很难理解的样子。

20170801update：当时竟然没有强调 next 函数的含义？ next[i] 的含义是，i 之前的整个前缀中，最长的「前缀和后缀相同」的长度。 看图： KMP 感觉是我学到现在最难懂的一个算法了 QAQ 为什么你们都那么强啊，看几个小时就看懂了……

题目链接 傻逼模拟。。读完题就ac了。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月07日 星期日 18时04分18秒 4File Name :code/whust2016/#1/D.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=280; 34int n,m; 35int total,adva,advb; 36struct Friend 37{ 38 int money; 39 int adv; 40}f[N]; 41struct Room 42{ 43 int type; 44 int cost; 45 int adv; 46}r[N]; 47struct Ans 48{ 49 int val; 50 int rid; 51 int fid; 52 bool operator < (Ans b)const 53 { 54 return val>b.val; 55 } 56}ans[300*300]; 57int main() 58{ 59 #ifndef ONLINE_JUDGE 60 freopen("code/in.txt","r",stdin); 61 #endif 62 cin>>total>>adva>>advb; 63 cin>>n; 64 for ( int i = 1 ; i <= n ; i++) 65 scanf("%d %d",&f[i].money,&f[i].adv); 66 scanf("%d",&m); 67 for ( int i = 1 ; i <= m ; i++) 68 scanf("%d%d%d",&r[i].type,&r[i].cost,&r[i].adv); 69 int cnt = 0 ; 70 for ( int i = 1 ; i <= m ; i++) 71 { 72 if (r[i].type==1) 73 { 74 if (r[i].cost<=total) 75 { 76 cnt++; 77 ans[cnt].val = r[i].adv+adva; 78 ans[cnt].rid = i; 79 ans[cnt].fid = -1; 80 } 81 continue; 82 } 83 else 84 { 85 for ( int j = 0 ; j <= n ; j++) 86 { 87 if (j==0) //自己住双人间 88 { 89 if (r[i].cost<=total) 90 { 91 cnt++; 92 ans[cnt].val = r[i].adv+advb; 93 ans[cnt].rid = i ; 94 ans[cnt].fid = -1; 95 } 96 } 97 else 98 { 99 if (r[i].cost<=total*2&&r[i].cost<=f[j].money*2) 100 { 101 cnt++; 102 ans[cnt].val = r[i].adv+f[j].adv; 103 ans[cnt].rid = i ; 104 ans[cnt].fid = j; 105 } 106 } 107 } 108 } 109 } 110// for ( int i = 1 ; i <= cnt ; i++) 111// { 112// printf("val:%d room: %d friend : %d \n",ans[i].val,ans[i].rid,ans[i].fid); 113// } 114 if (cnt==0) 115 { 116 puts("Forget about apartments. Live in the dormitory."); 117 }else 118 { 119 sort(ans+1,ans+cnt+1); 120 if (r[ans[1].rid].type==1) 121 { 122 printf("You should rent the apartment #%d alone.\n",ans[1].rid); 123 } 124 else 125 { 126 if (ans[1].fid==-1) 127 { 128 printf("You should rent the apartment #%d alone.\n",ans[1].rid); 129 } 130 else 131 { 132 133 printf("You should rent the apartment #%d with the friend #%d.\n",ans[1].rid,ans[1].fid); 134 135 } 136 } 137 } 138 #ifndef ONLINE_JUDGE 139 fclose(stdin); 140 #endif 141 return 0; 142}

题目链接 其实就是括号匹配的模型。。用栈即可。。被我写挂好几发。。该死该死。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月07日 星期日 17时34分13秒 4File Name :code/whust2016/#1/HH.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10 11#include <algorithm> 12#include <vector> 13#include <queue> 14#include <stack> 15#include <set> 16#include <map> 17#include <string> 18#include <cmath> 19#include <cstdlib> 20#include <deque> 21#include <ctime> 22#include <cctype> 23#define fst first 24#define sec second 25#define lson l,m,rt<<1 26#define rson m+1,r,rt<<1|1 27#define ms(a,x) memset(a,x,sizeof(a)) 28typedef long long LL; 29#define pi pair < int ,int > 30#define MP make_pair 31 32using namespace std; 33const double eps = 1E-8; 34const int dx4[4]={1,0,0,-1}; 35const int dy4[4]={0,-1,1,0}; 36const int inf = 0x3f3f3f3f; 37const int N=1E4+7; 38char st[N]; 39int s[N]; 40int n; 41int plow[N]; 42int pup[N]; 43int ans[N]; 44stack<int>stk; 45 46 47bool ok(int x, int y) 48{ 49 // cout<<"x:"<<x<<" y:"<<y<<endl; 50 if (plow[x]>0&&pup[y]>0) 51 { 52 ans[pup[y]] = plow[x]; 53 return true; 54 } 55 if (plow[y]>0&&pup[x]>0) 56 { 57 ans[pup[x]] = plow[y]; 58 return true; 59 } 60 return false; 61} 62int main() 63{ 64 #ifndef ONLINE_JUDGE 65 freopen("code/in.txt","r",stdin); 66 #endif 67 68 cin>>n>>st; 69 n*=2; 70 int cntA = 0 ; 71 int cnta = 0 ; 72 ms(pup,0); 73 ms(plow,0); 74 for ( int i = 0 ; i < n ; i++) 75 { 76 if (st[i]>='a'&&st[i]<='z') 77 { 78 cnta++; 79 plow[i] = cnta; 80 } 81 else 82 { 83 cntA++; 84 pup[i] = cntA; 85 } 86 } 87// for ( int i = 0 ; i < n ; i++) cout<<"plow[i]:"<<plow[i]<<" pup[i]:"<<pup[i]<<endl; 88 for ( int i = 0 ; i < n ; i++) 89 { 90 st[i] = toupper(st[i]); 91 } 92// cout<<"st:"<<st<<endl; 93 ms(ans,-1); 94 while (!stk.empty()) stk.pop(); 95 stk.push(0); 96 for ( int i = 1 ; i < n ; i++) 97 { 98 while (!stk.empty()&&st[stk.top()]==st[i]&&ok(stk.top(),i)&&i<n) 99 { 100 stk.pop(); 101 i++; 102 } 103 stk.push(i); 104 } 105 for ( int i = 1 ; i <= n/2 ; i++) 106 { 107 if (ans[i]==-1) 108 { 109 puts("Impossible"); 110 return 0; 111 } 112 } 113 for ( int i = 1 ; i < n/2 ; i++) printf("%d ",ans[i]); 114 printf("%d\n",ans[n/2]); 115 116 #ifndef ONLINE_JUDGE 117 fclose(stdin); 118 #endif 119 return 0; 120}

hdu 3415 题意：给出n个整数，是一个环（也就是a[n]右边是a[1]）求一段长度不超过k的数使得和最大，问最大和是多少并给出这段数的位置。 思路：为了处理环，先把n个数复制一下就好，然后求前缀和sum[i]

ural 1126 题意：n个数，求从第k个元素开始，求每k个元素的最大值（一共求n-k+1次） 思路：单调队列。 单调队列学习链接 其实单调队列挺容易的理解的。。。当时觉得写不明白大概是因为看到的代码写得太丑了2333

hdu 1559 题意：给你一个m×n的整数矩阵，在上面找一个x×y的子矩阵，使子矩阵中所有元素的和最大。 思路：二维前缀和就好。。。和单调栈没有半毛钱关系吧。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月03日 星期三 21时08分18秒 4File Name :code/hdu/1559.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 <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 28 29using namespace std; 30const double eps = 1E-8; 31const int dx4[4]={1,0,0,-1}; 32const int dy4[4]={0,-1,1,0}; 33const int inf = 0x3f3f3f3f; 34const int N=1E3+7; 35int a[N][N]; 36int sum[N][N]; 37int n,m,x,y; 38int main() 39{ 40 #ifndef ONLINE_JUDGE 41 freopen("code/in.txt","r",stdin); 42 #endif 43 int T; 44 cin>>T; 45 while (T--) 46 { 47 ms(sum,0); 48 scanf("%d%d%d%d",&n,&m,&x,&y); 49 for ( int i = 1 ; i <= n ; i++) 50 for ( int j = 1 ; j <= m ; j++) 51 { 52 scanf("%d",&a[i][j]); 53 sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1] + a[i][j]; 54 } 55 int ans = 0 ; 56 for ( int i = 1 ; i <= n-x+1 ; i++) 57 for ( int j = 1 ; j <= m-y+1 ; j++) 58 ans = max(ans,sum[i+x-1][j+y-1]-sum[i-1][j+y-1]-sum[i+x-1][j-1]+sum[i-1][j-1]); 59 60 printf("%d\n",ans); 61 } 62 63 #ifndef ONLINE_JUDGE 64 fclose(stdin); 65 #endif 66 return 0; 67}

poj 3494 题意：给出一个n*m个0-1图，求最大的全部由1组成的矩阵。 思路：同poj 1964，一共做n+2×m次单调栈。。。数组开小re一发。。某处stk忘记清空re 1发。。。智力-2.。。3A

poj 2796 题意：给出一个人n（1E5）天的情绪值（0..1E6），一段时间的value的定义是这段时间的情绪之和*这段时间情绪的最小值。 现在求value的最大值，并且输出得到这个最大值的区间。

poj 2082 题目链接 题意：这道题简直就是。。。教给大家怎么把一句话把简单的题让人出得看不懂。。。真的一点意思都没有。给出n个矩形的宽度和高度，这些矩形并排顺次排列在x轴上，问最大面积。

poj 1964 题意：n*m 的 maze，由 ‘R’ 和 ‘F’ 组成，现在要求找到面积最大的矩形，使得矩形中所有格子都是 ‘F’。 思路：单调栈。一开始神 tm TLE 了，复杂度明明没问题啊。 结果看到有人说这题数据量比较大，scanf 会超时，所以要用输入挂，getchar 什么的。

poj 3250 题意： n头牛排成一列，第n只牛在最前面，第1只牛在最后面。第i只牛能看到的牛的个数是，它前面的且没有被其他牛遮挡的牛的个数，遮挡的条件是高度大于或者相同。现在问所有牛能看到的牛的个数的和。

poj 2559 题意：给定从左到右多个矩形，已知这此矩形的宽度都为1，长度不完全相等。这些矩形相连排成一排，求在这些矩形包括的范围内能得到的面积最大的矩形，求该面积。所求矩形可以横跨多个矩形，但不能超出原有矩形所确定的范围。

题目链接 题意：定义一个函数 F。 For example: F(babbabbababbab, babb) = 6. The list of pairs is as follows: (1, 4), (4, 7), (9, 12) Its continuous sequences are: (1, 4) (4, 7) (9, 12) (1, 4), (4, 7) (4, 7), (9, 12) (1, 4), (4, 7), (9, 12) 二分。 题目描述得很烂，看例子吧，大概就是：如果字符串 y 在字符串 x 中出现 n 次，那么 F(x,y)=n*(n+1)/2

poj 2406 题意：给定一个字符串 L，已知这个字符串是由某个字符串 S 重复 R 次而得到的， 求 R 的最大值 思路：论文题。 转载论文中的题解： 做法比较简单，穷举字符串 S 的长度 k，然后判断是否满足。判断的时候， 先看字符串 L 的长度能否被 k 整除，再看 suffix(1) 和 suffix(k+1) 的最长公共前缀是否等于 n-k。在询问最长公共前缀的时候，suffix(1) 是固定的，所以 RMQ 问题没有必要做所有的预处理，只需求出 height 数组中的每一个数到 height[rank[1]] 之间的最小值即可。整个做法的时间复杂度为 O(n)

题目连接 题意：求所有不同的子串个数。 思路：后缀数组。和上一道题一样，就是数据范围变成了 5E4…1A 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月02日 星期二 18时32分28秒 4File Name :code/spoj/subst1.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set> 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=5E4+7; 32char s[N]; 33int sa[N],rk[N],t[N],t2[N],cnt[N],height[N]; 34int cmp (int *r,int a,int b,int l){ return r[a]==r[b]&&r[a+l]==r[b+l];} 35void getSa(int n,int m) 36{ 37 int *x=t,*y=t2; 38 ms(cnt,0); 39 for ( int i = 0 ; i < n ; i++) cnt[x[i]=s[i]]++; 40 for ( int i = 0 ; i < m ; i++) cnt[i]+=cnt[i-1]; 41 for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[i]]] = i; 42 for ( int k = 1 ; k <= n ; k<<=1) 43 { 44 int p = 0; 45 for ( int i = n-k ; i < n ; i++) y[p++] = i; 46 for ( int i = 0 ; i < n; i++) if (sa[i]>=k) y[p++] = sa[i]-k; 47 ms(cnt,0); 48 for ( int i = 0 ; i <n ; i++) cnt[x[y[i]]]++; 49 for ( int i = 0 ;i < m ; i++) cnt[i]+=cnt[i-1]; 50 for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[y[i]]]] = y[i]; 51 swap(x,y); 52 p = 1; 53 x[sa[0]] = 0; 54 for ( int i = 1 ; i < n ; i++ ) 55 x[sa[i]] = cmp(y,sa[i-1],sa[i],k)?p-1:p++; 56 if (p>=n) break; 57 m = p; 58 } 59} 60void getHeight( int n) 61{ 62 int k = 0 ; 63 for ( int i = 0 ; i <n ; i ++) rk[sa[i]] = i ; 64 height[0] = 0 ; 65 for ( int i = 0 ; i < n ; i++) 66 { 67 if (rk[i]==0) continue; 68 if (k) k--; 69 int j = sa[rk[i]-1]; 70 while (s[i+k]==s[j+k]) k++; 71 height[rk[i]] = k; 72 } 73} 74int getSuffix(char s[]) 75{ 76 int len = strlen(s); 77 int up = 0 ; 78 for ( int i = 0 ; i < len ; i++) 79 { 80 int val = s[i]; 81 up = max(up,val); 82 } 83 s[len++]='$'; 84 getSa(len,up+1); 85 getHeight(len); 86 return len; 87} 88int solve ( int n) 89{ 90 ms(cnt,0); 91 int up = 0; 92 for ( int i = 0 ;i <n ; i ++) cnt[height[i]]++, up = max(up,height[i]); 93 for ( int i = up-1 ; i >= 1; i--) cnt[i]+=cnt[i+1]; 94 int res = 0 ; 95 for ( int i = 1 ; i <=up ; i++) 96 res+=cnt[i]; 97 return res; 98} 99int main() 100{ 101 #ifndef ONLINE_JUDGE 102 freopen("code/in.txt","r",stdin); 103 #endif 104 int T; 105 scanf("%d",&T); 106 while (T--) 107 { 108 scanf("%s",s); 109 int len = getSuffix(s); 110 LL ans = 1LL*len*(len-1)/2; 111 ans-=1LL*solve(len); 112 printf("%lld\n",ans); 113 } 114 #ifndef ONLINE_JUDGE 115 fclose(stdin); 116 #endif 117 return 0; 118}

hdu5787 题意：给出l,r,k求区间[l,r]中满足任意相邻k个数字都不相同的数的个数. 思路：数位dp,dp[i][k1][k2][k3][k4]表示长度为i，前1位是k1，前2位是k2，前3位是k3，前4位是k4的方案数. 注意不允许前导0.2A