Codeforces Round 701 Div2

比赛链接

A - Add and Divide

Description

题目链接

Solution

由于 $\lfloor \frac{a}{b+1} \rfloor \le \frac{a}{b}$，故先对 $b$ 增值再进行除法运算更优，因此暴力枚举 $b$ 增值的次数再计算做除法的次数即可。容易证明操作次数最少时 $b$ 增值的次数不会超过 $10$ 次。

Code

Add and Divide

void solve() {
    LL a, b;
    cin >> a >> b;
    LL ans = INT_MAX;
    for (int j = 0; j <= 10; j++) {
        if (j == 0 && b == 1) continue;
        LL tmp = 0;
        while (qpow(b + j, tmp) <= a) tmp++;
        ans = min(ans, tmp + j);
    }
    cout << ans << endl;
}

B - Replace and Keep Sorted

Description

题目链接

Solution

对于数组 $b$ 的第 $i$ 位，其取值在 $[a_{i-1}+1,a_i)∪(a_i,a_{i+1}-1]$ 内，共 $f_{i} = a_{i+1}-a_{i-1}-2$ 个。对于区间 $[l,r]$，能生成的不同的数组 $b$ 共有 $\sum \limits_{l \le i \le r} f_i = a_{r+1}+a_{r}-a_{l}-a_{l-1}-2*(r-l+1)$ 个，其中规定 $a_{r+1}=k+1$，$a_{l-1} = 0$。

Code

Replace and Keep Sorted

const int MAXN = 1E5 + 5;
int n, q, k, a[MAXN];
 
void solve() {
    cin >> n >> q >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    a[0] = 0, a[n + 1] = k + 1;
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        cout << k + 1 + a[r] - a[l] - 2 * (r - l + 1) << endl;
    }
}

C - Floor and Mod

Description

题目链接

Solution

设 $a=kb+r$，由 $\lfloor \frac{a}{b} \rfloor = a \mod b$ 解得 $k=r$，即 $a = k(b+1)$，且 $b>k$。因为 $k^2 \le kb+k \le x$， 故 $k \le \sqrt{x}$。又由于 $1\le kb+k \le x$，故有 $k < b \le \frac{x}{k}-1$。我们在 $\sqrt{x}$ 内枚举 $k$，对每一个 $k$ 容易求出满足条件的 $b$ 的个数。

Code

Floor and Mod

void solve(int testNum) {
    int x, y;
    cin >> x >> y;
    LL ans = 0;
    for (int k = 1; k <= sqrt(x); k++) ans += max(0, min(y, x / k - 1) - k);
    cout << ans << endl;
}

D - Multiples and Power Differences

Description

题目链接

Solution

$1,2,....,16$ 的最小公倍数是 $720720$，因此先将每个数变为 $720720$，对于 $i+j$ 是偶数的位置，再加上 $a_{i,j}^2$ 即可。

Code

Multiples and Power Differences

const int MAXN = 505;
int n, m, a[MAXN][MAXN];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            if ((i + j) % 2 == 0)
                a[i][j] = 720720 + pow(a[i][j], 4);
            else
                a[i][j] = 720720;
        }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cout << a[i][j] << " ";
        cout << endl;
    }
}

E - Move and Swap

Description

题目链接

Solution

设 $dp[i]$ 表示红色硬币在节点 $i$，以该节点为起点继续移动能获得的最大分数。我们按层次从大到小进行状态转移，设当前为第 $l$ 层，第 $[l+1,d]$ 层节点的结果已求出，该层红色硬币位于节点 $i$，蓝色硬币位于节点 $p$。考虑这两个硬币接下来的移动，由题意有如下两种情况：

• 红蓝硬币不交换位置，则红色硬币下一步移向 $i$ 节点的所有儿子中能获得分数最大的那一个，蓝色硬币相应地移至下一层能使得分最大的节点，此时有 $dp_i = \max \limits_{j∈Son_i} {dp_j}+|a_i-a_p|$。

• 红蓝硬币交换位置，则红色硬币下一步移向 $p$ 节点的所有儿子中能获得分数最大的那一个，此时有 $dp_i = \max \limits_{j∈Son_p} {dp_j}+|a_i-a_p|$。根据 $a_p$ 和 $a_i$ 的大小关系有如下两种情况：

  • $a_p \le a_i$，则 $dp_i = a_i + (\max \limits_{j∈Son_p} {dp_j} - a_p)$

  • $a_p \ge a_i$，则 $dp_i = -a_i + (\max \limits_{j∈Son_p} {dp_j} + a_p)$

将每一层的节点按 $a$ 从小到大排序。要使 $dp_i$ 最大，对于第一种情况，$a_p$ 为该层最大值或最小值；对于第二种情况，将排序后的节点扫一遍，对 $\max \limits_{j∈Son_p} {dp_j} - a_p$ 记录前缀最大值，对 $\max \limits_{j∈Son_p} {dp_j} + a_p$ 记录后缀最大值即可。

