ACM

1631: [Usaco2007 Feb]Cow Party # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 670 Solved: 493 [Submit][Status][Discuss] Description # 农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X牛棚举行的奶牛派对．共有M(1≤M≤100000)条单向路连接着牛棚，第i条路需要Ti的时间来通过．牛们都很懒，所以不管是前去X牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少时间来回呢？ Input # 第1行：三个用空格隔开的整数.

hdu 3790 题目链接 题意：给出n个点m条无向边，每条边有一个距离和一个花费。给出s,t。问从s到t的最短距离以及最短距离时的最小花费。当有多个距离最短的方案时，选取花费最少的。

zoj 3195题目链接 题意：求树上三点的最短距离。。。 思路：两两求，和除以2. 因为忘记初始化p=0..WA了将近两个小时。。。？ 妈的智障。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月21日 星期六 14时44分39秒 4File Name :code/zoj/3195.cpp 5************************************************ */ 6 7 8 9#include <cstdio> 10#include <cstring> 11#include <iostream> 12#include <algorithm> 13#include <vector> 14#include <queue> 15#include <set> 16#include <map> 17#include <string> 18#include <cmath> 19#include <cstdlib> 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=5E4+7; 36int n,m; 37vector < pi > edge[N]; 38int q; 39int in[N]; 40int E[2*N],R[2*N],dis[N],depth[2*N]; 41int p; 42int dp[2*N][20]; 43void dfs( int u,int dep,int d,int pre) 44{ 45 46 // cout<<"u:"<<u<<" dep:"<<dep<<" d:"<<d<<endl; 47 p++; 48 E[p] = u; 49 depth[p] = dep; 50 R[u] = p ; 51 dis[u] = d; 52 53 54 int siz = edge[u].size(); 55 for ( int i = 0 ; i < siz ; i++) 56 { 57 int v = edge[u][i].fst; 58 if (v==pre) continue; 59 dfs(v,dep+1,d+edge[u][i].sec,u); 60 61 p++; 62 E[p] = u; 63 depth[p] = dep; 64 } 65} 66 67 68 69int _min( int l,int r) 70{ 71 if (depth[l]<depth[r]) return l; 72 return r; 73} 74void rmq_init() 75{ 76 for ( int i = 1 ; i <= 2*n+2 ; i++) dp[i][0] = i; 77 78 for ( int j = 1 ; (1<<j) <= 2*n+2 ; j++) 79 for ( int i = 1 ; i + (1<<j)-1 <= 2*n+2 ; i++) 80 dp[i][j] = _min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); 81} 82 83int rmq_min( int l,int r) 84{ 85 if (l>r) swap(l,r); 86 int k = 0 ; 87 while (1<<(k+1)<=r-l+1) k++; 88 return _min(dp[l][k],dp[r-(1<<k)+1][k]); 89} 90int solve (int x,int y) 91{ 92 int LCA = E[rmq_min(R[x],R[y])]; 93 int res = dis[x] + dis[y] - 2 * dis[LCA]; 94 return res; 95} 96int main() 97{ 98 #ifndef ONLINE_JUDGE 99 freopen("code/in.txt","r",stdin); 100 #endif 101 102 ms(in,0); 103 bool ok = false; 104 while (~scanf("%d",&n)){ 105 if (ok) puts(""); 106 ok = true; 107 for ( int i = 0 ; i <= n ; i++) edge[i].clear(); 108 for ( int i = 1 ; i <= n-1 ; i++) 109 { 110 int u,v,w; 111 scanf("%d%d%d",&u,&v,&w); 112 edge[u].push_back(make_pair(v,w)); 113 edge[v].push_back(make_pair(u,w)); 114 } 115 116 117 p = 0 ; 118 dfs(0,0,0,-1); 119 rmq_init(); 120 121 scanf("%d",&q); 122 while (q--) 123 { 124 int x,y,z; 125 scanf("%d%d%d",&x,&y,&z); 126 int ans = solve(x,y)+solve(x,z)+solve(y,z); 127 printf("%d\n",ans/2); 128 } 129 } 130 131#ifndef ONLINE_JUDGE 132 fclose(stdin); 133#endif 134 return 0; 135}

hdu2874题目链接 题意：给一个森林，问两点的最短距离，或者输出两点不联通。 思路：最最重要的一点是：添加虚点！ 最最重要的一点是：添加虚点！ 最最重要的一点是：添加虚点！ 所谓虚点，就是之前假设某个不存在的点，有点类似做辅助线。

题目链接 题意：求树上两点的最短距离？ 思路： dis[i]表示点i到根节点的距离，那么任意两点u,v的最短距离d = dis[u]+dis[v]-2*dis[LCA(u,v)]. 只需要求出rmq+dfs的在线方法求出lca(u,v)即可。

