剑锋所指,心之所向。

30 场 edu a2e 第 2 场

2.21 - 2.25

A.Display The Number

如图所示的火柴棍摆数字的摆法:

pic

你只有 n 根火柴棍,求能摆出的最大整数

逗你玩,贪心


发现我们只会用 1, 7 这两个数字

然后奇数摆一个 7,偶数就只摆 1

时间复杂度 O(n)

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int x;
    scanf("%d", &x);
    if (x & 1) putchar('7'), x -= 3;
    while (x > 0) putchar('1'), x -= 2;
    puts("");
}

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

观察真的很重要

B.Infinite Prefixes

无限长的,循环节为 s01t,求有多少个前缀,满足 0 的个数比 1 的个数多 x

模拟


分类讨论即可

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

int n, a[MAXN];
ll cnt[2], ans, x;

void solve() {
    scanf("%d %lld", &n, &x);
    cnt[0] = cnt[1] = ans = 0;
    for (int i = 1; i <= n; ++i) scanf("%1d", &a[i]), cnt[a[i]] ++;
    ll foo = cnt[0] - cnt[1], cur = 0;
    for (int i = 1; i <= n; ++i) {
        if (foo == 0) {
            if (cur == x) { puts("-1"); return ; }
        } else {
            if (abs(x - cur) % abs(foo) == 0 && ((x - cur) / foo >= 0)) ans ++;
        }
        cur += (a[i] == 1) ? -1 : 1;
    }
    printf("%lld\n", ans);
}

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

C.Obtain The String

给出字符串 s, tz 初始为空,操作为对 z 接上 t 的子序列,问能否经过若干次操作,使得 z = s

子序列自动机


直接模拟会炸掉,需要上个子序列自动机

时间复杂度 O(|T|)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;

int n, m, idx, ans, nxt[MAXN][30];
char s[MAXN], t[MAXN];

void solve() {
    scanf("%s %s", s + 1, t + 1);
    n = strlen(s + 1), m = strlen(t + 1);
    idx = ans = 0;
    bool flg = true;
    memset(nxt, 0, sizeof nxt);
    for (int j = 0; j <= 25; ++j) nxt[n][j] = n + 1;
    for (int i = n; i >= 1; --i) {
        for (int j = 0; j <= 25; ++j) nxt[i - 1][j] = nxt[i][j];
        nxt[i - 1][s[i] - 'a'] = i;
    }
    for (; idx < m && flg; ) {
        flg = false;
        int pos = 0;
        for (; ; ) {
            pos = nxt[pos][t[idx + 1] - 'a'];
            if (pos <= n) idx ++, flg = true;
            if (pos > n) break;
            if (idx == m) break;
        }
        ans ++;
    }
    if (idx < m) { puts("-1"); return ; }
    printf("%d\n", ans);
}

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

好像还有用 vector + binary-search 过的

D.Same GCDs

\sum_{x = 0}^{m - 1}[\gcd(a + x, m) = \gcd(a, m)]

数学,数论


经过一番操作,我们发现问题等价于

d = \gcd(a, m)

\sum_{x = 0}^{m - 1}[\gcd(x, m) = d]

m = dk_2

对于 [\gcd(x, m) = d] 为真的 x,则明显有 x = dk_1,且易证 k_2 \perp k_1

也就是说我们要求

\sum_{0 \leq x < m}^{d | x}[\dfrac{x}{d} \perp k_2]

转而枚举 \dfrac{x}{d},即

\sum_{k_1 = 1}^{k_2 - 1}[k_1 \perp k_2]

\phi(k_2)

