周总结（第一周）
3月份3个星期
* 三个星代表不会
再做 * 加强
题目1-完全二叉树(记忆)
考察数据结构
完全二叉树的深度dep=log2(N+1)+1
完全二叉树节点的深度depi=ceil(log2(i+1))向上舍入
完全二叉树的层次遍历，遍历每层的二叉树计算基础每层的总和，然后找出最大的和。用到log2()函数，计算以2为底的对数，还有ceil()向上取整函数，头文件是cmath.
完全二叉树的深度h与节点数N的关系为h=log2(N+1).
#include <iostream>
#include <cmath>
using namespace std;int main()
{int n,x,d;long long int num=0;cin>>n;long long arr[10005] = { 0 };//初始化数组int dep = log2(n + 1);//二叉树的深度for(int i=1;i<=n;i++){cin>>x;//直接将数据输入进去就可以int id = ceil(log2(i + 1));//计算当前的数据所在的深度arr[id]+=x;//把对应深度的数相加}for(int i=1;i<=dep+1;i++){if(num<arr[i]){//比较得出最大值得的最小深度num=arr[i];d=i;}}cout<<d<<endl;return 0;
}注意：直接输入数据就ok，将各深度相同的二叉树的权值进行相加；深度用数组的下标表示即可。
再做一遍：
#include <iostream>
#include <cmath>
using namespace std;
int a[10004];
int main()
{int N,x;cin>>N;int dep = log2(N + 1);for(int i=1;i<=N;i++){cin>>x;int id = ceil(log2(i + 1));a[id]+=x;}int maxn=-1;int d=0;for(int i=1;i<=dep;i++)//错误代码{if(maxn<a[i]) {maxn=a[i];d=i;}}cout<<d<<endl;return 0;
}
完全二叉树总共的深度dep=log2(N+1)+1
完全二叉树的结点的深度dep=ceil(log2(i+1))向上舍入最近的数
修改：
for(int i=1;i<=dep+1;i++){if(maxn<a[i]) {maxn=a[i];d=i;}}
题目2-后缀表达式
有点不熟悉，不清楚还有会有括号的出现
利用队列
这个题“（）”的存在是没有想到的。
错误代码；
应该考虑几种情况；
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{int n,m;cin>>n>>m;long long int a[n+m+10];for(int i=1;i<=n+m+1;i++){cin>>a[i];}sort(a+1,a+1+n);long long int sum=0;for(int i=1;i<=m;i++){sum-=a[i];}for(int i=m+n+1;i>=m+1;i--){sum+=a[i];}cout<<sum<<endl;return 0;
}
#include <bits/stdc++.h>
/*
1.不含负数单数减号1-（1-1-1）=1-1+1+1 相当于减掉一个最小的双数减号1+1-（1-1）总结减号数>=1都可以转换成减去最小的数
2.含有负数（例如：1-[-1+(-1)]-(-1)）(假设：负数f个，加号p个，减号m个，数n个，n=p+m+1)(f>0,m>=1,n-m>=1,f<=n)1个减号可以把p+1即n-m个负数转成正数，剩余的负数f-(n-m)个负数，此时减号还有m-1个（用到了一个）剩余的每个负数都由一个减号去转换。先不考虑（f-(n-m)大小，即先不考虑剩余负数的个数）a.当f-(n-m)<m-1,剩余负数小于减号数，会存在负数如果f-(n-m)<0，没有剩余负数，m=1上面不等式才成立如果f-(n-m)>0，因为m>=1,所以f-(n-m)<m-1不成立，说明不会剩余负数。这种情况没有负数，输出所有数的绝对值之和即可b.当f-(n-m)>m-1,f>n-1,即f>=n,即f==n，再由上述剩余的负数为m个，此时减号为m-1个，此时没有了减号，还有一个负数（绝对值总和减到取绝对值最小啊的那个负数的两倍）c.当f-(n-m)=m-1，此时没有负数也没有负号了，输出所有的数的绝对值之和根据a,b,c得当f==n(所有数全为负数)时，绝对值总和减到取绝对值最凶啊的那个负数的两倍当f!=n时，输出所有数的绝对值之和
*/
using namespace std;
int p,n,m;
long long sum=0,rsum=0;//sum是绝对值和，rsum是真实值和
int fu=0,min;
long long num[200001],fnum[200001];
int main()
{// 请在此输入您的代码cin>>p>>m;n=p+m+1;for(int i=0;i<n;i++){cin>>num[i];if(num[i]<0){fnum[fu]=num[i];fu++;//记录负数的个数sum-=num[i];//计算绝对值之和}elsesum+=num[i];rsum+=num[i];//计算真实值之和}if(m==0){//所有都是加号cout<<rsum;}else{//存在减号sort(num,num+n);if(fu==0){cout<<sum-2*num[0];}else{if(fu!=n){//存在负数存在减号cout<<sum;}else{//全为负数sort(fnum,fnum+fu);cout<<sum-(-2*fnum[fu-1]);}}}return 0;
}题目3-迷宫 *
考察深搜广搜的典型题目
利用队列，出对入队
#include <bits/stdc++.h>
using namespace std;
int n,m;
string Map[500];
const int d[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
const string dd="DLRU";//按照字典序增序
struct node {int i,j;string ans;//到达该节点需要的路径
};
queue<node> q;
void BFS()
{node s;s.i=0,s.j=0;s.ans="";Map[0][0]='1';q.push(s);//将第一个节点放入while(!q.empty()){node a=q.front(),b;//队列非空，取出队首int x=a.i;int y=a.j;q.pop();//弹出队首if(x==n-1&&y==m-1)//如果是最后一个就输出结果{cout<<a.ans.length()<<endl;cout<<a.ans<<endl;break;}for(int i=0;i<4;i++){//取出队首后，遍历队首四个方向int newx=x+d[i][0];int newy=y+d[i][1];if(newx<0||newy<0||newx>=n||newy>=m) continue;//越界.passif(Map[newx][newy]=='1') continue;//走过,passb.ans=a.ans+dd[i];//赋值，将该节点放入队列b.i=newx,b.j=newy;//赋值Map[newx][newy]='1';//赋值q.push(b);//放入队列}}
}
int main()
{/* cin>>n>>m;for(int i=0;i<n;i++){cin>>Map[i];}BFS();*/cout<<"DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR"<<endl;return 0;
}题目4-灵能传输 *
题目-灵能传输
B站视频
#include <bits/stdc++.h>using namespace std;
/*
ai-1 ,ai, ai+1 ---> ai-1+ai,-ai,ai+1+ai
si-1 ,si, si+1 ---> si, si-1,si
s0,s1,s2,s3,,,,,sn*/
typedef long long ll;
const int N=300010;int n;
ll s[N],a[N];
bool st[N];
int main()
{int T;cin>>T;while(T--){memset(s,0,sizeof(s));memset(a,0,sizeof(a));memset(st,0,sizeof(st));cin>>n;s[0]=0;for(int i=1;i<=n;i++){cin>>s[i];s[i]+=s[i-1];}ll s0=s[0],sn=s[n];if(s0>sn)swap(s0,sn);//?sort(s,s+1+n);for(int i=0;i<=n;i++){if(s[i]==s0){s0=i;break;}}for(int i=0;i<=n;i++){if(s[i]==sn){sn=i;break;}}//隔一个int l=0;int r=n;for(int i=s0;i>=0;i-=2){a[l++]=s[i];st[i]=true;}for(int i=sn;i<=n;i+=2){a[r--]=s[i];st[i]=true;}for(int i=0;i<=n;i++){if(!st[i]){a[l++]=s[i];st[i]=true;}}ll res=0;for(int i=1;i<=n;i++){res=max(res,abs(a[i]-a[i-1]));}cout<<res<<endl;}return 0;
}题目5-外卖店优先级
内存空间大小的问题，是否使用结构体
#include <iostream>
#include <cstring>
using namespace std;
const int N=10010;
int a[N][N];
//(10000 0000+20000 )*4(int)=4 0004 0000
//256M题目要求的空间，即2^8*z^20=256*1048567=2 6843 3152
int main()
{int n,m,t;cin>>n>>m>>t;int ts,id;memset(a,0,sizeof(a));for(int i=1;i<=m;i++){cin>>ts>>id;a[ts][id]+=2;}int sum[n+1]={0};int b[n+1]={0};for(int i=1;i<=t;i++){for(int j=1;j<=n;j++){if(a[i][j]==0&&sum[j]!=0){sum[j]-=1;if(sum[j]<=3) b[j]=0;}sum[j]+=a[i][j];if(sum[j]>5) b[j]=1;}}int ans=0;for(int j=1;j<=n;j++){//cout<<sum[j]<<" ";if(sum[j]>5||(sum[j]>3&&b[j]==1)) ans++;}cout<<ans<<endl;return 0;
}
利用结构体
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100005;
struct node
{int ts,id;
}a[N];
int ans=0;
int sum[N];//当前优先
int last[N];//这家店的上一次订单的时刻
bool hz[N];
bool cmp(node x,node y)
{if(x.ts==y.ts) return x.id<y.id;return x.ts<y.ts;
}
int main()
{int n,m,t;cin>>n>>m>>t;int sk,bh;for(int i=1;i<=m;i++){cin>>a[i].ts>>a[i].id;}sort(a+1,a+m+1,cmp);//求优先度sk=0;
// for(int i=1;i<=m;i++)
// cout<<a[i].ts<<" "<<[i].id;for(int i=1;i<=m;i++){//当前时刻有订单的信息sk=a[i].ts;bh=a[i].id;if(sk!=last[bh]){//当前时刻与上一个时刻sum[bh]=sum[bh]-(sk-last[bh]-1);//当前优先度}if(sum[bh]<0) sum[bh]=0;if(sum[bh]<=3) hz[bh]=0;sum[bh]+=2;if(sum[bh]>5) hz[bh]=1;last[bh]=sk;}for(int i=1;i<=n;i++){if(last[i]<t){sum[i]-=t-last[i];}if(sum[i]<=3){hz[i]=0;}}for(int i=1;i<=n;i++){if(hz[i]) ans++;}cout<<ans<<endl;return 0;
}题目6-修改数组
该题注意循环中的时间优化，还可以使用并查集
没有使用并查集
循环没有优化超时了
做法0.5：
#include <iostream>using namespace std;
const int N=1000010;
long long int a[N];
//256*2^20=268,435,456
//long long int 占8字节内存 ,没有超内存
int main()
{int n,x;cin>>n;for(int i=1;i<=n;i++){cin>>x;while(a[x]!=0){x++;}cout<<x<<" ";a[x]=1;}cout<<endl;return 0;
}
做法1：
将循环进行优化
#include <iostream>using namespace std;
const int N=1000010;
long long int a[N];
//256*2^20=268,435,456
//long long int 占8字节内存 ,没有超内存
int main()
{int n,x;cin>>n;for(int i=1;i<=n;i++){cin>>x;while(a[x]!=0){a[x]++;x+=(a[x]-1);}cout<<x<<" ";a[x]++;}cout<<endl;return 0;
}
