P1209 刷出一道墙 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2025年1月15日 21:27

刷出一道墙题解：

P1209

回复 0 | 赞 0 | 浏览 47

无敌简短的代码，差分数组的应用，初始数组每个元素值为0，每次刷给出起点和终点，只需修改差分数组即可，最后累加起来其实每个点刷的次数，需要使用scanf和printf作为输入输出减少时间。（参考了acwing上的模板） #include<bits/stdc++.h> using namespace std; const int N = 2000010; int a[N]; void insert(int l,int r,int x){ a[l] += x; a[r+1] -= x; } int main(){ ...

2024年3月15日 12:53

刷出一道墙题解：cout<<f[i]<<endl超时问题

P1209

回复 0 | 赞 2 | 浏览 976

#include <bits/stdc++.h> using namespace std; const int maxn =2e5+10; int f[maxn]; int main(){ int a,b; while(cin>>a>>b){ if(a==0&&b==0) break; f[a...

928上岸梦校！

2023年8月4日 16:48

如何在刷出一道墙中理解、设计前缀和数组

P1209

回复 0 | 赞 4 | 浏览 1.2k

使用前缀和思想简化时间复杂度，设计前缀和数组，使输出的数组中元素的值代表其对应节点被刷的次数。首先初始化前缀和数组，使每一个元素等于为0。该题的巧妙之处就在于：对于每一个输入的索引B与E，B作为开始刷的节点索引令前缀和数组中对应元素的值+1，E+1作为刷墙结束的下一个节点的索引令对应的值-1。这样在所有输入结束后的计算前缀和阶段，在每一个值为[1, -1)的索引区间中的元素值都会加1，而对于某次刷漆终点E的下一个索引为E+1的元素值由于-1而抵消影响（自身值为-1加上之前元素所累积的1而归零），此时数组中元素的值才代表其对应节点被刷的次数。 AC参考代码如下： ...

2023年3月25日 15:32

差分数组解决数组区间频繁加减一个数

P1209

回复 0 | 赞 3 | 浏览 1.9k

本题的结果数组初始值都是0(一开始没有刷墙，则每一个点都是0）差分数组初始化为0（结果数组都是0）假设diff[]为我们的差分数组，结果数组为res[] 先解释一下diff[i]的含义表示结果数组中下标为i-1的元素与下标为i的元素的差。即diff[i]=res[i]-res[i-1] 说一下差分数组的操作，如果对结果数组res，从i到j同是加上（减去）一个数x。差分数组的操作为 diff[i]+=x; diff[j+1]-=x; diff[i]+=x; 从i开始后面的每个数都加...

2021年3月24日 14:50

一次刷墙避免超时

P1209

回复 0 | 赞 4 | 浏览 8.8k

看了一位同学提交的思路很不错；开始我是打算对每一次刷墙就使那部分范围的wall的value值+1，最后统计wall值，但显然容易超时。后来发现可以将刷墙过程先不做，每次记录下刷的起点和终点，最后刷一遍就行；代码如下： include<bits/stdc++.h> using namespace std; int main(){ int B,E; int b,e; int wall[200005]={0}; &nbs...

尼古拉斯富贵

2021年3月13日 17:15

cout超时的看过来

P1209

回复 0 | 赞 1 | 浏览 8.0k

cin，cout之所以效率低，是因为先把要输出的东西存入缓冲区，再输出，导致效率降低。使用ios::sync_with_stdio(false); 可以来打消iostream的输入、输出缓存。同理endl是流操作，换成'\n'即可加速。

2021年2月1日 20:26

差分＋前缀和

P1209

回复 3 | 赞 3 | 浏览 10.7k

#include <iostream> #include <algorithm> #include <stdio.h> #include <string.h> using namespace std; /* 思路：题型：某一个区间同时加减一个数--->差分差分数组d不用专门求出来只求差分的变化再求个前缀和就行 &...

2020年5月3日 16:30

这题时间卡的有毒。。

P1209

回复 0 | 赞 3 | 浏览 9.1k

题目刷出一道墙

题解数量8

发布题解快速答疑

热门题解

1 如何在刷出一道墙中理解、设计前缀和数组

2 一次刷墙避免超时

3 这题时间卡的有毒。。

4 差分数组解决数组区间频繁加减一个数

5 差分＋前缀和

6 刷出一道墙题解：cout<<f[i]<<endl超时问题

7 cout超时的看过来

8 刷出一道墙题解：