AtCoder Beginner Contest 221

比赛链接

D Online games

Description

题目链接

Solution

离散化后做差分。设离散化前相邻两个修改位置为 $X_i$，$X_{i+1}$，离散化后的修改位置为 $i,i+1$，那么对差分数组求和（记为 $Sum$）后，答案为 $Sum_i$ 的天数会加上 $X_{i+1}-X_i$，开个桶统计下答案即可。

Code

Online games

#include <bits/stdc++.h>

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

using namespace std;
typedef long long LL;

const int MAXN = 4E5 + 5;
const int MOD = 1E9 + 7;
int n, last;
int a[MAXN], b[MAXN], from[MAXN], sum[MAXN], ans[MAXN];
vector<int> v;
unordered_map<int, int> mp;

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        b[i] = b[i] + a[i];
        v.push_back(a[i]), v.push_back(b[i]);
    }
    sort(v.begin(), v.end());
    last = unique(v.begin(), v.end()) - v.begin();
    for (int i = 0; i < last; i++) mp[v[i]] = i + 1, from[i + 1] = v[i];
    for (int i = 1; i <= n; i++) sum[mp[a[i]]]++, sum[mp[b[i]]]--;
    for (int i = 1; i <= last; i++) {
        sum[i] += sum[i - 1];
        if (i < last)
            ans[sum[i]] += (from[i + 1] - from[i]);
        else
            ans[sum[i]] += 1;
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    return 0;
}

E LEQ

Description

题目链接

Solution

设 $A_x \le A_i,x < i$，那么由 $(A_x,A_{x+1},\dots,A_i)$ 生成的包含端点的子序列个数为 $2^{i-x-1} = 2^{i-1}2^{-x}$。容易发现 $A_x$ 会贡献 $2^{-x}$，将所有小于等于 $A_i$ 的 $A_x$ 的贡献加起来（可使用值域树状数组快速求解）再乘以 $2^{i-1}$ 即可。

Code

LEQ

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
#define int long long

const int MAXN = 3E5 + 5;
const int MOD = 998244353;

vector<int> v;
unordered_map<int, int> mp;
int n, a[MAXN];

void desc() {
    sort(v.begin(), v.end());
    int m = unique(v.begin(), v.end()) - v.begin();
    for (int i = 0; i < m; i++) mp[v[i]] = i + 1;
}

LL qpow(LL a, LL b, LL MOD) {
    LL ans = 1, base = a % MOD;
    while (b) {
        if (b & 1) ans = ans * base % MOD;
        b >>= 1, base = base * base % MOD;
    }
    return ans;
}

struct BIT {  // Binary Index Trees, 1based
    int lowbit(int x) { return x & (~x + 1); }
    /* O(n) build tree*/
    BIT() {
        for (int i = 1; i <= n; i++) c[i] = 0;
    }
    void build() {
        for (int i = 1; i <= n; i++) {
            int j = i + lowbit(i);  // j is father of i
            if (j <= n) c[j] += c[i];
        }
    }
    /*@param x the position to add val*/
    void add(int x, LL val) {
        val %= MOD;
        while (x <= n) (c[x] += val) %= MOD, x += lowbit(x);
    }
    /*range [1, x] sum query*/
    LL query(int x, LL res = 0) {
        while (x) (res += c[x]) %= MOD, x -= lowbit(x);
        return res;
    }
    array<LL, MAXN> c;
} bit[3];
/*range [l, r] add val*/
inline void add(int l, int r, LL val) {
    bit[1].add(l, val), bit[1].add(r + 1, -val);
    bit[2].add(l, val * l), bit[2].add(r + 1, -val * (r + 1));
}
/*range [l, r] sum query*/
inline LL query(int l, int r, LL res = 0) {
    res =
        (bit[0].query(r) + bit[1].query(r) * (r + 1) % MOD - bit[2].query(r)) %
        MOD;
    res %= MOD;
    res -= (bit[0].query(l - 1) + bit[1].query(l - 1) * l % MOD -
            bit[2].query(l - 1)) %
           MOD;
    return (res % MOD + MOD) % MOD;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], v.push_back(a[i]);
    desc();
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int id = mp[a[i]];
        ans = (ans + query(1, id) * qpow(2, i - 1, MOD) % MOD) % MOD;
        add(id, id, qpow(qpow(2, i, MOD), MOD - 2, MOD));
    }
    cout << ans;
    return 0;
}

F Diameter set

Description

题目链接

Solution

首先求出树的直径，设为 $D$，直径上的点依次记为 $V_0,V_1,\dots,V_D$。下面对直径分奇偶讨论：

