解题报告 P4231 三步必杀

题目内容

P4231

大意:区间加等差,最后询问整个序列的异或和以及最大值

解题思路

区间加等差其实就是差分序列区间加常数,两端特殊修改。

但是注意到这里的数据范围是 1e7,线段树卡不过去,而且询问是在最后询问的,因此可以直接上二阶差分。

模拟一段区间加等差的过程:给 [3,6] 加上首项为 3,末项为 9 的等差数列:

0  0  0  0  0  0  0  0  这是原数列
0  0  3  5  7  9  0  0  这是加了等差数列之后的
0  0  3  2  2  2 -9  0  这是一阶差分
0  0  3 -1  0  0  -11 9 这是二阶差分

可见,我们如果要进行区间加等差的操作的话,需要在二阶差分上动 4 个点,分别是

d2[l]+=s;
d2[l+1]+=d-s;
d2[r+1]-=e+d;
d2[r+2]+=e;

其中 d 为公差,s 为首项,e 为末项。错误常发生于以为 d2[l+1]d2[r+1] 是不用修改的,但是实际上由于 s 可能不等于 d,故二阶差分的 l+1 处要进行处理。

最后,两次前缀和就可以还原出原序列,在还原的过程中可以顺便进行最大值查询和异或和操作。

总的复杂度 O(n+m),可以卡过去,如果是线段树的话是 O(m\log n+n),会被卡掉

要开 long long

#include <cstdio>
#include <cctype>
typedef long long ll;

const int maxn=1e7+5;
ll a[maxn],d1[maxn],d2[maxn];

inline ll read()
{
    char c = getchar();
    ll s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int main()
{
    int n=read(),m=read();
    ll l,r,s,e;
    while(m--)
    {
        l=read(),r=read(),s=read(),e=read();
        int d=(e-s)/(r-l);//得到公差
        d2[l]+=s;
        d2[l+1]+=d-s;
        d2[r+1]-=e+d;
        d2[r+2]+=e;
    }
    ll maxans=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        d1[i]=d1[i-1]+d2[i],a[i]=a[i-1]+d1[i];//还原
        maxans=maxans<a[i]?a[i]:maxans;
        ans^=a[i];
    }
    printf("%lld %lld\n",ans,maxans);
    return 0;
}

解题报告 P1083 借教室【NOIP2015TGD2T2】

题目内容

P1083

解题思路

嗯,这道题一看,暴力枚举

分析:这道题满足二分答案,为什么:

我们将订单挨个标号,很显然,订单越多,越难满足要求,这满足二分答案要求的单调性。我们只需将订单挨个枚举即可。

二分的答案是订单的标号,订单越多越到后面越不能满足,因此很容易找到那个”1″和”0″的分界,使用一个check函数即可判断。

至于check函数的实现,这里使用了差分的重要思想。每一个订单会给出起始时间s和末尾时间t,相当于在[s,t]这段时间内多租借d个教室,很像区间加问题。所以我们定义一个数组c存储需要使用的教室的差分,处理每个订单的时候就c[s[i]]+=d[i],c[t[i]+1]-=d[i]注意是t[i]+1,并且是-=,已掉坑不止5次。然后将差分数组加起来(求前缀和)判断这么多个订单能否满足能提供教室的条件,返回即可。

代码实现:

#include <cstdio>
#include <cstring>
#define f(i,a,b) for(int i=a;i<=b;++i)

const int maxn=1e6+5;
int n,m,r[maxn],d[maxn],s[maxn],t[maxn],diff[maxn];//r,d,s,t见题意,diff为差分数组

inline int read()//我喜欢快读
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}

bool check(int mid)
{
    memset(diff,0,sizeof(diff));//每次使用的时候要清零差分数组
    f(i,1,mid)
        diff[s[i]]+=d[i],diff[t[i]+1]-=d[i];//操作差分数组实现区间加
    int ans=0;//记录前缀和
    f(i,1,n)
    {
        ans+=diff[i];//每次加起来
        if(ans>r[i])//如果不能满足需要
            return 0;
    }
    return 1;//否则return true
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    n=read(),m=read();
    f(i,1,n)
        r[i]=read();
    f(i,1,m)
        d[i]=read(),s[i]=read(),t[i]=read();
    //以上读入数据
    int l=1,r=m;//开始二分
    while(l<r)//mid越大越难不挨卡
    {
        int mid=l+r>>1;
        if(check(mid))//如果满足要求
            l=mid+1;//说明mid可能还可以更大
        else
            r=mid;//否则mid就太大了
    }
    if(r!=m)//如果r!=m的话说明不能满足所有订单
        printf("-1\n%d\n",r);
    else//否则可以满足所有订单
        printf("0\n");
    return 0;
}

反思

蓝题,果然在二分的思维比较难,而且二分答案的代码细节非常多。

下次再写一波