头像

王烽




离线:1天前


最近来访(11)
用户头像
AC天
用户头像
无矩_5
用户头像
sun_63
用户头像
徐清
用户头像
不爱睡觉不爱起床的cong
用户头像
piabu


王烽
2天前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510;

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

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

    for(int i=0;i<n-1;i++){

        int t=-1;
        for(int j=1;j<=n;j++)
            if((!st[j])&&(t==-1||dist[t]>dist[j]))
                t=j;

        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],dist[t]+g[t][j]);

            st[t]=true;
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    return dist[n];
}
int main(){
    scanf("%d%d",&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);
    }
    printf("%d\n",dijkstra());
    return 0;
}



王烽
2天前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510,M=10010;

struct Edge{
    int a,b,c;
}Edge[M];

int n,m,k;
int dist[N];
int last[N];

void bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++){
        memcpy(last,dist,sizeof dist);
        for(int j=0;j<m;j++){
            auto e=Edge[j];
            dist[e.b]=min(dist[e.b],last[e.a]+e.c);
        }
    }
}
int main(){
     scanf("%d%d%d", &n, &m, &k);

    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        Edge[i] = {a, b, c};
    }

    bellman_ford();

    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n", dist[n]);

    return 0;
}





王烽
2天前
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

const int N=1e6+10;
typedef pair<int,int> PII;

int h[N],w[N],ne[N],e[N],idx;
int n,m;
int dist[N];
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 dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1});
    while(heap.size()){
        auto t=heap.top();
        heap.pop();
        int ver=t.second,distace=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]>dist[ver]+w[i]){
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    return dist[n];
}
int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    cout<<dijkstra()<<endl;
    return 0;
}


活动打卡代码 AcWing 846. 树的重心

王烽
3天前

图和树的存储方式

首先,树一种特殊的图,其次无向图是一种特殊的有向图(无向图要开两个数组)
所以只需要考虑有向图的存储
1、邻接矩阵,即开一个n*n的矩阵,两个下标表示两个点
存储的值表示两个点之间的距离(权)。
2、邻接表。给每个点对应成为数组的下标,数组里存储的(除了一开始的-1)
是与下标对应的链表的空着的地址,注意在插入了一个节点后idx变为了1,而不是2。

对递归函数返回值有什么用的疑问

1、递归函数的返回值可以作为调用

本题中一些变量的作用

1、函数的作用:返回的是以传入参数为根节点时树的节点数
2、由于只要函数能进行就说明有一个节点进来了,他就是我们认为的根节点,
所以节点总数sum置为1
3、res 记录的是当将该节点删除后节点的最大值

深度优先遍历是特殊的深度优先搜索

1、特殊点在于若我只需要遍历一遍树就可以得到我想要的答案
(无论你从什么地方开始遍历),**因为无论你从那个节点开始遍历,答案都是一样的**。
2、因此当你对该函数进行调用时,传入的参数的选择相当宽泛。
3、深度优先遍历无需清理现场,因为每个状态只会被选中一次。早选晚选结果都一样。

为什么会导致深度优先搜索从哪个点都可以遍历整个树呢?

1、树其实是作为有向图用邻接表来存的,这意味着我能知道每个节点所能到达的节点。
2、深度优先搜索相当于是每递归一次就构建一个节点,最后形成的树。
而深度优先遍历是已经给了你一个树。

如何根据输入的数去生成一个树

由于本题说明了节点间是无向边,所以当读入两个点时,就要将a插入b的后面,
b插入a的后面,所以原本只需要与节点数目相同的数组来模拟链表,而现在需要原来的两倍。

本题是怎么想到用深度优先遍历的

1、当你选中一个节点
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

王烽
3天前

为什么BFS可以处理最短路问题

1、当搜索到最后一个节点时,那个到这个节点的路就是最短路
原因:由于每一次都是遍历一层节点,相当于一群人以相同的速度在跑,
谁先结束就说明他走的路是最短路。

如何抽象

将每一次不同的状态看成是一个节点,如果某个状态可以通过变换变成另一种状态的话,
那就用权为1的边将他们连起来。最后转换成求最短路问题。

本题的难点

1、状态的存储。
可以将3维数组压缩成1维,然后将其变成一个字符串。虽然这样方便存储到队列中了,
但是怎么去记录每个状态到现在为止,所走的路的长度呢?
可以用哈希表,实现从字符串到整型的映射,整型就用来表示距离。

2、疑问为什么要存储状态?
因为你必须要依据现有的状态,才能知道下面可能的状态。

3、用什么记录状态?
若仅需要知道最短路的步数,可以用stl里的queue。
**注意但凡用队列存的元素,下标和他存储的值之间不会有任何关系(包括用数组模拟的)**
但是若需要拓扑排序,那么可以直接用数组模拟的queue
(因为模拟的数组在出队时,队首元素并没有真的被删除,而是通过头指针
向后移,失去了再次被头指针指到的可能)

