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

AtCoder Beginner Contest 343

时间：2024-03-07 11:24:29浏览次数：29  
标签：AtCoder cnt Beginner int max len long 343 字符串

A - Wrong Answer (abc343 A)

题目大意

给定\(a,b\)，输出 \(c\)，使得 \(a+b \neq c\)

解题思路

从\(0\)开始枚举\(c\)的取值即可。

神奇的代码 
#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 a, b;
    cin >> a >> b;
    int ans = 0;
    while (ans == a + b)
        ++ans;
    cout << ans << '\n';

    return 0;
}

B - Adjacency Matrix (abc343 B)

题目大意

给定一个邻接矩阵，对于第\(i\)个点，输出与之有连边的点的编号，升序。

解题思路

即输出第\(i\)行中值为 \(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;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            if (x)
                cout << j + 1 << " ";
        }
        cout << '\n';
    }

    return 0;
}

C - 343 (abc343 C)

题目大意

给定一个数\(n\)，问不超过 \(n\)的最大的数 \(x\)，其是回文数，且是某个数\(y\)的三次方。

解题思路

我们可以枚举\(y\)而不是 \(x\)，这样得到的 \(x=y^3\)就一定是个三次方数，剩下的就是判断 \(x\)是不是回文数。

\(n\)只有 \(10^{18}\)，对应的\(y\)的范围就只有\(10^6\)，判断回文数的复杂度是 \(O(\log )\)，因此直接枚举判断即可。

判断回文数可以直接用 to_string转换成字符串然后对应位比较。

神奇的代码 
#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 n;
    cin >> n;
    int up = 1e6;
    LL ans = 0;
    for (int i = 1; i <= up; ++i) {
        LL x = 1ll * i * i * i;
        if (x > n)
            break;
        string s = to_string(x);
        bool ok = true;
        int len = s.size();
        for (int i = 0; i < len; ++i) {
            ok &= s[i] == s[len - i - 1];
        }
        if (ok) {
            ans = x;
        }
    }
    cout << ans << '\n';

    return 0;
}

D - Diversity of Scores (abc343 D)

题目大意

初始\(n\)个人都是 \(0\)分。

第\(i\)个时刻，第 \(a_i\)个人分数增加 \(b_i\) 。

问每个时刻后，不同分数的个数。

解题思路

用map维护每个数出现的次数，当其次数减为\(0\)的就删去该元素。

每个时刻的答案就是 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, t;
    cin >> n >> t;
    map<LL, int> cnt;
    vector<LL> score(n);
    cnt[0] = n;
    for (int i = 0; i < t; ++i) {
        int a, b;
        cin >> a >> b;
        --a;
        cnt[score[a]]--;
        if (cnt[score[a]] == 0)
            cnt.erase(score[a]);
        score[a] += b;
        cnt[score[a]]++;
        cout << cnt.size() << '\n';
    }

    return 0;
}

E - 7x7x7 (abc343 E)

题目大意

三维坐标，三个\(7 \times 7 \times 7\)的方块放置。

给定 \(v1,v2,v3\)，要求

  • 恰好属于一个方块的体积是 \(v1\)。
  • 恰好属于两个方块的体积是 \(v2\)。
  • 恰好属于三个方块的体积是 \(v3\)。

输出任意一种摆放方式。

解题思路

由于数都不大，考虑直接枚举。

由于空间的平移不变形，第一个方块放置位置可以是\((0,0,0)\)。

考虑枚举第二个和第三个的方块，其坐标范围则是\([-7,7]\)。再远的地方和 \(-7,7\)的放置效果是一样的。

花\(O(2^6 7^6)\)枚举三个方块位置后，要求\(v1,v2,v3\)，再花\(O(2^3 7^3)\)统计的话总复杂度就是 \(10^{10}\)，会超时了。

考虑 \(v3\)怎么求，其实这跟求两个线段的交线长度、两个矩形的相交面积一样，分别考虑每一维的交线长度，即右端点的最小值 \(-\)左端点的最大值，然后三维长度乘起来就是相交体积。

\(v2\)就是俩俩相交，再减去 \(v3\)对应的部分。

