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

AtCoder Beginner Contest 344

时间：2024-03-10 15:34:23浏览次数：28  
标签：AtCoder Beginner int auto cin 344 lst using inf

A - Spoiler

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = int64_t;
using ldb = long double;

#define int i64
using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = INT_MAX;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    string s;
    cin >> s;
    int f = 1;
    for( auto i : s ){
        if( i == '|' ) f ^= 1;
        if( f and i != '|') cout << i;
    }
    return 0;
}

B - Delimiter

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = int64_t;
using ldb = long double;

#define int i64
using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = INT_MAX;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    vi a;
    int x;
    while( cin >> x ) a.push_back(x);
    reverse(a.begin(), a.end());
    for( auto i : a )
        cout << i << "\n";
    return 0;
}

C - A+B+C

先离线处理出所有可能组合出的数字。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = int64_t;
using ldb = long double;

#define int i64
using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = INT_MAX;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vi a(n);
    for (auto &i: a) cin >> i;
    int m;
    cin >> m;
    vi b(m);
    for (auto &i: b) cin >> i;
    int l;
    cin >> l;
    vi c(l);
    for (auto &i: c) cin >> i;
    set<int> vis;
    for (auto i: a)
        for (auto j: b)
            for (auto k: c)
                vis.insert(i + j + k);
    int q;
    cin >> q;
    for( int x ; q ; q -- ){
        cin >> x;
        if( vis.count(x) ) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

D - String Bags

其实是一个简单的01背包问题。

用\(f[i][j]\)表示前\(i\)个串拼出长度为\(j\)的前缀的最小花费。

现在对于一个给定的串，我们枚举他放置的位置，先看这个位置之前能不能被拼出来，再看能不能放进这个位置即可。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = int64_t;
using ldb = long double;

#define int i64
using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = INT_MAX;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    string t;
    cin >> t;
    int m = t.size();
    int n;
    cin >> n;
    string s;
    vector<int> f(m + 1, inf);
    f[0] = 0;
    for (int x; n; n--) {
        cin >> x;
        auto g = f;
        for (int len; x; x--) {
            cin >> s, len = s.size();
            for (int p = 0; p + len <= m; p++) {
                if (f[p] == inf) continue;
                if (t.substr(p, s.size()) == s)
                    g[p + len] = min(g[p + len], f[p] + 1);
            }
        }
        f.swap(g);
    }
    if (f.back() == inf) cout << "-1\n";
    else cout << f.back() << "\n";
    return 0;
}

还在群里学到了一个用map的写法

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using ldb = long double;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = 1e9;


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    string T;
    cin >> T;
    map<string, int> f;
    f[""] = 0;
    for (string s = ""; auto i: T)
        s += i, f[s] = inf;

    int n;
    cin >> n;
    for (int x; n; n--) {
        cin >> x;
        auto g = f;
        for (string s, ns; x; x--) {
            cin >> s;
            for (auto [k, v]: f) {
                ns = k + s;
                if (v == inf or ns.size() > T.size() or g.count(ns) == 0) 
                    continue;
                g[ns] = min(g[ns], v + 1);
            }
        }
        f.swap(g);
    }
    if (f[T] == inf) f[T] = -1;
    cout << f[T] << "\n";
    return 0;
}

E - Insert or Erase

单说插入和删除操作实际上都可以用链表\(O(1)\)的实现，难点是如何快速找到要插入或修改的位置。

我这里使用std::map<int,std::pair<int,int>>来模拟了链表的执行过程。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = int64_t;
using ldb = long double;

#define int i64
using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = INT_MAX;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    map<int, pii> List;
    for (int i = 1, x, lst = 0; i <= n; i++) {
        cin >> x;
        List[lst].second = x;
        List[x] = pair(lst, inf);
        lst = x;
    }
    int q;
    cin >> q;
    for (int op, lst, nxt, x; q; q--) {
        cin >> op;
        if (op == 1) {
            cin >> lst >> x;
            nxt = List[lst].second;
            List[x] = pair(lst, nxt);
            List[lst].second = List[nxt].first = x;
        } else {
            cin >> x;
            tie(lst, nxt) = List[x];
            List[x] = pair(-1, -1);
            List[lst].second = nxt;
            List[nxt].first = lst;
        }
    }
    for (int i = List[0].second; i != inf; i = List[i].second)
        cout << i << " ";
    cout << "\n";
    return 0;
}

F - Earn to Advance

一个比较板的dp。据说和某年的csp-j t2比较类似。

设 dp的状态为$f[i][j][x][y] \(表示走到\)(i,j)\(点且路径中经过\)p\(的最大值在\)(x,y)\(上，这样实际上就是\)O(n^4)\(的枚举就行。要注意的就是向下一步走的时候要判断\)p$最大值位置是否发生变化。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using ldb = long double;

#define int i64
using vi = vector<int>;
using pii = pair<int, int>;

