头像

Kue


访客:2212

离线:7小时前


活动打卡代码 AcWing 787. 归并排序

Kue
8天前
//这里填你的代码^^
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;
int  q[N], temp[N], a[N];

void merge_sort(int l, int r)
{
    // 当只有一个节点或没有节点
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j]) temp[k ++] = q[i++];
        else temp[k ++] = q[j ++];
    }
    while(i <= mid) temp[k++] = q[i++];
    while(j <= r) temp[k++] = q[j++];
    // 这一段代码比较关键,将排好序的temp,赋值给q
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = temp[j];
}
int main()
{
    int m;
    cin >> m;
    for(int i = 0; i < m; i++) cin >> q[i];

    merge_sort(0, m - 1);

    for(int i = 0; i < m; i++) printf("%d ", q[i]);
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Kue
12天前

对0 1 2进行 排序

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;
int q[N];

void quick_sort(int q[], int l, int r)
{
    int red = 0, white = 0, blue = r;
    while (l <= r) // 一定要加上等于号
    {
        if (q[l] == 0)
        {
            swap(q[l], q[red++]);
            l++;
        }else if (q[l] == 1)
        {
            l++;
        }else if (q[l] == 2)
        {
            swap(q[l], q[blue--]);
            r--;
        }

    }

}
int main()
{
    int m;
    scanf("%d", &m);
    for(int i = 0; i < m; i++) scanf("%d", &q[i]);

    quick_sort(q, 0, m - 1);
    for(int i = 0; i < m; i++) printf("%d ", q[i]);
    return 0;
}


问题 快速排序

Kue
12天前

题目链接 https://www.acwing.com/problem/content/description/787/

为啥快排要用do i ++ ,再while
不能直接用 while??

错误的代码:

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int x = q[l + r >> 1], i = l, j = r;
    while (i < j)
    {
    // 小数据量还行, 大数据量就会错误了
        while (q[i] < x) i++;
        while (q[j] > x) j--;
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);

}
int

编译器报了什么错误?Compile Error? Runtime Error?



分享 双向冒泡

Kue
12天前

通过两个指针, 来加快一趟冒泡(本质多加了个循环,两个指针)

#include <iostream>
#include <cstring>

using namespace std;
const int N = 100100;
int q[N];
void bubble_sort(int q[], int m)
{
    int low = 0, high = m - 1;
    for(int i = 0; i < m; i++)
    {
        bool flag = false;
        for(int j = low; j < m - 1; j++)
        {

            if (q[j] > q[j + 1]) swap(q[j], q[j + 1]), flag = true;
        }
        high--;
        for(int j = high; j >= 1; j--)
        {
            if (q[j - 1] > q[j]) swap(q[j - 1], q[j]), flag = true;
        }
        low++;
        if (!flag) return;
    }
}
int main()
{
    int m;
    scanf("%d", &m);
    for(int i = 0; i < m; i++) scanf("%d", &q[i]);
    bubble_sort(q, m);
    for(int i = 0; i < m; i++) printf("%d ", q[i]);
}


分享 冒泡排序

Kue
12天前

冒泡排序对于数据量大,效率还是不如快速排序

#include <iostream>
#include <cstring>

using namespace std;
const int N = 100100;
int q[N];
void bubble_sort(int q[], int m)
{
    for(int i = 0; i < m; i++)
    {
        bool flag = false;
        for(int j = 0; j < m - 1; j++)
        {

            if (q[j] > q[j + 1]) swap(q[j], q[j + 1]), flag = true;
        }
        if (!flag) return;
    }
}
int main()
{
    int m;
    scanf("%d", &m);
    for(int i = 0; i < m; i++) scanf("%d", &q[i]);
    bubble_sort(q, m);
    for(int i = 0; i < m; i++) printf("%d ", q[i]);
}


活动打卡代码 AcWing 785. 快速排序