\(v1\)就是所有体积加起来，减去 \(v2\)和 \(v3\)对应的部分。

这样就可以\(O(1)\)判断，最终的时间复杂度是 \(O(2^6 7^6)\)。

神奇的代码 
#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 v1, v2, v3;
    cin >> v1 >> v2 >> v3;
    array<array<int, 3>, 3> a;
    a[0] = {0, 0, 0};
    constexpr int len = 7;
    constexpr int sz = 4 * len;
    array<array<array<int, sz>, sz>, sz> cnt{};
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len; ++j) {
            for (int k = 0; k < len; ++k) {
                cnt[i][j][k]++;
            }
        }
    }
    auto calc = [&](auto& cnt) {
        array<int, 4> tmp{};
        for (auto& i : cnt)
            for (auto& j : i)
                for (auto& k : j) {
                    tmp[k]++;
                }
        return tmp;
    };
    auto calc3 = [&](int i, int j, int k, int l, int m, int n, int o, int p,
                     int q) {
        int a = max(0, min({i + len, l + len, o + len}) - max({i, l, o}));
        int b = max(0, min({j + len, m + len, p + len}) - max({j, m, p}));
        int c = max(0, min({k + len, n + len, q + len}) - max({k, n, q}));
        return a * b * c;
    };
    auto calc2 = [&](int i, int j, int k, int l, int m, int n) {
        int a = max(0, min(i + len, l + len) - max(i, l));
        int b = max(0, min(j + len, m + len) - max(j, m));
        int c = max(0, min(k + len, n + len) - max(k, n));
        return a * b * c;
    };
    auto solve = [&]() {
        for (int i = -len; i <= len; ++i) {
            for (int j = -len; j <= len; ++j) {
                for (int k = -len; k <= len; ++k) {
                    for (int l = -len; l <= len; ++l) {
                        for (int m = -len; m <= len; ++m) {
                            for (int n = -len; n <= len; ++n) {
                                int n3 = calc3(0, 0, 0, i, j, k, l, m, n);
                                int n2 = calc2(0, 0, 0, i, j, k) +
                                         calc2(0, 0, 0, l, m, n) +
                                         calc2(i, j, k, l, m, n) - 3 * n3;
                                int n1 = 3 * len * len * len - n2 * 2 - n3 * 3;
                                if (n1 == v1 && n2 == v2 && n3 == v3) {
                                    a[1] = {i, j, k};
                                    a[2] = {l, m, n};
                                    return true;
                                }
                            }
                        }
                    }
                }
            }
        }
        return false;
    };
    if (solve()) {
        cout << "Yes" << '\n';
        for (auto& i : a)
            for (auto& j : i)
                cout << j << ' ';
        cout << '\n';
    } else
        cout << "No" << '\n';

    return 0;
}

F - Second Largest Query (abc343 F)

题目大意

\(n\)个数\(a_i\)， \(q\)个询问 ，分两种：

  • 1 p x，将\(a_p = x\)
  • 2 l r，问\(a_{l..r}\)的次大值的出现次数，

解题思路

可以考虑带修莫队，但貌似会超时。

注意到次大值的出现次数这信息是可合并的，即两个区间的这一信息，可以合并起来，得到更大区间的这一信息。

因此用线段树维护这一信息即可，对应的是单点修改和区间查询。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 2e5 + 8;

class segment {
#define lson (root << 1)
#define rson (root << 1 | 1)
  public:
    array<int, 2> max[N << 2];
    array<int, 2> cmax[N << 2];

    void pushup(int root) {
        array<array<int, 2>, 4> tmp = {max[lson], max[rson], cmax[lson],
                                       cmax[rson]};
        map<int, int> cnt;
        for (auto& x : tmp) {
            cnt[x[0]] += x[1];
        }
        max[root] = {cnt.rbegin()->first, cnt.rbegin()->second};
        cmax[root] = {0, 0};
        cnt.erase(cnt.rbegin()->first);
        if (!cnt.empty())
            cmax[root] = {cnt.rbegin()->first, cnt.rbegin()->second};
    }

