头像

暗夜




离线:8小时前


活动打卡代码 AcWing 854. Floyd求最短路

暗夜
3天前
// 可以存在重边和自环,但不能有负权回路。时间复杂度n^3

#include<iostream>
#include<cstring>
using namespace std;

const int N=210,INF=0x3f3f3f3f;
int dist[N][N],n,m,k;

void foly()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}

int main()
{
    cin>>n>>m>>k;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j) dist[i][j]=0;
            else dist[i][j]=INF;

    while(m--)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        dist[a][b]=min(dist[a][b],w);
    }

    foly();

    while(k--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(dist[a][b]>INF/2) puts("impossible");
        else cout<<dist[a][b]<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 851. spfa求最短路

暗夜
4天前
// 对ford算法优化,每次更新已经更新的节点 负权边 时间复杂度<O(nm) 负环会陷入死循环
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int N=1e5+10;
int n,m,dist[N],h[N],e[N],ne[N],w[N],idx=0;
bool st[N];

void add(int a,int b,int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;

}

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;   // st用来记录当前节点是否在队列当中
    while(q.size())
    {
        int t=q.front();
        q.pop();
        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];
                if(!st[j]) 
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1; // 只更新更新过的节点,所以孤立的点始终是最大值,和ford算法的不同
    else return dist[n];
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        add(a,b,w);
    }

    int ans=spfa();
    if(ans==-1) puts("impossible");
    else cout<<ans;

}




暗夜
4天前
// 存在负权边的情况 时间复杂度O(nm) 限制k条路径以内到达n节点
#include<iostream>
#include<cstring>
using namespace std;

const int N=510,M=10010;
struct edge{
    int a,b,w;
}Edges[M];
int n,m,k,dist[N],backup[N];

int foly()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++)
    {
        memcpy(backup,dist,sizeof dist);
        for(int j=0;j<m;j++)
        {
            int a=Edges[j].a,b=Edges[j].b,w=Edges[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }
    if(dist[n]>0x3f3f3f3f/2) return -1;     // 有可能n号节点之前存在负权边,把n号点的距离更新为0x3f3f3f3f-x,实际上到不了n节点
    else return dist[n];
}

int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        Edges[i]={a,b,w};
    }

    int ans=foly();
    if(ans==-1) puts("impossible");
    else cout<<ans;
}



暗夜
4天前
// 稀疏图,邻接表,复杂度:nlog(m)

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

typedef pair<int,int> PII;
const int N=2e5+10;
int dist[N],h[N],e[N],ne[N],w[N],idx=0,n,m;
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int dijstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;    // 小根堆
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    heap.push({0,1});       // 距离,编号
    while(heap.size())
    {
        PII t=heap.top();       //每次取出堆中最小距离 O(1)
        heap.pop();

        int ver=t.second,distance=t.first;
        if(st[ver]) continue;       // 考虑重边,如果之前已经确定了距离则跳过本次判断
        st[ver]=true;

        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>distance+w[i])
            {
                dist[j]=distance+w[i];
                heap.push({dist[j],j});     //O(log(m))
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    memset(h,-1,sizeof h);

    cin>>n>>m;
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    int ans=dijstra();
    cout<<ans;

}



暗夜
5天前
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=510;
int dist[N],g[N][N];
bool st[N];
int n,m;

int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=1;i<n;i++)
    {
        int t=0;
        for(int j=1;j<=n;j++)   // 寻找不确定距离中的最短距离
        {
            if(!st[j]&&(t==0||dist[t]>dist[j]))     //t==0 找到第一个距离不确定的点
                t=j;
        }
        if(t==n) break; // 找到最短路,提前结束

        st[t]=true; 

        for(int j=1;j<=n;j++)   // 用当前刚确定的点,更新其他路径
        {
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }

    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    cin>>n>>m;

    memset(g,0x3f,sizeof g);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);
    }

    int t=dijkstra();
    cout<<t;
}



暗夜
6天前

题目链接 牛客巅峰挑战赛S2 第3场 Tree VI

题目:

系统中有一棵n个点的完全k叉树,现给出它的DFS先序遍历序列$a_i$,请你还原这棵树,并返回加密后的答案。
答案加密方法:所有边两个端点异或的和,即$\sum\limits_{i=1}^{n-1}u_i\ xor\ v_i$,其中$(u_i, v_i)$为一条树上的边。

下面给出完全二叉树的定义:若设二叉树的深度为k,除第 k 层外,其它各层 (1~k-1) 的结点数都达到最大个数,第k层所有的结点都连续集中在最左边。请你根据这个定义进行适度推广,得到完全k叉树的含义。

示例1

输入

3,[1,2,3,4,5]

返回值

13

说明:
QQ截图20201127092648.png
备注:

数据满足:1<=n,k<=10^5,1<=ai<=10^9

错误的代码:

class Solution {
public:
    /**
     * 
     * @param k int整型 表示完全k叉树的叉数k
     * @param a int整型vector 表示这棵完全k叉树的Dfs遍历序列的结点编号
     * @return long长整型
     */

