Codeforces Round #595 (Div. 3)

A. Yet Another Dividing into Teams

代码

const int N = (int)1e2+7;
 
// ------- 变量 ------- //
 
int n, a[N];
 
// ------- 函数 ------- //
 
void Init() {
    scanf("%d", &n);
    rep(i, 0, n) scanf("%d", a+i);
    sort(a, a + n);
}
 
int Solve() {
    rep(i, 1, n) if (a[i] == a[i-1] + 1) return puts("2");
    return puts("1");
}

B. Books Exchange

代码

const int N = (int)2e5+7;
 
// ------- 变量 ------- //
 
int n, p[N], vis[N];
 
// ------- 函数 ------- //
 
int dfs(int x, int t) {
    vis[x] = 1;
    if (vis[p[x]]) return vis[x] = t;
    return vis[x] = dfs(p[x], t+1);
}
 
void Init() {
    rep(i, 1, n+1) vis[i] = 0;
    scanf("%d", &n);
    rep(i, 1, n+1) scanf("%d", p+i);
}
 
int Solve() {
    rep(i, 1, n+1) if (!vis[i]) {
        dfs(i, 1);
    }
    rep(i, 1, n+1) printf("%d%c", vis[i], " \n"[i==n]);
    return 0;
}

C. Good Numbers

题意

求大于等于 $n$ 的最小的 $m$ 使得 $m$ 只能用若干互不相同的 $3$ 的幂次相加表示。

即 $m$ 在 $3$ 进制表示下系数只有 $0$ 和 $1$

$1 \le n \le 10^{18}$

题解

预处理出所有 $3$ 的幂次 $pw[\ ]$
二分找到第一个大于等于 $n$ 的 $pw[i]$
$ans$ 暂定为 $pw[i]$
大于 $pw[i]$ 的 $pw[\ ]$ 距离 $n$ 更远，显然不能作为答案
但 $ans$ 可能由若干小于 $pw[i]$ 的 $pw[\ ]$ 组成
于是从 $pw[i-1]$ 开始累加 $tmp$
若当前 $tmp < n$ ，则说明当前累加的 $pw[\ ]$ 都是必要的
因为 $\sum_{j=0}^{i-1}pw[j] < pw[i]$
若当前 $tmp >= n$ ，则记录可能的答案
并减去最近累加的 $pw[\ ]$ ，重复上述过程

代码

// ------- 变量 ------- //
 
ll n, pw[50];
 
// ------- 函数 ------- //
 
void Pre() {
    ll base = 1;
    rep(i, 0, 40) {
        pw[i] = base;
        base *= 3;
    }
}
 
void Init() {
    scanf("%I64d", &n);
}
 
int Solve() {
    int pos = lower_bound(pw, pw + 40, n) - pw;
    ll ans = pw[pos], tmp = 0;
    while (1) {
        pos--;
        if (pos < 0) break;
        tmp += pw[pos];
        if (tmp >= n) ans = min(ans, tmp), tmp -= pw[pos];
    }
    return printf("%I64d\n", ans);
}

D. Too Many Segments

数据结构 贪心

题意

$n$ 条线段，令数轴上的点不被超过 $k$ 条线段覆盖，最少需删除几条线段。

$1 \le k \le n \le 2 \cdot 10^5$

$1 \le l_i \le r_i \le 2 \cdot 10^5$

题解

从左往右扫描数轴上的点
若当前点不满足条件，则需要移除线段
贪心策略：
- 覆盖当前点的线段中
- 右端点最靠右边的线段，可能影响的点数最多
- 因此优先移除
可用优先队列维护
技巧： 对于每条线段，记录左端点和右端点 + 1

代码

const int N = (int)2e5+7;

// ------- 变量 ------- //

int n, k;
vector <pii> vl[N];
int vr[N];

// ------- 函数 ------- //

void Init() {
    scanf("%d%d", &n, &k);
    memset(vr, 0, sizeof(vr));
    rep(i, 1, N) vl[i].clear();
    rep(i, 0, n) {
        int l, r; scanf("%d%d", &l, &r);
        vl[l].pb(mp(r, i + 1));
        vr[r+1]++;
    }
}

int Solve() {
    vi ans;
    priority_queue <pii> Q;
    int cur = 0;
    rep(i, 1, N) {
        cur -= vr[i];
        for (auto o : vl[i]) {
            cur++;
            Q.push(o);
        }
        while (cur > k) {
            cur--;
            ans.pb(Q.top().se);
            vr[Q.top().fi+1]--;
            Q.pop();
        }
    }
    printf("%d\n", sz(ans));
    rep(i, 0, sz(ans)) printf("%d%c", ans[i], " \n"[i==sz(ans)-1]);
    return 0;
}

