博客

abc200-d

本题主要体验了unordered_map和位运算的快乐，stl还是太棒了

首先我们来看看什么是unordered_map👀

在本题中，由于N的最大值为200，而我们要找到对200取模后值相等的两个不同子序列。根据容斥原理，假如我们能找到201个互不相同子序列，那他们其中一定有两个子序列的和对200取模后的值相等，我们可以注意到（怎么注意到的啊喂！）当N=8的时候，就有256个这样的子序列了，那就可以断定一定存在这样的子序列，这时候我们就可以开始暴力了，非常的舒服，那么自然，当n>8时也一定是成立的，当n<8时也照常暴力即可。

时间复杂度达到了惊人的O(min(2^k,200)),k=min(n,8)也就是说最大时间复杂度也只有200，omg

上代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
unordered_map<int,vector<int>>md;
/*
    这里是unordered_map的一个定义，它分为键和值两个部分，键也就是key，哈希表区分元素的那个依据，这里是int类型，值是vector类型的一个向量，用来存这个序列的所有位置
    这里也能看出vector的好处，两个vector之间只需要用等号连接就能把一个里的数全放在另一个里面，爽啊
    stl真是太好用了，原始人，进化！
*/
int w[N];
void print(vector<int>d)
{
    cout<<d.size()<<' ';
    for(auto x:d)cout<<x<<' ';
    /*
        此处是vector的一个用法，d.size()能读取向量d里元素的数量，
        auto x:d代表了从d的第0位遍历到d.size()-1位，写起来很快啊
    */
    cout<<'\n';
}
int main()
{
    int n;
    cin>>n;
    int mins=min(n,8);
    for(int i=0;i<n;i++)cin>>w[i];
    for(int i=1;i<(1<<mins);i++){
        /*
            这里这个1<<mins代表将1左移mins位，等价于pow(2,mins)，但是在速度上要比pow快得多，这里mins最大值为8，不会爆int
        */
        int sum=0;
        vector<int>tmp;
        for(int j=0;j<mins;j++)
            if(i>>j&1)
                /*
                    这里的i>>j代表了将i右移j位，这里的i代表的数化作二进制数，就是前mins位的出勤情况，假如j=0，那么i就不右移，&1之后假如i的最低位是1返回值就是1，否则为0（因为1可看作高位全为0，即为0000001），如果是1，则这个位置上的数在这次计算中出勤了，加和要加上，并且把这个位置放在tmp里（因为j是从0开始，而序列下标是从1开始算的）
                */
                sum=(sum+w[j])%200,tmp.push_back(j+1);
        if(md[sum].size()){//如果这个键对应的向量里不是空的，说明之前已经有等于同一个值的数了，直接输出
            cout<<"YES\n";
            print(tmp);
            print(md[sum]);
            return 0;
        }else
            md[sum]=tmp;//太酷啦，一行就搞定了
    }
    cout<<"No\n";
    return 0;
}

2025年11月14日

差分前缀和专题洛谷题解

2025/10/26 小高

差分部分

P2367 语文成绩

题目大意

给定n和p，以及大小为n个变量的数组，p次区间修改，最后让我们输出数组最小值的大小

思路

这道题目是我们的例题，很明显的差分，在讲课时已经讲过，所以这里只贴上代码

代码

#include<bits/stdc++.h>
using namespace std;
int d[5000001];
int a[5000001];
int main()
{
    int n,p,x,y,z,i,min=1e9;
    cin>>n>>p;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=1;i<=n;i++)d[i]=a[i]-a[i-1];
    for(i=0;i<p;i++)
    {
        cin>>x>>y>>z;
        d[x]+=z;
        d[y+1]-=z;
    }
    for(i=1;i<=n;i++)
    {
        a[i]=a[i-1]+d[i];
        if(min>a[i])min=a[i];
    }
    cout<<min;
    return 0;
}

P3397 地毯

由于本题数据太小，~~其实直接暴力枚举也能过！~~

觉得没有过瘾的同志们可以去P13787 地毯加强版试试

题目大意

在n*n的格子上铺m个地毯，每个地毯的范围是左上角（x1,y1）和右下角（x2,y2），问每个格子上盖了几层地毯

思路

本题需要对二维的区间进行修改，每多一个地毯就相当于在这个地毯覆盖的所有格子上加1，所以可以二维差分，需要先掌握一维差分的知识。~~所以你学会一维差分了吗~~

~~放马过来吧~~

在左上左下右上右下四个角进行操作，如图位置