4、状态转移怎么办
你获得的状态就是queue里存储的状态,没错就是string,
你想的可能是找到谁可以和x换,所以你就想找到所有位于x上下左右的数字,
但是仔细想想,我x依次往上下左右走,每一次我都判别一下有没有越界,
没越界我就换(思考问题时,要尽量利用已有的条件)

5、怎么判断有没有走老路?
调用哈希表里的count(),看是否有这个状态。

BFS虽然不像DFS一样需要回溯,但是他依然需要状态数组

1、需要的原因:有可能一个节点在一条路上已经被走过了,
后来又有条路要走这个节点,此时由于前有个路已经走过这个节点,
就算这个节点是最短路的必经之路,你也不可能比前面的那条路快,
所以遍历到每个点时,必须给这个点打上标记,让其他路不经过这个节点。

和走迷宫的比较

1、为什么走迷宫只需要记录个下标就能作为状态,而我需要记录整个数组呢?
为了节省空间,状态肯定是越抽象越好,可是如何判断你这个状态是不是太抽象了呢?
看看最短路有没有可能在你对该状态的理解下走回头路,若有则必须改变这个状态。
2、并不是说BFS就一定没有给自己擦屁股的操作,走迷宫由于你得到的坐标后你也就知道了如果你走了会变成什么状态,
但是八数码则不是,因为你选择的状态要比坐标跟具象,所以需要先交换看状态有没有重复,若重复则换回去。

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 843. n-皇后问题

王烽
3天前

剪枝的两种思路

1、最优解剪枝,我能判断当前情况时最优解
2、可行性剪枝,我能判断当前情况一定不可行。
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 240. 食物链

王烽
4天前

为什么本题可以用并查集做?

1、无论两个动物之间是什么关系,他们都可以进到一个集合中
(因为若一个动物y与多种动物均有关系,则可以依靠y去推出那些与y有关系的动物之间的关系)
所以可以记录每个节点和根节点的关系。
**用与根节点的距离去表示与根节点的关系**

并查集的难点是他的扩展性(即除了在同一个集合外的其他信息该怎么维护)


//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 842. 排列数字

王烽
4天前

DFS问题考虑的关键是顺序

即以什么样的顺序去把所有的方案遍历一遍 

小小的疑惑

你是怎么不会遍历到重复的状态的,明明你每一次都把上一次的状态还原了。
1、外层的for循环其实将你的选项一开始就锁死在了i,而一次迭代后,由于i++了
你不可能再有机会选到上一次同样的状态

DFS整个过程的描述

1、DFS是如何知道那个状态已经选过的?他有一个状态数组,每一次在做决策之前,
他都要遍历状态数组,用if来看若选择这个状态可不可行,不可行的迭代一次,
直到有一次,终于可行了,执行if内的语句,用递归(会记录调用递归时的状态),
递归后函数重新开始,但此时的状态数组已经变了,就这样一次又一次的递归
状态数组全部改变了,你也可以输出结果了,此时终于有个函数结束了,
那就是最后一个开始的函数,
现在你回到了倒数第二个函数,此时倒数第二个函数的状态是for循环已经到了最后一层,
当执行完if后面的场景复原后他便结束了。
此时来到倒数第三个函数,由于倒数第三个函数for比前面多一层,所以它可以再一次发动递归,
当他发动的递归结束后,在他场景复原后,for循环由于i超了,也结束了。


总结:最后其实状态数组和最初是完全一样的,是循环次数的限制导致了递归的中止,而不是状态数组。
for循环的终止,意味着这个函数以及其递归产生的函数,
已经遍历完了所有的所有的可能,刚好此时这个函数结束。

容易理解错误的点

除了最后一层的递归函数及其上面的函数,每个函数都会**多次的**调用递归函数,
但是由于递归函数在for的中层循环体,除第一次以外每次想要调用递归函数前,
都经历了把自己之前所作的选择撤销,随后由于i++,你再也不会选到你刚刚撤销所在的状态,
就这样你把所有你可能的状态都选了一遍,此时for循环也就中止了。

失而复得的东西

总结:最后其实状态数组和最初是完全一样的,是循环次数的限制导致了递归的中止,而不是状态数组。
for循环的终止,意味着这个函数以及其递归产生的函数,已经遍历完了所有的所有的可能,
刚好此时这个函数结束,由调用这个函数的人来给他擦屁股。
每个函数在生命的末期,即在for循环最后一次执行到中间循环体时,他依然会再一次发动递归函数
此时的递归函数由于之前调用它的函数已经把所有情况都走了一遍了,所以状态数组里所有的数也都变了
但他不接受,所以它用for一个一个的遍历整个状态数组,每一次进到中间循环体去判别,终于他信了,
for循环的中止也意味着他死了。最后一个被递归调用的函数没有任何选择,他只能输出结果
然后死亡。此时再次回到调用他的函数身上,他发觉这么选不行,但留给他的选择只有这一个,
他抹除了自己的选择的同时也死了,回到上级,上级发现之前的后想,这样不行那我也抹除我的选择
因为是我的选择导致了他的死亡,所以上级for迭代一次,选到了上次他没选到的情况。

