AtCoder Beginner Contest 347

A - Divisible (abc347 A)

题目大意

给定\(n\)个数\(a_i\)以及\(k\),输出是 \(k\)的倍数的\(a_i\)整除以 \(k\)的值。

解题思路

按照题意判断取模和求整除即可。

神奇的代码
#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, k;
    cin >> n >> k;
    while (n--) {
        int a;
        cin >> a;
        if (a % k == 0)
            cout << a / k << ' ';
    }
    cout << '\n';

    return 0;
}



B - Substring (abc347 B)

题目大意

给定字符串\(s\),问子串种类数。

解题思路

\(|s|\)只有 \(100\),直接 \(O(n^2)\)枚举子串丢进 \(set\)里,答案就是 \(set\)的大小。

长度大的话得后缀自动机。

神奇的代码
#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;
    set<string> ans;
    for (int i = 0; i < s.size(); ++i)
        for (int j = i; j < s.size(); ++j) {
            ans.insert(s.substr(i, j - i + 1));
        }
    cout << ans.size() << '\n';

    return 0;
}



C - Ideal Holidays (abc347 C)

题目大意

一周前\(a\)天假期,后 \(b\)天工作日。

给定 \(n\)天的安排,问第一个安排定在哪天,使得每个安排都在假期。

解题思路

先让安排日期对\(a+b\)取模,剩下的问题就是, \([0,a+b-1]\)数轴上有一堆点,问能否有一个长度为 \(a\)的区间覆盖了所有点。

枚举覆盖的左端点,看与最右边的点的距离是否超过 \(a\)即可。

注意计算\(a+b+d_i\)会超 \(int\)范围。

神奇的代码
#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, a, b;
    cin >> n >> a >> b;
    LL tot = a + b;
    vector<LL> d;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        --x;
        x %= tot;
        d.push_back(x);
        d.push_back(x + tot);
    }
    ranges::sort(d);
    LL dis = numeric_limits<LL>::max();
    for (int i = 0; i < n; i++) {
        dis = min(dis, d[i + n - 1] - d[i] + 1);
    }
    if (dis <= a)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}



D - Popcount and XOR (abc347 D)

题目大意

给定\(a,b,c\),输出一对 \(x,y\),满足:

  • \(x < 2^{60}, y < 2^{60}\)
  • \(popcount(x) = a\)
  • \(popcount(y) = b\)
  • \(x \oplus y = c\)

\(popcount(x)\)即返回 \(x\)在二进制下\(1\)的个数。 \(\oplus\)是异或。

解题思路

构造题。

假设\(c\)在二进制下 \(1\)的个数为 \(cnt\)

那么这 \(cnt\)\(1\)要分配在 \(x,y\)里。假设分配了 \(l\)\(1\)\(x\)\(r\)\(1\)\(y\),其中 \(l+r=cnt\)

此时 \(x\)还剩下 \(a-l\)\(1\)\(y\)还剩下 \(b-r\)\(1\)要分配,这些 \(1\)的分配需要在 \(\oplus\)时抵消掉。

所以应有 \(a-l=b-r\)。结合 \(l+r=cnt\)可以解得 \(l,r\)值。

\(over=\frac{a+b-cnt}{2}\)是分配给\(x,y\)\(1\),以在 \(\oplus\)时抵消。

剩下的\(a-over\)\(b-over\)是分配给 \(x,y\),以凑成 \(c\)

因此就逐位遍历 \(c\),如果是 \(1\),则分配给 \(x\)\(y\)(看\(a,b > 0\)),如果是 \(0\),则都分配给 \(x,y\)(如果 \(over > 0)\)

至于无解条件,一个是 \(a+b < c\),一个是 \(a+b-cnt\)不是偶数,还有的情况难以言说,比如 \(a=60,b=60,cnt=60\),因为限定了\(x < 2^{60},y < 2^{60}\),没有多余的位置分配给用于抵消\(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 a, b;
    LL c;
    cin >> a >> b >> c;
    int aa = a, bb = b;
    auto popcount = [](LL x) {
        int ret = 0;
        while (x) {
            ret += x & 1;
            x >>= 1;
        }
        return ret;
    };
    int cc = popcount(c);
    if (cc > a + b || ((a + b - cc) & 1)) {
        cout << -1 << '\n';
        return 0;
    }

    int over = (a + b - cc) / 2;
    a -= over;
    b -= over;
    if (a < 0 || b < 0) {
        cout << -1 << '\n';
        return 0;
    }

    LL A = 0, B = 0;
    for (int i = 0; i < 60; i++) {
        if (c & (1LL << i)) {
            if (a) {
                A |= 1LL << i;
                a--;
            } else if (b) {
                B |= 1LL << i;
                b--;
            } else {
                assert(0);
            }
        } else if (over) {
            A |= 1LL << i;
            B |= 1LL << i;
            over--;
        }
    }
    if (popcount(A) != aa || popcount(B) != bb) {
        cout << -1 << '\n';
        return 0;
    }
    cout << A << ' ' << B << '\n';

    return 0;
}



E - Set Add Query (abc347 E)

题目大意

初始\(n\)\(0\)的数组\(a_i\)和空集合\(s\)。进行以下 \(q\)次操作。

每次操作给定一个 \(x\)

  • 如果 \(x\)在集合里,移除它,否则放入它。
  • 对于\(j \in s\),\(a_j += |s|\)

解题思路

朴素的模拟的复杂度是\(O(nq)\),考虑在这个过程,每个操作后,都要遍历一下集合里的元素,给数组\(a\)的对应位置相加。

当一个数\(x\)在集合 \(s\)里时,每个操作之后都会对 \(a_x\)作贡献,直到它被移除集合。

每次操作都计算贡献的话,就是朴素的模拟,复杂度上限就是 \(O(nq)\)。要优化,就不能每次操作算贡献了。

注意到一个数 \(x\)做出的贡献是一个连续的操作区间,贡献值就是这个操作区间的 \(|s|\)的和。那我们可以维护一个关于操作顺序的 \(|s|\)的前缀和\(presum\),当 \(x\)被移除时,我们就结算它对 \(a_x\)的贡献:就一个前缀和的相减,这里需要记录下\(x\)何时放入的。

操作结束后,再对还在\(s\)里的元素结算下贡献就好了。

神奇的代码
#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, q;
    cin >> n >> q;
    vector<LL> presum;
    presum.push_back(0);
    set<int> s;
    vector<int> la(n, 0);
    vector<LL> ans(n, 0);
    for (int i = 1; i <= q; ++i) {
        int x;
        cin >> x;
        --x;
        if (s.count(x)) {
            ans[x] += presum[i - 1] - presum[la[x] - 1];
            s.erase(x);
        } else {
            la[x] = i;
            s.insert(x);
        }
        presum.push_back(presum.back() + s.size());
    }
    for (auto& i : s) {
        ans[i] += presum[q] - presum[la[i] - 1];
    }
    for (auto& i : ans) {
        cout << i << ' ';
    }
    cout << '\n';

    return 0;
}



F - Non-overlapping Squares (abc347 F)

题目大意

给定一个\(n \times n\)的网格,问三个不重叠的 \(m \times m\)的网格覆盖,和的最大值。

解题思路

<++>

神奇的代码



G - Grid Coloring 2 (abc347 G)

题目大意

<++>

解题思路

<++>

神奇的代码



热门相关:宠宠欲恋   神秘复苏   遥望行止   盖世双谐   修罗武帝