Acwing枚举、模拟与排序（一）

WuShF

发布于 2024-03-03 08:52:39

1120

发布于 2024-03-03 08:52:39

文章被收录于专栏：笔记分享

连号区间数

原题链接：https://www.acwing.com/problem/content/1212/

初始最小值和最大值的依据是题目给出的数据范围。只要在数据范围之外就可以。连号的时候，相邻元素元素之间，差值为1。那么区间右边界和左边界，的值的差，就应该等于下标索引的差值。

#include"bits/stdc++.h"

using namespace std;
int P[10010];
int N;

int main() {
    cin >> N;
    for (int i = 0; i < N; i++)cin >> P[i];
    int res = 0;
    for (int i = 0; i < N; i++) {
        int minn = 10010;
        int maxx = 0;
        for (int j = i; j < N; j++) {
            minn = min(minn, P[j]);
            maxx = max(maxx, P[j]);
            if (maxx - minn == j - i)res++;
        }
    }
    cout << res;
    return 0;
}

递增三元组

原题链接：https://www.acwing.com/problem/content/1238/

如果选择暴力，那么复杂度是三次方。数据范围是1e5，这时间复杂度是不被允许的。（暴力杯或许可以）时间复杂度应控制到

n\log n

，意味着最多只能枚举一个数组。枚举A或C是等价的，都是在两边。以A为例，枚举A的时候，在考虑B和C的时候，B和C都不是完全独立的，B和C之间有相互限制。统计数量的时候不能用简单的乘法相乘。如果选择枚举B，那么A和C之间是相互独立的。 A的判断条件就是小于B，C的判断条件就是大于B。当前B的取值的合法三元组的数量，就是合法的A的数量乘合法的C的数量。那么现在的问题就是求合法的A和合法的C的数量。

前缀和

需要两个数组：

cnt[i]：表示在A中i这个值出现多少次
S[i]：表示在A中[0,i]出现多少次

求A中多少个数小于Bi，就是求S[Bi-1]的值。求C中多少个数大于Bi，就是求S[N-Bi]的值，N为数据范围的最大值。前缀和的时间复杂度为n。

#include"bits/stdc++.h"

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int as[N], cs[N];
int cnt[N], s[N];
int n;

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

    for (int i = 0; i < n; i++) cnt[a[i]]++;
    for (int i = 1; i < N; i++)s[i] = s[i - 1] + cnt[i];
    for (int i = 0; i < n; i++)as[i] = s[b[i] - 1];
    memset(cnt, 0, sizeof cnt);
    memset(s, 0, sizeof s);
    for (int i = 0; i < n; i++) cnt[c[i]]++;
    for (int i = 1; i < N; i++)s[i] = s[i - 1] + cnt[i];
    for (int i = 0; i < n; i++)cs[i] = s[N - 1] - s[b[i]];

    LL res = 0;
    for (int i = 0; i < n; i++) res += (LL) as[i] * cs[i];
    cout << res << endl;
    return 0;
}

特别数的和

原题链接：https://www.acwing.com/problem/content/1247/

一道简单模拟，for循环的范围参考题目给的数据范围。

#include"bits/stdc++.h"

using namespace std;

int n, res;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x = i;
        while (x) {
            int t = x % 10;
            x /= 10;
            if (t == 2 || t == 0 || t == 1 || t == 9) {
                res += i;
                break;
            }
        }
    }
    cout << res << endl;
    return 0;
}

错误票据

原题链接：https://www.acwing.com/problem/content/1206/

排序

#include"bits/stdc++.h"

using namespace std;
int n;
int a[100010];

int main() {
    int cnt;
    cin >> cnt;
    string line;
    getline(cin, line);
    while (cnt--) {
        getline(cin, line);
        stringstream ssin(line);
        while (ssin >> a[n++]);
    }
    sort(a, a + n);
    int res1, res2;
    for (int i = 1; i < n; i++) {
        if (a[i] == a[i - 1])res2 = a[i];
        else if (a[i] >= a[i - 1] + 2)res1 = a[i] - 1;
    }
    printf("%d %d", res1, res2);
    return 0;
}

忽略行数读入

#include"bits/stdc++.h"

using namespace std;
int n;
int a[100010];

int main() {
    int cnt;
    cin >> cnt;
    int maxx=0,minn=1e5;
    while(cin>>n){
        a[n]++;
        maxx=max(maxx,n);
        minn=min(minn,n);
    }
    int res1,res2;
    for(int i=minn;i<=maxx;i++){
        if(a[i]==0)res1=i;
        else if(a[i]==2)res2=i;
    }
    printf("%d %d",res1,res2);
    return 0;
}

归并排序

原题链接：https://www.acwing.com/problem/content/789/

#include"bits/stdc++.h"

using namespace std;
int n;
int q[100010], tmp[100010];

void merge_sort(int q[], int l, int r) {
    if (l >= r)return;
    int mid = l + r >> 1;
    merge_sort(q, 1, 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++];
    for (i = l, j = 0; i <= r; i++, j++)q[i] = tmp[i];
}


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;
}