侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

Codeforces Round 690 (Div. 3)

GabrielxD
2023-10-20 / 0 评论 / 0 点赞 / 298 阅读 / 2,109 字
温馨提示:
本文最后更新于 2023-10-23,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

Codeforces Round 690 (Div. 3) - Codeforces

Problem - A - Codeforces

方法一:模拟

思路

按题意模拟即可。

当输入序列 bb 的长度为奇数时:

  • b1,b2,...,bn2,bn2+1b_1, b_2, ..., b_{\lfloor\frac{n}{2}\rfloor}, b_{\lfloor\frac{n}{2}\rfloor + 1} 分别放在 a1,a3,...,an2,ana_1, a_3, ..., a_{n-2}, a_n
  • bn2+2,bn2+3,...,bn1,bnb_{\lfloor\frac{n}{2}\rfloor + 2}, b_{\lfloor\frac{n}{2}\rfloor + 3}, ..., b_{n - 1}, b_n 分别放在 an1,an3,...,a4,a2a_{n - 1}, a_{n - 3}, ..., a_4, a_2

当输入序列 bb 的长度为偶数时:

  • b1,b2,...,bn21,bn2b_1, b_2, ..., b_{\lfloor\frac{n}{2}\rfloor - 1}, b_{\lfloor\frac{n}{2}\rfloor} 分别放在 a1,a3,...,an3,an1a_1, a_3, ..., a_{n-3}, a_{n-1}
  • bn2+1,bn2+2,...,bn1,bnb_{\lfloor\frac{n}{2}\rfloor + 1}, b_{\lfloor\frac{n}{2}\rfloor + 2}, ..., b_{n - 1}, b_n 分别放在 an,an2,...,a4,a2a_{n}, a_{n - 2}, ..., a_4, a_2

数组从 0 开始也差不多,改下标即可。

代码

#include <cstdio>

using namespace std;

const int N = 310;
int t, n;
int a[N];

void solve() {
    scanf("%d", &n);
    for (int i = 0, j = n - 1 - (n & 1); i < n; ++i) {
        if (i < n / 2 + (n & 1)) scanf("%d", &a[i * 2]);
        else scanf("%d", &a[j]), j -= 2;
    }
    for (int i = 0; i < n; ++i) printf("%d ", a[i]);
    putchar('\n');
}

int main() {
    scanf("%d", &t);
    while (t--) solve();

    return 0;
}

Problem - B - Codeforces

方法一:模拟

思路

"2020" 分别拆成 "2""020" "20""20""202""2""2020",分别在字符串头尾匹配,如果匹配成功输出 "Yes" 即可。

代码

#include <cstdio>

using namespace std;

const int N = 210;
int t, n;
char s[N];

void solve() {
    scanf("%d%s", &n, s);
    if (s[0] == '2' && s[1] == '0' && s[2] == '2' && s[3] == '0') {
        puts("Yes");
        return;
    }
    if (s[n - 4] == '2' && s[n - 3] == '0' && s[n - 2] == '2' && s[n - 1] == '0') {
        puts("Yes");
        return;
    }
    if (s[0] == '2' && s[n - 3] == '0' && s[n - 2] == '2' && s[n - 1] == '0') {
        puts("Yes");
        return;
    }
    if (s[0] == '2' && s[1] == '0' && s[n - 2] == '2' && s[n - 1] == '0') {
        puts("Yes");
        return;
    }
    if (s[0] == '2' && s[1] == '0' && s[2] == '2' && s[n - 1] == '0') {
        puts("Yes");
        return;
    }
    puts("No");
}

int main() {
    scanf("%d", &t);
    while (t--) solve();

    return 0;
}

Problem - C - Codeforces

方法一:枚举 构造

思路

考虑到每位数都不能重复(且 0 对数位和没有贡献),所以最多能构造一个 9 位的数 123456789 ,也就是说无法构造出数位和 >45>45 的数,如果输入的 x>45x>45 直接输出 "-1" 即可。

构造时直接从高到低枚举每一位,从大到小枚举可以填的数(不重复)就能构造出符合条件的最小的数。

实际实现的时候可以从低位到高位枚举构造,然后反转输出即可。

代码

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

using namespace std;

int t, n;

void solve() {
    scanf("%d", &n);
    if (n > 45) {
        puts("-1");
        return;
    }
    int ans = 0;
    for (int d = 9; d >= 1; --d) {
        if (d <= n) {
            ans = ans * 10 + d;
            n -= d;
        }
    }
    while (ans) {
        printf("%d", ans % 10);
        ans /= 10;
    }
    putchar('\n');
}

int main() {
    scanf("%d", &t);
    while (t--) solve();

    return 0;
}

Problem - D - Codeforces

方法一:暴力枚举

思路

这题用 O(n2)O(n^2) 的做法是可以做的。