    array<array<int, 2>, 2> combine(array<array<int, 2>, 2> a,
                                    array<array<int, 2>, 2> b) {
        array<array<int, 2>, 4> tmp = {a[0], a[1], b[0], b[1]};
        map<int, int> cnt;
        for (auto& x : tmp) {
            cnt[x[0]] += x[1];
        }
        array<array<int, 2>, 2> ret;
        ret[0] = {cnt.rbegin()->first, cnt.rbegin()->second};
        ret[1] = {0, 0};
        cnt.erase(cnt.rbegin()->first);
        if (!cnt.empty())
            ret[1] = {cnt.rbegin()->first, cnt.rbegin()->second};
        return ret;
    }

    void build(int root, int l, int r, vector<int>& a) {
        if (l == r) {
            max[root] = {a[l - 1], 1};
            cmax[root] = {0, 0};
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid, a);
        build(rson, mid + 1, r, a);
        pushup(root);
    }

    void update(int root, int l, int r, int pos, int val) {
        if (l == r) {
            max[root] = {val, 1};
            cmax[root] = {0, 0};
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            update(lson, l, mid, pos, val);
        else
            update(rson, mid + 1, r, pos, val);
        pushup(root);
    }

    array<array<int, 2>, 2> query(int root, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            return {max[root], cmax[root]};
        }
        int mid = (l + r) >> 1;
        array<array<int, 2>, 2> lret = {{{0, 0}, {0, 0}}},
                                rret = {{{0, 0}, {0, 0}}};
        if (L <= mid)
            lret = query(lson, l, mid, L, R);
        if (R > mid)
            rret = query(rson, mid + 1, r, L, R);
        return combine(lret, rret);
    }
} sg;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    sg.build(1, 1, n, a);
    while (q--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            sg.update(1, 1, n, x, y);
        } else {
            auto ret = sg.query(1, 1, n, x, y);
            cout << ret[1][1] << '\n';
        }
    }

    return 0;
}

G - Compress Strings (abc343 G)

题目大意

给定\(n\)个字符串，问最小长度的字符串，使得这 \(n\)个字符串都是该串的子串。

解题思路

注意到\(n\)只有 \(20\)。

考虑最朴素的做法，就是花\(O(n!)\)枚举这\(n\)个字符串的顺序，然后再把俩俩相邻的字符串中，重复的部分（最长前后缀）删去，得到一个字符串。所有这样的字符串长度取个最小值则为答案，

但还是有点小问题，在原来的\(n\)个字符串中，对于相同的字符串，我们肯定只保留一个，而对于子串的情况，该子串也不需要。因此得事先预处理，将相同串和子串的都去掉，可以用hash的方法在\(O(n^210^5)\)内做到。

考虑优化这个朴素做法，容易发现，当确定了前 \(i\)个字符串的顺序后， 对于第\(i+1\)个字符串取什么，使得拼接字符串的长度所造成的影响，只取决于第 \(i\)个字符串是什么，对于前面的字符串的顺序怎样没关系。

因此我们不必保留前 \(i\)个字符串的顺序 这一信息，只需知道我取了哪些字符串，且第 \(i\)个字符串是什么。通过这两个信息，我就可以进行转移：即选择哪个还未取的字符串，以及取了之后最终长度是多少。

因此设\(dp[i][j]\)表示我取的字符串的二进制表示为 \(i\) ，最后一个字符串是\(j\)的最小长度。

事先花\(O(n^2 10^5)\)预处理 \(cost[i][j]\)表示字符串 \(i\)（左）和字符串 \(j\)（右）拼接起来 后增加的长度（枚举前后缀长度，再hash判断是否相等）。这样转移时枚举下一个字符串后，就可以\(O(1)\)得到代价。因此转移的复杂度是 \(O(n)\)。

总的时间复杂度是 \(O(n^2 2^n)\)

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

typedef long long LL;
typedef unsigned long long ULL;

const int x = 135;
const int N = 2e5 + 10;
const int p1 = 1e9 + 7, p2 = 1e9 + 9;
ULL xp1[N], xp2[N], xp[N];

