Educational Codeforces Round 74

Contest Info
Solutions

Contest Info

Solved	A	B	C	D	E	F	G
6/7	O	O	O	O	Ø	Ø	-

O 在比赛中通过
Ø 赛后通过
! 尝试了但是失败了
- 没有尝试

Solutions

A. Prime Subtraction

签到。

B. Kill 'Em All

签到。

C. Standard Free2play

贪心即可。

代码：

view code

#include <bits/stdc++.h>
#define debug(...) { printf("#  "); printf(__VA_ARGS__); puts(""); }
#define fi first
#define se second
#define endl "\n" 
using namespace std;
using db = double;
using ll = long long;
using ull = unsigned long long; 
using pII = pair <int, int>;
using pLL = pair <ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; } 
template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }
template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }
inline int rd() { int x; cin >> x; return x; }
template <class T> inline void rd(T &x) { cin >> x; }
template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }
inline void pt() { cout << endl; }
template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << " "; pt(args...); }
template <class T> inline void pt(const T &s) { cout << s << "\n"; }
template <class T> inline void pt(const vector <T> &vec) { for (auto &it : vec) cout << it << " "; cout << endl; } 
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }
constexpr int N = 2e5 + 10;
int h, n, a[N]; 
void run() {
    cin >> h >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    if (n == 1) return pt(0);
    int res = 0, lst = h; 
    for (int i = 2; i <= n; ++i) {
        if (lst <= a[i]) continue;
        lst = a[i] + 1;
        if (i == n) {
            if (lst >= 3) ++res; 
            break;
        }
        if (lst - a[i + 1] >= 3) {
            ++res;
            lst = a[i + 1] + 1;
        } else {
            lst = a[i + 1];
        }
    }
    pt(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T; cin >> _T;
    while (_T--) run();
    return 0;
}

D. AB-string

题意：
给出一个字符串\(S\)，其字符集只有'A', 'B'，现在统计有多少个子串是符合要求的，一个子串是符合要求的当且仅当其中每个字符都属于一个长度大于\(1\)的回文子串中。

思路：
考虑符合要求的串的长度肯定大于等于\(2\)，那么只有一种字符是符合要求的。
再考虑，枚举每个左端点，找多少个右端点是符合的。
首先\(AB\)是不符合的，但是\(ABA\)，并且后面不管加什么字符都是符合的。
那么\(AAAABA\)后面不管加什么字符都是符合的。
对于首字母是\(B\)的同理考虑即可。

代码：

view code

#include <bits/stdc++.h>
#define debug(...) { printf("#  "); printf(__VA_ARGS__); puts(""); }
#define fi first
#define se second
#define endl "\n" 
using namespace std;
using db = double;
using ll = long long;
using ull = unsigned long long; 
using pII = pair <int, int>;
using pLL = pair <ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; } 
template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }
template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }
inline int rd() { int x; cin >> x; return x; }
template <class T> inline void rd(T &x) { cin >> x; }
template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }
inline void pt() { cout << endl; }
template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << " "; pt(args...); }
template <class T> inline void pt(const T &s) { cout << s << "\n"; }
template <class T> inline void pt(const vector <T> &vec) { for (auto &it : vec) cout << it << " "; cout << endl; } 
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }
constexpr int N = 3e5 + 10;
int n; char s[N];
vector <int> A, B;
void run() {
    cin >> (s + 1);
    A.clear(); B.clear();
    for (int i = 1; i <= n; ++i) {
        if (s[i] == 'A') A.push_back(i);
        else B.push_back(i);
    }
    ll res = 0;
    for (int i = 1; i < n; ++i) {
        if (s[i] == 'A') {
            auto nx = upper_bound(B.begin(), B.end(), i);
            if (nx == B.end()) {
                res += (n - i);
            } else if (*nx == i + 1) {
                auto nnx = upper_bound(A.begin(), A.end(), *nx);
                if (nnx != A.end()) {
                    res += n - *nnx + 1;
                }
            } else {
                res += n - i - 1;
            }
        } else {
            auto nx = upper_bound(A.begin(), A.end(), i);
            if (nx == A.end()) {
                res += n - i;
            } else if (*nx == i + 1) {
                auto nnx = upper_bound(B.begin(), B.end(), *nx);
                if (nnx != B.end()) {
                    res += n - *nnx + 1;
                }
            } else {
                res += n - i - 1;
            }
        }
    }
    pt(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout << fixed << setprecision(20);
    while (cin >> n) run();
    return 0;
}

E. Keyboard Purchase

题意：
给出一个字符串\(S\)，现在要造一个键盘，这个键盘只有一排键，要敲打这段字符串\(S\)，花费是：
\[ \begin{eqnarray*} \sum\limits_{i = 2}^n |pos_{s_{i - 1}} - pos_{s_i}| \end{eqnarray*} \]

现在问最小代价，在选择合适的键盘下，键盘上键位是自定的。

思路：
我们考虑拆绝对值，那么对于两个相邻的\((a, b)\)，那么我们只需要关心\(pos_a\)是在\(pos_b\)的前面还是后面即可，这样就确定了绝对值中的符号。
那么用\(f[i][j]\)表示前\(i\)个位置，选择的字符二进制状态为\(j\)的最小代价。
那么只需要考虑\(f[i][S]\)转移到\(f[i + 1][S \cup \{v\}] for\;v \notin S\)

代码：

view code

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define debug(...) { printf("#  "); printf(__VA_ARGS__); puts(""); }
#define fi first
#define se second
#define endl "\n" 
using namespace std;
using db = double;
using ll = long long;
using ull = unsigned long long; 
using pII = pair <int, int>;
using pLL = pair <ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; } 
template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }
template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }
inline int rd() { int x; cin >> x; return x; }
template <class T> inline void rd(T &x) { cin >> x; }
template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }
inline void pt() { cout << endl; }
template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << " "; pt(args...); }
template <class T> inline void pt(const T &s) { cout << s << "\n"; }
template <class T> inline void pt(const vector <T> &vec) { for (auto &it : vec) cout << it << " "; cout << endl; } 
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }
constexpr int N = 1e5 + 10;  
int n, m, w[30][30], f[1 << 21], g[1 << 21][22], num[1 << 21], lg[1 << 21]; char s[N]; 
void run() {
    cin >> (s + 1); 
    memset(w, 0, sizeof w);
    for (int i = 1; i < n; ++i) {
        int c = s[i] - 'a', c2 = s[i + 1] - 'a';
        if (c == c2) continue;
        ++w[c][c2];
        ++w[c2][c];
    }
    int lim = 1 << m;
    memset(g, 0, sizeof g);
    for (int i = 1; i < lim; ++i) {
        for (int j = 0; j < m; ++j) {
            int lb = i & -i;
            g[i][j] = g[i ^ lb][j] + w[j][lg[lb]]; 
        }
    }
    memset(f, 0x3f, sizeof f); f[0] = 0; 
    for (int i = 0; i < lim; ++i) {
        for (int j = 0; j < m; ++j) {
            if (!((i >> j) & 1)) {
                int pos = num[i] + 1;
                chmin(f[i ^ (1 << j)], f[i] + g[i][j] * pos - g[(lim - 1) ^ i ^ (1 << j)][j] * pos);
            }
        }
    }
    pt(f[lim - 1]);
}