假如n=7，也就是说我们有一块7*7的地板，现在我们要在（3，3），（5，5）这个范围内铺一块地毯，也就是说这块地毯覆盖了17，18，19，24，25，26，31，32，33九块格子，按照题意，我们需要在这九个格子上分别加1，但如果用上差分的思想，我们可以对常数个格子进行数值上的改变，从而框定一片范围进行相同的操作。

根据一维差分，我们发现最终每个位置的值为该位置以及之前位置的改变量的累加和，所以只要改变本位置之前的各自的数值，在其他不变的情况下我们就可以对当前位置做出相同的改变。

在二维中也是一样，此位置的值受其前面所有格子的影响，也就是它正上正左以及左上方的所有格子的影响，所以我们选定17格，将其对应的计数变量的值加上一，其后方（右，下，右下）的所有值都加了一，如图范围

黄色部分都加一

但是我们只想要地毯覆盖范围加一，其他的值并不想变，该怎么办呢？嗯，或许我们可以对范围进行一些限制，比如在38格的位置减一，这会使得38格及以后的位置都减一，也就恢复了原值，如图

同理，我们在20格上减一，如图：

绿色部分为减一，黄色部分为加一

可以看到，大部分位置都恢复了我们想要的效果，剩下右下角绿色部分多减了1，但是这部分是一个矩形，只需要在41格子上加1即可完成，如图：

这样我们就仅仅通过四次计算就完成了一次操作，非常的高效[赞]

代码

#include<bits/stdc++.h>
using namespace std;
int a[1024][1024];
int main()
{
    int n,m,xa,ya,xb,yb;
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>xa>>ya>>xb>>yb;
        ++a[xa][ya];
        --a[xb+1][ya];
        --a[xa][yb+1];
        ++a[xb+1][yb+1];
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            printf("%d%c",a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1],j==n?'\n':' ');
    return 0;
}

此处printf("%d%c",a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1],j==n?'\n':' ');意义为当此处不是行末，则在数字后加入字符空格，否则换行

前缀和部分

~~剩下好像都是前缀和的题目~~

P6180 [USACO15DEC] Breed Counting S

题目大意

有n个变量，每个变量有一个值（1或2或3），q次查询，问区间a到b范围内每个值各出现了多少次

思路

这是一道典型的前缀和问题，只需分别存一下三个值对应的变量即可，如图所示：

然后依次查询，非常快速

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[200050],b[200050],c[200050];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    int d;
    for(int i=1;i<=n;i++){
        cin>>d;
        if(d==1)a[i]++;
        if(d==2)b[i]++;
        if(d==3)c[i]++;
        a[i]+=a[i-1];
        b[i]+=b[i-1];
        c[i]+=c[i-1];
    }
    int l,r;
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        cout<<a[r]-a[l-1]<<" ";
        cout<<b[r]-b[l-1]<<" ";
        cout<<c[r]-c[l-1]<<endl;
    }
    return 0;
}

P5638 [CSGRound2] 光骓者的荣耀

题目大意

有n-1个变量，存着n个城市之间的距离，可以使用传送跳过k段路，问我们最短要走多少路

题解

依旧是经典的前缀和，我们只需要将总路程存在前缀和里，然后挨个位置向后遍历即可，直接上代码

代码

    ```c++
    #include<bits/stdc++.h>
    using namespace std;
    long long n,k,a[1000010],minx,ji,shi;
    int main()
    {
        cin>>n>>k;
        for(int i=1;i<n;i++)
        {
            cin>>a[i];
            shi+=a[i];
        }
        if(k>0)
            for(int i=1;i<=n-k;i++)
            {
                if(i==1)
                    for(int j=i;j<i+k;j++)
                        ji+=a[j];
                else
                {
                    ji-=a[i-1];
                    ji+=a[i+k-1];
                }
                if(ji>minx)
                    minx=ji;
            }
        cout<<shi-minx<<endl;
    } 
    
    ```

不要忘了开long long ^-^

P8218 【深进1.例1】求区间和

题目大意

给我们大小为n的数组a，然后进行m次查询，分别求区间（l，r）的和

思路

这也是我们的例题，讲课时讲了，这里直接上题解了

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100050];
int pre[100050];
int m,l,r;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pre[i]=a[i]+pre[i-1];
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        cout<<pre[r]-pre[l-1]<<endl;
    }
    return 0;
}

P1719 最大加权矩形

题目大意