hdu 3530题目链接 题意：给出n个数，m,k，问最大的j-i+1，使得【i,j】间的最大值与最小值的差属于[m,k] 思路：rmq+尺取。 2A. 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月19日 星期四 16时52分03秒 4File Name :code/hdu/3530.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 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; 35int a[N]; 36int dp[N][20],dp2[N][20]; 37int m,k; 38 39void rmq_init() 40{ 41 for ( int i = 1 ; i <= n ; i ++) 42 dp[i][0] = dp2[i][0] = a[i]; 43 44 for ( int j = 1 ; (1<<j) <= n ; j++) 45 for ( int i = 1 ; i + (1<<j) -1 <= n ; i++) 46 { 47 dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); 48 dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]); 49 } 50} 51 52int rmq( int l,int r) 53{ 54 int k = 0 ; 55 while (1<<(k+1)<=r-l+1) k++; 56 int mx = max(dp[l][k],dp[r-(1<<k)+1][k]); 57 int mn = min(dp2[l][k],dp2[r-(1<<k)+1][k]); 58 59 return mx-mn; 60} 61 62int ruler() 63{ 64 int head = 1; 65 int tail = 1; 66 int res = -1 ; 67 while (tail<=n) 68 { 69 int cur = rmq(head,tail); 70 while (head<tail&&rmq(head,tail)>k) head++; 71 while (tail<n&&rmq(head,tail)<m) tail++; 72 //if (tail>n) break; 73 cur = rmq(head,tail); 74 if (cur>=m&&cur<=k) 75 { 76 res = max(res,tail-head); 77 } 78// cout<<"head:"<<head<<" tail:"<<tail<<" cur:"<<cur<<" res:"<<res<<endl; 79 tail++; 80 81 } 82 return res+1; 83} 84int main() 85{ 86 #ifndef ONLINE_JUDGE 87 freopen("code/in.txt","r",stdin); 88 #endif 89 90 while (scanf("%d %d %d",&n,&m,&k)!=EOF) 91 { 92 ms(dp,0); 93 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]); 94 if (m>k) 95 { 96 puts("0"); 97 continue; 98 } 99 rmq_init(); 100 printf("%d\n",ruler()); 101 } 102 103 104 105 #ifndef ONLINE_JUDGE 106 fclose(stdin); 107 #endif 108 return 0; 109}

poj1470题目链接 题意：求两点的lca. 思路：dfs+rmq. 读入技巧。 读入比较坑爹。。。 学会了一种新的读入技巧。 scanf("%2s",st); 表示读一个长度为2的字符串。。。读的时候会忽略各种空白字符。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月19日 星期四 15时44分12秒 4File Name :code/poj/1470.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 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=905; 34int n; 35vector <int> edge[N]; 36int in[N]; 37int E[2*N],R[2*N]; 38int depth[2*N]; 39int p; 40int dp[2*N][12]; 41int cnt[N]; 42void dfs( int u,int dep) 43{ 44 p++; 45 E[p] = u ; 46 depth[p] = dep; 47 R[u] = p; 48 int siz = edge[u].size(); 49 for ( int i = 0 ; i < siz ; i ++) 50 { 51 int v = edge[u][i]; 52 53 dfs(v,dep+1); 54 p++; 55 E[p] = u; 56 depth[p] = dep; 57 } 58} 59 60int _min( int l,int r) 61{ 62 if (depth[l]<depth[r]) return l; 63 return r; 64} 65void rmq_init() 66{ 67 for ( int i = 1 ; i <=2*n+2 ; i++) dp[i][0] = i; 68 69 for ( int j = 1 ; (1<<j) <= 2*n+2 ; j++) 70 for ( int i = 1 ; i + (1<<j)-1 <= 2*n+2 ; i++) 71 dp[i][j] = _min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); 72} 73 74int rmq_min( int l,int r) 75{ 76 if (l>r) swap(l,r); 77 int k = 0; 78 while (1<<(k+1) <= r-l+1) k++; 79 return _min(dp[l][k],dp[r-(1<<k)+1][k]); 80} 81int main() 82{ 83 #ifndef ONLINE_JUDGE 84 freopen("code/in.txt","r",stdin); 85 #endif 86 87 while (scanf("%d",&n)!=EOF) 88 { 89 ms(in,0); 90 for ( int i = 1 ; i <= n ; i++) edge[i].clear(); 91 for ( int i = 1 ; i <= n ; i++) 92 { 93 char ch[5]; 94 int x,num; 95 scanf("%d%2s%d%1s",&x,ch,&num,ch); 96// cout<<"x:"<<x<<" num:"<<num<<endl; 97 98 for ( int i = 1 ; i <= num ; i++) 99 { 100 int y; 101 scanf("%d",&y); 102 edge[x].push_back(y); 103 in[y]++; 104// cout<<"y:"<<y<<endl; 105 } 106 } 107 108 int root ; 109 for ( int i = 1 ; i <= n ; i++) if (in[i]==0) root = i ; 110// cout<<"root:"<<root<<endl; 111 p = 0; 112 dfs(root,0); 113 rmq_init(); 114 115 ms(cnt,0); 116 117 int q; 118 scanf("%d",&q); 119// cout<<"q:"<<q<<endl; 120 while (q--) 121 { 122 char ch[5]; 123 int x,y; 124 scanf("%1s%d%d%1s",ch,&x,&y,ch); 125 int LCA = E[rmq_min(R[x],R[y])]; 126// cout<<"x:"<<x<<" y:"<<y<<" LCA:"<<LCA<<endl; 127 cnt[LCA]++; 128 } 129// cout<<"n:"<<n<<endl; 130 for ( int i = 1 ; i <= n ; i++) 131 { 132// cout<<"cnt[i]:"<<cnt[i]<<endl; 133 if (cnt[i]==0) continue; 134 printf("%d:%d\n",i,cnt[i]); 135 } 136 } 137 138 #ifndef ONLINE_JUDGE 139 fclose(stdin); 140 #endif 141 return 0; 142}

poj1330题目链接 题意：给出一棵树，求两点的lca. 思路：将lca转化成rmq在线求解。 代码部分参考了：参考代码 感觉实现得很巧妙。。。 把树存成了有向图，dfs遇到的时候一定是第一次遇到，此时更新R. 然后第二次遇到某个点就是在回溯的时候了。

hdu4122 题目链接 题意：有n个订单和可以在m小时内制作月饼 接下来是n个订单的信息：需要在mon月，d日，year年，h小时交付订单r个月饼 接下来一行t,s表示制作的月饼可以保质t天，每保质一天需要花费s的价值 接下来m行表示从第0小时开始在该时间制作月饼的花费的价值 求完成所有订单消耗的最小价值

poj 3368 题目链接 题意：给出n个非减的数a[i]，求区间[l,r]中出现次数最多的数的出现的次数。 思路：由于数列非减，那么相等的数一定相邻。很容易系哪个到构造另一个数组f[i]，表示从当前位置向左边延伸最多延伸几个相等的数。

poj2452题目链接 题意：给你一组数a[n]，求满足a[i] < a[k] < a[j] (i <= k <= j)的最大的j-i。 思路：大概能想到是rmq，然后想出了一个错误复杂度的错误思路，还直到对拍才发现== 转载一篇题解：poj2452解题报告

hdu3193题目链接 题意：给出n个price 和distance，找到一个集合，集合中的每对在全集中找不到比他price和distance都要小的元素。小于是严格的。 思路：一开始以为找到最小值就好。。。结果漏洞百出。。这题还找不到题解。。。大概是太简单了。。？ 看了一份代码大概看明白了。。。

1首先先生成三个程序： 2$ g++ a+b.cpp -o a+b 3$ g++ a+b2.cpp -o a+b2 4$ g++ make.cpp -o make 5然后生成数据 6$ ./make > in.txt 7然后运行两个程序 8$ ./a+b < in.txt > out.txt 9$ ./a+b2 < in.txt > ans.txt 10最后对拍 11$ diff out.txt ans.txt 12输出的结果可以man diff查阅一下相关文档中关于输出含义的内容 13注：上面的$都是命令提示符，复制粘贴时不需要

lightoj 1081 题目链接 题意：和上一道一样，但是由于size变成了500，如果按照之前的做法会tle + mle… 很容易发现，由于是方阵，长宽是相等的，所以有一维是可以省略的。 也就是所谓的降维？

poj2019题目链接 题意：给一个方阵，k个查询，每个查询求某个方阵的最大值和最小值之差。 思路：二维rmq.同时用到最大值和最小值的话可以把初始化写在一起。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月16日 星期一 18时31分23秒 4File Name :code/poj/2019.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 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=251; 34int a[N][N]; 35int dp[N][N][8][8]; 36int dp2[N][N][8][8]; 37int n,b,q; 38 39void init_rmq() 40{ 41 for ( int i = 1 ;i <= n ; i++) 42 for ( int j = 1 ; j <= n ; j++) 43 dp[i][j][0][0] = dp2[i][j][0][0] = a[i][j]; 44 45 46 for ( int i = 0 ; (1<<i)<= n ; i++) 47 for ( int j = 0 ; (1<<j) <= n ; j++) 48 if (i==0 && j==0) continue; 49 else for ( int p = 1 ; p + (1<<i)-1 <= n ; p++) 50 for ( int q = 1 ; q + (1<<j)-1 <= n ; q++) 51 if (i==0) 52 { 53 dp[p][q][i][j] = max(dp[p][q][i][j-1],dp[p][q+(1<<(j-1))][i][j-1]); 54 dp2[p][q][i][j] = min(dp2[p][q][i][j-1],dp2[p][q+(1<<(j-1))][i][j-1]); 55 } 56 else 57 { 58 dp[p][q][i][j] = max(dp[p][q][i-1][j],dp[p+(1<<(i-1))][q][i-1][j]); 59 dp2[p][q][i][j] = min(dp2[p][q][i-1][j],dp2[p+(1<<(i-1))][q][i-1][j]); 60 } 61} 62 63 64int _rmq(int x1,int y1,int x2,int y2) 65{ 66 int k1 = 0 ; 67 int k2 = 0 ; 68 while (1<<(k1+1)<=x2-x1+1) k1++; 69 while (1<<(k2+1)<=y2-y1+1) k2++; 70 71 int tmp1 = dp[x1][y1][k1][k2]; 72 int tmp2 = dp[x2-(1<<k1)+1][y1][k1][k2]; 73 int tmp3 = dp[x1][y2-(1<<k2)+1][k1][k2]; 74 int tmp4 = dp[x2-(1<<k1)+1][y2-(1<<k2)+1][k1][k2]; 75 76 int mx = max(max(tmp1,tmp2),max(tmp3,tmp4)); 77 78 tmp1 = dp2[x1][y1][k1][k2]; 79 tmp2 = dp2[x2-(1<<k1)+1][y1][k1][k2]; 80 tmp3 = dp2[x1][y2-(1<<k2)+1][k1][k2]; 81 tmp4 = dp2[x2-(1<<k1)+1][y2-(1<<k2)+1][k1][k2]; 82 83 int mn = min(min(tmp1,tmp2),min(tmp3,tmp4)); 84 85 // cout<<"mx:"<<mx<<" mn:"<<mn<<endl; 86 87 return mx - mn; 88} 89 90 91int main() 92{ 93 #ifndef ONLINE_JUDGE 94 freopen("code/in.txt","r",stdin); 95 #endif 96 scanf("%d %d %d",&n,&b,&q); 97 for ( int i = 1 ; i <= n ; i++) 98 for ( int j = 1 ; j <= n ; j++) scanf("%d",&a[i][j]); 99 init_rmq(); 100 101 while (q--) 102 { 103 int x1,y1; 104 scanf("%d %d",&x1,&y1); 105 printf("%d\n",_rmq(x1,y1,x1+b-1,y1+b-1)); 106 } 107 108 109 110 #ifndef ONLINE_JUDGE 111 fclose(stdin); 112 #endif 113 return 0; 114}

hdu2888题目链接 题意：问某个矩阵内的最大值，并且问最大值是否是在四个角中出现。 思路：二维rmq.需要注意数组稍微开大1就会MLE，因为是四维数组，一维大一点，整个就会大很多==。

hdu3183题目链接 题意：n位长的数字串（n<=1000)，删掉m个（m<=n），使得剩下的数字串表示的数字最小。 忽略前导0. 思路：暴力搞就可以。要注意每位数字是有一定位置的范围的。比如当前是第i位数字，后面还要取n-m-i位数字，那么第i位数字最多只能取到第k位，k=m+i，因为这样才能保证后面还有n-m-i位数字。

1636: [Usaco2007 Jan]Balanced Lineup # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 680 Solved: 493 [Submit][Status][Discuss] Description # For the daily milking, Farmer John’s N cows (1 <= N <= 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height. Farmer John has made a list of Q (1 <= Q <= 200,000) potential groups of cows and their heights (1 <= height <= 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

1689: [Usaco2005 Open] Muddy roads 泥泞的路 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 311 Solved: 227 [Submit][Status][Discuss] Description # Farmer John has a problem: the dirt road from his farm to town has suffered in the recent rainstorms and now contains (1 <= N <= 10,000) mud pools. Farmer John has a collection of wooden planks of length L that he can use to bridge these mud pools. He can overlap planks and the ends do not need to be anchored on the ground. However, he must cover each pool completely. Given the mud pools, help FJ figure out the minimum number of planks he needs in order to completely cover all the mud pools.

题目链接：hdu4513 题意：给出一个n的数的序列，求出一个最长的回文字串，并且满足从[l,mid]单调增（非严格单调，可以相等），[mid,r]单调减（同样是可以相等） 思路：manacher…int型的也是可以搞的。。要求单调的话。。。while扩展的时候判一下就好了。。。