洛谷1578：[wc2002]奶牛浴场——题解(代码片段)

关键词： 奶牛的跳牛游戏 USACO题解 洛谷2415题解python

#include<cstdio>
#include<queue>
#include<cctype>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=2002;
inline int read()int x;scanf("%d",&x);return x;
struct node
    int x,y;
a[5010];
bool cmp1(node a,node b)
    return a.x<b.x||(a.x==b.x&&a.y<b.y);

bool cmp2(node a,node b)
    return a.y<b.y;

int main()
    int n=read(),m=read();
    int s=read();
    for(int i=1;i<=s;i++)a[i].x=read(),a[i].y=read();
    a[++s].x=0;a[s].y=0;a[++s].x=n;a[s].y=0;
    a[++s].x=0;a[s].y=m;a[++s].x=n;a[s].y=m;
    sort(a+1,a+s+1,cmp1);
    int ans=0;
    for(int i=1;i<=s;i++)
    int l=0,r=m,v=n-a[i].x;
    for(int j=i+1;j<=s;j++)
        if(l<=a[j].y&&a[j].y<=r)
        if(v*(r-l)<=ans)break;
        ans=max(ans,(a[j].x-a[i].x)*(r-l));
        if(a[i].y==a[j].y)break;
        if(a[j].y>a[i].y)r=min(r,a[j].y);
        else l=max(l,a[j].y);
        
    
    l=0,r=m,v=a[i].x;
    for(int j=i-1;j>=1;j--)
        if(l<=a[j].y&&a[j].y<=r)
        if(v*(r-l)<=ans)break;
        ans=max(ans,(a[j].x-a[i].x)*(r-l));
        if(a[i].y==a[j].y)break;
        if(a[j].y>a[i].y)r=min(r,a[j].y);
        else l=max(l,a[j].y);
        
    
    
    sort(a+1,a+s+1,cmp2);
    for(int i=1;i<=s-1;i++)ans=max(ans,(a[i+1].y-a[i].y)*n);
    printf("%d\\n",ans);
    return 0;

洛谷p1578奶牛浴场

P1578奶牛浴场题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产... 查看详情

p1578奶牛浴场

P1578奶牛浴场 题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位... 查看详情

p1578奶牛浴场(代码片段)

题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显... 查看详情

[luogup1578]奶牛浴场（dp）

传送门 O(s2)算法详见论文 王知昆--浅谈用极大化思想解决最大子矩形问题我就复制你能把我怎么样QAQ#include<cstdio>#include<iostream>#include<algorithm>#defineN5010#definemax(x,y)((x)>(y)?(x):(y))#definemin(x,y)((x)& 查看详情

洛谷p1824进击的奶牛题解

此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：https://www.luogu.org/problem/show?pid=1824题目描述FarmerJohn建造了一个有N(2<=N<=100,000)个隔间的牛棚，这些隔间分布在一条直线上，坐标是x1,...,xN... 查看详情

洛谷p2341[haoi2006]受欢迎的牛题解

此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：https://www.luogu.org/problem/show?pid=2341题目描述每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自... 查看详情

vijos1055奶牛浴场

Description求一个不覆盖指定点的最大子矩阵,(n,mleqslant3 imes10^5,Sleqslant5 imes10^3).Sol没有名字的算法都叫xjblg算法?枚举每个点成为极大子矩阵边界的情况,然后维护上下边界.还有一种情况就是左右边界是矩阵两边的情况,需要预处理一... 查看详情

dp悬线法奶牛浴场(代码片段)

虽然还是悬线法，但是这道题可不能轻易地套模板了，而是要换一种思路，横着扫一遍，竖着扫一遍，时间复杂度依旧是O(n^2),然而空间复杂度有一定的优化如果用原来的方法，显然时间空间都会炸（如果你想用map我也没办法...... 查看详情

洛谷p1472奶牛家谱cowpedigrees

 P1472奶牛家谱CowPedigrees102通过193提交题目提供者该用户不存在标签USACO难度普及+/提高 提交  讨论  题解  最新讨论暂时没有讨论题目描述农民约翰准备购买一群新奶牛。在这个新的奶牛群中,每一个... 查看详情

洛谷p2676超级书架题解(代码片段)

题目传送门题目一看就是贪心。C++福利来了：sort。基本思路就是：要使奶牛最少那么肯定高的奶牛先啦。直接排序一遍（从高到矮）然后while，搞定！#include<bits/stdc++.h>#definelllonglongusingnamespacestd;llN,B,H[20010];boolcmp(intx,inty)retur... 查看详情

洛谷p1828香甜的黄油sweetbutter题解

此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：https://www.luogu.org/problem/show?pid=1828题目描述农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=... 查看详情

洛谷p1547outofhay题解

此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：https://www.luogu.org/problem/show?pid=1547题目背景奶牛爱干草题目描述Bessie计划调查N(2<=N<=2,000)个农场的干草情况，它从1号农场出发。农场之... 查看详情

bzoj1827洛谷2986[usaco10mar]伟大的奶牛聚集greatcowgather(代码片段)

【题解】　　很容易想到暴力做法，枚举每个点，然后对于每个点O(N)遍历整棵树计算答案。这样整个效率是O(N^2)的，显然不行。　　我们考虑如果已知当前某个点的答案，如何快速计算它的儿子的答案。　　显然选择它的儿子... 查看详情

洛谷p2853[usaco06dec]cowpicnics题解(代码片段)

题目连接：https://www.luogu.com.cn/problem/P2853题意：有n个奶牛在不同牧场，牧场之间有m条路。求所以奶牛都能共同到达的牧场的数量思路：dfs每一个奶牛可以到的牧场。开一个d[N]数组记录d[i]i这个牧场能来的奶牛的个... 查看详情

洛谷p2733家的范围homeontherange

P2733家的范围HomeontheRange• o 26通过o 61提交• 题目提供者该用户不存在• 标签USACO• 难度普及+/提高提交讨论题解最新讨论• 暂时没有讨论题目背景农民约翰在一片边长是N(2<=N<=250)英里的正方形牧场上放牧他的奶... 查看详情

洛谷2234bzoj1588hnoi2002营业额统计

【题解】　　treap模板题，直接用Treap维护前驱、后继，每次找到更接近当前val的加上就好了。1#include<cstdio>2#include<algorithm>3#definels(a[u].l)4#definers(a[u].r)5#defineLLlonglong6usingnamespacestd;7constintmaxn=200010;8intn,k 查看详情

usaco2002feb奶牛自行车队

【USACO2002Feb】奶牛自行车队TimeLimit:1000msMemoryLimit:131072KBytesDescriptionN头奶牛组队参加自行车赛。车队在比赛时排成一列，需要绕场S圈。由于空气阻力的作用，领队奶牛消耗的体力要比后面的多。每头奶牛的初始体力都是相同的，... 查看详情

洛谷p2345奶牛集会

题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没有两头... 查看详情