int main() {
    memset(num, 0, sizeof num);
    for (int i = 1; i < 1 << 20; ++i) 
        num[i] = num[i ^ (i & -i)] + 1;
    memset(lg, 0, sizeof lg);
    lg[0] = -1; lg[1] = 0; 
    for (int i = 2; i < 1 << 20; i <<= 1) lg[i] = lg[i >> 1] + 1;
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout << fixed << setprecision(20);
    while (cin >> n >> m) run();
    return 0;
}

F. The Maximum Subtree

题意：
定义一张图是合法的当且仅当，每个点表示一个一维数轴上的线段的时候，两个点有边当且仅当他们表示的线段有交集。
现在给出一棵树，问最多选择多少个点构成的子树是合法的。

思路：
多\(wa\)几发就可以发现一个点如果之和父亲有边，那么这种点是随便加的。
那么对于一个点如果它和儿子连了边，那么它要和其父亲连边，那么其父亲最多连这样的点两个，并且其父亲是根。
然后再用每个点的子树的最大值更新答案。

代码：

view code

#include <bits/stdc++.h>
#define debug(...) { printf("#  "); printf(__VA_ARGS__); puts(""); }
#define fi first
#define se second
#define endl "\n" 
using namespace std;
using db = double;
using ll = long long;
using ull = unsigned long long; 
using pII = pair <int, int>;
using pLL = pair <ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; } 
template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }
template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }
inline int rd() { int x; cin >> x; return x; }
template <class T> inline void rd(T &x) { cin >> x; }
template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }
inline void pt() { cout << endl; }
template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << " "; pt(args...); }
template <class T> inline void pt(const T &s) { cout << s << "\n"; }
template <class T> inline void pt(const vector <T> &vec) { for (auto &it : vec) cout << it << " "; cout << endl; } 
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }
constexpr int N = 3e5 + 10;
int n, f[N], rt, res; 
vector <vector<int>> G; 
void dfs(int u, int fa) {
    int Max[2] = {0, 0};
    int sons = 0;
    for (auto &v : G[u]) {
        if (v == fa) continue;
        ++sons;
        dfs(v, u);
        if (f[v] > Max[0]) {
            swap(Max[0], Max[1]);
            Max[0] = f[v];
        } else if (f[v] > Max[1]) Max[1] = f[v];
    }
    if (u != rt) {
        f[u] = Max[0] + 1 + max(0, sons - 1);
        chmax(res, Max[0] + Max[1] + 1 + max(0, sons - 1));
    } else {
        f[u] = Max[0] + Max[1] + 1 + max(0, sons - 2);
        chmax(res, f[u]);
    }
}
void run() { 
    cin >> n;
    memset(f, 0, sizeof (f[0]) * (n + 10));
    G.clear(); G.resize(n + 1);
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    rt = 1; res = 0;
    for (int i = 2; i <= n; ++i) {
        if (G[i].size() > 1) {
            rt = i;
            break;
        }
    }
    dfs(rt, rt);
    pt(res); 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T; cin >> _T;
    while (_T--) run();
    return 0;
}

Educational Codeforces Round 74

Contest Info

Solutions

A. Prime Subtraction

B. Kill 'Em All

C. Standard Free2play

D. AB-string

E. Keyboard Purchase

F. The Maximum Subtree

相关推荐