23年10月28日
题目1
给定一个长度为 $n$ 的数组 $a_1,a_2,…,a_n$。
现在，要将该数组从中间截断，得到三个非空子数组。
要求，三个子数组内各元素之和都相等。
请问，共有多少种不同的截断方法？
看见这个题直接就能想到用前缀和去解，但是仅仅使用前缀和的话会超时
贴一下出错的垃圾代码
#include<iostream>
using namespace std;
int N = 1000001;
int main()
{
int n = 0;
int a[N] = {0};
int s[N] = {0};
int sum = 0;
int count = 0;
cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> a[i];
sum+=a[i];
s[i] = sum;
}
for(int i = 1; i < n; i ++)
{
for(int j = i+1; j < n;j ++)
{
if(s[i-1] == s[j-1] - s[i-1] && s[j-1] - s[i-1] == s[n-1] - s[j-1])
count ++;
}
}
cout << count << endl;
return 0;
} 然后去翻了下答案，惊呼我是蠢逼。就本题来讲，因为要划分出三个相等的子数组，所以只需要找到能够使子数组和为总和三分之一的位置即可。如果不存在这样的位置就可以输出0
进一步思考，只要遍历整个前缀和数组，其中每出现一个和等于三分之一总和的位置就意味着一种分割方式，每出现一个和等于三分之二总和的位置就意味着之前的分割方式有效，于是便有了以下的优雅解题代码
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n;const int maxn=1e5+10;
int m[maxn];
long long sum=0;
int main(){
cin>>n;
for(int i=1;i<=n;++i) cin>>m[i],sum+=m[i];
if(sum%3) cout<<"0";
else {
long long averge=sum/3;
long long tot=0,js=0;
long long ans=0;
for(int i=1;i<n;++i){
tot+=m[i];
if(tot==2*averge) ans+=js;
if(tot==averge) ++js;
}cout<<ans<<endl;
}return 0;
}
作者：归游
链接：https://www.acwing.com/solution/content/66543/
来源：AcWing优雅，太优雅了。
23年10月29日
题目1
输入一个长度为 $n$ 的整数序列。
接下来再输入 $m$ 个询问，每个询问输入一对 $l, r$。
对于每个询问，输出原序列中从第 $l$ 个数到第 $r$ 个数的和。
输入格式
第一行包含两个整数 $n$ 和 $m$。
第二行包含 $n$ 个整数，表示整数数列。
接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$，表示一个询问的区间范围。
输出格式
共 $m$ 行，每行输出一个询问的结果。
今天的题目依然是个很基础的前缀和，属于板子题，然而发现许久没写居然连这都会出错了，惯例先贴错误代码
#include<iostream>
using namespace std;
int N = 100001;
int main()
{
int n,m,l,r;
cin >> n >> m;
int a[N] = {0};
int s[N] = {0};
int sum = 0;
for(int i = 1; i < n+1; i ++)
{
cin >> a[i];
sum += a[i];
s[i] = sum;
}
for(int i = 1; i < m+1; i ++)
{
cin >> l >> r;
cout << s[r] - s[l] << endl;
}
return 0;
} 很显然，我计算的边界写错了，在输出查询结果的时候，应该是右边界减去左边界-1的下标，改正之后就可以a。同时，代码里还有一些不够优雅的多余计算和定义，小小优化一下。
#include<iostream>
using namespace std;
int N = 100001;
int main()
{
int n = 0, m = 0, l = 0, r = 0;
cin >> n >> m;
int a = 0;
int s[N] = {0};
for(int i = 1; i < n+1; i ++)
{
cin >> a;
s[i] = a + s[i-1];
}
for(int i = 1; i < m+1; i ++)
{
cin >> l >> r;
cout << s[r] - s[l-1] << endl;
}
return 0;
} 嗯，舒服了。
23年10月30日
题目1
输入一个 n 行 m 列的整数矩阵，再输入 q 个询问
每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
今日继续板子题，二维前缀和问题。已经忘了个一干二净。
先复习一下二维前缀和的原理。
二维前缀和依然是前缀和，只是建立在二维数组上，用于求解区域矩阵和问题，本质和一维前缀和完全相同。简单画个草图
当我们需要计算一个二维前缀和时，比如计算34号位的前缀和。我们只需要计算33号位前缀和加28号位前缀和再加上34号位的元素值，此时27号位的前缀和多计算了一遍，需要减掉，于是我们就可以抽象出前缀和的计算公式
s[i][j] = s[i-1][j] + s[i][j-1] + a[i][j] - s[i-1][j-1]
其中s数组是前缀和数组，a数组是元素值数组，i，j表示当前计算元素前缀和的下标
现在了解了计算前缀和数组的方法，下面就该使用了。
如何通过前缀和数组来计算某一特定区域内的和呢？也很简单。再上个草图
例如我们需要计算右下角为35号位，左上角为21号位的矩形区域的和。那么只需要用35号位的前缀和减去32号位的前缀和再减去17号位的前缀和，其中14号位的前缀和被减了两遍，需要加回来。以此可以抽象出计算公式
ans = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1 - 1][y1 -1]
其中ans为计算结果，x2，y2为待求区域右下角元素坐标，x1，y1为待求区域左上角元素坐标
原理了解清楚后写代码便没有难度，直接a
#include<iostream>
using namespace std;
int N = 1020;
int main()
{
int n = 0, m = 0, q = 0;
int x1 = 0,x2 = 0,y1 = 0,y2 = 0;
int a[N][N] = {{0}};
int s[N][N] = {{0}};
cin >> n >> m >> q;
for(int i = 1; i < n+1; i ++)
{
for(int j = 1; j < m+1; j ++)
{
cin >> a[i][j];
s[i][j] = s[i-1][j] + s[i][j-1] + a[i][j] - s[i-1][j-1];
}
}
for(int i = 0; i < q; i ++)
{
cin >> x1 >> y1 >> x2 >> y2;
cout << s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1 - 1][y1 -1] << endl;
}
return 0;
} 23年11月1日
题目1
地图上有 N 个目标，用整数 Xi,Yi 表示目标在地图上的位置，每个目标都有一个价值 Wi。
注意：不同目标可能在同一位置。
现在有一种新型的激光炸弹，可以摧毁一个包含 R×R个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 x，y轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
这道题目也属于前缀和，但是数据范围限制很麻烦，有较为严格的内存限制，所以需要尽可能的少创建数组。
我的思路是直接将所有目标录入创建的二维前缀和表中，然后从第一个元素开始，将其作为爆炸的右下角进行遍历，找出最大的价值范围后输出。但还是出现了栈溢出的段错误，百思不得其解。惯例贴一下错误代码
#include<iostream>
using namespace std;
#define N 5002
//s[i][j] = s[i-1][j] + s[i][j-1] + a[i][j] - s[i-1][j-1];
//s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1 - 1][y1 -1]
int s[N][N];
int main()
{
int n = 0, r = 0;
int x = 0, y = 0;
int w = 0, max_m = 0;
cin >> n >> r;
r = min(5002,r);
for (int i = 0; i < n; i++)
{
cin >> x >> y >> w;
s[x][y] += w + s[x][y - 1] + s[x - 1][y] - s[x - 1][y - 1];
}
for (int i = 1; i * i <= n + 1; i++)
{
for (int j = 1; j * j <= n + 1; j++)
{
cout << s[i][j] << " ";
if (i <= r && j <= r)
{
if (max_m < s[i][j]) max_m = s[i][j];
}
else if (i <= r && j > r)
{
if (max_m <= (s[i][j] - s[i][j - r - 1])) max_m = s[i][j] - s[i][j - r - 1];
}
else if (i > r && j < +r)
{
if (max_m <= (s[i][j] - s[i - r - 1][j])) max_m = s[i][j] - s[i - r - 1][j];
}
else if (i > r && j > r)
{
if (max_m <= s[i][j] - s[i - r - 1][j] - s[i][j - r - 1] + s[i - r - 1][j - r - 1])
max_m = s[i][j] - s[i - r - 1][j] - s[i][j - r - 1] + s[i - r - 1][j - r - 1];
}
}
}
cout << max_m << endl;
return 0;
}然后去寻找了一下答案，看了个思路类似的解法后发现并没有必要将第一个元素作为爆炸范围的右下角进行计算。将其作为左上角会更为方便。下面是答案代码：
#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int s[N][N];
void yuchuli()
{
for(int i=1;i<=5001;i++)
for(int j=1;j<=5001;j++)
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];//预处理前缀和的另外一种方式
}
int main()
{
int n,r;
cin>>n>>r;
int res=0;//记录总价值
while(n--)
{
int x,y,w;
cin>>x>>y>>w;
s[x+1][y+1]+=w;
}
if(r>=5001)
for(int i=1;i<=5001;i++)
for(int j=1;j<=5001;j++)
res+=s[i][j];
else
{
yuchuli();
for(int i=1;i<=5001-r;i++)
for(int j=1;j<=5001-r;j++)
{
int sum=s[i+r-1][j+r-1]-s[i+r-1][j-1]-s[i-1][j+r-1]+s[i-1][j-1];
res=max(res,sum);
}
}
cout<<res;
return 0;
}
作者：Bug-Free
链接：https://www.acwing.com/solution/content/10116/
来源：AcWing23年11月2日
题目1
输入一个长度为 n的整数序列。
接下来输入 m个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r] 之间的每个数加上 c。
请你输出进行完所有操作后的序列。
这是一道差分算法的板子题目，再来复习下差分算法。
差分算法可以视为前缀和算法的逆运算，理解难度也并不高。
比如现有以原数组a，构造差分数组d。
d[i] = a[i] - a[i-1]
即a[i] = d[i] + a[i-1] ,a为d的前缀和数组，d为a的差分数组。
差分数组可以产生一些奇妙的特性，因为原数组为差分数组d的前缀和数组，那么对差分数组中任意元素的加减，都会同时对前缀和数组的后续所有元素产生影响。
如此，利用这个特性我们就可以解决一类问题——频繁对特定数组某区间进行加减单一特定值的问题。
假如我们需要对原数组a的[l,r]区间进行自加1操作，那么我们只需要对a的差分数组的l元素进行加1，然后r+1元素进行减1即可。
注：因为对l元素进行加一会使前缀和数组l元素后的所有元素都加1，所以还需要将r+1元素减1来处理多余的影响。
所以我们就可以得到如下ac的板子代码
#include<iostream>
using namespace std;
#define N 100000
int d[N],a[N];
int main()
{
int n = 0,m = 0;
int l = 0,r = 0,c = 0;
int sum = 0;
cin >> n>> m;
for(int i = 1; i < n+1; i ++)
{
cin >> a[i];
}
for(int i = 1; i < n+1; i ++)
{
d[i] = a[i] - a[i-1];
}
for(int i = 0; i < m; i ++)
{
cin >> l >> r >> c;
d[l] += c;
d[r+1] -= c;
}
for(int i = 1; i < n+1;i ++)
{
sum += d[i];
cout << sum << " ";
}
return 0;
}题目2
给定一个空数组 $V$ 和一个整数数组 $a_1,a_2,…,a_n$。
现在要对数组 $V$ 进行 $n$ 次操作。
第 $i$ 次操作的具体流程如下：
- 从数组 $V$ 尾部插入整数 $0$。
- 将位于数组 $V$ 末尾的 $a_i$ 个元素都变为 $1$（已经是 $1$ 的不予理会）。
注意：
- $a_i$ 可能为 $0$，即不做任何改变。
- $a_i$ 可能大于目前数组 $V$ 所包含的元素个数，此时视为将数组内所有元素变为 $1$。
请你输出所有操作完成后的数组 $V$。
这个题可以使用差分算法求解，将v数组视为差分数组，每次变更操作视为对一个区间的元素进行+1，例如当a[i]大于区间范围时，变更区间即为[0,i]。操作后的结果即为v的前缀和数组，需要注意有重复变更的区间，需要将大于等于1的部分输出1，其他输出0即可。
当个懒狗，这次贴个没有优化的ac代码。
#include<iostream>
using namespace std;
#define N 300000
int v[N],a[N],s[N];
int main() {
int n = 0,q = 0;
cin >> q;
while(q--) {
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
if(a[i] >= i) {
v[1] += 1;
v[i+1] -= 1;
}
else if(a[i] == 0)
{
;
}
else {
v[i-a[i]+1] += 1;
v[i+1] -= 1;
}
}
for(int i = 1; i <= n; i++) {
s[i] = v[i] + s[i-1];
}
for(int i = 1; i <= n; i ++) {
if(s[i] >= 1) cout << 1 << " ";
else cout << 0 << " ";
}
for(int i = 0; i <= n+10; i ++)
{
v[i] = 0;
s[i] = 0;
a[i] = 0;
}
cout << endl;
}
return 0;
}23年11月10日
题目1
输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2)表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。
二维差分数组板子题，构造方法类似二维前缀和。在对一个元素进行加减后，会对整个以其为左上角的最大二维数组产生影响，所以还需要将多余的影响减掉。我们可以抽象出一个函数，专用于计算。
void insert(int x1,int y1,int x2,int y2,int c)
{
d[x1][y1] += c;
d[x2+1][y1] -= c;
d[x1][y2+1] -= c;
d[x2+1][y2+1] += c;
}同时，如果(x1,y1),(x2,y2)代表的坐标相等，就可以构造出一个差分数组元素
以下为摆出ac的板子：
#include<iostream>
using namespace std;
#define N 1010
int a[N][N],d[N][N];
void insert(int x1,int y1,int x2,int y2,int c)
{
d[x1][y1] += c;
d[x2+1][y1] -= c;
d[x1][y2+1] -= c;
d[x2+1][y2+1] += c;
}
int main() {
int n = 0,m = 0,q = 0;
cin >> n >> m >> q;
for(int i = 1; i <= n;i ++)
{
for(int j = 1; j <= m; j ++)
{
cin >> a[i][j];
insert(i,j,i,j,a[i][j]);
}
}
int x1 = 0,y1 = 0,x2 = 0,y2 = 0,c = 0;
while(q--)
{
x1 = 0,y1 = 0,x2 = 0,y2 = 0,c = 0;
cin >> x1 >> y1 >> x2 >> y2 >> c;
insert(x1,y1,x2,y2,c);
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
cout << d[i][j] << " ";
}
cout << endl;
}
return 0;
}23年11月12日
题目1
给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
这个题目当时没想清楚，直接看了答案。因为是对区间内进行加减操作，所以可以考虑差分，又要求保证操作次数最小，所以还可以再加上贪心思想。
我们将数列中所有数调整为一致的操作通过差分改变成通过对两个元素的加减使整个差分数组除第一个元素外其他元素值为0 。
每次调整两个元素，让数列中的负数与正数相匹配进行抵消。没有找到对应匹配元素的元素可以与差分数组的第一个元素进行匹配。于是我们可以统计整个差分序列，求出所有负数的和p与所有正数的和q，p与q中的最大值就是需要的最少操作次数。
那么如何求最终数列可能存在的数量呢？因为首先要保证操作次数最小，而正数负数匹配进行抵消一定是最快的，所以有可能产生不同序列的数量取决于找不到配对元素的元素。对于每个未配对的元素，我们有两种选择:要么使用差分数组的首元素，要么使用差分数组尾元素的下一个元素。由于有abs(p-q)个未配对的元素，因此可能的最终序列'a'的总数为abs(p-q)+1。
所以有如下ac代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 110000
ll n,m,i,j,p,q,a[N];
int main()
{
scanf("%lld",&n);
for (i=1;i<=n;i++)
scanf("%lld",&a[i]);
for (i=2;i<=n;i++)
{
ll c=a[i]-a[i-1];
if (c>0)//不要输入 if (c) 因为c是指不为0就好了,如果c为-1,那么最后的布尔值也为1,if(c)的意思是,只要c不为0,那么条件的布尔值都为1
p+=c;
else
q-=c;
}
ll ans1=max(p,q),ans2=abs(p-q)+1;
cout<<ans1<<endl<<ans2;
return 0;
}
作者：秦淮岸灯火阑珊
链接：https://www.acwing.com/solution/content/816/
来源：AcWing题目2
给定一个按照升序排列的长度为 n 的整数数组，以及 q个查询。对于每个查询，返回一个元素 k的起始位置和终止位置（位置从 0开始计数）。如果数组中不存在该元素，则返回 -1 -1
二分板子题，直接上y总模板，已经没有优化空间了
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
int n;
string str;
unordered_set<string> S;
bool check(int mid)
{
S.clear();
for (int i = 0; i + mid - 1 < n; i ++ )
{
string s = str.substr(i, mid);
if (S.count(s)) return false;
S.insert(s);
}
return true;
}
int main()
{
cin >> n >> str;
int l = 1, r = n;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << r << endl;
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/5509029/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。题目3
$n(n\le 100)$ 名同学参加歌唱比赛，并接受 $m(m\le 20)$ 名评委的评分，评分范围是 $0$ 到 $10$ 分。这名同学的得分就是这些评委给分中去掉一个最高分，去掉一个最低分，剩下 $m-2$ 个评分的平均数。请问得分最高的同学分数是多少？评分保留 $2$ 位小数。
小水题，直接上ac代码
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
int main(){
cout << setiosflags(ios::fixed) << setprecision(2);
int n, m;
double sum;
cin >> n >> m;
int goal[m];
double ans[n];
for(int i = 0; i < n; i ++)//分别对n个同学进行操作
{
sum=0;
for(int j = 0 ; j < m; j ++)//对具体同学的操作
{
cin >> goal[j];
sum += goal[j];
}
sort(goal,goal+m);
sum -= goal[0]+goal[m-1];
ans[i] = sum/(m-2);
}
sort(ans,ans+n);
cout << ans[n-1] << endl;
return 0;
}
Comments NOTHING