有n*n的矩阵，求其中加和最大的子矩阵

思路

这题同样是例题，也直接贴代码了

代码

#include<iostream>
#include<climits>
#define MAXN 130
#define LL long long
using namespace std;
LL a[MAXN][MAXN];
LL s[MAXN][MAXN];
int main()
{
    int N;
    cin>>N;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
        {
            cin>>a[i][j];
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
    LL ans=INT_MIN;
    for(int x1=1;x1<=N;x1++)
        for(int y1=1;y1<=N;y1++)
            for(int x2=x1;x2<=N;x2++)
                for(int y2=y1;y2<=N;y2++)
                    ans=max(ans,s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
    cout<<ans;
    return 0;
}

~~非常暴力的一个题~~

P1115 最大子段和

本题看上去或许使用dp更像正解一点，但是我们这里是前缀和专题，所以我们使用前缀和来解决它

题目大意

给了我们n个数，求其中的最大子段和

思路

要想求最大子段和，不妨换个角度，去考虑最小前缀以及最小后缀，即在整个数组总和已经确定的情况下，让1到L-1的和和R+1到n的和最小，那么中间L到R的值就是最大了。

我们先输入每一位，然后计算本位前缀和，再计算下如果子段截止在本位置的前一位，字段的和和到本位置截止哪个更小。再通过循环，算下从头到尾每一位在减去当前情况最小前缀的情况下哪个剩下的最大，就是答案啦。

总结：先算前缀和，再算从第一位到本位置的前缀和中的最小值，存在最小前缀数组里（mins），最后用每位前缀和减去对应的mins求最大就是答案啦

代码

#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
int a[MAXN];
int s[MAXN],mins[MAXN];
int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
        mins[i]=min(mins[i-1],s[i]);
    }
    int ans=a[1];
    for(int i=2;i<=N;i++) ans=max(ans,s[i]-mins[i-1]);
    cout<<ans<<endl;
    return 0;
}

P1147 连续自然数和

题目大意

给了我们数字m，求所有和为m的正整数段

思路

本题似乎也能直接暴力（神秘）

贴一段暴力代码

#include<bits/stdc++.h>
using namespace std;
int n,sum;
int main()
{
 cin>>n;
 int j=0;
 for(int i=1;i<=n/2;i++)
 {
     sum=0;    
     for(j=i;j<n;j++)  {sum+=j;if(sum>=n)break;}
     if(sum==n)cout<<i<<' '<<j<<endl; 
 }
 return 0;
}

我们还是来用前缀和做这道题，也非常的简单，只需要计算下从1到1000000的前缀和，然后按位遍历即可完成

代码

#include<bits/stdc++.h>
using namespace std;
int m;
int sum[1000005];
int main()
{
	cin>>m;
	for(int i=1;i<=1000000;i++)sum[i]=sum[i-1]+i;
	for(int i=1;i<=m/2+1;i++)
	{
		for(int j=i;j>=1;j--)
		{
			if(sum[i]-sum[j-1]>m)break;
			if(sum[i]-sum[j-1]==m&&i!=j)printf("%d %d\n",j,i);
		}
	}
	return 0;
}

P1387 最大正方形

题目大意

给我们n*m的只由0和1组成的矩形，求最大不包含0的正方形的边长

思路

这道题和我们讲的那道二维前缀和的题简直一模一样，同学们可以去听下回放，这里我们就直接贴代码了

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[110][110],pre[110][110];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            pre[i][j]=pre[i-1][j]+pre[i][j-1]+a[i][j]-pre[i-1][j-1];
        }
    }
    int maax=-1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int ii=i;ii<=n;ii++){
                for(int jj=j;jj<=m;jj++){
                    if(ii-i==jj-j)
                        if((pre[ii][jj]+pre[i-1][j-1]-pre[i-1][jj]-pre[ii][j-1])==(ii-i+1)*(jj-j+1))
                            if(ii-i+1>maax)maax=ii-i+1;
                }
            }
        }
    }
    cout<<maax<<endl;
    return 0;
}

P6568 [NOI Online #3 提高组] 水壶

题目大意

有大小为n的数组a，求其中长度小于等于k的最大子段和

思路

弱化版最大子段和，无需多言，上代码

代码

#include<bits/stdc++.h>
using namespace std;
long long n,k,a[3000000],b[3000000],ans=-1;
int main() {
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=b[i-1]+a[i];
	}
	for(int i=1;i<=n-k;i++)ans=max(ans,b[i+k]-b[i-1]);
	cout<<ans<<endl;
	return 0;
}

