AtCoder Beginner Contest 341（很菜的小白一枚）

youhualiuh / 2024-02-18 / 原文

解法不一,请谅解. (希望可以为你带来思路和解法) （我是小白勿喷）

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 可以快5倍
scanf printf 快10倍

A - Print 341(签到题)

思路:

给你一个整数N 有N个0和N + 1个1组成 0 1 交替输出1

解法:（语法题）

输出10最后输出最后剩余的1即可

Code:

#include <bits/stdc++.h>
    
using namespace std;
    
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int N; cin >> N;
    for (int i = 1; i <= N; ++i) {
        cout << "10";
    }
    cout << "1\n";
    return 0;
}

Code:

N = int(input())
print("10" * N + "1")

B - Foreign Exchange（签到题）

思路:

给你N个国家这些国家给定了每一个初始值的钱

给你N-1个对换的值也就是

1国每x钱兑换2国y钱这里的钱对于的S[1] 和 T[1] 接下来同上

解法:（语法题）

由于只枚举到N-1的S[] T[] 我们只要从第一个开始一个个遍历过去使得A[N]最大坑点数据范围

Code:

#include <bits/stdc++.h>
    
using namespace std;
const int N = 2e5 + 5;

long long A[N], S[N], T[N];

int main()
{
    int N; cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    
    for (int i = 1; i <= N - 1; i++) {
        cin >> S[i] >> T[i];
    }

    for (int i = 1; i <= N - 1; i++) {
        A[i + 1] += (A[i] / S[i]) * T[i];
    }

    cout << A[N] << '\n';
    return 0;
}

C - Takahashi Gets Lost

思路:

给你一个移动的字符串,满足这个网格,#可以理解为墙,不能碰到,只要在可移动的路满足你所要移动的字符串则加一,我的方法就是遍历所有的'.'即可

解法:（迷宫模拟）

按照题意首先观察数据很小所以遍历每一个点即可如果'.'则运行移动的条件,如果顺利完成则输出true(1) 不满足输出false(0)

我使用的Lambda 函数,具体了解可以去学习一下单独自定义函数也可以

Lambda 表达式 - OI Wiki (oi-wiki.org)

Code1:

#include<bits/stdc++.h>

using namespace std;

struct Node {//位移dx dy
    int dx;
    int dy;
};

int main() {
    int H, W, N; cin >> H >> W >> N;
    string T; cin >> T;
    vector<string> grid(H);
    for (int i = 0; i < H; ++i) {
        cin >> grid[i];
    }
    vector<Node> dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    //Lambda 函数
    auto is_valid = [&](int x, int y) {//越界
        return 0 <= x && x < H && 0 <= y && y < W && grid[x][y] == '.';
    };
    auto Simple_moves = [&](int x, int y, const string& T) {//遍历
        for (char move : T) {//对字符串 T 中的每个字符进行遍历
            Node movement = dirs["LRUD"s.find(move)];// 根据当前字符找到对应的方向
            x += Node.dx; y += Node.dy;
            if (!is_valid(x, y)) {
                return false;
            }
        }
        return true;
    };
    int count = 0;//计数
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (grid[i][j] == '.') {
                if (Simple_moves(i, j, T)) {
                    count++;
                }
            }
        }
    }
    cout << count << '\n';
    return 0;
}

Code2:

#include <bits/stdc++.h>
    
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
    
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int H, W, N; cin >> H >> W >> N;
    string T; cin >> T;
    vector<string> grid(H);
    for (int i = 0; i < H; i++) {
        cin >> grid[i];
    }
    int ans = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (grid[i][j] == '#') {
                continue;
            }
            bool flag = 1;
            int dx = i, dy = j;
            for (char move : T) {
                if (move == 'L') {
                    dy--;
                }
                else if (move == 'R') {
                    dy++;
                }
                else if (move == 'D') {
                    dx++;
                }
                else {
                    dx--;
                }
                if (grid[dx][dy] == '#') {
                    flag = 0;
                    break;
                }
            }
            if (flag) { ans ++; }
        }
    }
    cout << ans << '\n';
    return 0;
}

