比赛链接
AcWing 4194. Pow
难度:简单
知识点:数学,输出流控制
思路:调用数学库中的pow
参考代码:
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
int main()
{
int n,t;
cin>>n>>t;
//precision 精确度
cout<<setprecision(6)<<std::fixed<<n*pow(1.00011,t);
return 0;
}
AcWing 4195. 线段覆盖
难度:中等
知识点:差分
思路1:扫描线
思路2:差分,l、r的数据范围1e18,没法构建差分数组,可以使用map来记录
参考代码2
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
const int N=200010;
typedef long long LL;
map<LL,int> b;//<边界,线段覆盖数>差分数组,map可以自动排序
LL ans[N];//存储答案
int main()
{
int n;
scanf("%d", &n);
//差分,将区间(l,r)加1
for(int i=0;i<n;i++)
{
LL l,r;
//超过1e5的输入最好使用scanf
scanf("%lld%lld",&l,&r);
b[l]++,b[r+1]--;
}
LL sum=0,last=-1;//sum表示线段覆盖数,last表示上一条边界
for(auto &[k,v]:b)//加&可以减少复制的时间
{
if(last!=-1) ans[sum]+=k-last;
sum+=v;
last=k;
}
for(int i=1;i<=n;i++)
printf("%lld ",ans[i]);
return 0;
}
AcWing 4196. 最短路径
难度:困难
知识点:图论
思路:spfa求最短路,模板题+存上一个节点
参考代码:
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=100010,M=200010;//由于是无向边,所以边要点多一倍
int h[N], e[M], w[M], ne[M], idx;//邻接表存储
int q[N],pre[N];//存储走过的下,上一个节点,方便回溯找路径
LL dist[N];//存储距离
bool st[N];//表示是否被遍历过
int path[N];//存储走过的路径
void add(int a, int b, int c) // 添加一条边a->b,边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void spfa() // 求1号点到n号点的最短路距离
{
int hh = 0, tt = 0;
memset(dist, 0x3f, sizeof dist);
memset(pre,-1,sizeof pre);
dist[1] = 0;
q[tt ++ ] = 1;
st[1] = true;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
pre[j]=t;
if (!st[j]) // 如果队列中已存在j,则不需要将j重复插入
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
}
int main()
{
int n,m;
cin>>n>>m;
memset(h, -1, sizeof h);
while (m -- ){
int a,b,c;
cin>>a>>b>>c;
add(a, b, c),add(b,a,c);//无向边,添加两次
}
spfa();
if(pre[n]==-1) cout<<-1;//无法到达终点
else
{
int cnt=0;//记录经过点的个数
for(int i=n;i!=-1;i=pre[i])
path[cnt++]=i;
for(int i=cnt-1;i>=0;i--)
cout<<path[i]<<' ';
}
return 0;
}
总结不足:
1、C++的输出控制
2、复习基础课,差分+spfa
3、C++各种容器的使用