时间复杂度 O(\sqrt(m))

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll phi(ll n) {
    ll ret = n, tmp = n;
    for (ll i = 2; i * i <= tmp; ++i)   {
        if (n % i == 0) {
            ret = ret / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) ret = ret / n * (n - 1);
    return ret;
}

void solve() {
    ll a, b;
    scanf("%lld %lld", &a, &b);
    printf("%lld\n", phi(b / __gcd(a, b)));
}

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

算是第一次推真正意义上的式子吧

转化枚举好妙啊

E.Permutation Separation

给定两个长度为 n 的序列 p, a(保证 p1\cdots n 的排列),取一个数 k (1 \leq k \leq n - 1),则对序列 p 被划分成 \{p_{i} \mid 1 \leq i \leq k\}\{p_i \mid k < i \leq n\}。之后要移动两个部分的某些元素到另一个部分,使得第一个部分的最大值小于第二个部分的最小值。移动 p_i 的代价为 a_i。求出最小代价

数据结构,区间修改,区间最值


代码中有若干个详细的,从暴力到正解一步一步的优化

时间复杂度 O(n \log n)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 2e5 + 10;

int n, val[MAXN];
ll cost[MAXN], ans = 9223372036854775807, tmpans[MAXN];

#define mid ((l + r) >> 1)
#define ls k << 1, l, mid
#define rs k << 1 | 1, mid + 1, r
struct Segmenttree {
    ll data, add;
} t[MAXN << 2];

void pushdown(int k, int l, int r) {
    t[k << 1].data += t[k].add, t[k << 1 | 1].data += t[k].add;
    t[k << 1].add += t[k].add, t[k << 1 | 1].add += t[k].add;
    t[k].add = 0;
}

void pushup(int k) { t[k].data = min(t[k << 1].data, t[k << 1 | 1].data); }

void add(int k, int l, int r, int ql, int qr, ll val) {
    if (ql <= l && r <= qr)  { t[k].data += val, t[k].add += val; return ; }
    pushdown(k, l, r);
    if (ql <= mid) add(ls, ql, qr, val);
    if (qr > mid) add(rs, ql, qr, val);
    pushup(k);
}

ll getmin(int k, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return t[k].data;
    ll tmp = 9223372036854775807;
    pushdown(k, l, r);
    if (ql <= mid) tmp = min(tmp, getmin(ls, ql, qr));
    if (qr > mid) tmp = min(tmp, getmin(rs, ql, qr));
    return tmp;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &val[i]);
    for (int i = 1; i <= n; ++i) scanf("%lld", &cost[i]);
    /*
    for (int blc = 1; blc < n; ++blc) {
        // version 1
        memset(tmpans, 0, sizeof tmpans);
        for (int s = 1; s <= n; ++s) {
            for (int i = 1; i <= blc; ++i) if (val[i] > s) tmpans[s] += cost[i];
            for (int i = blc + 1; i <= n; ++i) if (val[i] <= s) tmpans[s] += cost[i];
            ans = min(ans, tmpans[s]);
        }

        // version 2
        memset(tmpans, 0, sizeof tmpans);
        for (int i = 1; i <= blc; ++i) {
            for (int s = 0; s < val[i]; ++s) tmpans[s] += cost[i];
        }
        for (int i = blc + 1; i <= n; ++i) {
            for (int s = val[i]; s <= n; ++s) tmpans[s] += cost[i];
        }
        for (int s = 0; s <= n; ++s) ans = min(ans, tmpans[s]);

        // version 3
        memset(t, 0, sizeof t);
        for (int i = 1; i <= blc; ++i) add(1, 0, n, 0, val[i] - 1, cost[i]);
        for (int i = blc + 1; i <= n; ++i) add(1, 0, n, val[i], n, cost[i]);
        ans = min(ans, getmin(1, 0, n, 0, n));
    }
    */

    // final version
    add(1, 0, n, 0, val[1] - 1, cost[1]);
    for (int i = 2; i <= n; ++i) add(1, 0, n, val[i], n, cost[i]);
    ans = getmin(1, 0, n, 0, n);
    for (int blc = 2; blc < n; ++blc) {
        add(1, 0, n, val[blc], n, -cost[blc]);
        add(1, 0, n, 0, val[blc] - 1, cost[blc]);
        ans = min(ans, getmin(1, 0, n, 0, n));
    }
    printf("%lld\n", ans);
    return 0;
}

感觉这 E 力度过小,不过一步一步从暴力到正解的过程让人十分舒适

全世界都这样写的,就不对比了

总结

  1. E 题推的很顺利
  2. 做题效率有所提升

不好

  1. D 题不会推,对数学题还是经验太少
  2. A,B 细节错了好多,要多静态差错!
  3. 希望以后能做的更快一点,效率更高一点!

codeforces 1288/edu. 80 题解与总结
上一篇 «
codeforces 1303/edu. 82 题解与总结
» 下一篇