1231.航班时间
思路
又是这种字符串题，时间题和日期题，年份题我一看就头大，题目要求是计算确切航班时间，知晓的是往返航班的起始时间（都在当地），由于时差的原因，相对时间（当地时间之差）会有不同，因此，我们要计算确切时间的话，直接将往返时间相加/2即可（条件满足）
一个很好的思路是将当前时间全部转化为秒，相当于一个数值，计算两个时间点的算法就是直接将两个时间点相减即可计算出秒差
不过这题还有可能隔天
很多人包括前期的我就在疑惑这个隔天要怎么计算，尤其是隔天，而且前一天时间还比后一天时间大的情况
其实也是到达时间减去起始时间，只不过结果是个负数，但是没问题，加上1整天的秒数即可得出正确结果。 感到疑惑的大佬可以自去验证一下
比如 一天24小时，第一天18时，第二天4时到达，时间差等于(4-18+24)=10小时.你一个小时一个小时算也刚好是10小时
AC代码
//10:32:05
//18:22:05
#include<iostream>
#include<string>
using namespace std;
void caculateTime(string s,string e); //主功能函数
int main()
{
int N;
std::cin>>N;
string start,End; //存储出发时间，到达时间
getline(cin,start); //一次读取一行的输入函数,第一次读取先把第一行的换行符给略过
while(N>0)
{
getline(cin,start); //连续读两次，分别是去程和返程的细节
getline(cin,End);
caculateTime(start,End);
N--;
}
return 0;
}
void caculateTime(string s,string e)
{
int ALL = 24*3600; //一整天的秒数
int sday=0; //去程的隔天数
int eday=0; //返程的隔天数
if(s.length()==22)
sday = s[20]-'0';
if(e.length()==22)
eday = e[20]-'0';
//依次计算四个时间对应的总秒数
int t[4]={0};
t[0] = ((s[0]-'0')*10+s[1]-'0')*3600 + ((s[3]-'0')*10+s[4]-'0')*60 + ((s[6]-'0')*10+s[7]-'0');
t[1] = ((s[9]-'0')*10+s[10]-'0')*3600 + ((s[12]-'0')*10+s[13]-'0')*60 + ((s[15]-'0')*10+s[16]-'0');
t[2] = ((e[0]-'0')*10+e[1]-'0')*3600 + ((e[3]-'0')*10+e[4]-'0')*60 + ((e[6]-'0')*10+e[7]-'0');
t[3] = ((e[9]-'0')*10+e[10]-'0')*3600 + ((e[12]-'0')*10+e[13]-'0')*60 + ((e[15]-'0')*10+e[16]-'0');
//std::cout<<s[0]<<" "<<s[1]<<" "<<s[3]<<" "<<s[4]<<" "<<s[6]<<" "<<s[7]<<std::endl;
//std::cout<<s[9]<<" "<<s[10]<<" "<<s[12]<<" "<<s[13]<<" "<<s[15]<<" "<<s[16]<<std::endl;
//std::cout<<t[0]<<" "<<t[1]<<" "<<t[2]<<" "<<t[3]<<std::endl;
int cha1=0; //去程花费时间
int cha2=0; //返程花费时间
cha1 = t[1]-t[0]+sday*ALL;
cha2= t[3]-t[2]+eday*ALL;
int cha = (cha1+cha2)/2; //结果（总秒数形式）
//std::cout<<cha1<<" "<<cha2<<" "<<cha<<std::endl;
//计算小时，分钟，秒
int hour = cha/3600;
cha = cha%3600;
int minute = cha/60;
int second = cha%60;
//输出（因为需要格式，这里的代码略显臃肿，大佬可以考虑采用printf格式化输出)
if(hour<10)
std::cout<<"0";
std::cout<<hour<<":";
if(minute<10)
std::cout<<"0";
std::cout<<minute<<":";
if(second<10)
std::cout<<"0";
std::cout<<second<<std::endl;
}
1264.动态求连续区间和
思路
越到后面的题越难了啊，这题是与线段树相关的，当然树状数组也可以做，所以特地去网上学习了一下线段树，然后按照思路自己写了个很菜的线段树出来，放到这道题上勉强AC（977ms），共涉及到线段树的创建，改动，查询
AC代码（线段树）
#include<iostream>
using namespace std;
int n,m;
int N[100001]; //定义输入数组用于存储原数组
//数据结构定义
struct lineTree
{
int l; //当前区间的左界
int r; //当前区间的右界
int sum; //当前区间的总和
int mod; //当前区间修改后的差值
};
lineTree line[1000001]; //定义线段树数组（一定要开的够大）
//线段树的创建函数
void build(int i,int l,int r)
{
line[i].l=l; //设立当前线段树结点的起始节点
line[i].r=r;
if(line[i].l==line[i].r) //如果起始相同，直接将对应位置元素放入该处
{
line[i].sum=N[l];
return;
}
int mid = (l+r)/2; //求出mid
//递归遍历创建节点数，i*2是左节点，i*2+1是右节点
build(i*2,l,mid);
build(i*2+1,mid+1,r);
line[i].sum=line[2*i].sum+line[2*i+1].sum;
}
//修改函数，修改原数组中的某个元素，导致线段树全部要修改
//indexA是当前下标,pos是要修改的原数组下标，m是要修改成的值
void modified(int indexA,int pos,int m)
{
//找到目标位置并进行修改
if(line[indexA].l==line[indexA].r)
{
line[indexA].mod=m; //将修改值直接设为该值（因为是加起来所以直接等于修改值）
line[indexA].sum+=m;
return;
}
//如果所在下标处在左子节点里，搜索左子节点
if(pos<=line[indexA*2].r)
{
modified(indexA*2,pos,m);
line[indexA].sum+=line[indexA*2].mod;
line[indexA].mod=line[indexA*2].mod;
line[indexA*2].mod=0;
}
//如果所在下标处在右子节点里，搜索右子节点
else if(pos>=line[indexA*2+1].l)
{
modified(indexA*2+1,pos,m);
line[indexA].sum+=line[indexA*2+1].mod;
line[indexA].mod=line[indexA*2+1].mod;
line[indexA*2+1].mod=0;
}
}
//搜索函数，搜索s到e区间内的和
int Search(int cur,int s,int e)
{
//如果该区间处在目标区间中直接返回
if((s<=line[cur].l)&&(e>=line[cur].r))
return line[cur].sum;
//如果该区间与目标区间没有交联，直接返回0
if(line[cur].l>e||line[cur].r<s)
return 0;
int total=0;
//如果左子区间与目标区间有交集，遍历左子区间
if(line[2*cur].r>=s) total+=Search(cur*2,s,e);
//如果右子区间与目标区间有交集，遍历右子区间
if(line[2*cur+1].l<=e) total+=Search(cur*2+1,s,e);
return total;
}
int main()
{
std::cin>>n>>m;
for(int i=1;i<=n;i++) //输入原数组的值
std::cin>>N[i];
build(1,1,n); //建立初始线段树
while(m--)
{
int whether,v2,v3; //用于存储三个参数
std::cin>>whether>>v2>>v3;
if(whether) //如果whether为1则进行修改操作
modified(1,v2,v3);
else
std::cout<<Search(1,v2,v3)<<std::endl;
}
return 0;
}
【2020.4.13更新】增加了树状数组的做法，在代码注释里面可能说的不太清楚，因为本人描述能力较差，以后可能会单独写个博客结合图片更加清楚
AC代码（树状数组）
#include<iostream>
using namespace std;
int n,m;
int trArray[100001]; //存放树状数组
//获取当前数化为二进制后从左往右数第一个1所在位置
//（比如5，化为二进制后为101，返回的结果就是2的0次方为1，而8化为二进制后为100，因此返回的结果就是2的2次方即4）
int getlow(int x)
{
return x&(-x);
}
//add函数负责将位置为x的元素加上v，同时与其关联的其他元素依次相加
void add(int x,int v)
{
for(int i=x;i<=n;i+=getlow(i))
trArray[i]+=v;
}
//query函数负责查询1到pos位置的数之和
int query(int pos)
{
int sum=0;
for(int i=pos;i;i-=getlow(i))
sum+=trArray[i];
return sum;
}
int main()
{
std::cin>>n>>m;
//向树状数组中添加元素
for(int i=1;i<=n;i++)
{
int temp;
std::cin>>temp;
add(i,temp);
}
while(m--)
{
int whether,v2,v3;
std::cin>>whether>>v2>>v3;
if(whether)
add(v2,v3);
else
std::cout<<query(v3)-query(v2-1)<<std::endl; //计算v2到v3的元素之和
}
return 0;
}
1270.数列区间最大值
思路
涉及到区间，又涉及到高达十万次的查询，可定不能用普通暴力方法做，首先当然想到的就是刚学的线段树，只要将先前求和的线段树稍微改造一下就变成了存储最大值的线段树了，学以致用
不过需要注意的是这题cin和cout好像会超时，将换成printf和scanf就顺利AC了
AC代码
#include<iostream>
using namespace std;
int N[100001];
struct lineTree{
int l; //区间左界
int r; //区间右界
int MAX; //存储区间内最大值
};
lineTree T[500002]; //线段树数组
//线段树建立函数
void build(int i,int l,int r)
{
T[i].l=l;
T[i].r=r;
if(T[i].l==T[i].r)
{
T[i].MAX=N[l]; //对于单元素节点直接将最大值设为原数组中对应数值
return;
}
int mid=(l+r)/2;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
T[i].MAX=max(T[i*2].MAX,T[i*2+1].MAX); //待当前节点左子节点与右子节点建立完后求解当前节点的最大值
}
//查询函数，查询区间[s,e]中最大值
int Search(int cur,int s,int e)
{
//如果当前区间被目标区间包含，直接返回最大值
if(s<=T[cur].l && e>=T[cur].r)
{
return T[cur].MAX;
}
//毫不相干返回0
if(s>T[cur].r||e<T[cur].l)
return 0;
//设置最大值为-1
int MAXTemp=-1;
//与左子节点区间有交集，遍历并求最大值，后面与右子节点区间同理
if(T[2*cur].r>=s) MAXTemp = max(MAXTemp,Search(2*cur,s,e));
if(T[2*cur+1].l<=e) MAXTemp = max(MAXTemp,Search(2*cur+1,s,e));
//std::cout<<"MAXTemp:"<<MAXTemp<<std::endl;
return MAXTemp;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m); //所有cin,cout均改成scanf与printf不然会超时
//std::cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%d",&N[i]);
//std::cin>>N[i];
build(1,1,n);
while(m--)
{
int from,to;
//std::cin>>from>>to;
scanf("%d%d",&from,&to);
printf("%d\n",Search(1,from,to));
//std::cout<<Search(1,from,to)<<std::endl;
}
return 0;
}
797.差分
思路
一开始尝试用普通方法试过，秒超时，用printf和scanf也过不了，不得不说这个时间是卡的真准，刚好是最后一组数据超时了
后来才知道这又是一题模板题，是差分的标准模板，专门解决给区间内元素同时加上某个元素的题型
超时代码
#include<iostream>
using namespace std;
int N[100001];
int main()
{
int n,m;
std::cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%d",&N[i]);
while(m--)
{
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
for(int i=l;i<=r;i++)
N[i]+=c;
}
for(int i=1;i<=n;i++)
printf("%d ",N[i]);
return 0;
}
AC代码(差分模板)
#include<iostream>
using namespace std;
int N[200000];
int main()
{
int n,m;
std::cin>>n>>m;
for(int i=1;i<=n;i++) //键入原数组元素
scanf("%d",&N[i]);
for(int i=n;i;i--) //将每个元素减去前一个元素（直到最后一个元素）
{
N[i]=N[i]-N[i-1];
}
while(m--)
{
int l,r,c;
std::cin>>l>>r>>c;
N[l]+=c; //将区间左界所在元素加上对应的值（这样以后遍历恢复现场后所对应的增加量就会随之作用于区间内所有数）
N[r+1]-=c; //将区间右界之后的那个所在元素减去对应的值，这样才不会影响区间之外的数
}
for(int i=1;i<=n;i++) //恢复现场
N[i]=N[i]+N[i-1];
for(int i=1;i<=n;i++)
{
printf("%d ",N[i]);
}
return 0;
}
1236.递增三元组
思路
这题常规方法肯定是无法完成的，时间复杂度高达O(N3),题解里看到有用二分的，但是感觉太麻烦了，于是返回参考了北大大佬yxb的代码
仔细分析后理解了这题的思路
前缀和
不需要排序，三个数组，每次遍历只需要找出比b[i]大的a数组元素个数以及比c[i]小的元素个数即可
在大佬的代码上作了优化，少开了一个数组
#include<iostream>
#include<string.h>
using namespace std;
int N;
const int S=100020; //前缀和数组大小
typedef long long int ll;
int a[S]; //存储A数组
int b[S]; //存储B数组
int c[S]; //存储C数组
int dd[S]; //前缀和数组
int as[S]; //存储比对应下标的B数组元素小的A数组元素个数
int cs[S]; //存储比对应下标的B数组元素大的C数组元素个数
int main()
{
ll res=0;
std::cin>>N;
//先读入三个数组，这里注意的是因为数组元素可以为0，对后期处理会有不便（亲身实践，会出bug，后来还是决定+1）
for(int i=0;i<N;i++)
{
std::cin>>a[i];
a[i]++;
}
for(int i=0;i<N;i++)
{
std::cin>>b[i];
b[i]++;
}
for(int i=0;i<N;i++)
{
std::cin>>c[i];
c[i]++;
}
//在对应前缀和数组元素值下标处加一，比如a[i]=6,就让dd[6]加1
for(int i=0;i<N;i++)
{
dd[a[i]]++;
}
//计算前缀和
for(int i=1;i<=S;i++)
dd[i]+=dd[i-1];
//计算as大小，比如b[i]=3,就等于dd[2](小于3的数的个数)
for(int i=0;i<N;i++)
as[i]=dd[b[i]-1];
/*for(int i=0;i<20;i++)
std::cout<<dd[i]<<" ";
std::cout<<std::endl;
*/
memset(dd,0,sizeof(dd));
for(int i=0;i<N;i++)
dd[c[i]]++;
//计算前缀和
for(int i=1;i<=S;i++)
dd[i]+=dd[i-1];
//计算cs大小，比如b[i]=3,就等于dd[S-1]-dd[3](不小于等于3的的数的个数)
for(int i=0;i<N;i++)
cs[i]=dd[S-1]-dd[b[i]];
//组合计算，相乘
for(int i=0;i<N;i++)
{
//std::cout<<as[i]<<" "<<cs[i]<<std::endl;
res+=(ll)cs[i]*as[i];
}
std::cout<<res<<std::endl;
return 0;
}
466.回文日期
思路
找出给定日期范围内的所有回文日期即可，本人一开始使用的方法是对所有日期遍历然后再依次判断日期合法性与回文，果然还是超时了
后来看了解题思路，需要从另外一个角度来考虑，就是找出所有八位数回文串观察他们是否在日期范围内，这样一来只需要遍历一遍回文，然后判断日期是否合法就行了
超时代码
#include<iostream>
#include<math.h>
#include<string>
using namespace std;
bool vaild(int year,int month,int day)
{
if(month>12)
return false;
switch(day)
{
case 1:
case 3:
case 5:
case 7:
case 8:
case 10:
case 12:
if(day>31)
return false;
break;
case 4:
case 6:
case 9:
case 11:
if(day>30)
return false;
case 2:
if((year%4==0&&year%100!=0)||(year%1000==0))
{
if(day>29)
return false;
}
else{
if(day>28)
return false;
}
}
}
bool isHui(int e)
{
string numC = to_string(e);
for(int i=0;i<4;i++)
{
if(numC[i]!=numC[7-i])
return false;
}
return true;
}
int main()
{
int total=0;
int from,to;
std::cin>>from>>to;
for(int i=from;i<=to;i++)
{
int year = i/10000;
int month=(i%10000)/100;
int day=(i%100);
if(vaild(year,month,day))
{
if(isHui(i))
total++;
}
// std::cout<<year<<" "<<month<<" "<<day<<std::endl;
}
std::cout<<total<<std::endl;
return 0;
}
AC代码
#include<iostream>
#include<math.h>
#include<string>
using namespace std;
bool vaild(int year,int month,int day)
{
//筛选月份
if(month>12||month==0)
return false;
switch(month)
{ //大月
case 1:
case 3:
case 5:
case 7:
case 8:
case 10:
case 12:
if(day>31||day==0)
return false;
break;
//小月
case 4:
case 6:
case 9:
case 11:
if(day>30||day==0)
return false;
break;
case 2:
if((year%4==0&&year%100!=0)||(year%1000==0)) //闰年
{
if(day>29||day==0)
return false;
}
else{ //平年
if(day>28||day==0)
return false;
}
}
return true;
}
int main()
{
int total=0;
int from,to;
std::cin>>from>>to;
for(int i=1000;i<=9999;i++) //枚举所有8位数回文
{
int front=i;
int back=i;
for(int j=0;j<4;j++)
{
front=front*10+back%10;
back/=10;
}
//std::cout<<front<<std::endl;
int year = front/10000; //提取年月日用于验证日期合法性
int month=(front%10000)/100;
int day=(front%100);
//std::cout<<year<<" "<<month<<" "<<day<<std::endl;
if(vaild(year,month,day)&&from<=front&&to>=front) //合法并且在给定日期范围内total加一
{
//std::cout<<year<<" "<<month<<" "<<day<<std::endl;
//std::cout<<front<<std::endl;
total++;
}
// std::cout<<year<<" "<<month<<" "<<day<<std::endl;
}
std::cout<<total<<std::endl;
return 0;
}
本次做题进度到此结束，剩下的题将在下一P呈现
Q.E.D.
Comments | 0 条评论