1. D 为奇数
   设 $A=V_{\frac{D-1}{2}}$, $B = V_{\frac{D+1}{2}}$。割掉连接 $A,B$ 的边，得到两个子树 $T_A,T_B$。易证 $T_A$ 中任意两点距离不超过 $D-1$，$T_B$ 中任意两点距离不超过 $D-1$，因此距离为 $D$ 的两点只能一个在 $T_A$ 中，一个在 $T_B$ 中。设 $T_A$ 中和 $A$ 距离为 $\frac{D-1}{2}$ 的点有 $M_1$ 个，$T_B$ 中和 $B$ 距离为 $\frac{D-1}{2}$ 的点有 $M_2$ 个，那么答案为 $M_1M_2$。
2. D 为偶数
   设 $C=V_{\frac{D}{2}}$。将 $C$ 以及它所连的边（设有 $k$) 条删去，得到 $k$ 个子树，记为 $T_1,T_2,\dots,T_k$，它们的根为 $R_1,R_2,\dots,R_k$。易证 $T_i$ 中任意两点距离不超过 $D-2$。因此符合条件的点集中，任意两点不在同一子树中。设 $T_i$ 中和 $R_i$ 距离为 $\frac{D}{2}-1$ 的点有 $M_i$ 个，那么答案为 $(M_1+1)(M_2+1)\dots(M_k+1)-(M_1+M_2+\dots+M_k)-1$。

Code

Diameter set

#include <bits/stdc++.h>

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

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 998244353;

int n, D, ed;
vector<int> G[MAXN];
array<int, MAXN> pre, dis;

inline void dfs1(int cur, int fa) { // 求直径
    for (auto &to : G[cur]) {
        if (to == fa) continue;
        dis[to] = dis[cur] + 1, pre[to] = cur;
        if (dis[to] > D) D = dis[to], ed = to;
        dfs1(to, cur);
    }
}

void getDia() {
    dfs1(1, 0);
    dis[ed] = 0, pre[ed] = -1, D = 0;
    dfs1(ed, 0);
}

int getNode(int ed, int d) {
    while (d) ed = pre[ed], d--;
    return ed;
}

int dfs2(int now, int fa, int d) { // 求到 now 距离为 d 的点的个数
    if (!d) return 1;
    int ans = 0;
    for (auto &to : G[now]) {
        if (to == fa) continue;
        ans += dfs2(to, now, d - 1);
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }
    getDia();
    if (D % 2 == 0) {
        int center = getNode(ed, D / 2);
        vector<int> v;
        for (auto &to : G[center]) v.push_back(dfs2(to, center, D / 2 - 1));
        LL tmp = 1;
        for (auto &sz : v) tmp = tmp * (sz + 1) % MOD;
        tmp--;
        for (auto &sz : v) tmp -= sz;
        cout << (tmp % MOD + MOD) % MOD;
    } else {
        int a = getNode(ed, (D - 1) / 2);
        int b = getNode(ed, (D + 1) / 2);
        int m1 = dfs2(a, b, D / 2);
        int m2 = dfs2(b, a, D / 2);
        cout << 1ll * m1 * m2 % MOD;
    }
    return 0;
}

G Jumping sequence

Description

题目链接

Solution

将坐标系顺时针旋转 $45°$，再施加 $\sqrt{2}$ 的缩放，得到新的坐标系 $(X+Y,X-Y)$。在这个坐标系中，向上移动表示为 $(+D,-D)$，向下移动表示为 $(-D,+D)$，向左移动表示为 $(-D,-D)$，向右移动表示为 $(+D,+D)$，从而问题转化为找到两个 $+1,-1$ 序列 $s,s'$，使得

$\sum\limits_{i=1}^{N} s_iD_i=A+B,\sum\limits_{i=1}^{N} s'_iD_i=A-B$

定义 $S=\sum\limits_{i=1}^{N}D_i$，那么问题可以继续转化为找到 $0,1$ 序列 $t,t'$，满足

$\sum\limits_{i=1}^{N} t_iD_i=\frac{S+A+B}{2},\sum\limits_{i=1}^{N} t'_iD_i=\frac{S+A-B}{2}$

显然上述等式右边小于零，大于 $S$，或者不是偶数时无解。否则，设 $dp[i][s]$ 表示考虑前 $i$ 个数，和为 $s$ 的方案是否存在，我们可以在 $O(NS)$ 时间内求解。由于 $NS$ 可达 $7.2*10^9$，朴素 $DP$ 无法通过此题。考虑到我们只关心方案是否存在，因此可用 $bitset$ 优化。