B4005 [GESP202406 四级] 黑白方块

题目大意

有n*m的网格，格子里只可能是1或0，求包含相同个数的0，1的最大矩阵

思路

和之前的最大正方形一摸一样，只不过这次判定条件是x*y/2=sum，上代码

代码

#include<bits/stdc++.h>
using namespace std;
int n, m;
char s;
int a[20][20]; 
int b[20][20];  
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> s;
			a[i][j] = (s == '1') ? 1 : 0;
			b[i][j] = a[i][j] + b[i-1][j] + b[i][j-1] - b[i-1][j-1];
		}
	}
	int maxx = 0;  
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= m; j++) 
			for (int ii = i; ii <= n; ii++) 
				for (int jj = j; jj <= m; jj++) {
					int black = b[ii][jj] - b[i-1][jj] - b[ii][j-1] + b[i-1][j-1];
					int area = (ii - i + 1) * (jj - j + 1); 
					if (area % 2 == 0 && black == area / 2) if (area > maxx) maxx = area;
				}
	cout << maxx << endl;
	return 0;
}

B4192 [海淀区小学组 2023] 分数线

题目大意

给了长度为n的数组a，要求从某一位置分成两段，且这两段总和都在x和y之间

思路

直接前缀和，然后遍历一遍分别判断即可

代码

```c++
#include<bits/stdc++.h>
using namespace std;
const int N=100001;
long long m,c[N];
long long d[N],x,y;
int main(){
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>c[i];
		d[i]=c[i]+d[i-1];
	}
	cin>>x>>y;
	for(int i=1;i<=m;i++){
		int n2=d[i-1],n1=d[m]-d[i-1];
		if(n1>=x&&n1<=y&&n2>=x&&n2<=y){
			cout<<i<<"\n";
			return 0;
		}
	}
	cout<<"0\n";
	return 0;
}

```

P1865 A % B Problem

题目大意

告诉了我们查询n次和右端点最大值，求区间内多少个质数

思路

本题思路非常简单，依旧是前缀和，但是其中涉及了一个求质数的知识点还没学到，所以看上去有些难度，所以我把它放在了最后一题。

对于质数筛的知识点会由讲数论的学长给大家详细讲解，这里我们就不说了，~~因为这题的数据有点水~~，直接暴力判断质数就能过了

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,l,r,t,a[1000005];
bool judge(long long x)
{
	if(x==1)return false;
	for(long long i=2;i<=sqrt(x);i++)
		if(x%i==0)return false;
	return true;
}
int main()
{
	scanf("%lld %lld",&n,&m);
	for(long long i=1;i<=m;i++)
	{
		if(judge(i))a[i]=a[i-1]+1;
		else a[i]=a[i-1];
	}
	for(long long i=1;i<=n;i++)
	{
		scanf("%lld %lld",&l,&r);
		if(l>m||r>m||l<1||r<1){printf("Crossing the line\n");}
		else printf("%lld\n",a[r]-a[l-1]);
	}
	return 0;
}

其实本题的左右值最大也只是1到m，而m最大是1e6，因此不开long long也是完全可以的

到这里就结束了，你听懂了吗 ^ – ^

听懂了，讲的不赖b（￣▽￣）d　
讲的什么鬼啊(╯‵□′)╯︵┻━┻

2025年11月2日

世界，您好！

欢迎使用 WordPress。这是您的第一篇文章。编辑或删除它，然后开始写作吧！

2025年10月31日

博客

abc200-d

差分前缀和专题洛谷题解

差分部分

P2367 语文成绩

题目大意

思路

代码

P3397 地毯

题目大意

思路

代码

前缀和部分

P6180 [USACO15DEC] Breed Counting S

题目大意

思路

代码

P5638 [CSGRound2] 光骓者的荣耀

题目大意

题解

代码

P8218 【深进1.例1】求区间和

题目大意

思路

代码

P1719 最大加权矩形

题目大意

思路

代码

P1115 最大子段和

题目大意

思路

代码

P1147 连续自然数和

题目大意

思路

代码

P1387 最大正方形

题目大意

思路

代码

P6568 [NOI Online #3 提高组] 水壶

题目大意

思路

代码

B4005 [GESP202406 四级] 黑白方块

题目大意

思路

代码

B4192 [海淀区小学组 2023] 分数线

题目大意

思路

代码

P1865 A % B Problem

题目大意

思路

代码

世界，您好！