AtCoder Beginner Contest 359

A - Count Takahashi (abc359 A)

题目大意

给定\(n\)个字符串,问有多少个字符串是Takahashi

解题思路

注意判断比较即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int ans = 0;
    while (n--) {
        string s;
        cin >> s;
        ans += s == "Takahashi";
    }
    cout << ans << '\n';

    return 0;
}



B - Couples (abc359 B)

题目大意

给定\(n\)个数字,问有多少个数字,其左右两个数字相同。

解题思路

枚举中间的数字,然后判断其左右俩数字是否相同即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    n *= 2;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    int ans = 0;
    for (int i = 1; i < n - 1; ++i) {
        ans += a[i - 1] == a[i + 1];
    }
    cout << ans << '\n';

    return 0;
}



C - Tile Distance 2 (abc359 C)

题目大意

给定一个坐标系,有格子,如下:

给定起点和终点,问从起点到终点,要穿过多少次蓝线。

解题思路

观察上述格子,可以发现在\(y\)轴移动,每移动一次,必定穿过一次蓝线。

由于每行格子交错排列的,每往上走一个,我左右可走的区间都扩大了\(1\)。比如我在\((5,0)\),我可以左边往上走到\((3,1) \to (5,1)\)的格子,也可以右边往上走到\((5,1) \to (7,1)\)

这样,原本我左右走的横坐标区间是\([4,6)\),往上走一格后,横坐标区间扩大为\([3,7)\),往上走\(n\)格,可到达的横坐标区间范围为\([4-n, 6+n)\),只要我终点的横坐标在这区间,那我就可以只花费\(y\)轴移动的代价就抵达终点了。而如果不在这个区间,那就再左右移动,每移动一次,横坐标区间就变动\(2\)

容易发现这样移动一定是最优的。\(y\)轴移动的蓝线穿过不可避免,然后\(x\)轴的蓝线穿过已经尽可能在移动\(y\)轴时避免了。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    LL sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    LL dy = abs(sy - ty);
    LL odd = (sx & 1);
    LL l = sx - odd + (sy & 1) * (odd ? 1 : -1);
    LL r = l + 2;
    l -= dy, r += dy;
    LL ans = dy + max(0ll, l - tx + 1) / 2 + max(0ll, tx - r + 2) / 2;
    cout << ans << '\n';

    return 0;
}



D - Avoid K Palindrome (abc359 D)

题目大意

给定一个包含AB?的字符串\(s\),将?变成AB,问有多少种情况,使得\(s\)没有长度为\(k\)的回文子串。

解题思路

注意\(k \leq 10\)

从左到右考虑每个字符,如果当前是?,则考虑其变为A,B,是否出现长度为\(k\)的回文串。

我们需要知道该?\(k-1\)位的情况,加上该字母,就可以判断出新增的子串是不是回文串。

即设\(dp[i][j]\)表示考虑前\(i\)位字符,其中?都已经替换成AB后,且后\(9\)位的字符状态为\(j\)(因为只有AB两种,可以编码成01,用二进制压缩表示)。

然后考虑当前位的情况,如果取值为A\(0\),则判断\(j << 1\)状态是不是回文串,不是的话则有\(dp[i+1][(j<<1) \& mask] += dp[i][j]\),否则就状态非法,不转移。因为\(j<<1\)是后\(10\)个字符的状态信息,而\(j\)的含义是后\(9\)位,所以\(\& mask\)是把第\(10\)位去掉。

同理,取值为\(B\)的话,即\(1\),则判断\((j << 1) | 1\)是不是回文串,不是的话就转移,否则不转移。