void init_xp() {
    xp1[0] = xp2[0] = xp[0] = 1;
    for (int i = 1; i < N; ++i) {
        xp1[i] = xp1[i - 1] * x % p1;
        xp2[i] = xp2[i - 1] * x % p2;
        xp[i] = xp[i - 1] * x;
    }
}

struct String {
    char s[N];
    int length, subsize;
    bool sorted;
    ULL h[N], hl[N];

    ULL hash() {
        length = strlen(s);
        ULL res1 = 0, res2 = 0;
        h[length] = 0; // ATTENTION!
        for (int j = length - 1; j >= 0; --j) {
#ifdef ENABLE_DOUBLE_HASH
            res1 = (res1 * x + s[j]) % p1;
            res2 = (res2 * x + s[j]) % p2;
            h[j] = (res1 << 32) | res2;
#else
            res1 = res1 * x + s[j];
            h[j] = res1;
#endif
            // printf("%llu\n", h[j]);
        }
        return h[0];
    }

    // 获取子串哈希，左闭右开区间
    ULL get_substring_hash(int left, int right) const {
        int len = right - left;
#ifdef ENABLE_DOUBLE_HASH
        // get hash of s[left...right-1]
        unsigned int mask32 = ~(0u);
        ULL left1 = h[left] >> 32, right1 = h[right] >> 32;
        ULL left2 = h[left] & mask32, right2 = h[right] & mask32;
        return (((left1 - right1 * xp1[len] % p1 + p1) % p1) << 32) |
               (((left2 - right2 * xp2[len] % p2 + p2) % p2));
#else
        return h[left] - h[right] * xp[len];
#endif
    }

    void get_all_subs_hash(int sublen) {
        subsize = length - sublen + 1;
        for (int i = 0; i < subsize; ++i)
            hl[i] = get_substring_hash(i, i + sublen);
        sorted = 0;
    }

    void sort_substring_hash() {
        sort(hl, hl + subsize);
        sorted = 1;
    }

    bool match(ULL key) const {
        if (!sorted)
            assert(0);
        if (!subsize)
            return false;
        return binary_search(hl, hl + subsize, key);
    }

    void init(const char* t) {
        length = strlen(t);
        strcpy(s, t);
    }
};

const int inf = 1e9;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init_xp();
    int n;
    cin >> n;
    vector<String> s(n);
    for (auto& i : s) {
        string x;
        cin >> x;
        i.init(x.c_str());
        i.hash();
    }
    vector<String> t;
    vector<int> sub(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j || sub[j])
                continue;
            if (s[i].length > s[j].length)
                continue;
            s[j].get_all_subs_hash(s[i].length);
            s[j].sort_substring_hash();
            if (s[j].match(s[i].h[0])) {
                sub[i] = true;
                break;
            }
        }
        if (!sub[i])
            t.push_back(s[i]);
    }
    n = t.size();
    int up = (1 << n);
    vector<vector<int>> dp(up, vector<int>(n, inf));
    dp[0][0] = 0;
    auto calc = [&](int i, int j) {
        int ans = min(t[i].length, t[j].length);
        while (ans > 0 &&
               t[i].get_substring_hash(t[i].length - ans, t[i].length) !=
                   t[j].get_substring_hash(0, ans))

            --ans;
        return t[j].length - ans;
    };
    vector<vector<int>> cost(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j)
                continue;
            cost[i][j] = calc(i, j);
        }
    }
    for (int i = 0; i < n; ++i)
        dp[1 << i][i] = t[i].length;
    for (int i = 0; i < up; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) {
                for (int k = 0; k < n; ++k) {
                    if (j != k && i & (1 << k)) {
                        dp[i][j] =
                            min(dp[i][j], dp[i ^ (1 << j)][k] + cost[k][j]);
                    }
                }
            }
        }
    }
    cout << ranges::min(dp.back()) << '\n';

    return 0;
}

标签：AtCoder,cnt,Beginner,int,max,len,long,343,字符串
From： https://www.cnblogs.com/Lanly/p/18058486