尝试枚举第一段子数组的长度 len ,然后从 len 向后枚举之后的段,如果后面的子数组和 >> 第一段子数组和,就说明以 [0,len1][0, len - 1] 为第一段的答案不存在,继续枚举 len ,如果后面的子数组和 == 第一段子数组和,就继续向后枚举其他段,枚举到数组结尾时就说明该答案可行。此时,若第一段子数组和为 avg ,则操作数最小值为 ni=0n1a[i]avgn - \frac{\sum_{i=0}^{n - 1}{a[i]}}{avg}

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 3010;
int t, n;
int a[N];

void solve() {
    scanf("%d", &n);
    int mx = 0, tot = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        mx = max(mx, a[i]);
        tot += a[i];
    }
    int avg = 0;
    for (int len = 1; len <= n; ++len) {
        avg += a[len - 1];
        if (avg < mx) continue;
        int sum = 0;
        for (int i = len; i < n; ++i) {
            if (sum + a[i] < avg) sum += a[i];
            else if (sum + a[i] == avg) sum = 0;
            else {
                sum = -1;
                break;
            }
        }
        if (sum == avg || sum == 0) {
            printf("%d\n", n - (tot / avg));
            return;
        }
    }
}

int main() {
    scanf("%d", &t);
    while (t--) solve();

    return 0;
}

Problem - E1 - Codeforces

方法一:二分 组合数学

代码

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;
int t, n;
int a[N];

int right_bound(int l, int r, int x) {
    while (l < r) {
        int m = l + r + 1 >> 1;
        if (a[m] <= x) l = m;
        else r = m - 1;
    }
    return r;
}

void solve() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    sort(a, a + n);
    LL ans = 0;
    for (int i = 0; i < n; ++i) {
        int cnt = right_bound(i + 1, n - 1, a[i] + 2) - i;
        ans += 1LL * cnt * (cnt - 1) / 2;
    }
    printf("%lld\n", ans);
}

int main() {
    scanf("%d", &t);
    while (t--) solve();

    return 0;
}

Problem - E2 - Codeforces

方法一:二分 组合数学 快速幂

代码

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10, MOD = 1e9 + 7;
int t, n, m, k;
int a[N];
int fac[N], ifac[N];

LL kasumi(LL base, LL exp, LL mod) {
    LL res = 1LL;
    while (exp) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

int right_bound(int l, int r, int x) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (a[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return r;
}

LL C(int n, int m) {
    if (n < m) return 0;
    if (n == m) return 1;
    return 1LL * fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}

void solve() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    sort(a, a + n);
    LL ans = 0LL;
    for (int i = 0; i < n; ++i) {
        int cnt = right_bound(0, n - 1, a[i] + k) - i;
        ans = (ans + C(cnt, m - 1)) % MOD;
    }
    printf("%lld\n", ans);
}

int main() {
    scanf("%d", &t);
    fac[0] = ifac[0] = 1;
    for (int i = 1; i <= 2e5; ++i) {
        fac[i] = (int) (1LL * i * fac[i - 1] % MOD);
        ifac[i] = (int) kasumi(fac[i], MOD - 2, MOD);
    }
    while (t--) solve();

    return 0;
}

Problem - F - Codeforces

方法一:离散化 树状数组

代码

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

#define fi first
#define se second

using namespace std;

typedef pair<int, int> PII;

const int N = 2e5 + 10;
int t, n;
PII segs[N];
int alls[N * 2];
int tr[2][N * 2];

int lowbit(int x) {
    return x & -x;
}

void add(int u, int i, int x) {
    for (; i <= n * 2; i += lowbit(i)) tr[u][i] += x;
}

int qry(int u, int i) {
    int res = 0;
    for (; i > 0; i -= lowbit(i)) res += tr[u][i];
    return res;
}

void solve() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int l, r;
        scanf("%d%d", &l, &r);
        segs[i] = {l, r};
        alls[i] = l, alls[i + n] = r;
    }
    sort(alls + 1, alls + n * 2 + 1);
    int sz = (unique(alls + 1, alls + n * 2 + 1) - (alls + 1));
    sort(segs + 1, segs + n + 1);
    for (int i = 1; i <= sz; ++i) tr[0][i] = tr[1][i] = 0;
    for (int i = 1; i <= n; ++i) {
        segs[i].fi = lower_bound(alls + 1, alls + sz + 1, segs[i].fi) - alls;
        segs[i].se = lower_bound(alls + 1, alls + sz + 1, segs[i].se) - alls;
    }
    for (int i = 1; i <= n; ++i) {
        add(1, segs[i].fi, 1);
    }
    int mx = 0;
    for (int i = 1; i <= n; ++i) {
        const int& l = segs[i].fi, & r = segs[i].se;
        int lc = qry(0, sz) - qry(0, l - 1);
        int rc = qry(1, r) - qry(1, l - 1);
        int cnt = lc + rc;
        mx = max(mx, cnt);
        add(1, l, -1);
        add(0, r, 1);
    }
    printf("%d\n", n - mx);
}

int main() {
    scanf("%d", &t);
    while (t--) solve();

    return 0;
}
0

评论区