欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

题解 P2879 【[USACO07JAN]区间统计Tallest Cow】

程序员文章站 2022-07-12 17:38:44
...
  • 题目链接:
    https://www.luogu.org/problemnew/show/P2879

  • 思路:

    先不管最大高度,我们读入一对x,y.说明,x+1~y-1之间牛的身高都小于x,y。

    然后不妨将这个区间打个标记-1。所有操作后,可知最高的那个牛它的标记一定是0,并且标记数量与身高排名正相关,于是再将所有奶牛的标记数加上最高身高h就是可能的最大身高。

    因为之前的操作保证标记的数量是按着身高排名来的,加上最大身高当然是最大可能身高。

    然后我们是要将x+1~y-1打标记,根据差分数组的思维,就要让x+1处-1,y处+1。

  • 注意:

    • 判重,用map,pair或hash。
    • 可能读入x,y大小关系符的需要swap
  • 代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=10005;
int n,m,h,i;
int f[maxn],tp[maxn];
bool h_[19260817];    //暴力Hash需谨慎  逃)
bool m_hash(int x,int y)
{
    int t=(x*y+x/y+x+y+(x>>1)-(y>>1))%19260817; +1s
    if(h_[t])return 0;
    else h_[t]=1;
    return 1;
}
int main()
{
    cin>>n>>i>>h>>m;
    for(register int i=1;i<=m;i++)
    {
        register int a,b;
        scanf("%d %d",&a,&b);
        if(a>b)swap(a,b);
        if(m_hash(a,b)){
        tp[a+1]--,tp[b]++;
        }
    }
    for(register int i=1;i<=n;i++)
    {
        f[i]=f[i-1]+tp[i];
        cout<<f[i]+h<<endl;
    }
    return 0;
}