linux下的对拍写法

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.