头像

SpongeBob


访客:603

离线:3天前



#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]; //True表示已经确定最短路

int dijkstra() {
    //所有节点距离起点的距离初始化为无穷大
    memset(dist, 0x3f, sizeof dist);
    //起点距离自己的距离为零
    dist[1] = 0;

    //迭代n次,每次可以确定一个点到起点的最短路
    for (int i = 0; i < n; ++i) {
        int t = -1;
        //遍历没有确定最短路的点,并且找到其中距离最小的点
        for (int j = 1; j <= n; ++j) {
            if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }

        st[t] = true;

        //找到了距离最小的点t,并用最小的点t去更新其他的点到起点的距离
        for (int j = 1; j <= n; ++j) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }

    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    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); //如果有重边,请保留权值最小的一条边
    }

    cout << dijkstra() << endl;

    return 0;
}




#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+10;

int n,m; //m个节点n条边
int h[N], e[N], ne[N], idx;
int q[N];//队列存储层次遍历序列
int d[N];//存储i号节点的入度

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

//返回布尔序列是否存在, 若存在,则存储在q数组中
bool topsort()
{
    int hh=0,tt=-1;

    for (int i = 1; i <= n; ++i) {
        //遍历每一个节点, 入度为零则入队
        if(!d[i])
            q[++tt]=i;
    }

    while(hh<=tt)
    {
        //队列不空,则取出头节点
        int t=q[hh++];
        //遍历头节点的每一个出边
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            //出边能到达的节点,入度减1
            //如果结点j,入度为0则入队
            if(--d[j]==0)
                q[++tt]=j;
        }
    }

    return tt==n-1;
}

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

    memset(h,-1,sizeof h);

    for (int i = 0; i < m; ++i) {
        int a, b;
        cin>>a>>b;
        add(a,b);
        //b节点入度加1
        d[b]++;
    }

    if(topsort()){
        for (int i = 0; i < n; ++i) {
            cout << q[i] << ' ';
        }
        puts("");
    }else {
        puts("-1");
    }
}



2.JPG

#include <cstring>
#include <iostream>

using namespace std;

const int N=1e5+10;

int h[N], e[N], idx, ne[N];
int d[N]; //存储每个节点离起点的距离  d[1]=0
int n, m; //n个节点m条边
int q[N]; //存储层次遍历序列 0号节点是编号为1的节点

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

int bfs()
{
    int hh=0,tt=0;

    q[0]=1; //0号节点是编号为1的节点

    memset(d,-1,sizeof d);

    d[1]=0; //存储每个节点离起点的距离

    //当我们的队列不为空时
    while(hh<=tt)
    {
        //取出队列头部节点
        int t=q[hh++];

        //遍历t节点的每一个邻边
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            //如果j没有被扩展过
            if(d[j]==-1)
            {
                d[j]=d[t]+1; //d[j]存储j节点离起点的距离,并标记为访问过
                q[++tt] = j; //把j结点 压入队列
            }
        }
    }

    return d[n];
}

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

    cout<<bfs()<<endl;
}





1.png

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10; //数据范围是10的5次方
const int M = 2 * N; //以有向图的格式存储无向图,所以每个节点至多对应2n-2条边

int h[N]; //邻接表存储树,有n个节点,所以需要n个队列头节点
int e[M]; //存储元素
int ne[M]; //存储列表的next值
int idx; //单链表指针
int n; //题目所给的输入,n个节点
int ans = N; //表示重心的所有的子树中,最大的子树的结点数目

bool st[N]; //记录节点是否被访问过,访问过则标记为true

//a所对应的邻接表中插入b
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

//返回以u为根的子树中节点的个数,包括u节点
int dfs(int u) {
    int res = 0; //存储 删掉某个节点之后,最大的连通子图节点数
    st[u] = true; //标记访问过u节点
    int sum = 1; //存储,以u为根的树 的节点数, 包括u

    //访问u的每个子节点
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        //因为每个节点的编号都是不一样的,所以 用编号为下标 来标记是否被访问过
        if (!st[j]) {
            int s = dfs(j);  // u节点的单棵子树节点数
            res = max(res, s); // 记录最大联通子图的节点数
            sum += s; //以j为根的树 的节点数
        }
    }

    res = max(res, n - sum); // 以 j的父亲节点为根 的树 的节点数
    ans = min(res, ans); //最小的最大联通子图
    return sum;
}

int main() {
    memset(h, -1, sizeof h); //初始化h数组 -1表示空
    cin >> n; //表示树的结点数

    // 题目接下来会输入,n-1行数据
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a); //无向图
    }

    dfs(1); //可以任意选定一个节点开始 u<=n

    cout << ans << endl;

    return 0;
}





SpongeBob
27天前

b-search.png
b-search-1.png




SpongeBob
27天前

merge_sort_pair.PNG




SpongeBob
27天前

快速排序算法:
分界点选的是带排序数组中的一个值,这里选的是中值

int x = q[(l + r) >> 1]

归并排序算法:
分界点选的是带排序数组中的一个位置,这里是中间位置

int mid = l + r >> 1



SpongeBob
27天前

merge_sort.PNG




SpongeBob
2个月前

正确代码 注释处为修改代码 请问哪里的逻辑出了问题呢?

#include <iostream>

using namespace std;
const int N = 1e5 + 10;
int n,k;
int q[N];

int quick_sort(int l,int r,int  k)
{
    if(l>=r) return q[l];
    int x=q[(l+r)>>1],i=l-1,j=r+1; //int mid =l+r >> 1,i=l-1,j=r+1;
    while(i<j)
    {
        do i++; while (q[i] < x); //do i++; while (q[i] < q[mid]);
        do j--; while (x < q[j]); //do j--; while (q[mid] < q[j]);
        if( i<j) swap(q[i], q[j]);
    }
    int sl=j-l+1;
    if(k<=sl) quick_sort(l, j, k);
    else quick_sort(j + 1, r, k - sl);
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &q[i]);
    }
    cout<<quick_sort(0, n - 1, k);
}

修改代码

#include <iostream>

using namespace std;
const int N = 1e5 + 10;
int n,k;
int q[N];

int quick_sort(int l,int r,int  k)
{
    if(l>=r) return q[l];
    int mid =l+r >> 1,i=l-1,j=r+1;
    while(i<j)
    {
        do i++; while (q[i] < q[mid]);
        do j--; while (q[mid] < q[j]);
        if( i<j) swap(q[i], q[j]);
    }
    int sl=j-l+1;
    if(k<=sl) quick_sort(l, j, k);
    else quick_sort(j + 1, r, k - sl);
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &q[i]);
    }
    cout<<quick_sort(0, n - 1, k);
}



SpongeBob
2个月前
#include<iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
//    n=576;
    int p[] = {100, 50, 20, 10, 5, 2, 1};
    cout<<n<<endl;
    for(int i=0; i<7;i++){
        printf("%d nota(s) de R$ %d,00\n", n/p[i], p[i]);
        n%=p[i];
    }
}