D - Only one of two

思路:

给你一个N M数找到第K的数可以被N整除但是不被M整除

被M整除但是不被N整除

解法:（二分 + 数论）

这题使用二分搜索,因为我们会发现N 和 M就相当于两个集合而且集合相交就是N M都能整除也就是lcm(N, M) 我们的mid / lcm(n, m) * 2是因为它交集是两个集合想到其实很简单在加上各自的整除即可

Code:

mid / N 计算了在区间 [1, mid] 中能够被 N 整除的数的个数；
mid / M 计算了在区间 [1, mid] 中能够被 M 整除的数的个数；
mid / lcm(N, M) 计算了在区间 [1, mid] 中同时能够被 N 和 M 整除的数的个数。因为这些数会被重复计算在前两个中，所以需要减去这部分重复计算的数量，因此乘以 2；
最后用 res 记录总的满足条件的数的个数。

#include <bits/stdc++.h>
    
using namespace std;
using ll = long long;
    
ll lcm(ll x, ll y) {
    return x / __gcd(x, y) * y;
}

int main()
{
    ll N, M, K; cin >> N >> M >> K;
    ll left = 0, right = 1e18;
    auto check = [&](ll mid) {
        ll res = mid / N + mid / M - mid / lcm(N, M) * 2;
        return res; // 返回 res 的值
    };
    while (left + 1 <  right) {
        ll mid = (left + right) >> 1;
        if (check(mid) < K) {
            left = mid;
        }
        else {
            right = mid;
        }
    }
    cout << right << '\n';
    return 0;
}

E - Alternating String

思路: （对勾A题的问题,要交替才是好串）

这一题题意简单明了给你一个01字符串如果x 等于 1 则更新l r区间(更新指如果为1 变为0) 如果x 等于2 则查询这个是不是好串输出YES or NO

1 L R 01交换
2 L R 判断好串

解法:(线段树差分树状数组)

解法很多,我这里举线段树和差分，跟着题意来就可以

原题历史链接:F - Vacation Query (atcoder.jp) and ：https://www.luogu.com.cn/problem/P2572

Code1（差分）:

这里的it == st.end()
->it 已经到达集合 st 的末尾
upper_bound(N) 这里找到第一个大于N
*it 大于等于右边界 R
L--;：因为题目中给出的索引是 1-based 的 而在代码中我们通常使用 0-based 的索引
因此，我们将 L 减 1 使得索引从 0 开始

/* 
差分
我们利用set来标记数字相同的位置

} */
#include <bits/stdc++.h>
    
using namespace std;
    
int main()
{
    int N, Q;
    string S; cin >> N >> Q >> S;
    set<int> st;
    for (int i = 1; i < N; i++) {
        if (S[i] == S[i - 1]) {
            st.insert(i);
        }
    }
    while (Q--) {
        int x, L, R; cin >> x >> L >> R;
        L--;
        if (x == 1) {
            if (L > 0) {
                if (st.count(L)) {
                st.erase(L);
                } 
                else {
                    st.insert(L);
                }
            }
            if (R < N) {
                if (st.count(R)) {
                    st.erase(R);
                } 
                else {
                    st.insert(R);
                }
            }
        }
        else {
            auto it = st.upper_bound(L);
            cout << (it == st.end() || *it >= R ? "Yes\n" : "No\n");
        }
    }
    return 0;
}

Code2(atcoder自带的segtree):

https://atcoder.github.io/ac-library/production/document_en/segtree.html

#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;

bool op(bool a, bool b) { return a & b; }
bool e() { return true; }

