题目链接

涂气球

题目大意

N个气球排成一排,从左到右依次编号为1,2,3….N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽”牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了,你能帮他算出每个气球被涂过几次颜色吗?

输入描述

每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行,每行包括2个整数a b(1 <= a <= b <= N)。
当N = 0,输入结束。

输出描述

每个测试实例输出一行,包括N个整数,第I个数代表第I个气球总共被涂色的次数。

样例输入

3
1 1
2 2
3 3
3
1 1
1 2
1 3
0

样例输出

1 1 1
3 2 1

解题思路

差分,对于区间操作,每次会把区间[L,R]之间的所有气球涂一次,那么就让a[L]++,a[r+1]–,再求一次前缀和就可以得出答案。

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
typedef long long ll;
const int maxn=1e5+7;
int a[maxn],b[maxn];
int x,y,n;
using namespace std;
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;++i)
        {
            scanf("%d %d",&x,&y);
            if(x>y) swap(x,y);
            a[x]++;a[y+1]--;
        }
        for(int i=1;i<=n;i++)
        {
            b[i]=b[i-1]+a[i];
            if(i!=n) printf("%d ",b[i]);
            else printf("%d",b[i]);
        }
        puts("");
    }
    return 0;
}

题目链接

激光炸弹

题目大意

一种新型的激光炸弹,可以摧毁一个边长为R的正方形内的所有的目标。
现在地图上有n(N ≤ 10000)个目标,用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置,每个目标都有一个价值。
激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆破范围,即那个边长为R的正方形的边必须和x,y轴平行。
若目标位于爆破正方形的边上,该目标将不会被摧毁。

输入描述

输入文件的第一行为正整数n和正整数R,接下来的n行每行有3个正整数,分别表示 x,y ,v。

输出描述

输出文件仅有一个正整数,表示一颗炸弹最多能炸掉地图上总价值为多少的目标(结果不会超过32767)。

样例输入

2 1
0 0 1
1 1 1

样例输出

1

解题思路

二维前缀和,sum[x][y]就等于位置(x,y)上的所有目标的价值之和。求一下sum[x][y]的二维前缀和S。

AC代码

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
const int N=5e3+7;
int sum[N][N],a[N][N];
int main()
{
    int n,r;
    scanf("%d %d",&n,&r);
    int x,y,v,rx=r,ry=r;
    while(n--)
    {
        scanf("%d %d %d",&x,&y,&v);
        x++,y++;
        a[x][y]=v;
        rx=max(x,rx);
        ry=max(y,ry);
    }
    rep(i,1,rx)
        rep(j,1,ry)
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
    int ans=0;
    rep(i,r,rx)
        rep(j,r,ry)
            ans=max(ans,sum[i][j]-sum[i-r][j]-sum[i][j-r]+sum[i-r][j-r]);
    printf("%d\n",ans);
    return 0;
}

题目链接

IncDec Sequence

题目大意

给定一个长度为 n(n<=1e5)的数列 a1, a2, …, an,每次可以选择一个区间 [l,r],使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。

输入描述

第一行一个整数n
接下来 n 行,每行一个整数,第 i+1 行的整数表示 ai。

输出描述

第一行输出最少操作次数。
第二行输出最终能得到多少种结果。

样例输入

4
1
1
2
2

样例输出

1
2

解题思路

求出序列 a 的差分序列 b, b[1]=a[1],b[i]=a[i]-ai-1。b[n+1]=0。题目对于序列 a 的操作,相当于每次从序列 b 中选出任意两个数,一个加 1,另一个减 1。目标把 b[2]…b[n]变为全0。最后得到的数列 a 就是由 n 个 b[1]构成。
从差分序列中选取任意两个数的方法可分为四类:

1.选取 b[i] 和 b[j] (2<=i,j<=n)。会改变b[2]…b[n]中两个数的值。应该在保证b[i]和b[j]一正一负的前提下,尽量采取这种操作,更快地接近目标。

2.选取b[1]和b[j] (2<=j<=n)

3.选取b[i]和b[n+1] (2<=i<=n)

4.选取b[1]和b[n+1],永远不会改变b[2]…b[n]的值,相当于浪费一次操作,一定不是最优解。

设b[2],b[3]…b[n]中正数总和为p,负数总和的绝对值是q。首先用正负数配对的方式执行第1类操作,可执行min(p,q)次。剩余|p-q|个没有配对,对每个可以选择与b[1]或b[n+1]配对,就是执行第2类或第3类操作,共需|p-q|次

综上所述,最少操作次数就是min(p,q)+|p-q|=max(p,q)次。根据|p-q|次第2、3类操作的选择情况,能产生|p-q|+1种不同的b[1]的值,就是最后得到的序列a可能有|p-q|+1种。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7;
int a[N],b[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    ll p=0,q=0;
    for(int i=1;i<=n;++i) 
    {
        b[i]=a[i]-a[i-1];
        if(i>1)
        {
            if(b[i]>0) p+=b[i];
            else q-=b[i];
        }
    }
    printf("%lld\n%lld\n",max(p,q),abs(p-q)+1);
    return 0;
}

题目链接

Tallest Cow

题目大意

有 N 头牛站成一行。两头牛能够互相看见,当且仅当它们中间的牛身高都比它们矮。现在,我们只知道其中最高的两头牛是第p头,它的身高是 H,不知道剩余 N-1 头牛的身高。但是,我们还知道 M 对关系,每对关系都指明了某两头牛A[i]和B[i]可以互相看见。求每头牛的身高最大可能是多少。
数据范围: 1<=N,M<=1e4, 1<=H<=1e6。

解题思路

对一个区间的操作转化为左右两个端点的操作,

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+7;
int a[maxn],b[maxn],vis[maxn][maxn];
int main()
{
    int n,num,h,r,x,y;
    scanf("%d %d %d %d",&n,&num,&h,&r);  // n头牛,最高的牛的位置是num,身高是h,有 r 对关系
    for(int i=1;i<=r;++i)
    {
        scanf("%d %d",&x,&y);
        if(x>y) swap(x,y);
        if(!vis[x][y]) a[x+1]--,a[y]++;  //去除重复的关系&&差分
        vis[x][y]=1;  //标记出现过
    }
    for(int i=1;i<=n;++i)
    {
        b[i]=b[i-1]+a[i];  //前缀和
        printf("%d\n",b[i]+h);
    }
    return 0;
}

一个爱折腾且喜欢研究算法的大学生