E. By Elevator or Stairs?

dp

题意

$n$ 层楼，给出每层楼之间走楼梯 $a[\ ]$ 和乘电梯的代价 $b[\ ]$ 以及电梯启动的代价 $c$ ，求，从 $1$ 层到每一层的最短时间。

题解

$dp[i][0]$ 表示从第 $i-1$ 层走楼梯到第 $i$ 层的最短时间

$dp[i][1]$ 表示从第 $i-1$ 层乘电梯到第 $i$ 层的最短时间

代码

const int N = (int)2e5+7;
 
// ------- 变量 ------- //
 
int n, c, a[N], b[N], ans[N][2];
 
// ------- 函数 ------- //
 
void Init() {
    scanf("%d%d", &n, &c);
    rep(i, 1, n) scanf("%d", a+i);
    rep(i, 1, n) scanf("%d", b+i);
}
 
int Solve() {
    ans[1][0] = 0; ans[1][1] = INF;
    rep(i, 2, n+1) {
        ans[i][0] = min(ans[i-1][0], ans[i-1][1]) + a[i-1];
        ans[i][1] = min(ans[i-1][0] + c + b[i-1], ans[i-1][1] + b[i-1]);
    }
    rep(i, 1, n+1) printf("%d%c", min(ans[i][0], ans[i][1]), " \n"[i==n]);
    return 0;
}

F. Maximum Weight Subset

dp 树

题意

$n$ 个节点的树，点权 $a[\ ]$ ，求最大点权和的节点子集，且子集内节点之间的距离大于 $k$ 。

$1 \le n,k \le 200$

$1 \le a_i \le 10^5$

题解

$dp[u][dep]$ 表示

在以 $u$ 为根的子树中，
选择满足约束条件的节点子集，所能获得的最大点权和，
且子集中所有节点距离根节点至少有 $dep$ 距离

设树根为 $1$ ，则答案为 $dp[1][0]$

设当前根节点为 $u$ ，距离限制为 $dep$ ，则

当 $dep = 0$ 时

$dp[u][dep] = a[u] + dp[v][k]$
当 $dep \neq 0$ 时

$dp[u][dep] = max{\ dp[v][dep-1] + \sum dp[other][max(dep-1, k-dep)]\ }$

此时 $dp$ 值表示的是恰好距离为 $dep$ ，因此，求前缀最值

per(dep, 0, k+1) dp[u][dep] = dp[v][dep+1];

代码

const int N = (int)2e3+7;

// ------- 变量 ------- //

int n, k, a[N], dp[N][N], pre[N], suf[N];
vi _e[N], e[N];

// ------- 函数 ------- //

void _dfs(int u, int f = 0) {
    for (auto v : _e[u]) if (v != f) {
        e[u].pb(v);
        _dfs(v, u);
    }
}

void dfs(int u) {
    for (auto v : e[u]) dfs(v);
    pre[0] = suf[sz(e[u])+1] = 0;
    per(dep, 0, k+1) {
        if (dep == 0) {
            dp[u][dep] = a[u];
            for (auto v : e[u]) dp[u][dep] += dp[v][k];
        } else {
            rep(i, 0, sz(e[u])) {
                int v = e[u][i];
                pre[i+1] = pre[i] + dp[v][max(dep-1, k-dep)];
            }
            per(i, 0, sz(e[u])) {
                int v = e[u][i];
                suf[i+1] = suf[i+2] + dp[v][max(dep-1, k-dep)];
            }
            dp[u][dep] = 0;
            rep(i, 0, sz(e[u])) {
                int v = e[u][i];
                dp[u][dep] = max(dp[u][dep], dp[v][dep-1] + suf[i+2] + pre[i]);
            }
        }
        if (dep < k) dp[u][dep] = max(dp[u][dep], dp[u][dep+1]);
    }
}

void Init() {
    scanf("%d%d", &n, &k);
    rep(i, 1, n+1) _e[i].clear(), e[i].clear();
    rep(i, 1, n+1) scanf("%d", a+i);
    rep(i, 1, n) {
        int u, v; scanf("%d%d", &u, &v);
        _e[u].pb(v); _e[v].pb(u);
    }
    _dfs(1);
}

int Solve() {
    dfs(1);
    return printf("%d\n", dp[1][0]);
}

Codeforces Round #595 (Div. 3)