$\Huge\color{DeepSkyBlue}{第 50 周周赛题解}$

缺少的数

• 容易发现一个性质，就是如果下标与原数不等，则就是这个缺少的数，当然我们要保证他下标从 1 开始

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int a[N], n;

int main(){

    //freopen("T1缺少的数.in", "r", stdin);
    //freopen("T1缺少的数.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n - 1; i ++ ) scanf("%d", &a[i]);

    sort (a + 1, a + n);

    for (int i = 1; i <= n; i ++ )
        if (a[i] != i){
            printf("%d\n", i);
            return 0;
        }

    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

选区间

注意要$sort$两遍，因为你也不知道那个类的$l$或者是$r$更大火更小

$$时间复杂度取瓶颈： O(nlogn)$$

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 200010;

int n, m;

struct Node{
    int l, r;
}p1[N], p2[N];

bool cmp1(Node a, Node b){
    return a.r < b.r;
}

bool cmp2(Node a, Node b){
    return a.l < b.l;
}

int minr, maxl;
int ans;

int main(){

    //freopen("T2选区间.in", "r", stdin);
    //freopen("T2选区间.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &p1[i].l, &p1[i].r);
    scanf("%d", &m);
    for (int i = 1; i <= m; i ++ ) scanf("%d%d", &p2[i].l, &p2[i].r);

    sort (p1 + 1, p1 + n + 1, cmp1);
    sort (p2 + 1, p2 + m + 1, cmp2);
    minr = p1[1].r;
    maxl = p2[m].l;
    if (minr >= maxl) ans = max(ans, 0);
    else ans = max(ans, maxl - minr);

    sort (p1 + 1, p1 + n + 1, cmp2);
    sort (p2 + 1, p2 + m + 1, cmp1);
    minr = p2[1].r;
    maxl = p1[n].l;
    if (minr >= maxl) ans = max(ans, 0);
    else ans = max(ans, maxl - minr);

    printf("%d\n", ans);

    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

选元素

$老规矩用DP$

• $f[i][j]表示前i个数中，选择为特殊数的有 j 个$
• $$f[i][j] = max(f[i][j], f[u][j - 1] + x)$$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stdio.h>

using namespace std;

typedef long long ll;

const int N = 210;

ll f[N][N];
int n, k, m;
int v;

int main(){

    //freopen("T3选元素.in", "r", stdin);
    //freopen("T3选元素.out", "w", stdout);

    scanf("%d%d%d", &n, &k, &m);

    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i ++ ){
        int x; scanf("%d", &x);

        for (int j = 1; j <= m; j ++ ) // 限制 j 次
            for (int u = max(0, i - k); u < i; u ++ )
                f[i][j] = max(f[i][j], f[u][j - 1] + x);
                //            不选这个位置，选这个位置
    }

    ll res = -1;
    for (int i = n - k + 1; i <= n; i ++ ) res = max(res, f[i][m]);
    printf("%lld\n", res);

    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

K倍区间

根据前缀和，我们发现选择 $i -> j$只需要用 $O(1)$的时间复杂度求解，但此时暴力是不行的, 其实下次遇到此情况可以将满足的式子用字母列出来找规律，会比本身就很抽象的$algorithm$明显一点

$$s[i] - s[i - 1] ≡ 0 s[i] - s[i - 2] ≡ 0 。。。$$

$$(a - b) mod p = a mod p - b mod p$$

所以只需要找同余的个数就行啦！！
本题数据范围很小，不必有$unorderedmap$

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 100010;

ll s[N];
int n, k, cnt[N];

int main(){

    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++ ){
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }

    ll sum = 0;
    cnt[0] ++ ; // cnt[0] 本身就可以被 k 整除
    for (int i = 1; i <= n; i ++ ){
        sum += cnt[s[i] % k];
        cnt[s[i] % k] ++ ;
    }

    printf("%lld\n", sum);

    return 0;
}

数独简单版

下次要注意

$$N <= 30的情况下 可以考虑用 dfs + 剪枝$$

• 是真的很简单$WAWAWA…$
• $row[][], col[][], cell[][][]$是本题的精髓

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stdio.h>

using namespace std;

const int N = 10;

char a[N][N];
bool row[N][N], col[N][N], cell[3][3][N];

bool dfs(int x, int y){
    if (y == 9) x ++ , y = 0; // y 出界，说明可以换下一行
    if (x == 9){ // x 出界了，说明已经找到方案了
        for (int i = 0; i < 9; i ++ ) printf("%s\n", a[i]);
        return true;
    }

    if (a[x][y] != '.') return dfs(x, y + 1);
    for (int i = 0; i < 9; i ++ ){
        if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]){
            a[x][y] = i + '1';
            row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true; // 假设我们去这个值

            if (dfs(x, y + 1)) return true;

            row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
            a[x][y] = '.'; // 回溯即可
        }
    }

    return false; // 没有结果
}

int main(){

    for (int i = 0; i < 9; i ++ ){
        scanf("%s", a[i]);
        for (int j = 0; j < 9; j ++ )
            if (a[i][j] != '.'){
                int t = a[i][j] - '1'; // 映射到 0 ~ 8
                row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
            }
    }

    dfs(0, 0);

    return 0;
}

糖果传递

$$有别名：均分纸牌问题^{环形}$$

讲述基本都在代码里

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

using namespace std;

typedef long long ll; // 十年 OI

const int N = 1000010;

ll c[N], a[N], avg;
int n;

int main(){

    //freopen("T6均分糖果.in", "r", stdin);
    //freopen("T6均分糖果.out", "w", stdout);

    scanf("%d", &n);
    ll sum = 0;
    for (int i = 1; i <= n; i ++ ){
        scanf("%d", &a[i]);
        sum += a[i];
    }
    avg = sum / n; // 求 average

    for (int i = 2; i <= n; i ++ ) c[i] = c[i - 1] - avg + a[i];
    //c[i] = c[i] + 1 + avg - a[i];
    sort(c + 1, c + n + 1);

    ll res = 0;
    for (int i = 1; i <= n; i ++ ) res += abs(c[i] - c[n + 1 >> 1]); // 中位数是最优解
    printf("%lld\n", res);

    //fclose(stdin);
    //fclose(stdout);

    return 0;
}