AtCoder Beginner Contest 336

A - Long Loong (abc336 A)

题目大意

给定一个数\(n\),将 long中的o重复\(n\)次后输出。

解题思路

模拟即可。

神奇的代码
#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;
    cout << "L" << string(n, 'o') << "ng" << '\n';

    return 0;
}



B - CTZ (abc336 B)

题目大意

给定一个数\(n\),问 \(n\)的二进制表示下的末尾零的数量。

解题思路

即找到最小的\(i\)使得 \(n & (1 << i)\) 不为零的位置。枚举即可。

或者直接用内置函数 __builtin_ctz。(count tail zero?

神奇的代码
#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 x;
    cin >> x;
    cout << __builtin_ctz(x) << '\n';

    return 0;
}



C - Even Digits (abc336 C)

题目大意

定义一个数种类,每个数位都是偶数。

给定\(n\),问第 \(n\)大的数。

解题思路

每一位的取值只有0,2,4,6,8五种,其实就是一个5进制的转换,再将每个数位乘以\(2\)即可。

神奇的代码
#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;
    --n;
    string ans;
    while (n) {
        ans += (n % 5) * 2 + '0';
        n /= 5;
    }
    reverse(ans.begin(), ans.end());
    if (ans.empty())
        ans = "0";
    cout << ans << '\n';

    return 0;
}



D - Pyramid (abc336 D)

题目大意

给定一个数组\(a\),求经过以下操作可以得到的最长的金字塔序列。

金字塔序列形如\(1,2,3,4,5,...,k-1,k,k-1,...,5,4,3,2,1\)

可进行的操作为:

  • 将某数减1
  • 将开头或末尾的数移除

解题思路

考虑这个金字塔序列的特点,如果选择中间最高点的\(k\)的位置,以及 \(k\)的值,那剩下的就是看从该位置左右延伸,是否都不小于对应的值。但这复杂度是 \(O(n^3)\),不大行。

注意到金字塔序列是一个对称的,可以考虑 \(1\)的位置,然后看看能往左和往右延伸到多远。那最后再枚举左边的 \(1\)的位置和右边 \(1\)的位置, 看看它们往右和往左延伸的距离能不能覆盖这两个\(1\)之间的值。

考虑如何求从 \(a_i\)往右能延伸多远,假设能延伸到\(a_j\),就要要求这期间的 \(a_k\)都满足 \(a_k \leq k - i + 1\)。朴素求法是 \(O(n^2)\)。但注意到一个性质,比如 \(a_i\)能延伸到 \(a_j\),那 \(a_{i+1}\)至少也会延伸到 \(a_{j}\),因为原本在\(a_i\)为起点时,\(k \in [i,j]\)需要满足 \(a_k \leq k - i + 1\), 而以\(a_{i+1}\)为起点时需要满足的是 \(a_k \leq k - i\) ,条件更松了,之前满足的也肯定满足,因此求\(a_{i+1}\)时直接从上次的 \(a_j\)继续往右延伸即可,而不必重新从\(a_{i+1}\)开始求 。即双指针的求法,复杂度是\(O(n)\)

往左和往右的求法是一样的,当求出从 \(a_i\)往左和往右延伸的最远距离 \(l_i\)\(r_i\)后,如果枚举两个 \(1\)的位置判断,那还是 \(O(n^2)\)不行。但容易发现这个也可以用双指针的方法枚举两个 \(1\)的位置。因此时间复杂度就是 \(O(n)\)

注意金字塔序列的长度是奇数。

神奇的代码
#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;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    auto solve = [&](vector<int>& a) {
        vector<int> pos(n);
        int l = 0;
        for (int i = 0; i < n; ++i) {
            while (l < i && a[i] <= i - l) {
                pos[l] = i - l;
                ++l;
            }
        }
        while (l < n) {
            pos[l] = n - l;
            ++l;
        }
        return pos;
    };
    auto r = solve(a);
    ranges::reverse(a);
    auto l = solve(a);
    int ans = 0;
    ranges::reverse(l);
    int R = 0;
    for (int L = 0; L < n; ++L) {
        while (R < n && r[L] + l[R] >= R - L + 1) {
            if ((R - L + 1) & 1)
                ans = max(ans, (R - L + 1) / 2 + 1);
            ++R;
        }
    }
    cout << ans << '\n';

    return 0;
}



E - Digit Sum Divisible (abc336 E)

题目大意

给定\(n\),问 \(1 \sim n\)中,能被自己的数位和整除的数的个数。

解题思路

\(n\)\(10^{14}\),显然不能枚举求。

对能整除的数的计数,可以从高位到低位一位一位地考虑,只要知道高位对除数的取余结果,就可以决定低位的取值,进而知道取余的结果变为多少,最后看是否为 \(0\)来判断是不是整除。即一个经典的数位\(dp\)的形式。

但棘手的是 除数不是固定的,它是由一个数的数位和决定,在一般的数位\(dp\)过程中,其数位和会变化,即除数会变化,这就导致余数不能求得,进而最后的能否整除就难以判断。

但注意到数位和的范围不大,它只有\([1,9\times 14]\),可以考虑枚举数位和\(sum\), 那剩下的就是求:数位和是\(sum\),且对\(sum\) 取余结果为\(0\)的值的数的个数。

这两个都是常规条件,数位\(dp\)即可解决。

时间复杂度为\(O((10\log n)^4)\)

