锐客网

  1. 首页 > it技术 > >

[NOIP模拟]beautiful

【[NOIP模拟]beautiful】题目描述:
一个长度为 n 的序列，对于每个位置 i 的数 ai 都有一个优美值，其定义是：找到序列中最长的一段 [l,r] ，满足 l≤i≤r，且 [l,r] 中位数为ai（我们比较序列中两个位置的数的大小时，以数值为第一关键字，下标为第二关键字比较。这样的话 [l,r] 的长度只有可能是奇数），r-l+1 就是 i 的优美值。接下来有 Q 个询问，每个询问 [l,r] 表示查询区间 [l,r] 内优美值的最大值。
输入格式：
第一行输入 n 。
接下来 n 个整数，代表 ai。
接下来 Q ，代表有 Q 个区间。
接下来 Q 行，每行两个整数 l,r (l≤r)，表示区间的左右端点。
输出格式：
对于每个区间的询问，输出答案。
样例输入：
8
16 19 7 8 9 11 20 16
8
3 8
1 4
2 3
1 1
5 5
1 2
2 8
7 8
样例输出：
7
3
1
3
5
3
7
3
数据规模：
对于 30% 的数据，满足：n,Q≤50；
对于 70% 的数据，满足：n,Q≤2000；
对于所有数据，满足 n≤2000；Q≤100000；ai≤200 。
题目分析:
1、看到n,Q不是很大,我们如果先预处理出每个数的优美值，再比较询问区间中最大的，这一步可以用RMQ，每次询问O(1),总计复杂度（Q）。但这道题其实询问可以直接扫一遍，虽然O(n*Q)，但是它不可能故意卡你，每次都从1扫到n，所以理想平均是（n/2*Q），当然还是数据水了一点点。
2、对于预处理优美值，可以枚举每一个数，对于它分别向左右两边依次扫，看他最长是哪个区间的中位数，注意第二关键字的处理，详细见代码，复杂度O(n^2)。
总的复杂度最小为：O（n^2+Q）。
附代码:

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int n,a[2010],w[2010],q; int readint() { char ch; int i=0,f=1; for(ch=getchar(); (ch<'0'||ch>'9')&&ch!='-'; ch=getchar()); if(ch=='-') { ch=getchar(); f=-1; } for(; ch>='0'&&ch<='9'; ch=getchar()) i=(i<<3)+(i<<1)+ch-'0'; return i*f; }void init() { int l[4010],r[4010]; //l、r下标存的是向左向右有多少比其大（小）的数 ，存的是半径长度 for(int i=1; i<=n; i++) { int cnt=0; memset(l,255,sizeof(l)); l[n]=0; //初始化为-1；l[n]（r[n]）则说明向左一定区间，它就是这个区间的中位数，因为下面 memset(r,255,sizeof(r)); r[n]=0; // 是利用对称性求解，所以如果r[n]（l[n]）=-1,则这种情况会被舍掉 ，显然不对 for(int j=i-1; j>=1; j--)//依次向左扩展 { if(a[j]>a[i]) cnt++; //记录大于它的个数， if(a[j]<=a[i]) cnt--; //记录小于它的个数，因为题目中有第二关键字下标，所以向左时相等取小 l[n+cnt]=i-j; //更新，当前比它大（小）多少个时的长度，以n为起点，避免出现负数 }//因为每次半径在变大，所以如果更新同一个l，是无需比较的 cnt=0; for(int j=i+1; j<=n; j++)//基本同上 { if(a[j]>=a[i]) cnt++; //向右时相等取大 if(a[j]for(int j=1-i; j<=i-1; j++)//因为向左最多i-1个数,对称性，所以向右也最多i-1个,否则怎么可能是中位数 if(l[n+j]>=0&&r[n-j]>=0)//对称性，相当于是向左向右大于它小于它的个数相等，>=0是因为必须要更新过，否则有都没有 { w[i]=max(w[i],l[n+j]+1+r[n-j]); //左右半径之和，再加本身 } } }int main() { //freopen("beautiful.in","r",stdin); //freopen("beautiful.out","w",stdout); n=readint(); for(int i=1; i<=n; i++) a[i]=readint(); init(); scanf("%d",&q); while(q--) { int l,r; l=readint(); r=readint(); int ans=0; for(int i=l; i<=r; i++) ans=max(ans,w[i]); printf("%d\n",ans); }return 0; }

    推荐阅读


    上一篇：IP地址CIDR合法性校验

    下一篇：四月是一位诗人