Codeforces Round #799（Div. 4，CF1692）全题解

文章目录

- - A
  - B
  - C
  - D
  - E
  - F
  - G
  - H

传送门

本文CSDN

本文juejin

第一次AK CF纪念，虽然只是个div4。以前也有div3差点AK的经历，现在div3难度上来了，这种机会永远不会再有了吧……

为什么E水题写得尤其慢？因为中途洗了个澡。

这套题的概况：应该是最难的一场div4了。A~D不是算法题，E~H是算法题，H的dp有点难，想了我不少时间，差点没过。

作者：hans774882968以及hans774882968

签到。

设sz是集合大小。n - sz为偶数，则答案恰好为sz，否则需要多删一个元素，答案sz-1。

#include 
using namespace std;
typedef long long LL;
typedef pair pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 3e5 + 5;

int n, a[N];

void dbg() {
    puts ("");
}
templatevoid dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
templateinline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
templatevoid read (T &x, R &...r) {
    read (x);
    read (r...);
}

int main() {
    int T;
    read (T);
    while (T--) {
        read (n);
        rep (i, 1, n) read (a[i]);
        map mp;
        rep (i, 1, n) mp[a[i]]++;
        printf ("%dn", mp.size() - ( (n - mp.size() ) % 2) );
    }
    return 0;
}

题意：8*8棋盘，给出bishop的攻击范围，找bishop的位置。

水。当前点和对角线4个邻居都是'#'的点就是。

#include 
using namespace std;
typedef long long LL;
typedef pair pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 3e5 + 5;

int n;
char s[15][15];

void dbg() {
    puts ("");
}
templatevoid dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
templateinline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
templatevoid read (T &x, R &...r) {
    read (x);
    read (r...);
}

int main() {
    int T;
    read (T);
    while (T--) {
        re_ (i, 0, 8) scanf ("%s", s[i]);
        rep (i, 1, 6) rep (j, 1, 6) {
            if (s[i][j] == '#' && s[i - 1][j + 1] == s[i + 1][j + 1] && s[i - 1][j + 1] == s[i - 1][j - 1] && s[i - 1][j + 1] == s[i + 1][j - 1] && s[i - 1][j + 1] == '#')
                printf ("%d %dn", i + 1, j + 1);
        }
    }
    return 0;
}

题意：给出当前时刻（用%02d:%02d表示，如05:50）和delta，表示从当前时刻开始，每delta分钟看一次闹钟，注意该过程是永久的。问总共能看到几个回文时刻。

虽然过程是永久的，但只需要处理到下一次走到当前时刻，即lcm(1440,delta)分钟。这个过程只需要枚举1440 // gcd(1440,delta)次，很稳。

from collections import defaultdict
from math import gcd