相关文章

  • AT_abc343_G [ABC343G] Compress Strings 题解
    分析水题，评分能有$2100$可能是因为很多人卡E了。我说真的，E好难啊。$n$只有$20$，考虑从状压的角度入手。定义状态函数$f_{s,i}$表示当某个字符串$T$包含了所有$s$的二进制中为$1$的下标$S_j$且$T$末尾包含的子串为$S_i$时$T$的最小长度。那很显然的就有转......
  • abc343比赛总结
    写在前面A简单，随便取两个值判一下，不过这道题的名字不吉利，叫什么WA啊？B简单，读入的时候判断一下是不是\(1\)就行了。Ｃ有点点难，题目不是那么好理解（尤其是英文不好的话）。虽然说\(N\le10^{18}\)但是仔细算一下其实只需要1e6的遍历一遍就够了，毕竟有个三次方。D......
  • abc343G 题解
    题意给你\(N\)个由小写字母组成的字符串\(S_1,S_2,\ldots,S_N\)，找出一个母串使得它包含所有这些字符串作为它的子串，最小化该母串的长度并输出。\(1\leqN\leq20\)，\(\sum|S_i|\leq2\times10^5\)（没错洛谷翻译就是我写的）思路首先如果有一个字符串被另一个字符串......
  • AtCoder Beginner Contest 321
    \[\large\text{Round12:AtCoderBeginnerContest321}\]一言:只要你在，我便无所不能。——进击的巨人感觉只有最后一道题有点意思，其他的就是时间问题，但是速度还是不够快，思维要跟上啊。有意思的是，周考考了回退背包，这里居然又来一次。。\(\text{G:ElectricCircuit}......
  • AtCoder Regular Contest 171
    \[\large\text{Round13:AtCoderRegularContest171}\]一言:我并不是要失去自由，而是要去收获那无可替代的不自由。——SSSS.电光机王几年没写了，但是我们仍然要捡回来！没啥好写的，T1，T2能力范围之内，T3不会，T4感觉很好，但是没做出来。\(\text{D:RollingHash}\)这题无论......
  • AtCoder Beginner Contest 298
    \[\large\text{Round5:AtCoderBeginnerContest298(VP)}\]一言:成一事者，是失之不渝的愚者；毁一事者，是停滞不前的贤者。——不正经的魔法讲师\(\text{Ex:SumofMinofLength}\)这次比赛总体难度不是很大，可能也是我第一次自己独立做出\(\text{Ex}\)。（虽然不是场切......
  • AtCoder Beginner Contest 315
    \[\large\text{Round6:AtCoderBeginnerContest315}\]一言:愿悲、爱恋、你和宇宙以及那颗星辰，能够永远拥抱我们。——THEBEYOND-機動戦士ガンダム40周年纪念曲这场打的一般，主要还是一开始网卡爆了把心态弄得很不好，一定程度上影响了发挥。\(\text{G:Ai+Bj+Ck......
  • AtCoder Beginner Contest 310
    \[\large\text{Round8:AtCoderBeginnerContest310(VP)}\]一言:虚伪的眼泪，会伤害别人，虚伪的笑容，会伤害自己。——反叛的鲁鲁修\(\text{F}\)竟然没有第一时间想到状压，还是太蒟了。。\(\text{F:Make10Again}\)这题看到一个子集，再加上子集和的范围只需要考虑小于......
  • AtCoder Beginner Contest 313
    \[\large\text{Round2:AtCoderBeginnerContest313(VP)}\]一言：当我拔出第二把剑时，就是为了我所爱之人——刀剑神域这场比赛真的是大败而归，只A了\(A,B,C,E\)。。。虽然但是，\(F,G\)确实不可做，但是\(D\)题还是有点可惜了。\(\text{D:OddorEven}\)感觉考场......
  • ABC343 A~E 解题报告
    A-WrongAnswer模拟题，只需要每次输出\(0\)到\(9\)内不等于\(a+b\)的值就行了。#include<bits/stdc++.h>usingnamespacestd;template<typenameT>Tread(Tx){Topt=1,sum=0;charch=getchar();while(!isdigit(ch)){if(ch=='-')opt=......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99