Code

Move and Swap

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl
#define int long long

using namespace std;
typedef long long LL;

template <class T>
void read(T& x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

template <class T, class... Args>
void read(T& x, Args&... args) {
    read(x), read(args...);
}

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, m, d, dp[MAXN], a[MAXN], mxSonVal[MAXN], fa[MAXN];
int pre[MAXN], pos[MAXN];
vector<int> G[MAXN];
vector<pair<int, int> > v[MAXN];

void dfs1(int now, int f, int level) {
    v[level].push_back(make_pair(a[now], now));
    fa[now] = f;
    d = max(d, level);
    for (auto& to : G[now])
        if (to != f) dfs1(to, now, level + 1);
}

void levelDp() {
    for (int level = d; level >= 0; level--) {
        int cnt = v[level].size();
        for (int i = 0; i < cnt; i++) {
            int node = v[level][i].second;
            dp[node] =
                max(dp[node],
                    mxSonVal[node] + max(a[node] - v[level][0].first,
                                         v[level][cnt - 1].first - a[node]));
        }
        for (int i = 0; i < cnt; i++) {
            int node = v[level][i].second;
            if (i == 0)
                pre[i] = -a[node] + mxSonVal[node];
            else
                pre[i] = max(pre[i - 1], -a[node] + mxSonVal[node]);
        }
        for (int i = cnt - 1; i >= 0; i--) {
            int node = v[level][i].second;
            if (i == cnt - 1)
                pos[i] = a[node] + mxSonVal[node];
            else
                pos[i] = max(pos[i + 1], a[node] + mxSonVal[node]);
        }
        for (int i = 0; i < cnt; i++) {
            int res = 0;
            int node = v[level][i].second;
            res = max({res, pre[i] + a[node], pos[i] - a[node]});
            dp[node] = max(dp[node], res);
            mxSonVal[fa[node]] = max(mxSonVal[fa[node]], dp[node]);
        }
    }
}

void solve(int caseNum) {
    read(n);
    for (int i = 2; i <= n; i++) {
        int v;
        read(v);
        G[i].push_back(v);
        G[v].push_back(i);
    }
    for (int i = 2; i <= n; i++) read(a[i]);
    dfs1(1, 1, 0);
    for (int i = 1; i <= n; i++) sort(v[i].begin(), v[i].end());
    levelDp();
    printf("%lld\n", dp[1]);
    for (int i = 0; i <= n; i++) {
        G[i].clear(), v[i].clear();
        dp[i] = 0, mxSonVal[i] = 0;
    }
    d = 0;
}

signed main() {
    int testCase = 1;
    read(testCase);
    for (int i = 1; i <= testCase; i++) solve(i);
    return 0;
}

F - Copy or Prefix Sum

Description

题目链接

Comment

题解中提到的做法很有意大利风格…

Solution

设 $dp_{i,j}$ 表示满足题目条件的长度为 $i$，和为 $j$ 的数列 $a$ 的个数。如果 $b_i = a_i$，那么对 $\forall j \neq 0,dp_{i+1,j+b_i}=dp_{i,j}$；如果 $b_i = \sum \limits_{j=1}^{i}a_j$，则对 $\forall j, dp_{i+1,b_i} = \sum dp_{i,j}$。我们用一个 $map$ 维护 $dp$，每一次更新实际上是对 $map$ 中所有元素的第一关键字加一个值，第二关键字不变，之后再修改某一个元素的第二关键字为所有元素第二关键字的和。上述过程用 Venice Technique 便可轻松实现。

Code

Copy or Prefix Sum

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl
#define int long long

using namespace std;
typedef long long LL;

template <class T>
void read(T& x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

template <class T, class... Args>
void read(T& x, Args&... args) {
    read(x), read(args...);
}

const int MOD = 1E9 + 7;
int n, T;

struct VeniceSet {
    map<int, int> dp;
    int waterLevel = 0;
    int sumDp = 1;
    VeniceSet(int v) { dp[v] = 1; }
    void addSum(int v) { sumDp = (sumDp + v) % MOD; }
    void change(int v, int res) { dp[v + waterLevel] = res % MOD; }
    int get(int v) { return dp[v + waterLevel]; }
    void remove(int v) { dp[v + waterLevel] = 0; }
    void updateAll(int v) { waterLevel += v; }
    int size() { return dp.size(); }
};

signed main() {
    read(T);
    while (T--) {
        read(n);
        int b;
        read(b);
        VeniceSet mySet(b);
        for (int i = 2; i <= n; i++) {
            read(b);
            mySet.updateAll(-b);
            int tmp = mySet.get(b);
            mySet.change(b, mySet.sumDp);
            mySet.addSum(-tmp + mySet.sumDp);
        }
        printf("%lld\n", (mySet.sumDp + MOD) % MOD);
    }
    return 0;
}