2011-0032
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
这道题给你一个矩形花坛，花坛里从外向里每一圈长方形边框都是同一种花（不同方框也可能是同一种）。现在有Q个询问，每次询问给4个数，描述花坛内部一个子矩形的左上角和右下角，问你在这个子矩形中，有多少种花，数目最多的花是哪一种，有多少朵？（相同数量下取种类的标号最小的那个）
其实因为询问只有10000，矩形不超过500*500，所以每个询问我们完全可以用O（N）的复杂度来查询，每一次分别从左往右，从上到下地搜索一遍，来判断。
标程编辑中.....
#include <cstdio>
int kind,o,n,m,q,t,l,b,r,tot,index,count,m1,m2;
int a[501],c[501];
void inint(int k)
{
if(k==1)
{
for(int i=1;i<=(n+1)/2;i++)
scanf("%d",&a[i]);
o=1;
} else
{
for(int i=1;i<=(m+1)/2;i++)
scanf("%d",&a[i]);
o=m;m=n;n=o;
o=2;
}
}
int shu(int kind,int t,int b)
{
if(t<kind) t=kind;
if(b>n-kind+1) b=n-kind+1;
int tot=b-t+1;
if(tot<0) tot=0; else
{
if(t==kind) tot--;
if(b==n-kind+1) tot--;
if(n==kind+kind-1) tot++;
}
return tot;
}
int heng(int kind,int l,int r)
{
if(l<kind) l=kind;
if(r>m-kind+1) r=m-kind+1;
if(r-l+1<0) return 0;else
return r-l+1;
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
if(n>=m) inint(2); else inint(1);
m1=(n+1)/2;
m2=m-m1+1;
scanf("%d",&q);
for(int k=1;k<=q;k++)
{
scanf("%d%d%d%d",&t,&l,&b,&r);
t++;l++;b++;r++;
if(o==2)
{
count=t;t=l;l=count;
count=b;b=r;r=count;
}
for(int i=1;i<=250;i++) c[i]=0;
for(int i=t;i<=b;i++)
{
if(i<=m1) kind=i; else kind=n-i+1;
c[a[kind]]+=heng(kind,l,r);
}
for(int i=l;i<=r;i++)
{
if(i<=m1) kind=i; else kind=m-i+1;
if(kind<=m1)
c[a[kind]]+=shu(kind,t,b);
}
count=0;tot=0;
for(int i=1;i<=250;i++)
{
if(c[i]>0) tot++;
if(c[i]>count)
{
count=c[i];index=i;
} else
if((c[i]==count)&&(a[i]<index)) index=i;
}
printf("%d %d %d\n",tot,index,count);
}
}
return 0;
}
by hzwlzrj这道题给你一个矩形花坛，花坛里从外向里每一圈长方形边框都是同一种花（不同方框也可能是同一种）。现在有Q个询问，每次询问给4个数，描述花坛内部一个子矩形的左上角和右下角，问你在这个子矩形中，有多少种花，数目最多的花是哪一种，有多少朵？（相同数量下取种类的标号最小的那个）
其实因为询问只有10000，矩形不超过500*500，所以每个询问我们完全可以用O（N）的复杂度来查询，每一次分别从左往右，从上到下地搜索一遍，来判断。
标程编辑中.....
#include
int kind,o,n,m,q,t,l,b,r,tot,index,count,m1,m2;
int a[501],c[501];
void inint(int k)
{
if(k==1)
{
for(int i=1;i<=(n+1)/2;i++)
scanf("%d",&a[i]);
o=1;
} else
{
for(int i=1;i<=(m+1)/2;i++)
scanf("%d",&a[i]);
o=m;m=n;n=o;
o=2;
}
}
int shu(int kind,int t,int b)
{
if(t if(b>n-kind+1) b=n-kind+1; int tot=b-t+1; if(tot<0) tot=0; else { if(t==kind) tot--; if(b==n-kind+1) tot--; if(n==kind+kind-1) tot++; } return tot; } int heng(int kind,int l,int r) { if(l if(r>m-kind+1) r=m-kind+1; if(r-l+1<0) return 0;else return r-l+1; } int main() { while(scanf("%d %d",&n,&m)!=EOF) { if(n>=m) inint(2); else inint(1); m1=(n+1)/2; m2=m-m1+1; scanf("%d",&q); for(int k=1;k<=q;k++) { scanf("%d%d%d%d",&t,&l,&b,&r); t++;l++;b++;r++; if(o==2) { count=t;t=l;l=count; count=b;b=r;r=count; } for(int i=1;i<=250;i++) c[i]=0; for(int i=t;i<=b;i++) { if(i<=m1) kind=i; else kind=n-i+1; c[a[kind]]+=heng(kind,l,r); } for(int i=l;i<=r;i++) { if(i<=m1) kind=i; else kind=m-i+1; if(kind<=m1) c[a[kind]]+=shu(kind,t,b); } count=0;tot=0; for(int i=1;i<=250;i++) { if(c[i]>0) tot++; if(c[i]>count) { count=c[i];index=i; } else if((c[i]==count)&&(a[i] } printf("%d %d %d\n",tot,index,count); } } return 0; } by hzwlzrj