AcWing 第29场周赛

比赛链接
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++各种容器的使用

上一篇:数据结构 第七讲 图(中)


下一篇:js 箭头函数 ES6