9,5复盘

T1缺少的数

原题链接：4416. 缺少的数 - AcWing题库

解题思路

布尔数组记录有哪些数就行了

源代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;

bool st[N];
int n;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i < n; i ++)
    {
        int a;
        scanf("%d", &a);
        st[a] = true;
    }

    for(int i = 1; i <= n; i ++)
    {
        if(!st[i])
        {
            printf("%d", i);
            break;
        }
    }

    return 0;
} 

T2选区间

原题链接：4417. 选区间 - AcWing题库

解题思路

找距离最远的两个区间我们只需要找l最靠右，r最靠左的两个区间就行了

但是我们不知道两组中那组靠前那组靠后的最大距离最大，所以我们都要试一遍

我们先求出两组中l的最大值，r的最小值，又另外一组作差（l-r）

如果是负数说明有交集，就把值改为0

最后取最大值输出

源代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>

#define l first;
#define r second;

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int n, m;
PII a[N], b[N];
int mxl1, mxl2, mnr1 = 1e9 + 10, mnr2 = 1e9 + 10;
int ans;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        a[i] = {x, y};
        mxl1 = max(mxl1, x);//找最大值和最小值
        mnr1 = min(mnr1, y);
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; i ++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        b[i] = {x, y};
        mxl2 = max(mxl2, x);//找最大值和最小值
        mnr2 = min(mnr2, y);
    }

    int d1 = mxl2 - mnr1;//作差求距离
    int d2 = mxl1 - mnr2;
    if(d1 < 0)d1 = 0;//看看有没有交集，有交集距离就是0
    if(d2 < 0)d2 = 0;
    ans = max(d1, d2);
    printf("%d", ans);

    return 0;
} 

T3选元素

解题思路

这道题可以用dp

状态表示：f[i][j]表示选在前i个里面选j个，必定选第i个的最大元素和

属性：max

状态转移：f[i][j] = max(f[i][j], f[t][j-1] + a[i])（t = i-k~i-1）

[i][j]表示选在前i个里面选j个，必定选第i个的最大元素和，可以由选j个，最后一个选i的前k个数作为最后一个数的元素选法转移过来，因超过k个连续的数里面选的数就是不能用的选法

源代码

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

using namespace std;

const int N = 210;

long long a[N];
long long f[N][N];//f[i][j]表示选在前i个里面选j个，必定选第i个的最大元素和
long long n, k, x;
long long ans;

int main()
{
    scanf("%lld%lld%lld", &n, &k, &x);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%lld", &a[i]);
    }

    memset(f, -0x3f, sizeof(f));//初始化，刚开始没有方案就是-INF
    f[0][0] = 0;//basecase
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= x; j ++)
        {
            for(int t = max((long long)0, i - k); t < i; t ++)//要保证每个长度为k的连续子序列有一个选的元素所以只能选前k个，要不然就有连续子序列没有选的元素
            {
                f[i][j] = max(f[i][j], f[t][j - 1] + a[i]);
            }
        }
    }
    ans = -1;//如果后面的东西都没有可行方案都是-INF，就输出-1
    for(int i = n - k + 1; i <= n; i ++)//最后的选的一点必须在后k个，因为要不然后面的连续子序列没有被选的元素
    {
        ans = max(ans, f[i][x]);
    }

    printf("%lld", ans);

    return 0;
}

T4K倍区间

原题链接：1230. K倍区间 - AcWing题库

解题思路

我们先求前缀和，我们可以利用两个前缀和的差表示一个区间的和，所以如果两个前缀和%k，都相等，那么它们的差/k的余数就被消掉了，所以我们可以用一个数组计算前缀和数组的余数。然后把每个余数求选两个的方案数，最后求和

源代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;

int a[N];
long long s[N];
int n, k;
int cnt[N];
int ans;

int main()
{
    scanf("%d%d", &n , &k);
    s[0] = 0;
    cnt[0] = 1;//0%3==0，记得加
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];//前缀和
        cnt[s[i] % k] ++;//求余
    }
    for(int i = 1; i <= n; i ++)
    {
        if(cnt[i] != 0)//方式加负数
        {
            ans += (cnt[i] * (cnt[i] - 1));//加方案
        }
    }
    printf("%d", ans);

    return 0;
}