int main() {
  int n, q;
  string s;
  cin >> n >> q >> s;
  vector<bool> arr(n - 1);
  for (int i = 0; i < n-1; ++i) {arr[i] = s[i] != s[i+1];}
  atcoder::segtree<bool, op, e> segt(arr);//atcoder库
  while (q--) {
    int x, l, r;
    cin >> x >> l >> r;
    --l, --r;
    if (x == 1) {
      if (l > 0)
        segt.set(l-1, !segt.get(l - 1));
      if (r < n - 1)
        segt.set(r, !segt.get(r));
    }
    else {
      if (l == r || segt.prod(l, r)) cout << "Yes" << '\n';
      else cout << "No" << '\n';
    }
  }
  return 0;
}

Code3(手写线段树):

#include <bits/stdc++.h>

using namespace std;
const int MAX = 5e5+10;

struct segtree{
    vector<int> a;
    int n;
    
    segtree(int sz){
        n = sz;
        a.resize(4 * sz);
    }
    
    int query(int v, int ql, int qr, int l, int r){
        if(r < ql || l > qr) return 0;
        if(ql <= l && r <= qr) return a[v];
        int mid = (l + r) / 2;
        return query(2 * v, ql, qr, l, mid) + query(2 * v + 1, ql, qr, mid + 1, r);
    }
    int query(int l, int r){
        return query(1, l, r, 0, n - 1);
    }

    void update(int v, int up, int ux, int l, int r){
        if(l == r){
            a[v] = ux;
            return;
        }
        int mid = (l+r)/2;
        if(up <= mid) update(2 * v, up, ux, l, mid);
        else update(2 * v + 1, up,  ux, mid + 1, r);
        a[v] = a[2 * v] + a[2 * v + 1];
    }
    void update(int p, int x){
        update(1, p, x, 0, n - 1);
    }
};

int main(){
    int n, q; cin >> n >> q;
    string s; cin >> s;
    segtree seg(n-1);
    for(int i = 0; i < n-1; i++) if(s[i] != s[i+1]) seg.update(i,1);
    while(q--){
        int op, l, r; cin >> op >> l >> r;
        l--, r--;
        if(op == 1){
            if(l > 0) seg.update(l - 1, 1 - seg.query(l - 1, l - 1));
            if(r < n - 1) seg.update(r, 1 - seg.query(r, r));
        }
        if(op == 2){
            if(seg.query(l,r - 1) == r - l) cout << "Yes" << '\n';
            else cout << "No" << '\n';
        }
    }
    return 0;
}

F - Breakdown

思路&&解法:

利用01背包求解碎片总是往点权小的点跑，这里有个方向性。我们可以先求权值小的点，那考虑权值大的点时，其考虑放置碎片的点的答案都求出来了，因此可以求出该点的答案。考虑

dp这里就是先排序最后利用01背包跑出来即可

Code:

简单无向图N个顶点 M条边
每个顶点赋值权重Wi 都有棋子Ai
选中棋子与所在顶点相邻的几个顶点必须小于这个选中的棋子的权重
移除这个选中棋子在放进选择的放置一个棋子 求操作
如果没可以没有地方去就移除
进行排序 就变成了类似背包的问题

#include <bits/stdc++.h>
    
using namespace std;
using ll = long long;

int main()
{
    
    int N, M; cin >> N >> M;//顶点数 and 边数
    vector<int> graph[N];//邻接表
    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        u--, v--;//因为索引
        graph[u].push_back(v);
        graph[v].push_back(u);//无向边储存
    }
    vector<int> W(N), A(N);//W代表权重 A代表棋子数量
    for (int i = 0; i < N; i++) {
        cin >> W[i];
    }

    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    vector<int> p(N);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(),  p.end(), 
        [&](int i, int j) {
            return W[i] < W[j];
    });
    vector<int> dp(N);
    for (auto x : p) {
        vector<int> f(W[x]);
        for (auto y : graph[x]) {
            if (W[y] < W[x]) {
                for (int i = W[x] - 1; i >= W[y]; i--) {
                    f[i] = max(f[i], f[i- W[y]] + dp[y]);
                }
            }
        }
        dp[x] = 1 + f[W[x] - 1];
    } 
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        ans += 1LL * A[i] * dp[i];
    }
    cout << ans << '\n';
    return 0;
}