def get_time(v):
    return "%02d:%02d" % (v // 60, v % 60)


def lcm(a, b):
    return a // gcd(a, b) * b


for _ in range(int(input())):
    time_s, d = input().split()
    d = int(d)
    h, m = map(int, time_s.split(':'))
    cur = h * 60 + m
    ans = 0
    las = cur + lcm(1440, d)
    for ti in range(cur, las, d):
        time_s = get_time(ti % 1440)
        if time_s == time_s[::-1]:
            ans += 1
    print(ans)

题意：给出01数组，每次你可以删除数组首元素和末尾元素，问最少删除几次可以得到一个和为s的子数组。如果无法得到输出-1。

双指针老模板题了。枚举所得子数组的右边界r，然后找到最小的l，使得a[l~r]等于s，则r-l+1为一个候选。

#include 
using namespace std;
typedef long long LL;
typedef pair pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 3e5 + 5;

int n, s, a[N];

void dbg() {
    puts ("");
}
templatevoid dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
templateinline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
templatevoid read (T &x, R &...r) {
    read (x);
    read (r...);
}

int main() {
    int T;
    read (T);
    while (T--) {
        read (n, s);
        rep (i, 1, n) read (a[i]);
        int tot = accumulate (a + 1, a + n + 1, 0);
        if (tot < s) {
            puts ("-1");
            continue;
        }
        int l = 1, cur = 0, ans = 0;
        rep (i, 1, n) {
            cur += a[i];
            if (cur < s) {
                continue;
            }
            while (l < i && cur > s) {
                cur -= a[l++];
            }
            ans = max (ans, i - l + 1);
        }
        printf ("%dn", n - ans);
    }
    return 0;
}

题意：给你一个数组，求是否存在3个不同下标，使得a[i]+a[j]+a[k]以3结尾。

以3结尾，即模10余3，故只需要扔到模10的桶里，然后3重循环枚举。

#include 
using namespace std;
typedef long long LL;
typedef pair pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 10 + 5;

int n, a[N];

void dbg() {
    puts ("");
}
templatevoid dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
templateinline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
templatevoid read (T &x, R &...r) {
    read (x);
    read (r...);
}

bool jdg() {
    rep (i, 0, 9) {
        if (!a[i]) continue;
        a[i]--;
        rep (j, 0, 9) {
            if (!a[j]) continue;
            a[j]--;
            rep (k, 0, 9) {
                if (!a[k]) continue;
                if ( (i + j + k) % 10 == 3) return true;
            }
            a[j]++;
        }
        a[i]++;
    }
    return false;
}

int main() {
    int T;
    read (T);
    while (T--) {
        read (n);
        memset (a, 0, sizeof a);
        rep (i, 1, n) {
            int x;
            read (x);
            x %= 10;
            a[x]++;
        }
        puts (jdg() ? "YES" : "NO");
    }
    return 0;
}

题意：给你一个长为n的数组和k。问有多少个下标i，1 <= i <= n-k满足：2^0 * a[i] < 2^1 * a[i+1] < ... < 2^k * a[i+k]。a[i] <= 1e9, n <= 2e5。

小于号有传递性，所以只需要满足2^j * a[i+j] < 2^(j+1) * a[i+j+1]，即a[i+j] < 2 * a[i+j+1]。我们先预处理出fl[i] = (a[i-1] < 2 * a[i])，然后快速判定长为k的区间是否不存在0即可。这个判定可以用前缀和数组完成。

#include 
using namespace std;
typedef long long LL;
typedef pair pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 2e5 + 5;

int n, k, fls[N];
LL a[N];

void dbg() {
    puts ("");
}
templatevoid dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
templateinline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
templatevoid read (T &x, R &...r) {
    read (x);
    read (r...);
}

int main() {
    int T;
    read (T);
    while (T--) {
        read (n, k);
        rep (i, 1, n) read (a[i]);
        rep (i, 2, n) fls[i] = (2 * a[i] > a[i - 1]) + fls[i - 1];
        int ans = 0;
        rep (i, 1, n - k) {
            if (fls[i + k] - fls[i] == k) {
                ans++;
            }
        }
        printf ("%dn", ans);
    }
    return 0;
}

题意：输出任意一个区间[l,r]及其众数，满足2*区间众数-(r-l+1)最大。

首先可以反证法证明答案所选择的数总可以是区间端点，这种不失一般性为答案添加好性质的套路很常见。目标函数本来是2*区间众数-(r-l+1)，现在就变成2*a[r]的出现次数-(r-l+1)。定义dp[i]为以i为右端点的最优目标函数值，则max(dp[i])为最优目标函数值，其对应下标idx为所选区间右端点，a[idx]为所选值。再定义pt[i]为以i为右端点的条件下的左端点，则pt[idx]为所选区间左端点。

dp转移：模仿最大子段和的dp做法，dp[i] = max (1, dp[pre[i]] + (pre[i] - i + 2) )。

pt更新：pt[i] = dp[i] == 1 ? i : pt[pre[i]]。

pre[i]~~还是熟悉的配方还是熟悉的味道~~，表示a[i]上一次出现的下标，不存在则为0（1-indexed）。

更新：再也不敢在cf里用umap了……hack里加了卡umap的数据。

#include 
using namespace std;
typedef long long LL;
typedef pair pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 2e5 + 5;

int n, a[N], pre[N], dp[N], pt[N];

void dbg() {
    puts ("");
}
templatevoid dbg (const T &f, const R &... r) {
    cout << f << " ";
    dbg (r...);
}
templateinline void read (Type &xx) {
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {}
templatevoid read (T &x, R &...r) {
    read (x);
    read (r...);
}

int main() {
    int T;
    read (T);
    while (T--) {
        read (n);
        rep (i, 1, n) read (a[i]);
        map tmp;
        rep (i, 1, n) {
            pre[i] = tmp[a[i]];
            tmp[a[i]] = i;
        }
        rep (i, 1, n) {
            dp[i] = max (1, dp[pre[i]] + (pre[i] - i + 2) );
            pt[i] = dp[i] > 1 ? pt[pre[i]] : i;
        }
        int idx = max_element (dp + 1, dp + n + 1) - dp;
        printf ("%d %d %dn", a[idx], pt[idx], idx);
    }
    return 0;
}

Codeforces Round #799（Div. 4，CF1692）全题解

C/C++/C#相关栏目本月热门文章