poj 1986 Distance Queries (lca,在线做法dfs+rmq)

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. 然后第二次遇到某个点就是在回溯的时候了。

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}

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

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