判断完可行性后，从终态倒着往前推，枚举四个方向，看之前的状态是否可行来确定每一步的方向。

Code

Jumping sequence

#include <bits/stdc++.h>

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

using namespace std;
typedef long long LL;

const int MAXN = 2E3 + 5;
const int MOD = 1E9 + 7;
int n, st, ed, sumd;
array<int, MAXN> d;
bitset<3600001> dp[MAXN];

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> st >> ed;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
        sumd += d[i];
    }
    int a = sumd + st + ed, b = sumd + st - ed;
    if (b < 0 || a < 0 || a % 2 || b % 2 || a / 2 > sumd || b / 2 > sumd)
        return cout << "No", 0;
    a /= 2, b /= 2;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) dp[i] = dp[i - 1] | (dp[i - 1] << d[i]);
    if (!dp[n][a] || !dp[n][b]) return cout << "No", 0;
    cout << "Yes\n";
    // u10,d01,l00,r11
    string ans = "";
    for (int i = n; i >= 1; i--) {
        if (a - d[i] >= 0 && b - d[i] >= 0 && dp[i - 1][a - d[i]] &&
            dp[i - 1][b - d[i]])
            a -= d[i], b -= d[i], ans = "R" + ans;
        else if (dp[i - 1][a] && dp[i - 1][b])
            ans = "L" + ans;
        else if (b - d[i] >= 0 && dp[i - 1][a] && dp[i - 1][b - d[i]])
            b -= d[i], ans = "D" + ans;
        else
            a -= d[i], ans = "U" + ans;
    }
    cout << ans;
    return 0;
}

H Count Multiset

Description

题目链接

Solution

将 multiset 中元素从小到大排列，记为 $A_1,A_2,\dots,A_k$。

令 $B_1 = A_1$，$B_i = A_i-A_{i-1},i\ge 2$，那么问题转化为：

对 $k=1,2,\dots,N$，求满足下面三个条件的序列个数：

• $B_1>0$。
• 不存在长度超过 $M-1$ 的连续的 $0$。
• $\sum\limits_{i=1}^{k}B_i*(k-i+1)=N$。

将 $B$ 翻转，那么上述问题可以继续转化为：

对 $k=1,2,\dots,N$，求满足下面三个条件的序列个数：

• $B_k>0$。
• 不存在长度超过 $M-1$ 的连续的 $0$。
• $\sum\limits_{i=1}^{k}B_i*i=N$。

设 $dp[i][s]$ 表示求满足下列条件的 $B$ 的个数：

• $B_i>0$
• 不存在长度超过 $M-1$ 的连续的 $0$。
• $\sum\limits_{j=1}^{i}B_j*j=N$。

易得状态转移方程：$dp[i][s] = \sum\limits_{j=i-M+1}^{i-1}\sum\limits_{k=1}^{\lfloor \frac{s}{i} \rfloor}dp[j][s-i*k]$。直接转移需要枚举 $i,j,k,s$，时间复杂度 $O(N^3M)$ 无法通过此题。

对状态转移式进行变形，得 $dp[i][s] = \sum\limits_{k=1}^{\lfloor \frac{s}{i} \rfloor}\sum\limits_{j=i-M+1}^{i-1}dp[j][s-i*k] = \sum\limits_{k=1}^{\lfloor \frac{s}{i} \rfloor}(\sum\limits_{j=1}^{i-1}dp[j][s-i*k]-\sum\limits_{j=1}^{i-M+1}dp[j][s-i*k])$。我们先按第一维求和，再对第二维以间隔 $i$ 求和即可在 $O(N^2)$ 时间内完成求解。

Code

Count Multiset

#include <bits/stdc++.h>

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

using namespace std;
typedef long long LL;

const int MAXN = 5E3 + 5;
const int MOD = 998244353;
int n, m;
LL dp[MAXN][MAXN], sum[MAXN][MAXN], tmp[MAXN];

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        if (i <= m)
            for (int s = i; s <= n; s += i) dp[i][s] = 1;
        for (int s = 0, j = i - m; s <= n; s++)
            tmp[s] = ((s >= i ? tmp[s - i] : 0) + sum[i - 1][s] -
                      (j > 0 ? sum[j - 1][s] : 0)) %
                     MOD;
        for (int s = i; s <= n; s++) dp[i][s] = (dp[i][s] + tmp[s - i]) % MOD;
        for (int s = 0; s <= n; s++)
            sum[i][s] = (sum[i - 1][s] + dp[i][s]) % MOD;
    }
    for (int i = 1; i <= n; i++) cout << (dp[i][n] + MOD) % MOD << '\n';
    return 0;
}