数位\(dp\)就考虑递归的形式,从高位到低位考虑每一位的取值,记录中间状态有:当前考虑的位数,取值是否受\(n\)的限制,高位的取余结果,已经填的高位的数位和(下述代码里是低位需要的数位和,反了过来)。然后记忆化一下。记忆化的数组\(dp[pos][mod][sum]\)可以理解成:已经填了\(pos\)的高位,其取余结果为 \(mod\),数位和为 \(sum\)时,低位的全部填法中,满足题目要求(取余为\(0\)和数位和)的填法数量。

有时候 \(dp\)数组会加一维 \(limit\),这个可有可无, 没有的话就这部分会重复求解,但因为数量不多,所以不会太费时间。有的话就可能会更快,但会费点空间。

神奇的代码
#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;
    vector<int> s;
    while (n) {
        s.push_back(n % 10);
        n /= 10;
    }
    ranges::reverse(s);
    LL ans = 0;
    int maxsum = 9 * min(14ul, s.size());
    vector<vector<vector<LL>>> dp(
        s.size(), vector<vector<LL>>(maxsum + 1, vector<LL>(maxsum + 1, -1)));
    auto solve = [&](auto self, int pos, int limit, int mod, int sum,
                     int div) -> LL {
        if (sum < 0)
            return 0ll;
        if (pos == s.size())
            return LL(mod == 0 && sum == 0);
        if (!limit && dp[pos][mod][sum] != -1)
            return dp[pos][mod][sum];
        int up = (limit ? s[pos] : 9);
        LL ret = 0;
        for (int i = 0; i <= up; ++i) {
            ret += self(self, pos + 1, limit && i == up, (mod * 10 + i) % div,
                        sum - i, div);
        }
        if (!limit)
            dp[pos][mod][sum] = ret;
        return ret;
    };
    for (int i = 1; i <= maxsum; ++i) {
        for (auto& i : dp)
            for (auto& j : i)
                ranges::fill(j, -1);
        auto ret = solve(solve, 0, 1, 0, i, i);
        ans += ret;
    }
    cout << ans << '\n';

    return 0;
}



F - Rotation Puzzle (abc336 F)

题目大意

给定一个\(h \times w\)的矩阵,\([1,h\times w]\)的恰好填了一次。

问能否经过不超过 \(20\)次操作,使得矩阵变成一个正常的矩阵,即\((i,j)\)上的数是 \(((i-1) \times w + j)\)。若可,输出最小的操作次数。

操作为:选定一个 \((h-1) \times (w-1)\) 的子矩阵,旋转\(180\)度。

解题思路

注意到只有\(4\)个子矩阵,那每次操作其实只有 \(4\)种选择,直接\(BFS\)的复杂度是 \(O(4^20)\),即 \(O(2^40)\)

注意到这是个非常特别的复杂度,它的一半即 \(O(2^20)\)是可做的。

注意到起始局面和终点局面都是已知的,且操作都是可逆的。因此可以从起点和终点分别$BFS$10步, 然后看搜得的局面是否有交集,取步数和最小值即可。

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

const int inf = 1e9;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int h, w;
    cin >> h >> w;
    vector<vector<int>> a(h, vector<int>(w));
    for (auto& i : a)
        for (auto& j : i)
            cin >> j;
    vector<vector<int>> b(h, vector<int>(w));
    for (int i = 0, cnt = 1; i < h; ++i)
        for (int j = 0; j < w; ++j) {
            b[i][j] = cnt;
            cnt++;
        }
    auto tr = [&](vector<vector<int>>& st, int x, int y) {
        auto ret = st;
        for (int i = x; i < x + h - 1; ++i)
            for (int j = y; j < y + w - 1; ++j) {
                ret[i][j] = st[h - 2 - (i - x) + x][w - 2 - (j - y) + y];
            }
        return ret;
    };
    auto BFS = [&](vector<vector<int>>& st, int up) {
        map<vector<vector<int>>, int> dis;
        queue<vector<vector<int>>> team;
        team.push(st);
        dis[st] = 0;
        while (!team.empty()) {
            auto u = team.front();
            team.pop();
            if (dis[u] == up)
                break;
            for (int i = 0; i <= 1; ++i)
                for (int j = 0; j <= 1; ++j) {
                    auto v = tr(u, i, j);
                    if (dis.count(v))
                        continue;
                    dis[v] = dis[u] + 1;
                    team.push(v);
                }
        }
        return dis;
    };
    auto sol1 = BFS(a, 10);
    auto sol2 = BFS(b, 10);
    int ans = inf;
    for (auto& [tu, dis] : sol1) {
        if (sol2.count(tu)) {
            ans = min(ans, dis + sol2[tu]);
        }
    }
    if (ans == inf)
        ans = -1;
    cout << ans << '\n';

    return 0;
}



G - 16 Integers (abc336 G)

题目大意

给定\(16\)个数 \(x_{i,j,k,l}\)

\(n\)为这 \(16\)个数的和。

问一个长度为 \(n+3\)\(01\)数组\(a\)的数量,满足以下条件:

  • 对于每一个数 \(x_{i,j,k,l}\),数组\(a\)中恰好有 \(x_{i,j,k,l}\)个下标\(s\)满足:\(a_s = i, a_{s+1} = j, a_{s + 2}=k, a_{s+3}=l\)

解题思路

感觉是个神仙题,以后再来探索吧

神奇的代码



热门相关:随身英雄杀   唐土万里   少林武僧在异界   重生隐婚:Hi,高冷权少!   天河大帝