ABC363(A-F)

A - Piling Up

题目大意

在 Atcoder 中，每隔 \(100\) 分是一个级别，其中 \([1, 99]\)，\([100, 199]\)，\([200, 299]\)，\([300, 399]\) 各自代表一个级别。输入一个分数 \(R\)，问：至少需要增加多少分才能进入下一个级别？

参考代码

C++

#include <iostream>

using namespace std;

int main()
{
    int x;
    cin >> x;
    cout << 100 - (x % 100) << endl;    
    return 0;
}

---

B - Japanese Cursed Doll

题目大意

有 \(N\) 个人，初始时，第 \(i\) 个人的头发是 \(L_i\)。每个人的头发在 \(1\) 天结束后可以增加 \(1\)。问：从哪一天开始才有至少 \(P\) 个人的头发长度大于等于 \(T\) ？

解题思路

排序取第 \(P\) 个人的长度即可。

参考代码

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n, t, p;
    cin >> n >> t >> p;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end(), greater<int>());
    cout << max(0, t - a[p-1]) << endl;
    return 0;
}

---

C - Avoid K Palindrome 2

题目大意

给你一个长度为 \(N(1 \le N \le 10)\) 的字符串 \(S\)，问：有多少个 \(S\) 的排列不存在长度为 \(K\) 的回文子串？

解题思路

\(N \le 10\)，直接枚举全排列即可。

参考代码

C++

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    int ans = 0;
    do
    {
        auto check = [&s, k](int x) -> bool
        {
            for (int i = x, j = x + k - 1; i < j; i++, j--)
                if (s[i] != s[j])
                    return false;
            return true;
        };
        bool flag = true;
        for (int i = 0; i + k - 1 < n; i++)
            if (check(i))
            {
                flag = false;
                break;
            }
        ans += flag;
    } while (next_permutation(s.begin(), s.end()));
    cout << ans << endl;
    return 0;
}

---

D - Palindromic Number

题目大意

给你一个整数 \(N(1 \le N \le 10 ^ {18})\)，问：第 \(N\) 个回文数字是多少？

解题思路

对于回文数字，其前半段（如果是奇数长度，还需要算上最中间的数）就能唯一确定整个数字。

因此，回文数字的大小实际对应前半段的数字大小。除了数字 \(0\) 之外，第一个数字不能为 \(0\)，可以很容易知道，长度为 \(1\) 的前半段有 \(10\) 个（算上 \(0\)），从长度 \(k(k \ge 2)\) 开始，长度为 \(k\) 的前半段最多有 \(9 \times 10 ^{k-1}\) 个。因此，按照每一次乘以 \(10\) 倍来枚举即可。

参考代码

C++

#include <iostream>

#include <algorithm>

using namespace std;
using LL = long long;

int main()
{
    LL n;
    cin >> n;
    if(n <= 10)
    {
        cout << n - 1;
        return 0;
    }
    n -= 10;
    LL k = 9;
    for(int len = 2; ; len++)
    {
        if(n <= k)
        {
            int strlen = (len + 1) / 2;
            string str = to_string(n-1);
            string zero(strlen - str.size(), '0');
            str = zero + str;
            str[0]++;
            cout << str;
            if(len & 1)
                str.pop_back();
            reverse(str.begin(), str.end());
            cout << str;
            break;
        }
        n -= k;
        if(len % 2 == 0)
            k *= 10;
    }
    return 0;
}

---

E - Sinking Land

题目大意

给你一个 \(H \times W(1 \le H, W \le 1000)\) 的二维矩阵，矩阵中每一个位置代表岛屿。最外围的岛屿被海平面包围。在矩阵中，\(A_{i, j}\) 代表岛屿相对于海平面的高度。每隔一年，海平面高度上升 \(1\)，同时，有一些岛屿可能会被淹没。位于矩阵第 \(i\) 行第 \(j\) 列的岛屿淹没的条件是：

• 矩阵第 \(i\) 行第 \(j\) 列的岛屿的上下左右至少一个方向与海平面邻接。
• \(A_{i, j}\) 小于当前海平面的高度。

某个岛屿被淹没之后，岛屿的位置就会变成海平面，这有可能导致新的岛屿被淹没。

给你一个整数 \(Y\)， 对于 \(i = 1, 2, \cdots, Y\)，求出第 \(i\) 年过后还剩下多少岛屿没有被淹没。

解题思路

某个岛屿被淹没后连锁淹没的情况可以 dfs 处理，dfs 处理过程中，对于目前比海平面更高的岛屿，加到小根堆当中。

初始的时候，只需将四周的所有岛屿加入堆中，然后每过一年，取出堆顶的岛屿，如果被淹没就出堆，同时 dfs。

参考代码

C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Node
{
    int r, c, h;
    bool operator>(const Node &other) const
    {
        return h > other.h;
    }
};

