本文共 2565 字，大约阅读时间需要 8 分钟。

  首先是 Buildings

题目大概：

这道题是给出n，m，是一个矩形的大小，然后有一个地块x，y不能填矩形，问，如果用小矩形填满这个大矩形，使得最大的小矩形最小的填法，这个矩形大小是多少。

思路：

首先这个矩形一定是宽度为1，才最小而且符合题目要求。

这个题可以观察题目给出的样例，可以得知，就是求解   x，y   四周的这四个矩形填满   应该需要多大的矩形，取最小值。然后就是不管有没有这个x，y，直接用（n+1）/2，来整体求这个大矩形的最小值。

具体的如果n，m为奇数，而且x，y在中央，那么应该是n/2需要特判。

感想：

一般这种找规律的题，首先要从样例出发，找出规律，然后具体的特例需要自己造数据。

一般这种构造类型的题，需要自己取找构造的点，就是受题目限制很大的点，根据这些要点来构造，比如这里，x，y这个矩形的四周就是这个要点。

代码：

#include 
   
    using namespace std;const int maxn=1e5+10;int n,m,x,y;int main(){    while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF)    {        if(n>m)        {            swap(n,m);            swap(x,y);        }        if(n==m&&n%2==1&&x==(n+1)/2&&y==(m+1)/2)        {            printf("%d\n",n/2);            continue;        }        int mi_1=min(x-1,min(y,m-y+1));        int mi_2=min(n-x,min(y,m-y+1));        int ans=(n+1)/2;        int sum=max(mi_1,max(mi_2,ans));        printf("%d\n",sum);    }    return 0;}
   

Gorgeous Sequence

题目大概：

给出n个数，然后给出3中操作

0  把 区间 l   r  的比v大的值改成v。

1 求区间  l  r  的最大值。

2 求区间  l  r 的和。

思路：

这个题的1  2操作都是线段树的基本操作，但是0操作有些复杂，如果直接修改，时间上会受不了。就采用了吉如一的线段树操作。维护最大值，次大值，最大值数量。这样在次大值<v<最大值的时候，就可以很快的把最大值都修改成 v，并用懒惰标记标记一下，这样维护后，对于修改后，最大值，次大值，最大值数量的维护，和的维护，都比较容易求解。

感想：

这样的维护，就把很多必须深入修改的东西，统一了起来。因为每次修改，修改到一定层数，一定会出现思路中讲到的修改方式，以此来进行懒惰修改，节约时间。这一点一定要借鉴学习，以后需要类似的问题，要转化成可以标记懒惰数组的形式。

代码：

#include 
   
    using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const int maxn=1e6+10;int n,m;long long sum[maxn];int max_1[maxn],max_2[maxn];int maxsum[maxn];void pushup(int rt){    sum[rt]=sum[rt<<1]+sum[rt<<1|1];    max_1[rt]=max(max_1[rt<<1],max_1[rt<<1|1]);    maxsum[rt]=0;    max_2[rt]=max(max_2[rt<<1],max_2[rt<<1|1]);    if(max_1[rt]==max_1[rt<<1])    {        maxsum[rt]+=maxsum[rt<<1];    }    else max_2[rt]=max(max_1[rt<<1],max_2[rt]);    if(max_1[rt]==max_1[rt<<1|1])    {        maxsum[rt]+=maxsum[rt<<1|1];    }    else max_2[rt]=max(max_1[rt<<1|1],max_2[rt]);}void pushdown(int rt){    if(max_1[rt]
    
     <<1])    {        sum[rt<<1]-=(long long)maxsum[rt<<1]*(max_1[rt<<1]-max_1[rt]);        max_1[rt<<1]=max_1[rt];    }    if(max_1[rt]
     
      <<1|1])    {        sum[rt<<1|1]-=(long long)maxsum[rt<<1|1]*(max_1[rt<<1|1]-max_1[rt]);        max_1[rt<<1|1]=max_1[rt];    }}void build(int l,int r,int rt){    if(l==r)    {        scanf("%I64d",&sum[rt]);        max_1[rt]=sum[rt];        max_2[rt]=-1;        maxsum[rt]=1;        return;    }    int m=(l+r)/2;    build(lson);    build(rson);    pushup(rt);}void update(int L,int R,int v,int l,int r,int rt){    if(v>=max_1[rt])return;    if(L<=l&&r<=R&&max_2[rt]
      
       =L)update(L,R,v,lson);    if(m
      
     
    
   

转载地址：https://blog.csdn.net/a1046765624/article/details/81088768 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！