    typedef long long LL;
    LL ans=0,nn=0;
    vector<int> aa;
    int kk,a_size;
    LL dfs(int u,int cnt)    //u:bfs序  cnt:dfs序
    {
        LL root=cnt;    //记录当前子树的根节点下标
        for(int i=u*kk+1;i<=u*kk+kk&&i<a_size;i++)
        {
            LL s=dfs(i,++nn);    //返回儿子的结点编号
            ans+=aa[s]^aa[root];    //异或求和
        }
        return root;
    }

    long long tree6(int k, vector<int>& a) {
        // write code here
        kk=k;    //k叉树
        aa=a;
        a_size=a.size();
        dfs(0,0);
        return ans;
    }
};

错误:

段错误:您的程序发生段错误,可能是数组越界,堆栈溢出(比如,递归调用层数太多)等情况引起
case通过率为90.00%


活动打卡代码 AcWing 845. 八数码

暗夜
10天前
#include<iostream>
#include<cstring>
#include<queue>
#include<unordered_map>
using namespace std;

unordered_map<string,int> d;
queue<string> q;

int bfs(string start)
{
    q.push(start);
    d[start]=0;
    string end="12345678x";

    int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
    while(q.size())
    {
        string t=q.front();
        q.pop();
        int dis=d[t];
        if(t==end) return dis;

        int k=t.find('x'),x0=k/3,y0=k%3;
        for(int i=0;i<4;i++)
        {
            int x=x0+dx[i],y=y0+dy[i];
            if(x>=0&&x<3&&y>=0&&y<3)
            {
                swap(t[k],t[x*3+y]);
                if(d.count(t)==0)
                {
                    q.push(t);
                    d[t]=dis+1;
                }
                swap(t[k],t[x*3+y]);
            }
        }
    }
    return -1;
}

int main()
{
    string start;
    char ch[2];
    for(int i=0;i<9;i++)
    {
        scanf("%s",&ch);
        start+=ch[0];
    }

    cout<<bfs(start)<<endl;


    return 0;
}



分享 满k叉树

暗夜
11天前

20180810203141565.png

  • 第i个结点的第一个孩子=(i-1)k+2
  • 第i个结点最后一个孩子=(i-1)k+2+k-1=ik+1
  • 第i个结点的父结点=[(i-2)/k]+1

简单推导:
1. 第i个结点之前有i-1个结点,所以排在i的第一个孩子之前的有(i-1)k个结点
2. 第i个结点第一个孩子编号=(i-1)k+1
3. 但是这种算法漏掉了根节点,所以应该再加上1,即(i-1)k+2

引用大佬博客
https://blog.csdn.net/sinat_36231857/article/details/81569323




暗夜
11天前

QQ截图20201120213145.png

  • max int:2e9
  • max long long:9e18

QQ截图20201122155314.png

  • ‘A’:65
  • ‘a’:97
  • ‘0’:48


分享 STL库总结

暗夜
11天前

变长数组

头文件 vector

1. 初始化

vector<int> a(10); //也可不定义数量
vector<int> a(10,1); //每个元素给初值
vector<int> a(b); //用b来初始化a,拷贝构造
vector<int> a(b.begin(),b.bengin()+3);//部分元素拷贝
int b[3]={1,2,3}; vector<int> a(b,b+2);//数组构造

2. 赋值

a.push_back(x)//在a的最后插入元素x
a.back() //返回最后一个元素
a.front() //返回第一个元素
a.clear() //清空
a.empty() //是否为空
a.pop_back() //删除最后一个元素
a.erase(a.begin()+i,a.begin()+j)//删除任意区间元素
a.insert(a.begin()+i,x)//在位置i插入元素x
a.insert(a.begin()+i,m,x)//在位置i插入m个x
a.size() //返回a的元素个数
a.resize(10)//将a的数量调整为10,多删少补
a.resize(10,2)//将a的数量调整为10,多删少补,补的值为2
a.swap(b) //a,b交换
a==b //a,b是否相等   

3. 重要用法

sort(a.begin(),a.end()) //从小到大排序
reverse(a.begin(),a.end()) //倒序排列 并不是倒叙排序
sort(all.begin(),all.end());<br/>
all.erase(unique(all.begin(),all.end()),all.end());//去重。unique将相邻且重复的元素放到末尾,所需要先排序

队列

头文件 queue

基本操作

q.empty()               如果队列为空返回true,否则返回false
q.size()                返回队列中元素的个数
q.pop()                 删除队列首元素但不返回其值
q.push()                在队尾压入新元素
q.front()               返回队首元素的值,但不删除该元素
q.back()                返回队列尾元素的值,但不删除该元素

优先队列

  • 定义:priority_queue< Type, Container, Functional >
  • 基本操作和普通队列一致
//升序队列,小根堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列,大根堆,默认情况
priority_queue <int,vector<int>,less<int> >q;
priority_queue<int> q; //同上
//greater和less是std实现的两个仿函数(就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator(),这个类就有了类似函数的行为,就是一个仿函数类了)