gpt4free gpt12345 top986edff49a09b869e883df619f0a3cdd3a93cb65最大数列和
1234567891011121314151617181920212223242526#include <bits/stdc++.h>using namespace std;int main() { int n; cin>>n; int a[n+5]; int pre[n+5];//存储第i个数之前间隔一个相加 直到数组开头 的和的值 for(int i=1;i<=n;i++) { cin>>a[i]; } pre[0]=0; pre[1]=a[1]; pre[2]=a[2]; for(int i=3;i<=n;i++) { pre[i]=pre[i-2]+a[i]; } int k; cin>>k; int ans=-1e18; ...
学习笔记
这6道题有几道是非常相似的,可以在不同情景中充分认识一个算法思想–前缀和与差分
对于前缀和与差分，我在CSDN找到了一篇比较形象的文章点击跳转
总结:题目很练基本功,第三题因为没有把和数组定义为长整型而导致一直无法AC,改为long long避免了数组溢出才全部通过
6道题:题目均来自蓝桥云课
1.区间次方和
本题是定义一个二维数组，第二维度存储前第一维度值项前1-5次方的值 在输入的同时计算pre数组
然后以时间复杂度O(n)解决本题所要求的最大10^5的数据量
因为相加过程，取模之前会有大于Int所能存放的最大值，所以数组定义为长整型
C++AC代码:
1234567891011121314151617181920212223#include <bits/stdc++.h>using namespace std;typedef long long ll;int mol=1e9+7;int n,m;ll num[100005];//瀛樺偍绗琲涓暟1-5娆℃柟鐨勫€?ll pre[100005][7];//存放前i个数字的j次方之和int main() ...
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758//基于二分查找实现 时间复杂度O(log2n)//枚举+检查#include <bits/stdc++.h>using namespace std;int a[50005];int l,n,m;int ans;bool check(int mid){//mid是理想的最短跳跃距离的值 本函数相当于在模拟理想能否实现 实现与否通过返回的结果体现 int i=0,now=0,cnt=0; while(i<n+1) { i++;//先跳出一步 if(a[i]-a[now]<mid){ //搬走石头 cnt++; } else{ now=i;//>=mid 跳过来 ...
AC代码:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354//单调栈类问题#include <bits/stdc++.h>using namespace std;int n;int h[1000000],v[1000000];int le[1000000],ri[1000000];int ans=-100;//存储接收到的能量最大的发射站所接受的能量int ma[1000000]={0};stack<int>st;//模拟单调栈的栈int main(){ cin>>n; for(int i=1;i<=n;i++) { cin>>h[i]>>v[i]; } //先从右到左遍历,构建right 存储第i个点发射站右边的第一个比它高的发射站 若没有 则right[i]=0 for ...
我的AC代码:
12345678910111213141516171819202122232425262728293031#include <cstdio>#include <stack>using namespace std;int n;int a[3000005];int f[3000005];stack<int>st;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=n;i>=1;i--) { //比当前数小的都Pop掉了 留下了比当前数大的 //也就是说 单调栈永远维护一个状态:数字越弹越大 while(!st.empty()&&a[st.top()]<=a[i]) { ...
这个题我是第二次才ac 第一遍没想到用栈来”瞻前” 因为是从左到右合嘛 第一遍的只过了百分之四十测试用例第一次代码:(通过率40%)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130//通过率40%#include <bits/stdc++.h>using namespace std;string s;int main(){while(cin>>s){ //因为有多组数据 list<char> paopao; //把这个字符 ...
原题链接:跳转点此我的代码:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117#include <bits/stdc++.h>using namespace std;int getNum(string s){ stack<int> exp; int len=s.length(); int i=0;// "12#3#+15#*"//12#3#+15#*//12//15 15//15*15 while(i<len) { if(s[i]==&# ...
原题跳转链接点击此处跳转洛谷下面是我写的代码:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162//前缀和数组#include <iostream>using namespace std;int n,m;int r[1000005];int d[1000005],s[1000005],t[1000005];long long sum[1000005]={0};//前缀和数组//4 3//2 5 4 3//2 1 3//3 2 4//4 2 4//前缀和数组的维护过程://sum[1]=2//sum[2]=3//sum[2]=7//sum[3]=sum[2]+sum[3]=7+0=7//sum4=sum3+sum4-d1=0+7-2=5//本题前缀和数组记录某天一共需要教室的数量 但是常规构建该数组的时间复杂度为n^2 利用前缀和思想 时间复杂度为nint main() ...