const int inf = LLONG_MAX;


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;

    vector p(n, vi(n));
    for (auto &it: p)
        for (auto &i: it) cin >> i;

    vector r(n, vi(n - 1));
    for (auto &it: r)
        for (auto &i: it) cin >> i;

    vector d(n - 1, vi(n));
    for (auto &it: d)
        for (auto &i: it) cin >> i;

    vector f(n, vector(n, vector(n, vector(n, pair(inf, -inf)))));
    f[0][0][0][0] = pair(0, 0);

    auto calc = [](int a, int b, int c) {
        if (a >= b) return 0ll;
        return (b - a + c - 1) / c;
    };

    auto cmp = [](pii x, pii y) {
        if (x.first != y.first) return x.first < y.first;
        return x.second > y.second;
    };
    for (int i = 0, wait, newX, newY, newDis, newLst; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int x = 0; x <= i; x++)
                for (int y = 0; y <= j; y++) {
                    const auto &[dis, lst] = f[i][j][x][y];
                    if (dis == inf) continue;
                    if (i + 1 < n) {
                        wait = calc(lst, d[i][j], p[x][y]);
                        newX = x, newY = y;
                        if (p[i + 1][j] > p[x][y]) newX = i + 1, newY = j;
                        newDis = dis + wait + 1, newLst = lst + wait * p[x][y] - d[i][j];
                        f[i + 1][j][newX][newY] = min(f[i + 1][j][newX][newY], pair(newDis, newLst),cmp);
                    }
                    if (j + 1 < n) {
                        wait = calc(lst, r[i][j], p[x][y]);
                        newX = x, newY = y;
                        if (p[i][j + 1] > p[x][y]) newX = i, newY = j + 1;
                        newDis = dis + wait + 1, newLst = lst + wait * p[x][y] - r[i][j];
                        f[i][j + 1][newX][newY] = min(f[i][j + 1][newX][newY], pair(newDis, newLst), cmp);
                    }
                }
    int res = inf;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            res = min(res, f[n - 1][n - 1][i][j].first);
    cout << res << "\n";
    return 0;
}

标签：AtCoder,Beginner,int,auto,cin,344,lst,using,inf
From： https://www.cnblogs.com/PHarr/p/18064240

相关文章

  • abc344E 维护元素唯一的序列
    给定序列A[N]，元素值各不相同，有Q个操作，格式如下：1xy:在元素x后面插入元素y，保证插入时x唯一。2x:将元素x从序列中删除，保证删除时x唯一。输出所有操作完成后的序列。1<=N,Q<=2E5;1<=A[i]<=1E9;A[i]!=A[j]用链表来快速插入和删除，另外还需要map来快速定位，类似LRU的实现。......
  • ABC344G 题解
    ABC344G题解给定平面上\(n\)个点和\(q\)条直线，问对于每条线，有多少点在它上方。形式化的，对于直线\(y=ax+b\)统计有多少点\((x,y)\)满足\(y\geax+b\)，即\(-ax+y\geb\)。故我们可以将所有点按照\(-ax+y\)排序，从而利用二分简单的得出结果。但是我们显然不可能暴力进......
  • AtCoder Beginner Contest 344
    AtCoderBeginnerContest344ABCD略EInsertorErase手写链表调了这么久。。链表模板。FEarntoAdvance考虑DP，但是我们发现不是很好转移，然后我们发现\(n\le80\)，我们观察一下题目的性质。如果路径确定了，那么我们肯定会在最大值的地方使劲加到终点为止。那么我们考......
  • abc344_D - String Bags 题解
    一个月没有碰oi，感觉水平已经退化到负的了。来复健一下。D-StringBagslink题意：给你\(n\)组字符串组，按\(1\)~\(n\)的顺序，对于每组字符串组，可从中至多选一个字符串。求能否用所选串按顺序拼接成指定串，以及选取字符串的最小个数。然后读完题发现是个\(01\)背包；对于第......
  • AT_abc344_e 题解
    本文同步发表于洛谷。赌狗天天输的一集。赛时各种【数据删除】原因导致没做出来。大意给你一个长度为\(N\)的序列\(A=(A_1,\ldots,A_N)\)。保证\(A\)中的元素是不同的。你要处理\(Q\)个操作。每个操作是以下两种类型之一：1xy：在\(A\)中元素\(x\)后面紧接着插入......
  • AtCoder Beginner Contest 344
    基本情况ABCE秒了，D小细节处理出错（太久没写dp）+4。D-StringBagshttps://atcoder.jp/contests/abc344/tasks/abc344_d分组背包，但是字符串的细节要注意signedmain(){intn;std::stringT,str[110][15];intF[110][110],a[110];std::cin>>T>>n;......
  • AT_abc344_d 题解
    赌狗天天输的一集。大意你最开始有一个空字符串\(S\)。你还有编号为\(1,2,\dots,N\)的袋子，每个袋子都包含一些字符串。袋子\(i\)包含\(A_i\)个字符串\(S_{i,1},S_{i,2},\dots,S_{i,A_i}\)。对\(i=1,2,\dots,N\)重复以下步骤仅一次（这里原题没有讲清楚）：......
  • AtCoder Regular Contest 171
    Preface小补一场ARC，D还是很有意思的但想了半天不会，鉴定为纯纯的彩笔A-NoAttacking考虑怎么放rook能使得留下来能放pawn的格子数量最多，手玩一下会发现先按照\((2,2),(4,4),(6,6),\cdots\)的顺序放，放满后再接着放\((1,1),(3,3),(5,5),\cdots\)是最优的手玩一下可以得出在放......
  • AtCoder Beginner Contest 343
    A-WrongAnswer(abc343A)题目大意给定\(a,b\)，输出\(c\)，使得\(a+b\neqc\)解题思路从\(0\)开始枚举\(c\)的取值即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio(false);cin.......
  • AtCoder Beginner Contest 321
    \[\large\text{Round12:AtCoderBeginnerContest321}\]一言:只要你在，我便无所不能。——进击的巨人感觉只有最后一道题有点意思，其他的就是时间问题，但是速度还是不够快，思维要跟上啊。有意思的是，周考考了回退背包，这里居然又来一次。。\(\text{G:ElectricCircuit}......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99