比赛链接：2017 计蒜之道初赛第六场 题解
A:水题
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { int d; scanf("%d",&d); printf("+-----+\n"); printf("|"); if(d>=20) printf("-"); else printf(" "); if(d>=90) printf(" 4G|\n"); else if(d>=60) puts(" 3G|"); else puts(" E|"); d-=20; for(int i=2;i<6;i++) { printf("|"); if(d>=20) { for(int j=0;j<i;j++) printf("-"); for(int j=i;j<5;j++) printf(" "); d-=20; } else for(int j=0;j<5;j++) printf(" "); puts("|"); } printf("+-----+\n"); return 0; }B,C:对于每个pair，RMQ一下就行了。
#include<bits/stdc++.h> using namespace std; const int N=2e5+100; const int M=2007; int dp[N][30]; int mm[N],h[N],n,k,x[M],y[M]; int gg=0; void initRMQ(int n) { mm[0]=-1; for(int i=1;i<=n;i++) { mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1]; dp[i][0]=h[i]; } for(int j=1;j<=mm[n];j++) for(int i=1;i+(1<<j)-1<=n;i++) dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } int rmq(int x,int y) { int k=mm[y-x+1]; return min(dp[x][k],dp[y-(1<<k)+1][k]); } int main() { freopen("in.txt","r",stdin); scanf("%d%d",&n,&k); for(int i=1;i<=n;++i) scanf("%d",&h[i]); initRMQ(n); int m,ans=0; scanf("%d",&m); for(int i=0;i<m;++i) scanf("%d%d",&x[i],&y[i]); for(int i=0;i<m;++i) for(int j=i+1;j<m;++j) { int mi=rmq(min(x[i],x[j]),max(x[i],x[j])); int y1=y[i],y2=y[j],res=0; if(y1>mi) res+=y1-mi,y1=mi; if(y2>mi) res+=y2-mi,y2=mi; res+=abs(y1-y2)+abs(x[i]-x[j]); if(res<=k) ++ans; } printf("%d\n",ans); return 0; }D: 有点类似单调栈的经典题 。 因此从前往后维护一个单调栈。对于每个点，枚举单调栈划分的区间，在每个区间内枚举高度。这样就能找到合法的区间能使其中的点与它组成的pair合法。 复杂度是 O(nh2) 。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+100; int n,pre[21][N],k,h[N]; vector<int> rm[N]; int main() { int t,m,x,y; scanf("%d%d",&n,&k); for(int i=1;i<=n;++i) scanf("%d",&h[i]); scanf("%d",&m); for(int i=0;i<m;++i) { scanf("%d%d",&x,&y); ++pre[y][x]; rm[x].push_back(y); } for(int i=1;i<=20;i++) for(int j=1;j<=n;j++) pre[i][j]+=pre[i][j-1]; for(int i=1;i<=n;i++) sort(rm[i].begin(),rm[i].end()); vector<int> s; ll ans=0; for(int i=1;i<=n;++i) { for(int j=0;j<rm[i].size();++j) for(int p=j+1;p<rm[i].size();++p) if(rm[i][p]-rm[i][j]<=k) ++ans; else break; if(s.size()) for(auto &u:rm[i]) { int l=1; for(auto r:s) { for(int v=1;v<=20;++v) { int L=0; if(u<=h[r]) L=i-k+abs(u-v); else L=i-k+abs(h[r]-u)+abs(h[r]-v); if(L>r) continue; if(L<l) L=l; ans+=pre[v][r]-pre[v][L-1]; } l=r+1; } } while(!s.empty()&&h[s.back()]>=h[i]) s.pop_back(); s.push_back(i); } cout << ans << endl; return 0; }