可以事先预处理每个状态是否是回文串,然后当\(i \geq k\)时再考虑转移的合法性。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int mo = 998244353;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    string s;
    cin >> n >> k >> s;
    int up = (1 << k);
    vector<int> p(up);
    for (int i = 0; i < up; i++) {
        vector<int> bit(k);
        int num = i;
        for (int j = 0; j < k; j++) {
            bit[j] = (num & 1);
            num >>= 1;
        }
        auto rev = bit;
        reverse(rev.begin(), rev.end());
        p[i] = rev == bit;
    }

    up = 1 << (k - 1);
    int mask = up - 1;
    vector<int> dp(up, 0);
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        int chr = s[i];
        vector<int> dp2(up, 0);
        for (int j = 0; j < up; j++) {
            if (chr == '?') {
                if (i + 1 < k || !p[j << 1]) {
                    int nxt = (j << 1) & mask;
                    dp2[nxt] = (dp2[nxt] + dp[j]) % mo;
                }
                if (i + 1 < k || !p[j << 1 | 1]) {
                    int nxt = (j << 1 | 1) & mask;
                    dp2[nxt] = (dp2[nxt] + dp[j]) % mo;
                }
            } else {
                if (i + 1 < k || !p[j << 1 | (chr - 'A')]) {
                    int nxt = (j << 1 | (chr - 'A')) & mask;
                    dp2[nxt] = (dp2[nxt] + dp[j]) % mo;
                }
            }
        }
        dp.swap(dp2);
    }
    LL ans = 0;
    for (int i = 0; i < up; i++) {
        ans = (ans + dp[i]) % mo;
    }
    cout << ans << '\n';
    return 0;
}



E - Water Tank (abc359 E)

题目大意

给定柱子长度。然后如下如所示。

每一时刻,\(0\)位会多一高度的水,如果该水高度高过柱子,且高过\(1\)位的水高度,则该高度的水会跑到\(1\)位,同理继续判断\(1\)位,该水是否跑到\(2\)位。

问每一位出现水的最早时刻。

解题思路

  • 考虑\(1\)位,其答案就是第一根柱子高度\(3(a_1)+1\)

  • 考虑\(2\)位,需要\(0\)位水高\(3\)\(1\)位水高\(1\),答案就是\(3+1+1\)

  • 考虑\(3\)位,则需要\(0,1,2\)的水高均为\(4\),答案就是\(4+4+4+1\)

  • 考虑\(4\)位,则需要\(0,1,2\)水高\(4\)\(3\)位水高\(1\),答案就是\(4+4+4+1+1\)

  • 考虑\(5\)位,则需要\(0,1,2,3,4,\)位水高\(5\),答案就是\(5+5+5+5+5+1\)

观察上述例子的求解过程,如果要求第\(i\)位的答案,则要求第\(i-1\)装满,装满的意思就是和柱子\(a_i\)高度同高,而同高会连带着\(i-2,i-3,...\)位同高,但需要多少位呢?观察上述会发现,假设前面比柱子\(a_i\)还高的柱子是\(a_j\),那么\(j,j+1,...,i-1\)位的水高都必须是\(a_i\)

因此,求解第\(i\)位的答案,则需要\(i-1,i-2,...,j\)位与\(a_i\)同高,然后\(j-1,j-2,...,k\)\(a_j\)同高,然后\(k-1,k-2,...\)\(a_k\)同高,其中\(a_i \leq a_j \leq a_k\),也就是说需要维护一个从左到右,柱子高度单调递减的序列,这可以用栈维护,即单调栈,栈底是最左边,栈顶是最右边。在维护递减高度时,顺带维护每个递减区间的水高度总和即可。

, 神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> h(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> h[i];
    h[0] = 1e9 + 8;
    vector<int> hei;
    hei.push_back(0);
    LL ans = 0;
    for (int i = 1; i <= n; ++i) {
        while (!hei.empty() && h[hei.back()] <= h[i]) {
            ans -= h[hei.back()] * (LL)(hei.back() - hei[hei.size() - 2]);
            hei.pop_back();
        }
        ans += h[i] * (LL)(i - hei.back());
        hei.push_back(i);
        cout << ans + 1 << " \n"[i == n];
    }

    return 0;
}



F - Tree Degree Optimization (abc359 F)

题目大意

给定\(n\)个点的点权\(a_i\),构造一棵树,使得\(\sum_{i=1}^{n} d_i^2a_i\)最小,其中\(d_i\)表示点\(i\)的度。

解题思路

由于是一棵树,则有\(\sum d_i = 2n-2, 1 \leq d_i \leq n - 1\)

对于任意满足上述条件的\(d_i\),都可以构造出对应的树,使得每个点的度数都是\(d_i\)。(构造方法为,每次选择度数为1和非1的点连边,然后更新剩余度数,归纳可证)

那剩下就是如何分配这些度数。

如果给点\(1\)分配一个度,是其\(d_1 = 1 \to 2\),则代价是\(4a_1 - a_1\),而如果是\(d_1 = 2 \to 3\),则代价是\(9a_1 - 4a_1\)

