首页 > 其他分享 >AtCoder Beginner Contest 359

AtCoder Beginner Contest 359

时间：2024-06-23 17:00:06浏览次数：3  
标签：AtCoder Beginner int sum cin cc using LL 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\)，将?变成A或B，问有多少种情况，使得\(s\)没有长度为\(k\)的回文子串。

解题思路

注意\(k \leq 10\)

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

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

即设\(dp[i][j]\)表示考虑前\(i\)位字符，其中?都已经替换成A或B后，且后\(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)

题目大意

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

example

每一时刻，\(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;
}

标签：AtCoder,Beginner,int,sum,cin,cc,using,LL,359
From： https://www.cnblogs.com/Lanly/p/18263628

相关文章

  • UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)
    A-CountTakahashi(abc359A)解题思路遍历判断即可神奇的代码#include<iostream>#include<algorithm>#include<vector>#include<queue>#include<map>#include<set>#include<cstring>usingnamespacestd;#defineendl'\n......
  • ABC359 G - Sum of Tree Distance
    题目链接题目大意给出一棵树，树上每个节点都有一种颜色，求所有颜色相同的节点两两之间距离的总和。 题解想来写题解主要是看了一下官方解法都写的需要“重心分解”，应该是对应中文语境下的树的点分治。实际上点分治写起来很费事，可以用启发式合并替代。具体来说，dfs时每个节点......
  • UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359) 题
    点我看题A-CountTakahashi没啥好说的点击查看代码#include<bits/stdc++.h>#definerep(i,n)for(inti=0;i<n;++i)#definerepn(i,n)for(inti=1;i<=n;++i)#defineLLlonglong#definefifirst#definesesecond#definepbpush_back#definemprmake_pair......
  • abc359_G Sum of Tree Distance 题解
    题目链接：Atcoder或者洛谷先考虑暴力，显然是枚举整棵树的路径，这个枚举复杂度显示是\(O(n^2)\)，还不考虑计算\(f(i,j)\)，考虑使用点分治优化枚举复杂度：\(O(n\log{n})\)。接下来考虑如何计算每条路径的\(f(i,j)\)，注意到\(f(i,j)\)：当且仅当\(a[i]=a[j]\)时，答案加上\(dis(i,j......
  • AtCoder Beginner Contest 359 解题报告
    AtCoderBeginnerContest359吐槽：A-F还算正常，G题你tm给我放了个出过的板子（ABC340G）是几个意思啊？？？ASimulate.#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineendl'\n'#definePBemplace_back#definePPBpop_back#defineMPmake_pai......
  • AtCoder ABC 358
    比赛链接A-WelcometoAtCoderLandAC_Code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongsignedmain(){strings,t;cin>>s>>t;if(s=="AtCoder"&&t=="Land")co......
  • AtCoder Beginner Contest 357-F
    Problem同步于博客ProblemYouaregivensequencesoflength\(N\),\(A=(A_1,A_2,\ldots,A_N)\)and\(B=(B_1,B_2,\ldots,B_N)\).Youarealsogiven\(Q\)queriestoprocessinorder.Therearethreetypesofqueries:1lrx:Add\(x\)toeachof......
  • AtCoder Beginner Contest 358
    A-WelcometoAtCoderLandvoidsolve(){strings,t;cin>>s>>t;if(s=="AtCoder"&&t=="Land"){cout<<"Yes\n";return;}cout<<"No\n&qu......
  • [atcoder 358] 【动态规划】
    dp[i][j]表示前i个和为j的个数。那么就有递推式dp[i][j]+=dp[i][j-x]*c(j,j-x);其中x满足从0到c[i],并且x满足<=j组合数递推公式c(n,k)=c(n,k-1)+c(n,k);importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;impor......
  • ATcoder ABC 358 补题记录（A~D，G）
    A直接模拟即可。#pragmaGCCoptimize(3)#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1000100,mod=998244353;inta[N];signedmain(){strings,t;cin>>s>>t;if(s=="AtCoder"&&t==&qu......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99