首页

更好的阅读体验

题单链接

JC0501. Subsequences Summing to Sevens S

题目大意

给定 $n$ 个数，求最长的一个区间使得区间和能被 7 整除，输出区间长度，若没有符合要求的区间，输出 0

思路

先求出这个数组的前缀和，然后对 7 取模，我们发现对于一个合法区间 $[l,r]$，$qzh[l]$ 和 $qzh[r]$ 的值一定相同，因为区间和对 7 取模为 0，问题就转化成了找出 $qzh$ 数组中两个相同的 0~6 出现的最远距离

代码

#include<bits/stdc++.h>
#define int long long
#define _123hh2 0
#define in inline
#define ri register
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
void write(int x) {if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=5e4+1;
int awa[maxn],qzh[maxn];
int l[7],r[7];
signed main()
{
    int n=read(),ans=0;
    for(int i=1;i<=n;i++) awa[i]=read(),qzh[i]=qzh[i-1]+awa[i],qzh[i]%=7;
    for(int i=1;i<=n;i++) r[qzh[i]]=i;
    for(int i=n;i>=1;i--) l[qzh[i]]=i;
    l[0]=0;
    for(int i=0;i<7;i++) ans=max(ans,r[i]-l[i]);
    write(ans);
    return _123hh2;
}

JC0502. 地毯

题目大意

给出 $n*n$ 的格子和 $m$ 个地毯，每个地毯给出坐标 $(x_1,y_1),(x_2,y_2)$ 分别代表左上角和右下角

问每个格子被多少地毯覆盖

思路

经典的二维差分，可以拆成一维差分来做

代码

#include<bits/stdc++.h>
#define int long long
#define _123hh2 0
#define in inline
#define ri register
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
void write(int x) {if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e3+11;
int awa[maxn][maxn];
signed main()
{
    int n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int x1=read(),y1=read(),x2=read(),y2=read();
        for(int j=y1;j<=y2;j++) awa[x1][j]++,awa[x2+1][j]--;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            awa[i][j]+=awa[i-1][j];
            cout<<awa[i][j]<<" ";
        }
        cout<<endl;
    }
    return _123hh2;
}

JC0503. 激光炸弹

题目大意

你可以摧毁边长为 $m$ 的正方形内所有目标，每个目标都有相应价值和坐标，问一次能摧毁的最大价值

思路

用二维数组模拟地图，并逐行前缀和，依次枚举炸弹可能炸的位置并统计答案即可

代码

#include<bits/stdc++.h>
// #define int long long
#define _123hh2 0
#define in inline
#define ri register
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
void write(int x) {if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=5e3+11;
int awa[maxn][maxn];
signed main()
{
    int n=read(),m=read(),ans=0;
    for(int i=1;i<=n;i++)
    {
        int x=read(),y=read(),w=read();
        awa[x+1][y+1]=w;
    }
    for(int i=1;i<=5001;i++)
    {
        for(int j=1;j<=5001;j++)
        {
            awa[i][j]+=awa[i-1][j]+awa[i][j-1]-awa[i-1][j-1];
        }
    }
    for(int i=m;i<=5001;i++)
    {
        for(int j=m;j<=5001;j++)
        {
            ans=max(ans,awa[i][j]-awa[i][j-m]-awa[i-m][j]+awa[i-m][j-m]);
        }
    }
    write(ans);
    return _123hh2;
}

JC0504. IncDec Sequence

题目大意

给定一个数组 $a$，每次可以选择一个区间 $[l,r]$，使这个区间内的数都加 1 或减 1，问最少多少次才能把数组中所有元素都相同，并求出最终数组的种类

思路

差分数组性质 $cf[i]=a[i]-a[i-1]$

根据性质可以得到该数组的差分数组，那么问题转化成将差分数组归零的操作数，即统计差分数组的操作数

统计出差分数组 $cf[2,n]$ 中的正数和和负数和，不统计 $cf[1]$ 是因为第一位的数是影响数组整体元素的，它+1/-1不会对对结果产生影响，所以每次操作我们可以

  • 差分数组的某一正数-1，负数+1
  • 差分数组的某一正数-1
  • 差分数组的某一负数+1

我们贪心的尽量多的执行第一个操作，若有剩余，在执行第二/三个操作

这样最小操作数就是正数和和负数和的相反数的最大值

我们发现，执行完第一个操作后我们的差分数组若没有存在剩余的数，则最终得到的数列肯定是一种，而若存在剩余的数，则该数可以产生它自身的值的贡献数+1，因为它既可以让原数组从1到它自身前的一个数都+1/-1，也可以让它自身到数组末尾的数都+1/-1

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e5+1;
int awa[maxn],cf[maxn],n;
int sum1,sum2;
signed main()
{
    n=read();
    for(ri int i=1;i<=n;i++) awa[i]=read(),cf[i]=awa[i]-awa[i-1];
    for(ri int i=2;i<=n;i++)
    {
        if(cf[i]>0) sum1+=cf[i];
        else sum2-=cf[i];
    }
    write(max(sum1,sum2)),puts(""),write(abs(sum1-sum2)+1);
    return _123hh2;
}

JC0505. 水壶

题目大意

给出有 $n$ 个数的数组 $arr[n]$，你可以进行不超过 $k$ 次操作，将 $arr[x]$ 的数全部转移到 $arr[x+1]$ 中 $(1 \leq x \leq n-1)$，问操作后数组中可能得到的最大的数是多少

思路

我们发现数组中的数只能从左往右转移且每次只能向右移动一个单位，所以要得到最大的数肯定是从某一位置开始一直往后进行转移操作，这样问题就转化成了求有 $n$ 个数的数组中长度为 $k+1$ 的区间和的最大值，前缀和维护即可

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e6+1;
int awa[maxn],qzh[maxn];
signed main()
{
    int n=read(),k=read(),ans=0;
    for(int i=1;i<=n;i++) awa[i]=read(),qzh[i]=awa[i]+qzh[i-1];
    for(int i=k+1;i<=n;i++) ans=max(ans,qzh[i]-qzh[i-k-1]);
    write(ans);
    return _123hh2;
}