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

AtCoder Beginner Contest 349

时间:2024-04-13 22:56:02浏览次数:36  
标签:AtCoder return Beginner int auto pos cin 349 dp

A - Zero Sum Game (abc349 A)

题目大意

\(n\)个人游戏,每局有一人 \(+1\)分,有一人 \(-1\)分。

给定最后前 \(n-1\)个人的分数,问第 \(n\)个人的分数。

解题思路

零和游戏,所有人总分是 \(0\),因此最后一个人的分数就是前 \(n-1\)个人的分数和的相反数。

神奇的代码
n = input()
print(-sum([int(i) for i in input().split()]))


B - Commencement (abc349 B)

题目大意

对于一个字符串,如果对于所有 \(i \geq 1\),都有恰好 \(0\)或 \(2\) 个自负出现\(i\)次,则该串是好串。

给定一个字符串\(s\),问它是不是好串。

解题思路

\(|s|\)只有 \(100\),统计每个字符的出现次数,再枚举 \(i\)即可。

神奇的代码
#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);
    string s;
    cin >> s;
    bool ok = true;
    map<char, int> cnt;
    for (auto c : s)
        cnt[c]++;
    auto check = [&](int c) {
        int cc = 0;
        for (auto& [k, v] : cnt) {
            cc += (v == c);
        }
        return cc == 0 || cc == 2;
    };
    for (int i = 1; i <= s.size(); ++i) {
        ok &= check(i);
    }
    cout << (ok ? "Yes" : "No") << endl;

    return 0;
}



C - Airport Code (abc349 C)

题目大意

给定一个字符串\(s\)和字符串 \(t\),问字符串 \(t\)能否从字符串 \(s\)得到。操作为:

  • 从 \(s\)挑三个字母,不改变顺序变成 \(t\)。
  • 从 \(s\)挑两个字母,加上\(X\),不改变顺序变成 \(t\)。

解题思路

就子序列匹配问题。就近匹配原则即可。

神奇的代码
#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);
    string s, t;
    cin >> s >> t;
    if (t.back() == 'X')
        t.pop_back();
    auto pos = s.find_first_of(tolower(t[0]));
    for (int i = 1; i < t.size() && pos < s.size(); ++i) {
        pos = s.find_first_of(tolower(t[i]), pos + 1);
    }
    if (pos < s.size())
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}



D - Divide Interval (abc349 D)

题目大意

给定\([l,l+1,...,r-1,r)\)序列,拆分成最少的序列个数,使得每个序列形如 \([2^ij, 2^i(j+1))\)。

给出拆分方案。

解题思路

拆分的序列个数最小,那肯定想让一个序列尽可能的长,而长的话,就是让\(2^i\)尽可能大。

因此就贪心地让\(2^i\)尽可能大,即 \(l=2^i * j\),这里的\(i\)是最大的 \(i\)(这意味着 \(j\)是奇数),并且 \(r \leq 2^i(j + 1)\),如果 \(r > 2^i(j + 1)\),那说明 \(2^i\)太大了,就变成 \(2^(i-1) 2j\)来试试。

神奇的代码
#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 l, r;
    cin >> l >> r;
    vector<array<LL, 2>> ans;
    while (l < r) {
        LL p2 = 1;
        LL bl = l;
        while (bl % 2 == 0 && l + p2 <= r) {
            bl >>= 1;
            p2 <<= 1;
        }
        while (l + p2 > r) {
            p2 >>= 1;
            bl <<= 1;
        }
        ans.push_back({l, l + p2});
        l += p2;
    }
    cout << ans.size() << '\n';
    for (auto& i : ans) {
        cout << i[0] << ' ' << i[1] << '\n';
    }

    return 0;
}



E - Weighted Tic-Tac-Toe (abc349 E)

题目大意

给定\(3 \times 3\)的网格,高桥和青木画 \(OX\)。

每个格子有分数。

若存在同行同列或同对角线,则对应方赢,否则全部画满后,所画格子的分数和较大者赢。

问最优策略下,谁赢。

解题思路

朴素的博弈\(dp\),状态即为当前的棋盘样子,总状态数为 \(3^9=2e4\),直接搜索即可。

即设 \(dp[i]\)表示当前局面 \(i\)的当前操作者(称为先手)的必赢\((dp[i] = 1)\)或必输 \((dp[i] = 0)\)。

转移,则枚举当前操作者的行为,即选择哪个格子,进入后继状态。

如果所有后继状态都是(先手)必赢,那么当前状态则是(先手)必输,即\(dp[i] = 0\)如果所有\(dp[j] = 1\), \(j\)是后继状态。

否则,如果有一个后继状态是先手必输,那么当前状态的先手就可以控制局面走向该状态,使得当前状态是必胜态,即\(dp[i] = 1\)如果存在一个\(dp[j] = 0\)。

转移显而易见是\(O(9)\),总状态数只有 \(O(2e4)\),因此朴素搜索就可以通过了。