这可以把问题抽象成每个点起始度数为\(1\),然后把剩下的\(n-2\)个度分配给每个点,使得代价最小,每次仅分配\(1\)的度,那我肯定是贪心的分配给代价最小的点。

用优先队列维护上述代价即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>>
        q;
    LL ans = accumulate(a.begin(), a.end(), 0ll);
    for (int i = 0; i < n; i++) {
        q.push({a[i] * 3ll, 2});
    }
    for (int i = 0; i < n - 2; i++) {
        auto [x, y] = q.top();
        q.pop();
        ans += x;
        if (y < n - 1) {
            LL ori = x / (2 * y - 1);
            LL nxt = ori * (2 * y + 1);
            q.push({nxt, y + 1});
        }
    }
    cout << ans << '\n';

    return 0;
}



G - Sum of Tree Distance (abc359 G)

题目大意

给定一棵树,点有点权\(a_i\)。求\(\sum_i \sum_j f(i,j)\),其中\(a_i == a_j\)\(f(i,j)\)表示点\(i \to j\)的距离,边权为\(1\)

解题思路

距离的最终来源是边数,考虑每条边被算入了多少次,即对答案贡献的次数。

\(\sum_i \sum_j f(i,j) = \sum_e sum_e\),其中\(sum_e\)表示边\(e\)对答案贡献的次数,考虑该次数怎么算。

考虑边\((u,v)\),将该树分成了两个连通块,如果这两个连通块各有一点\(i,j\),其\(a_i == a_j\),那么从点\(i \to j\)必定经过该边,因此需要统计每个点权,在两个连通块的出现次数,其乘积的和则是该边的贡献。

问题就变成了统计一个子树里,各个点权的出现次数\(cc_i\),事先预处理每个点权的出现次数\(cnt_i\),对点权求和,即\(\sum cc_i \times (cnt_i - cc_i)\)就是该边对答案的贡献。

由于点权是稀疏的,用map来维护出现次数,合并儿子之间的map,采用启发式合并,即用数量少的合并到数量大的,这样每次合并最坏的复杂度是\(O(\frac{n}{2})\),而最坏的情况最多只有\(O(\log n)\)次(每一次最坏情况,合并后的点数会翻倍,最多翻倍\(O(\log n)\)次。

合并的时候,计算边贡献的式子,\(\sum cc_i \times (cnt_i - cc_i)\)只有一项发生变化,可以动态\(O(1)\)维护出更新后的贡献\(sum\)

最终的时间复杂度就是\(O(n \log^2 n)\),一个\(\log\)是启发式合并,另一个\(\log\)map

代码里的\(sum\)是考虑父亲边\(u \to fa\)对答案的贡献。由于返回类型是\(pair\),用\(map\)构造\(pair\)会复制构造造成巨大的性能损失,用\(move\)函数进行移动构造。或者返回值仅为\(map\),编译器也会优化成移动构造。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> edge(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    vector<int> a(n);
    vector<int> cnt(n);
    for (auto& x : a) {
        cin >> x;
        --x;
        cnt[x]++;
    }
    LL ans = 0;
    auto dfs = [&](auto& dfs, int u, int fa) -> pair<map<int, int>, LL> {
        map<int, int> cc;
        LL sum = 0;
        for (auto v : edge[u]) {
            if (v == fa)
                continue;
            auto&& [son_ret, son_sum] = dfs(dfs, v, u);
            if (son_ret.size() > cc.size()) {
                swap(son_ret, cc);
                swap(son_sum, sum);
            }
            for (auto& [k, v] : son_ret) {
                sum -= 1ll * cc[k] * (cnt[k] - cc[k]);
                cc[k] += v;
                sum += 1ll * cc[k] * (cnt[k] - cc[k]);
            }
        }
        sum -= 1ll * cc[a[u]] * (cnt[a[u]] - cc[a[u]]);
        cc[a[u]]++;
        sum += 1ll * cc[a[u]] * (cnt[a[u]] - cc[a[u]]);
        ans += sum;
        return {move(cc), sum};
    };
    dfs(dfs, 0, 0);
    cout << ans << '\n';

    return 0;
}



热门相关:恐怖复苏   痴情错付   战神小农民   我的抖音太无敌   灭世之门