头像

aventador


访客:666

离线:2个月前



aventador
2个月前

C++ 代码

注意区间

# include <iostream>
using namespace std;
const int N = 1e4;
int main()
{
    double x;
    cin >> x;
    double l = -N, r = N;
    while(r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%lf", l);
    return 0;
}



aventador
2个月前

C++ 代码

利用快速排序算法的模板

  1. 首先将原始的数组读取进来,记为q[]
  2. 然后分别将q[]数组的奇数和偶数对应的下标记录下来,存在新的数组里面e[]和o[]
  3. 然后分别对q[]的e[]下标以及o[]下标进行排序
  4. 输出
# include <iostream>
using namespace std;
const int N = 1010;
int n, m, q[N], o[N], e[N];

void quick_sort_up(int q[], int o[], int l, int r)
{
    if (l >= r) return;
    int x = q[o[l + r >> 1]], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i ++; while (q[o[i]] < x);
        do j --; while (q[o[j]] > x);
        if(i < j) swap(q[o[i]], q[o[j]]);
    }
    quick_sort_up(q, o, l, j), quick_sort_up(q, o, j + 1, r);
}

void quick_sort_down(int q[], int e[], int l, int r)
{
    if (l >= r) return;
    int x = q[e[l + r >> 1]], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i ++; while (q[e[i]] > x);
        do j --; while (q[e[j]] < x);
        if(i < j) swap(q[e[i]], q[e[j]]);
    }
    quick_sort_down(q, e, l, j), quick_sort_down(q, e, j + 1, r);
}

int main()
{
    scanf("%d", &m);
    for (int k = 0; k < m; k ++)
    {
        scanf("%d", &n);
        // 分别作为奇数和偶数的idx
        int idxo = 0, idxe = 0;

        for (int i = 0; i < n; i ++ )  
        {
            scanf("%d", &q[i]);
            // 记录奇数和偶数对应的下标
            if(q[i] % 2 == 0) e[ idxe++] = i;
            else o[ idxo++] = i;
        }
        // 快速排序
        quick_sort_up(q, o, 0, idxo - 1);
        quick_sort_down(q, e, 0, idxe - 1);

        printf("Case #%d: ", k + 1);
        for (int i = 0; i < n; i ++) printf("%d ", q[i]);
        puts("");
    }
    return 0;
}



aventador
2个月前

与快排做法相同

# include <iostream>
using namespace std;
const int N = 1e3 + 10;
int n, l, r, a[N];
void sort (int a[], int l, int r)
{
    if(l >= r) return;
    int x = a[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i ++; while(a[i] < x);
        do j --; while(a[j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    sort(a, l, j), sort(a, j + 1, r);
}
int main()
{
    scanf("%d%d%d", &n, &l, &r);
    for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
    sort(a, l, r);
    for (int i = 0; i < n; i ++) printf("%d ", a[i]);

}



aventador
2个月前

标准做法

# include <iostream>
using namespace std;
const int N = 1e5 + 10;
int m, n, x, q[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
    while ( m-- )
    {
        scanf("%d", &x);

        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (q[l] != x) printf("-1 -1\n");
        else
        {
            printf("%d ", l);
            // while (q[l + 1] == x) l ++;
            int l = 0, r = n - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }

            printf("%d\n", l);
        }
    }
    return 0;

}

投机取巧

# include <iostream>
using namespace std;
const int N = 1e5 + 10;
int m, n, x, q[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
    while ( m-- )
    {
        scanf("%d", &x);

        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (q[l] != x) printf("-1 -1\n");
        else
        {
            printf("%d ", l);
            while (q[l + 1] == x) l ++;
            printf("%d\n", l);
        }
    }
    return 0;

}



aventador
2个月前

算法1

(max函数)

C++ 代码

# include <iostream>
using namespace std;
int main()
{
    int a, b, c, x, y, z;
    scanf("%d%d%d", &a, &b, &c);
    x = min(a, min(b, c)), z = max(a, max(b, c)), y = a + b + c - x - z;
    printf("%d\n%d\n%d\n\n%d\n%d\n%d", x, y, z, a, b, c);
}



aventador
2个月前

C++ 代码

# include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N], tmp[N], n;
void merge_sort(int q[], int l, int r)
{
    // 递归出口
    if(l >= r) return;
    // 取中间值
    int mid = l + r >> 1;
    // 递归过程
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    // 归并过程
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++] = q[i ++];
        else tmp[k ++] = q[j ++];
    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];
    // 复制过程
    for (i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
    merge_sort(q, 0, n - 1);
    for (int i = 0; i < n; i ++) printf("%d ", q[i]);
    return 0;
}



aventador
2个月前

C++ 代码

注意死循环

当长度为2的时候,容易陷入死循环,因此递归的时候注意j j+1还是 i-1 i

注意x的取值

为了减少复杂度 x = q[(l + r) / 2]

# include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N];
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int x = q[(l + r) / 2], 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 n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i ++) printf("%d ", q[i]);
    return 0;
}