神奇的代码
#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);
    typedef array<array<LL, 3>, 3> tu;
    tu a;
    for (auto& x : a)
        for (auto& y : x)
            cin >> y;
    map<tu, int> dp;
    auto check_end = [&](tu& pos) -> int {
        LL p1 = 0, p2 = 0;
        int left = 0;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                left += !pos[i][j];
                p1 += (pos[i][j] == 1) * a[i][j];
                p2 += (pos[i][j] == 2) * a[i][j];
            }
        }
        if (left == 0) {
            if (p1 > p2)
                return 0;
            else
                return 1;
        }

        for (int i = 0; i < 3; ++i) {
            if (pos[i][0] == pos[i][1] && pos[i][1] == pos[i][2] &&
                pos[i][0] != 0) {
                if (pos[i][0] == 1)
                    return 0;
                else
                    return 1;
            }
            if (pos[0][i] == pos[1][i] && pos[1][i] == pos[2][i] &&
                pos[0][i] != 0) {
                if (pos[0][i] == 1)
                    return 0;
                else
                    return 1;
            }
        }

        if (pos[0][0] == pos[1][1] && pos[1][1] == pos[2][2] &&
            pos[0][0] != 0) {
            if (pos[0][0] == 1)
                return 0;
            else
                return 1;
        }

        if (pos[0][2] == pos[1][1] && pos[1][1] == pos[2][0] &&
            pos[0][2] != 0) {
            if (pos[0][2] == 1)
                return 0;
            else
                return 1;
        }

        return -1;
    };

    auto dfs = [&](auto self, tu& pos, int role) -> bool {
        int status = check_end(pos);
        if (status != -1) {
            return dp[pos] = status == role;
        }
        if (dp.find(pos) != dp.end())
            return dp[pos];
        bool lose = false;
        for (auto& i : pos)
            for (auto& j : i) {
                if (j)
                    continue;
                j = (role + 1);
                lose |= (!self(self, pos, role ^ 1));
                j = 0;
            }
        return dp[pos] = lose ? 1 : 0;
    };

    tu ini{};
    bool win = dfs(dfs, ini, 0);
    cout << (win ? "Takahashi" : "Aoki") << endl;

    return 0;
}



F - Subsequence LCM (abc349 F)

题目大意

给定一个序列\(a\)和\(m\),问子序列的数量,使得其\(lcm\)(最小公倍数)为 \(m\)。

子序列之间的不同,当且仅当有元素在原位置不一样,即使它们的数字可能是一样的。

解题思路

我们可以依次考虑每个\(a\),选或不选,很显然是\(O(2^n)\)。

我们不能维护每个数选择的状态,但是要维护怎样的状态呢?是怎样的中间状态能够导出它们的最小公倍数呢。

给定\(n\)个数,考虑怎么求它们的最小公倍数。

根据其定义,假设最小公倍数是\(m\),那就意味着 \(m\)是每个数的倍数。

从质因数的角度来思考倍数,那就是 \(m\)的每个质因子的幂 \(\geq\)每个数对应质因子的幂。

因此 \(m\)的每个质因子的幂就是这些数对应质因子幂的最大值。(最大公因数对应的其实就是幂的最小值)

从上述求最小公倍数的做法,可以引出维护的中间状态。

即设\(dp[i][j]\)表示考虑前 \(i\)个数,选择若干个后,每个质数幂的值的状态为 \(j\)的方案数。这样通过状态 \(j\)就可以知道最后的最小公倍数是不是 \(m\)。但很显然这一状态数是比较大的,稍加思考会发现我们不需要保留当前的幂值是多少,因为求最小公倍数时,我们是 取最大值,我们只想让它最后为\(m\)对应的值即可,因此这里的数量状态可以变成二元状态。

设 \(dp[i][j]\)表示考虑前 \(i\)个数,选择若干个后,其质数幂的最大值是否达到 \(m\)对应的质数幂的值的状态为 \(j\)(对于每个 \(m\)的质数,都有 未达到达到这一\(01\) 状态,因此\(j\)是一个二进制压缩的状态)的选择方案数。初始条件是 \(dp[0][0]=0\)。

转移就考虑,选择当前数后,状态 \(j\)是否会变化。因此要事先预处理每个数选择后对这一状态的影响。即事先对\(m\)质因数分解,再预处理每个 \(a_i\)对转移的影响。

考虑时间复杂度, \(m\)为 \(10^{16}\),至多可能有15+个质数,总的复杂度是 \(O(2^15 10^5)\),粗略算也有 \(1e9\)了。当前的 \(dp\)还过不了。考虑进一步优化。

现在的问题已经变成,给定若干个 \(010101\)数,要求选若干个数,使得其与结果为 \(11111\)的方案数。上述的 \(dp\)方式复杂度是 \(1e9\),会超时。