Kue
12天前
//这里填你的代码^^
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    // x = q[l] 会超时.....
    int x = q[l + r >> 1], i = l - 1, j = r + 1;
    while (i < j)
    {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);

}
int main()
{
    int m;
    scanf("%d", &m);
    for(int i = 0; i < m; i++) scanf("%d", &q[i]);

    quick_sort(q, 0, m - 1);
    for(int i = 0; i < m; i++) printf("%d ", q[i]);
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 1538. 链表排序

Kue
16天前
//这里填你的代码^^
#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

const int N = 100010;
int q[N], w[N];
unordered_map<int, int> pos;
int main()
{
    int m , s;
    cin >> m >> s;
    vector<int> res;
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> c >> b;
        q[a] = b;
        pos[c] = a;
        w[a] = c;
        //res.push_back(c);
    }
    int cnt = 0;
    for(int i = s; i != -1; i = q[i])
    {
        cnt++;
        res.push_back(w[i]);
    }
    sort(res.begin(), res.end());
    if (!cnt) printf("%d %d", cnt, s);
    else printf("%d %05d\n", cnt, pos[res[0]]);

    for(int i = 0; i < res.size(); i++)
    {
        int x = res[i];
        printf("%05d %d ", pos[x], x);
        if (i != res.size() - 1) printf("%05d\n", pos[res[i + 1]]);
        else printf("-1\n");
    }
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 1640. 堆

Kue
16天前
//这里填你的代码^^
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int N = 1010;
int h[N];
int m, n;
bool max_h , min_h;
vector<int> res;
void post_order(int u)
{
    bool f1 = false, f2 = false;
    if (u * 2 <= n) post_order(u * 2), f1 = true;
    if (u * 2 + 1 <= n) post_order(u * 2 + 1), f2 = true;
    if (f1)
    {
        if (h[u] > h[u * 2]) max_h = true;
        else if (h[u] < h[u * 2]) min_h = true;
    }
    if (f2)
    {
        if (h[u] >= h[u * 2 + 1]) max_h = true;
        else if (h[u] < h[u * 2 + 1]) min_h = true;
    }
    res.push_back(h[u]);
}
int main()
{
    cin >> m >> n;
    while (m --)
    {
        res.clear();
        max_h = false, min_h = false;
        bool flag = true;
        for(int i = 1; i <= n; i++) cin >> h[i];
        post_order(1);
        if (max_h && min_h) puts("Not Heap");
        else if (max_h) puts("Max Heap");
        else if (min_h) puts("Min Heap");
        for(int i = 0; i < res.size(); i++)
        {
            if (flag) flag = false;
            else printf(" ");
            printf("%d", res[i]);
        }
        printf("\n");
    }
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Kue
17天前

类似图的顶点覆盖

A safari park(野生动物园)has K species of animals, and is divided into N regions. The managers hope to spread the animals to all the regions, but not the same animals in the two neighboring regions. Of course, they also realize that this is an NP complete problem, you are not expected to solve it. Instead, they have designed several distribution plans. Your job is to write a program to help them tell if a plan is feasible.

Input Specification:
Each input file contains one test case. For each case, the first line gives 3 integers: N (0<N≤500), the number of regions; R (≥0), the number of neighboring relations, and K (0<K≤N), the number of species of animals. The regions and the species are both indexed from 1 to N.

Then R lines follow, each gives the indices of a pair of neighboring regions, separated by a space.

Finally there is a positive M (≤20) followed by M lines of distribution plans. Each plan gives N indices of species in a line (the i-th index is the animal in the i-th rigion), separated by spaces. It is guaranteed that any pair of neighboring regions must be different, and there is no duplicated neighboring relations.

Output Specification:
For each plan, print in a line Yes if no animals in the two neighboring regions are the same, or No otherwise. However, if the number of species given in a plan is not K, you must print Error: Too many species. or Error: Too few species. according to the case.

Input:
6 8 3
2 1
1 3
4 6
2 5
2 4
5 4
5 6
3 6
5
1 2 3 3 1 2
1 2 3 4 5 6
4 5 6 6 4 5
2 3 4 2 3 4
2 2 2 2 2 2
OutPut:
Yes
Error: Too many species.
Yes
No
Error: Too few species.

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

const int N = 510;
int a[N], b[N];

int main()
{
    int m, n, k, q;
    cin >> m >> n >> k;
    for(int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        a[i] = x, b[i] = y;
    }
    cin >> q;
    while (q --)
    {
        unordered_set<int> hset;
        vector<int> res(m + 1);
        for(int i = 1; i <= m; i++)
        {
            cin >> res[i];
            hset.insert(res[i]);
        }
        if (hset.size() < k) puts("Error: Too few species.");
        else if (hset.size() > k) puts("Error: Too many species.");
        else{
            bool flag = true;
            for(int i = 0; i < n; i++)
            {
                int x = a[i], y = b[i];
                if (res[x] == res[y])
                {
                    flag = false;
                    break;
                }
            }
            if (flag) puts("Yes");
            else puts("No");
        }
    }
}



Kue
17天前
//这里填你的代码^^
#include <iostream>
#include <cstring>

using namespace std;

const int N = 510;
int g[N][N], d[N];
bool visit[N];
int m, n;
void dijkstra(int s)
{
    d[s] = 0;
    for(int i = 1; i <= n; i++)
    {
        int u = -1;
        for(int j = 1; j <= n; j++)
        {
            // 找最短边
            if (!visit[j] && (u == -1 || d[j] < d[u]))
            {
                u = j;
            }
        }
        if (u == -1) return;
        visit[u] = true;
        for(int j = 1; j <= n; j++)
        {
            if (d[j] > d[u] + g[u][j])
            {
                d[j] = d[u] + g[u][j];
            }
        }
    }
}
int main()
{
    memset(g, 0x3f, sizeof g);
    memset(d, 0x3f, sizeof d);
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        // 有重边, 且是有向图
        g[a][b] = min(c, g[a][b]);
    }
    dijkstra(1);
    if (d[n] != g[1][n]) printf("%d", d[n]);
    else printf("-1");

}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~