Codeforces Round (2022-08-04)

Educational Codeforces Round 133 (Rated for Div. 2)

A. 2-3 Moves

题目链接

题意

从数轴上的 0 出发，每次可以向左或向右走 2 或 3。求到达正整数 $n$ 最少需要几步。

思路

一步最多走 3，所以尽量用 3。余 2 就补一步 2；余 1 时，把一个 3 和剩下的 1 换成两个 2，也只多一步。

只有 $n=1$ 要单独处理，先走 3 再退 2，需要两步。

代码

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

#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e5 + 17;
const int N = 1e5;
const int mo = 1e9 + 7;



void debug(int x) {
    printf("??? %d\n", x);
}

void debug(int *X, int x) {
    printf("??? ");
    for(int i = 1; i <= x; i++) printf("%d%c", X[i], " \n"[i == x]);
}

void solve() {
    int n, ans;
    scanf("%d", &n);
    if(n % 3 == 0) ans = n / 3;
    else if(n % 3 == 2) ans = n / 3 + 1;
    else if(n >= 4) ans = n / 3 + 1;
    else ans = 2;
    printf("%d\n", ans);
}

int main() {
    int T;
    // T = 1;
    scanf("%d", &T);
    // cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

B. Permutation Chain

题目链接

题意

从排列 $1,2,\ldots,n$ 开始，每次交换任意两个数，并要求满足 $p_i=i$ 的位置数严格减少。求最长的排列链，并输出链上的所有排列。

思路

先交换第 1、2 个位置，一下少两个不动点。以后每次把第一个位置和下一个还没动的位置交换，就只少一个不动点，一直换到最后。

不动点不可能恰好有 $n-1$ 个，所以第一步至少少两个，链最多有 $n$ 个排列。这个构造正好能做到， $n=1$ 时直接输出它自己。

代码

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

#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e5 + 17;
const int N = 1e5;
const int mo = 1e9 + 7;



void debug(int x) {
    printf("??? %d\n", x);
}

void debug(int *X, int x) {
    // printf("??? ");
    for(int i = 1; i <= x; i++) printf("%d%c", X[i], " \n"[i == x]);
}

int a[maxn];

void solve() {
    int n, ans;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) a[i] = i;
    printf("%d\n", n);
    for(int i = 1; i <= n; i++) {
        debug(a, n);
        swap(a[i + 1], a[1]);
    }

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

int main() {
    int T;
    // T = 1;
    scanf("%d", &T);
    // cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

C. Robot in a Hallway

题目链接

题意

机器人从两行网格的左上角出发，每秒可以走到相邻格子或原地等待。除起点外，每个格子都有解锁时间，必须在解锁后才能开始移进去；要求每格恰好进入一次，求最早结束时间。

思路

路线只能是前面按列来回走，后面沿着一行走到最右边，再从另一行折回来。确定从哪里开始绕这一圈，整条路线就定下来了。

把路线上的格子依次编号，走到第 $p$ 个位置要花 $p-1$ 秒。这个格子的解锁时间是 $a_p$ ，出发前至少等 $a_p+1-(p-1)$ 秒，取全局最大值，再加上总步数就是这条路线的时间。起点已经站在里面，不受这个限制。

这里用线段树维护这个最大值。每次把转弯位置向后推两列，中间一段的访问时间整体后移，两端有两个格子提前，分别做区间加和单点加就行。另一种奇偶的转弯位置，先走到左下、再往右一步，扣掉这段时间后同样处理。

枚举到最后一条路线就停，后面已经没有格子可换了，不能继续更新空区间。总时间 $O(m\log m)$ 。

代码

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

#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 4e5 + 17;
const ll oo = 1e18;

void debug(int x) {
    printf("??? %d\n", x);
}

void debug(int *X, int x) {
    printf("??? ");
    for(int i = 1; i <= x; i++) printf("%d%c", X[i], " \n"[i == x]);
}

int m, n, a[maxn], b[maxn];

struct SegmentTree {
    struct node {
        ll w, lz;
    } t[maxn * 4];
    #define ls (x << 1)
    #define rs (x << 1 | 1)
    #define mid ((l + r) >> 1)
    void push_down(int x) {
        t[ls].w += t[x].lz;
        t[ls].lz += t[x].lz;
        t[rs].w += t[x].lz;
        t[rs].lz += t[x].lz;
        t[x].lz = 0;
    }
    void push_up(node& nx, node& nl, node& nr) {
        nx.w = max(nl.w, nr.w);
    }
    void build(int x = 1, int l = 1, int r = n) {
        t[x].lz = 0;
        if(l == r) {
            t[x].lz = 0;
            t[x].w = a[l] + 1 - (l - 1);
            if(l == 1) t[x].w = 0;
            // cout << "!!!" << t[x].w << endl;
            return;
        }
        build(ls, l, mid);
        build(rs, mid + 1, r);
        push_up(t[x], t[ls], t[rs]);
        // printf("%d %d %d %lld %lld %lld %lld\n", x, l, r, t[x].mx, t[x].mn, t[x].p, t[x].pp);
    }
    void modify(int ml, int mr, ll k, int x = 1, int l = 1, int r = n) {
        if(ml <= l && r <= mr) {
            t[x].w += k;
            t[x].lz += k;
            return;
        }
        push_down(x);
        if(ml <= mid) modify(ml, mr, k, ls, l, mid);
        if(mr > mid) modify(ml, mr, k, rs, mid + 1, r);
        push_up(t[x], t[ls], t[rs]);
    }
    node query(int ql, int qr, int x = 1, int l = 1, int r = n) {
        if(ql <= l && r <= qr) return t[x];
        push_down(x);
        node res, rl, rr;
        if(ql <= mid) rl = query(ql, qr, ls, l, mid);
        if(qr > mid) rr = query(ql, qr, rs, mid + 1, r);
        if(qr <= mid) return rl;
        if(ql > mid) return rr;
        push_up(res, rl, rr);
        return res;
    }
} sgt;


void solve() {
    scanf("%d", &m);
    ll ans1 = oo, ans = oo;
    n = m * 2;
    for(int i = 1; i <= m; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= m; i++) scanf("%d", &a[m - i + 1 + m]);
    // debug(a, n);
    sgt.build();
    for(int i = 1; i <= m + 1; i += 2) {
        ll tmp = sgt.query(1, n).w;
        // printf("??? %lld\n", tmp);
        // printf("??? ");
        // for(int i = 1; i <= n; i++) printf("%d%c", sgt.query(i, i).w, " \n"[i == n]);
        ans1 = min(ans1, max(0ll, tmp));
        if(i + 2 > m) break;
        sgt.modify(i + 1, 2 * m - i - 1, -2);
        sgt.modify(2 * m - i, 2 * m - i, (2 * (m - i - 1)));
        sgt.modify(2 * m - i + 1, 2 * m - i + 1, (2 * (m - i)));
    }
    ans = min(ans1 + n - 1, ans);
    // printf("%lld\n", ans);
    for(int i = 1; i <= n; i++) b[i] = a[i];
    m--;
    int inv = max(b[n] + 2, b[n - 1] + 1);
    for(int i = 1; i <= m; i++) a[i] = b[n - i] - inv;
    for(int i = 1; i <= m; i++) a[i + m] = b[n / 2 - i + 1] - inv;
    // a[1]++;
    n -= 2;
    // a[1] = 0;
    ans1 = oo;
    sgt.build();
    for(int i = 1; i <= m + 1; i += 2) {
        ll tmp = sgt.query(1, n).w;
        // printf("??? %lld\n", tmp);
        // printf("??? ");
        // for(int i = 1; i <= n; i++) printf("%d%c", sgt.query(i, i).w, " \n"[i == n]);
        ans1 = min(ans1, max(0ll, tmp));
        if(i + 2 > m) break;
        sgt.modify(i + 1, 2 * m - i - 1, -2);
        sgt.modify(2 * m - i, 2 * m - i, (2 * (m - i - 1)));
        sgt.modify(2 * m - i + 1, 2 * m - i + 1, (2 * (m - i)));
    }
    ans1 += n - 1;
    // cout << ans1 << endl;
    n += 2;
    ans = min(ans1 + inv, ans);

    printf("%lld\n", ans);
}

int main() {
    int T;
    // T = 1;
    scanf("%d", &T);
    // cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

D. Chip Move

题目链接

题意

棋子从 0 出发，每步向右走正整数距离。第 1 步长度必须是 $k$ 的倍数，第 2 步是 $k+1$ 的倍数，以此类推；求到达每个 $1\le x\le n$ 的方案数，模 $998244353$ 。

思路

按走了多少步来做 DP。第 $i$ 步的最小长度是 $d=k+i-1$ ，到达 $j$ 的方案，可以从上一步的 $j-d$ 走过来，也可以把本轮到达 $j-d$ 的最后一步再加长 $d$ ：

$f_i(j)=f_{i-1}(j-d)+f_i(j-d).$

所以每轮从小到大扫，直接滚动数组。走 $i$ 步至少到达 $ki+i(i-1)/2$ ，小于这个位置的状态都不用读；最小距离超过 $n$ 就结束。

最多只有 $O(\sqrt n)$ 轮，把每轮的结果累加到答案，时间 $O(n\sqrt n)$ ，空间 $O(n)$ 。

代码

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

#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 2e5 + 17;
const int N = 1e5;
const int mo = 998244353;

int add(int x, int y) {
    return (x + y) % mo;
}

void debug(int x) {
    printf("??? %d\n", x);
}

void debug(int *X, int x) {
    // printf("??? ");
    for(int i = 1; i <= x; i++) printf("%d%c", X[i], " \n"[i == x]);
}

int n, k, f[2][maxn], ans[maxn];

void solve() {
    scanf("%d%d", &n, &k);
    f[0][0] = 1;

    for(int i = 1, c = 1, lst = 0; i <= n; i++, c ^= 1) {
        int st = k * i + i * (i - 1) / 2;
        if(st > n) break;
        // debug(st);
        // debug(lst);
        for(int j = st; j <= n; j++) {
            int tmp = j - (k + i - 1);
            // f[c][j] = add(f[c ^ 1][tmp], f[c][tmp]);
            // cout << tmp << endl;
            f[c][j] = add(tmp >= lst ? f[c ^ 1][tmp] : 0, tmp >= st ? f[c][tmp] : 0);
            ans[j] = add(ans[j], f[c][j]);
        }
        lst = st;
        // debug(f[c], n);
    }
    // debug(f[c ^ 1], n);
    debug(ans, n);
    // printf("%d\n", n);


}

int main() {
    int T;
    T = 1;
    // scanf("%d", &T);
    // cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

A. 2-3 Moves

题意

思路

代码

B. Permutation Chain

题意

思路

代码

C. Robot in a Hallway

题意

思路

代码

D. Chip Move

题意

思路

代码

Random Posts