STL

# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n;
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    sort(a, a + n);
    for(int i = 0; i < n; i ++) cout << a[i] << " ";
    cout << endl;
    return 0;
}



aventador
3个月前

C++ 代码

例如:
S = “abababc”
P = “abababab”
p的next数组为:ne = [0,0,1,2,3,4,5,6]
1. next数组的意义:p字符串的每一个位置对应的最小回退长度
2. 回退一步的意义:返回到最长的前面部分已经匹配的长度对应的下标
3. 求next数组方法与kmp匹配方法类似

# include <iostream>
using namespace std;
const int N = 10010, M = 100010;
int n, m;
char s[M], p[N];
int ne[N];
int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
    //求next的过程
    for (int i = 2, j = 0; i <= n; i ++)
    {
        while (j && p[i] != p[j + 1]) j = ne[i];
        if (p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }
    //KMP匹配过程
    for (int i = 1, j = 0; i <= m; i ++)
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p [j + 1]) j ++;
        if (j == n) // 匹配成功
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}



aventador
3个月前

C++ 代码

  1. 构造单调队列解决,数据从队尾进入,从队头输出,队列存的是原始数据的下标
  2. 每次输出最小值的时候,从队首到队尾是单调递增的
  3. 当队列非空且队列头滑出窗口外了则需要hh++
  4. 当队列非空且队尾元素<=(>=)当前数据,tt–
  5. 数据入队
  6. 输出
# include <iostream>
using namespace std;
const int N = 1000010;

int a[N], q[N];

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i ++)
    {
        if (hh <= tt && i - k + 1 > q[hh]) hh ++;
        while (hh <= tt && a[i] <= a[q[tt]]) tt --;
        q[ ++tt] = i;
        if (i >= k - 1 ) printf("%d ", a[q[hh]]);
    }
    puts("");

    hh = 0, tt = -1;
    for (int i = 0; i < n; i ++)
    {
        if (hh <= tt && i - k + 1 > q[hh]) hh ++;
        while (hh <= tt && a[i] >= a[q[tt]]) tt --;
        q[ ++tt] = i;
        if (i >= k - 1 ) printf("%d ", a[q[hh]]);
    }
    puts("");
    return 0;


}



aventador
3个月前

C++ 代码

利用单调栈的思想求解
1. 构造一个单调递增的栈
2. 比较栈顶元素与即将入栈元素的大小
3. 如果即将入栈的元素小于栈顶元素则栈顶指针tt–,直到为空栈或者都比该元素小
4. 非空则输出栈顶元素,否则输出-1
5. 入栈

# include<iostream> 
using namespace std;
const int N = 100010;

int stk[N], tt;

int main()
{
    int m, x;
    scanf("%d", &m);
    for (int i = 0; i < m; i ++)
    {
        scanf("%d", &x);
        while(tt && x <= stk[tt]) tt--;
        if(tt) printf("%d ", stk[tt]);
        else printf("-1 ");
        stk[ ++tt] = x;
    }
}