首页 > 其他分享 >AtCoder Beginner Contest 303 题解 A - E

AtCoder Beginner Contest 303 题解 A - E

时间：2023-05-28 21:02:58浏览次数：55  
标签：AtCoder min int 题解 303 cin long include dp

A - Similar String

题目大意

忽略0和o的差别以及1和l的差别比较两个字符串。

解题思路

  1. 可以硬求，直接写个超长的if判断一下。
  2. 可以对两个字符串进行修改，0都换成o，1都换成l，然后直接比较两个字符串。

AC Code

硬求

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

void solve() {
    int n;
    string s1, s2;
    cin >> n >> s1 >> s2;
    for (int i = 0; i < n; ++i) {
        if (s1[i] != s2[i] && !(s1[i] == '1' && s2[i] == 'l') && !(s1[i] == 'l' && s2[i] == '1') && !(s1[i] == '0' && s2[i] == 'o') && !(s1[i] == 'o' && s2[i] == '0')) {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

替换

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

void solve() {
    int n;
    string s1, s2;
    cin >> n >> s1 >> s2;
    for (int i = 0; i < n; ++i) {
        if (s1[i] == '0') {
            s1[i] = 'o';
        } else if (s1[i] == '1') {
            s1[i] = 'l';
        }
        if (s2[i] == '0') {
            s2[i] = 'o';
        } else if (s2[i] == '1') {
            s2[i] = 'l';
        }
    }
    cout << (s1 == s2 ? "Yes" : "No") << endl;
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

B - Discord

题目大意

给定 \(n\) 个人在一起拍的 \(m\) 张照片，如果两个人没有挨在一起过就会生气。问生气的两人组的组数。

解题思路

这种说法很像图论中的无向边，考虑到数据范围很小，我们可以使用一个邻接矩阵存放每两人之间的关系，遍历找出没有挨在一起的组数即可。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 60;
const int MOD = 1e9 + 7;

bool a[N][N];

void solve() {
    int n, m;
    cin >> n >> m;
    int tmp = 0;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            int x;
            cin >> x;
            a[x][tmp] = true;
            a[tmp][x] = true;
            tmp = x;
        }
        tmp = 0;
    }
    LL cnt = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (!a[i][j]) cnt++;
        }
    }
    cout << cnt << endl;
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

C - Dash

题目大意

高橋社长在二维平面上按照给出的指令行动，图上有 \(m\) 个回血道具，如果血量低于 \(k\) 就回到 \(k\)，同时消耗掉这个道具。每走一步就会扣一点血，问最终高橋社长能否走完指令。

解题思路

按照题目意思模拟即可，但是本题的范围由绝对值确定，所有需要开两倍大小的数组，然后将原点设在中心，不过显然我们不能开一个巨大无比的二维数组，所以可以使用一个map数组代替。不过我赛时交了个错的代码因为数据不够强过了，我把二维映射到了一维，居然数据没有卡掉这个bug。

AC Code

学长的正解

#include<functional>
#include<iostream>
#include<map>
#include<string>
#include<unordered_map>
#include<vector>
#include<stack>
using namespace std;
typedef long long ll;
#pragma G++ optimize (3)
#define int ll
#define inc(i, l, r) for(ll i=l;i<=r;i++)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"

ll inf;
map<int,int>mpp[400200];

signed main() {
    inf = 998244353;
    IOS;
    inf = 1e9 + 7;
    int _ = 1;
    //cin >> _;
    while (_--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        string s;
        cin >> s;

        inc(i, 1, b) {
            int x, y;
            cin >> x >> y;
            mpp[x + 200000][y + 200000]++;
        }
        int x = 0, y = 0;
        int pd = 1;
        inc(i, 0, a - 1) {
            c--;
            if (c < 0) {
                pd = 0;
                break;
            }
            if (s[i] == 'U')y++;
            else if (s[i] == 'D')y--;
            else if (s[i] == 'L')x--;
            else x++;
            if (mpp[x + 200000][y + 200000] && c < d) {
                mpp[x + 200000][y + 200000]--;
                c = d;
            }
        }
        if (pd)cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

蒟蒻的错解

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 4e5 + 10;
const int MOD = 1e9 + 7;

int g[N];

void solve() {
    int n, m, h, k;
    string s;
    cin >> n >> m >> h >> k >> s;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        cin >> x >> y;
        g[x + 200000] = y;
    }
    int xx = 0, yy = 0;
    for (int i = 0; i < n; ++i) {
        h--;
        if (h < 0) {
            cout << "No" << endl;
            return;
        }
        if (s[i] == 'R') {
            xx++;
        } else if (s[i] == 'L') {
            xx--;
        } else if (s[i] == 'U') {
            yy++;
        } else if (s[i] == 'D') {
            yy--;
        }
        if (g[xx + 200000] == yy && h < k) {
            h = k;
            g[xx + 200000] = -0x3f3f3f3f;
        }

    }
    cout << "Yes" << endl;
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

D - Shift vs. CapsLock

题目大意

我们需要输入一个只有A和a的字符串，有以下三种操作：

  • 点一下A键，耗时 \(X\) 秒
  • 按住SHIFT键，同时点一下A键，耗时 \(Y\) 秒
  • 按一下CAPSLOCK键，耗时 \(Z\) 秒

起始状态下，屏幕没有任何字，大写锁定指示灯熄灭。

解题思路

三种操作方式，两种状态间有相关关系，具有无后效性，感觉就很像一个线性dp。

我们可以按照输入第 \(i\) 位，大写锁定状态为 \(j(0或1)\) 进行dp，注意单独输入 a 时，有两种可能，第一种是按下A键，第二种是先按CAPSLOCK，再按SHIFT + A，再根据当前dp状态决定是否需要再按一次CAPSLOCK。

最后记得取两种大写锁定状态的最小值。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 3e5 + 10;
const int MOD = 1e9 + 7;

LL dp[N][2];

void solve() {
    LL x, y, z;
    string s;
    cin >> x >> y >> z >> s;
    if (s[0] == 'a') {
        dp[0][0] = min(x, 2 * z + y);
        dp[0][1] = z + min(x, y);
    } else {
        dp[0][0] = min(y, 2 * z + x);
        dp[0][1] = z + min(x, y);
    }
    for (int i = 1; i < s.length(); ++i) {
        if (s[i] == 'A') {
            dp[i][1] = min(dp[i - 1][1] + min(x, 2 * z + y), dp[i - 1][0] + z + min(x, y));
            dp[i][0] = min(dp[i - 1][0] + min(y, 2 * z + x), dp[i - 1][1] + z + min(x, y));
        } else {
            dp[i][1] = min(dp[i - 1][0] + z + min(x, y), dp[i - 1][1] + min(y, 2 * z + x));
            dp[i][0] = min(dp[i - 1][1] + z + min(x, y), dp[i - 1][0] + min(2 * z + y, x));
        }
    }
    cout << min(dp[s.length() - 1][0], dp[s.length() - 1][1]);
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

E - A Gift From the Stars

题目大意

定义星星表示一个除了中间结点外的结点都连在中间结点上且度数为 \(1\) 的无向图，给定一个无向图，是将多个星星连接起来的，问给定的无向图删去加的边后，能找到的每个星星的大小（中心结点的度数）。

解题思路

首先我们使用一个邻接矩阵获取每个点的度数，随后遍历每个结点，找到度数为 \(1\) 的点，这个点就肯定是某个星星的枝，由这个结点出发，搜索对它连通的区域，使用一个计数变量op来记录我们走的步骤，考虑到：枝—中心—枝是一个三元组，计数变量在\((0\sim2)\)之间循环。每当计数变量取到 \(1\) 的时候，就是我们的中间结点，将这个星星的大小压到答案数组里，如此往复一次遍历每一个结点情况即可。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;

vector<vector<int>> g(N);
vector<int> res;

void dfs(int cur, int lst, int op) {
    if (op == 1) {
        res.push_back(g[cur].size());
    }
    for (auto i : g[cur]) {
        if (i != lst) {
            dfs(i, cur, (op + 1) % 3);
        }
    }
}

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 1; i <= n; ++i) {
        if (g[i].size() == 1) {
            dfs(i, 0, 0);
            break;
        }
    }
    sort(res.begin(), res.end());
    for (int i : res) {
        cout << i << ' ';
    }
    cout << endl;
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

标签：AtCoder,min,int,题解,303,cin,long,include,dp
From： https://www.cnblogs.com/SanCai-Newbie/p/17438828.html

相关文章

  • AtCoder Beginner Contest 303 G Bags Game
    洛谷传送门AtCoder传送门经典题，考虑区间dp，\(f_{l,r}\)表示只考虑\([l,r]\)区间，先手得分减后手得分最大值。对于第一种操作直接\(f_{l,r}\gets\max(a_l-f_{l+1,r},a_r-f_{l,r-1})\)，第二种操作，考虑枚举\([l,r]\)长为\(r-l+1-B\)的子段，即可转移。第三种操......
  • P9356 「SiR-1」Bracket 题解
    P9356「SiR-1」Bracket题解首先我们来先考虑一下如何计算一个给定的\(f(s[1,n])\)。一般括号序列的题目都是比较套路的将\(\texttt{(}\)赋值为\(1\)，将\(\texttt{)}\)赋值为\(-1\)，然后求一下前缀和记为\(sum_i\)，那么一个括号序列是合法的当且仅当\(\foralli\in[1,n],......
  • comp2123 问题解答
    comp2123Assignment5s12023Problem1.Wewanttodesignadivideandconqueralgorithmforcomputingtheunionofacollectionofrectangles.Theinputrectanglesarealignedwiththeaxesandtheyareallstabbedbythey-axis.Eachrectangleisrepresen......
  • LeetCode-Java题解 977. Squares of a Sorted Array
    题目地址：977.SquaresofaSortedArray解题思路：    又是一道双指针的题目，看见秒想到双指针（平方直接调用sort方法也行，但是这么写这题就没意思了）。但是，我一直在想，不增加空间消耗的情况下，如何进行排列，想了半天把自己绕进去了。开辟一个新数组，倒序放置就非常简单了。一定要利......
  • phpcms常见问题解答
    phpcms常见问题解答1.为什么phpcms首页幻灯片怎么显示不出来?答：需要设置文章的标题图片如果设置标题图片，则可以在首页以及栏目页以图片方式链接到文章。2.自定义phpcms的标签只能是全HTML?答：在自定义标签内容中可以插入html代码，也可以插入多个函数标签或者变量标签。插入函......
  • Gym102978C Count Min Ratio 题解
    赛时无人场切。震撼，震撼。学到许多。全程贺zak。首先我们套路推下式子。枚举左边的红蓝球个数，答案即为\[\begin{aligned}&\sum_{b=0}^B\sum_{r=0}^R\binom{b+r}b\binom{B-b+R-r}{B-b}\min(\fracrb,\frac{R-r}{B-b})\\=&\sum_{x=1}^{\fracRB}\sum_{b=0}^B\sum_{r=0}^R\binom......
  • Traceback (most recent call last):错误问题解决
    原因是没有配置pymysql配置mysql连接https://blog.csdn.net/zzzcl112/article/details/80503690#:~:text=%5Broot%40VM_0_8_centos%20local%5D%20%23%20tar%20-zxvf%20PyMySQL-0.8.1.tar.gz%20%E8%BF%9B%E5%85%A5%2Fusr%2Flocal%2FPyMySQL-0.8.1%E7%9B%AE%E5%BD%95%2C%E6%89%A7%E8%......
  • 时代的眼泪：CF1562A The Miracle and the Sleeper 题解 2021-09-23 23:00:33
    CF1562ATheMiracleandtheSleeper题解笑死，晚上熬夜打CF比赛只过了A题还加了CF值！？由于本人太弱，这道橙题都干了1h题目描述有\(T\)组数据，给出一个区间\([l,r]\),在这个区间中选择2个数a,b，使它们a%b的值最大.注意：\(l\ler\le10^9\),\(T\le10^3\)解题步骤暴力......
  • #296. 最强大脑 题解
    2021-09-2222:16:56星期三#296.最强大脑题解这是一道非常简单的bfs水题。。。。但是为什么没有人做呢？难道是因为网上搜不到？理解题意：输入为2个n*m大小矩阵。第一个矩阵表示每个点的分数值，第二个矩阵则表示这个点是否是特殊点(1&0)这里规定了一种移动方式，你可......
  • #295. 「BJWC2010」矩阵距离 题解 2021-09-23 21:42:32
    #295.「BJWC2010」矩阵距离又是一道需要真正思考了才可以做出来的水题。题目描述给出一个N*M的01矩阵，输出每个0到离这个点最近的1的距离。思考历程暴力由于$N\le10^3$如果在赛场上出现这个题，我们优先考虑暴力。暴力也是很简单，从每个为0的点出发bfs找到与最近的......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99