超时的1e9
#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;
    LL m;
    cin >> n >> m;
    bool one = (m == 1);
    vector<pair<LL, int>> fac;
    int up = 1e8;
    for (int i = 2; i <= up; ++i) {
        if (m % i == 0) {
            fac.push_back({i, 0});
            while (m % i == 0) {
                m /= i;
                fac.back().second++;
            }
        }
    }
    if (m != 1) {
        fac.push_back({m, 1});
    }

    vector<int> a;
    for (int i = 0; i < n; ++i) {
        LL x;
        cin >> x;
        bool ok = true;
        int sign = 0;
        for (int j = 0; j < fac.size(); ++j) {
            auto& [p, v] = fac[j];
            int cnt = 0;
            while (x % p == 0) {
                x /= p;
                ++cnt;
            }
            ok &= (cnt <= v);
            if (cnt == v)
                sign |= (1 << j);
        }
        ok &= (x == 1);
        if (ok)
            a.push_back(sign);
    }

    vector<int> dp(1 << fac.size(), 0);
    dp[0] = 1;
    for (int x : a) {
        vector<int> dp2 = dp;
        for (int i = 0; i < (1 << fac.size()); ++i) {
            dp2[i | x] = (dp2[i | x] + dp[i]);
            if (dp2[i | x] >= mo)
                dp2[i | x] -= mo;
        }
        dp.swap(dp2);
    }
    int ans = dp.back();
    if (one) {
        ans = (ans - 1 + mo) % mo;
    }
    cout << ans << '\n';

    return 0;
}



欲知后事如何,且等作业写完后再写

G - Palindrome Construction (abc349 G)

题目大意

<++>

解题思路

<++>

神奇的代码



标签:AtCoder,return,Beginner,int,auto,pos,cin,349,dp
From: https://www.cnblogs.com/Lanly/p/18133534

相关文章

  • AtCoder Beginner Contest 347
    A-Divisible#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;#defineinti64usingvi=vector<i64>;usingpii=pair<int,int>;usingpiii=tuple<int,int,int>;constintinf=1e......
  • 三十二 1349. 修理牛棚 (贪心)
    1349.修理牛棚(贪心)略importjava.util.*;publicclassMain{privatestaticfinalintN=210;privatestaticintM,S,C;privatestaticint[]a,b;publicstaticvoidmain(String[]args){Scannersc=newScanner(System......
  • atcoder beginer 347 (abc347) D E 题解
     D就是二进制下,哪些位置有重合(两个1),哪些位置没有重合(1个1,1个0),剩下的都是0。xor的结果<2^60,就是小于60位(二进制下)。注意要有要求两个数需要是2^60,于是要有大小的判断,因为有的a,b会2^60,但是按照题目要求,这个情况不行。比如xor的结果,60位都是1,然后a、b各有60个1,那么需要有30个1......
  • atcoder beginer 348 (abc348) D E F 题解
     E非常经典的树上操作(树上DP)。父节点到某个子节点,值是如何变化的。1#include<cstdio>2#include<cstdlib>3#include<cstring>4#include<cmath>5#include<cstdbool>6#include<string>7#include<algorithm>8#include<iost......
  • AtCoder Beginner Contest 348
    B-FarthestPoint难度:⭐题目大意一个坐标系有x个点,对于每个点找出距离其最远的点;解题思路数据很小,暴力就行;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#defineendl'\n'......
  • [ABC348] Atcoder ABC 248 A~G 题解
    [ABC348]AtcoderABC248A~G题解A模拟B模拟,不卡精度。C模拟D注意,药不可以拿着,只可以在那个格子吃掉。这就意味着,我们无论何时到达某个点,到达的点的集合都是固定的。所以对于每个药店跑BFS,然后看起点到终点是否连通即可。intn,m,k,ad[N][N],f[N][N],in[N][N],......
  • 两个链表的交集(力扣349)
    题目如下:给定两个数组 nums1 和 nums2 ,返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。示例1:输入:nums1=[1,2,2,1],nums2=[2,2]输出:[2]示例2:输入:nums1=[4,9,5],nums2=[9,4,9,8,4]输出:[9,4]解释:[4......
  • AtCoder Beginner Contest 348 A-F 题解
    A-PenaltyKickQuestion高桥将在一场足球比赛中获得\(N\)个点球。对于第\(i\)个罚球,如果\(i\)是\(3\)的倍数,他将罚球失败,否则罚球成功。请打印他罚球的结果。Solution当\(i\%3==0\)时说明能被\(3\)整除Code#include<bits/stdc++.h>usingnamespacest......
  • Day5.一刷数据结构算法(C语言版) 242有效的字母异位词; 349两个数组的交集; 202快乐数; 1
        现在我们开始学习哈希表.        经过本次学习我认识到c++的便利,但是我使用的是c,那些功能c又用不了,导致代码长度一下子拉长了...        一刷的时候我还是先用c吧,等二刷的时候试试c++.        进入正题:        什么时候......
  • AtCoder Beginner Contest 348
    地址。赛时情况A、B题都很显然,C题大概推了好一会儿,最后还是做出来了。D题感觉十分难做,估计很难写,看了E。感觉还是不会,听说是原题,搜了一下,发现是树的重心,我还不会。直接贺题解,发现不对。修改了一下还是不对,最后发现INF取小了,过了。后面的不看了。赛后总结还行,跳过D......