除了最后两层的节点所对应的函数,其余函数可以多次发动递归(即回溯不是一下子回到头上),
且当第二次发动递归时,由于上一次递归的结束,中间循环体递归调用的后半部的还原现场发动
随后再次for循环时,由于i++,所以不能选之前已经选过的状态,实现了一个完美的回溯在调用。
由于每一次递归前都会经过for循环,即for循环i++保证了一个函数不会以相同的状态去递归调用下一个函数,
且他能从头到尾找到第一个空着的状态,如果有一个状态复原了,那么还能保证不会再去选那个复原的状态。
i<n保证了我不能选择超出情况的状态


并不能把所有的for循环都在思维层面是理解为是在遍历数组

本题for循环是为了遍历找到没有被选中的状态

DFS中形参作为层数的重要性

你觉得for循环,以及状态函数的判别,已经将一个函数可以调用递归函数的个数锁死了,层数也固定了,为什么还需要有
一个专门的变量去表示遍历的层数呢?因为本题需要输出所有的可能性,你可能会想那我在for的后面加个输出不就行了?
但是此时一个答案会被输出多次,因为按原本的排布,由于语句是顺序执行的,一旦一开始判别了这个函数由于层数不够
不配输出,那后来即使他for循环结束,他依然不配输出。
但按照你的想法改了之后,无论是不是最后一层,只要for循环结束就输出,这显然是错误的。

C++代码

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~#include<iostream>

using namespace std;

const int N=10;

int n,path[N];
bool st[N]; //由于这里st的下标表示这个数有没有被选中,而数字是从1开始的
            //所以后面for循环从i=1,开始。

void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++)cout<<path[i]<<' ';
        puts("");
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){
            path[u]=i;
            st[i]=true;
            dfs(u+1);
            st[i]=false;
        }
    }
}

    int main(){
        cin>>n;
        dfs(0);
        return 0;
    }



活动打卡代码 AcWing 841. 字符串哈希

王烽
4天前

字符串前缀哈希法的思路

1、将每一个字符对应一个哈希值(不能将字符映射成0)
(可以直接用ASCALL,即直接把字符当成数字和数字加写在一个表达式里)
2、将字符串看成是一个p进制的数字(一般选取131,1331)
3、为了保证字符串哈希后的值不太大,对字符串转数字后取余
(一般选取“2的64次方”,采用unsign long long,若溢出就相当于取余)
4、不考虑冲突

字符串前缀哈希法的用处

你现在可以求得任意一段字符的哈希值了。

如何求任意一段字符的哈希值(哈希值相同意味着字符串相同)

1、字符减去之后,位数减小了,所以应该先把减的数提高到与被减数相同的位数,再相减
2、如何在不改变,原来所有位上的数字的前提下,去提高位数呢?乘以它的进制!

构造前缀数组

与上面理由相同,从前向后每增加一位,就需要将原来的数字乘以他的进制。
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



活动打卡代码 AcWing 143. 最大异或对

王烽
4天前

本题也是从暴力双指针开始优化的

小总结:优化的思路总是减少第二个指针的操作次数。
1、给你一个数,现在让你找一个和他异或最大的,
此时你想对异或后影响最大的是什么?是最高位与其异或产生的结果。
此时你将状态减少了一半,随后你对他的下一位重复以上操作。
就这样你每一次都将状态减少了二分之一。
2、此时想你的优化思路,所进行的操作与什么数据结构相匹配
没错,就是trie树。

本题的小技巧

1、由于异或是满足交换律的,所以采用边查边比的方式,避免了a^b后b^a情况的发生。
#include<iostream>
#include<algorithm>

using namespace std;

const int N=100010,M=3100010;

int n;
int a[N],son[M][2],idx;

void insert(int x){
    int p=0;
    for(int i=30;i>=0;i--){
        int &s=son[p][x>>i&1];
        if(!s)s=++idx;
        p=s;
    }
}

int search(int x){
    int p=0,res=0;
    for(int i=30;i>=0;i--){
        int s=x>>i&1;
        if(son[p][!s]){
            res+=1<<i;
            p=son[p][!s];
        }
        else p=son[p][s];
    }
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);

    int res=0;
    for(int i=0;i<n;i++){
        insert(a[i]);
        res=max(res,search(a[i]));
    }
    printf("%d",res);
    return 0;
}