int main()
{
    int n, m, y;
    cin >> n >> m >> y;

    vector<vector<int>> h(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> h[i][j];

    vector<vector<bool>> vis(n, vector<bool>(m));
    priority_queue<Node, vector<Node>, greater<Node>> heap;

    for (int i = 0; i < m; i++)
    {
        vis[0][i] = true;
        heap.push({0, i, h[0][i]});
        if(n > 1)
        {
            vis[n - 1][i] = true;
            heap.push({n - 1, i, h[n - 1][i]});
        }
    }
    for (int i = 1; i < n - 1; i++)
    {
        vis[i][0] = true;
        heap.push({i, 0, h[i][0]});
        if(m > 1)
        {
            vis[i][m - 1] = true;
            heap.push({i, m - 1, h[i][m - 1]});
        }
    }

    int cnt = n * m;

    auto dfs = [&](auto &&self, int r, int c, int now) -> void
    {
        auto inlim = [n, m](int r, int c) -> bool
        {
            return r >= 0 && r < n && c >= 0 && c < m;
        };

        const int dr[] = {-1, 1, 0, 0};
        const int dc[] = {0, 0, -1, 1};

        cnt--;
        for (int i = 0; i < 4; i++)
        {
            int nr = r + dr[i], nc = c + dc[i];
            if (!inlim(nr, nc) || vis[nr][nc])
                continue;
            vis[nr][nc] = true;
            if (h[nr][nc] <= now)
                self(self, nr, nc, now);
            else
                heap.push({nr, nc, h[nr][nc]});
        }
    };

    for (int i = 1; i <= y; i++)
    {
        while (!heap.empty() && heap.top().h == i)
        {
            dfs(dfs, heap.top().r, heap.top().c, i);
            heap.pop();
        }
        cout << cnt << '\n';
    }

    return 0;
}

---

F - Palindromic Expression

题目大意

给你一个整数 \(N(1 \le N \le 10^{12})\)，构造出满足下列所有条件的字符串 \(S\)

• \(1 \le |S| \le 1000\)，且 \(S\) 由 1 2 3 4 5 6 7 8 9 * （注意：没有字符 0 ）这些字符组成。
• \(S\) 是一个回文字符串。
• \(S\) 的首字母不能是 *。
• 将字符 * 解释为乘法符号后，字符串 \(S\) 的表达式的计算结果等于 \(N\)

如果能够造出 \(S\)，输出 \(S\)，否则输出 -1。

解题思路

稍微推理一下性质。

• 首先，如果存在 \(S\)，对于条件 \(1 \le |S| \le 1000\) 实际上我们一定可以在长度 \(1000\) 之内构造出 \(S\)，这是因为最浪费长度的字符串应该是 2*2*2*2*2*...*2，所以长度 \(1000\) 的限制不用考虑。

我们定义 \(dp[i]\) 满足前 \(3\) 个条件，且表达式计算的结果等于 \(i\) 的字符串。如果不存在这样的字符串，则 \(dp[i]\) 的结果为空字符串。

显然，如果 \(i\) 本身就是一个回文数字（且不含 \(0\)），\(dp[i]\) 的结果就是 \(i\) 对应的字符串。

否则，我们必须借助乘法符号，于是考虑枚举最左边的数字，在枚举的时候还需要考虑到右边的数字需要和左边数字回文对称。然后将 \(i\) 除掉左右两边数字，继续递归。

考虑优化枚举的效率：我们可以提前预处理出 \(N\) 的所有合法的因数，这里“合法指的是”每个因数必须不包含 0，且保证 \(N\) 能整除 “因数 \(\times\) 回文因数”。这样筛选之后，因数的个数不会很多，记忆化搜索一波就可以了。

参考代码

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;
using LL = long long;

int main()
{
    LL n;
    cin >> n;

    auto check_no_zero = [](LL num) -> bool
    {
        string s = to_string(num);
        return s.find("0") == string::npos;
    };

    auto rev = [](LL num) -> LL
    {
        string s = to_string(num);
        reverse(s.begin(), s.end());
        return stoll(s);
    };

    vector<LL> factor;
    for (LL x = 2; x * x <= n; x++)
        if (check_no_zero(x) && n % x == 0 && n / x % rev(x) == 0)
            factor.emplace_back(x);

    auto check = [&check_no_zero](LL num) -> bool
    {
        if (!check_no_zero(num))
            return false;
        string s = to_string(num);
        for(int i = 0, j = s.size() - 1; i < j; i++, j--)
            if(s[i] != s[j])
                return false;
        return true;
    };

    unordered_map<LL, string> res;
    auto DP = [&](auto &&self, LL num) -> string
    {
        if (auto it = res.find(num); it != res.end())
            return it->second;
        if(check(num))
            return res[num] = to_string(num);

        res[num] = "";

        for (auto x : factor)
        {
            if (x * x > num)
                break;
            LL rx = rev(x);
            if (num % x != 0 || num / x % rx != 0)
                continue;
            if (x * rx > num)
                continue;
            if (x * rx == num)
            {
                res[num] = to_string(x) + "*" + to_string(rx);
                break;
            }
            string mid = self(self, num / x / rx);
            if (!mid.empty())
            {
                res[num] = to_string(x) + "*" + mid + "*" + to_string(rx);
                break;
            }
        }

        return res[num];
    };

    string ans = DP(DP, n);
    cout << (ans.empty() ? "-1" : ans) << endl;;
    return 0;
}

---

---

最后更新: 2024-07-26
创建日期: 2024-07-26