Atcoder Beginner Contest 400 题解

C

题意

给定一个数 \(n\)，求 \([1, n]\) 内满足 \(2^a \times b^2 = x\) 的 \(x\) 的个数。

题解

显然我们应该枚举阶乘而不是根号，否则时间复杂度太大，那么我们枚举 \(2^i\)，显然需要找到满足 \(2^i\times b^2 \le n\) 的最大的 \(b\)，可以二分。但是这样计数会有重叠，比如 32 可以等于 \(2^1\times 4^2\)，也可以等于 \(2^3\times 2^2\)，由于左边都是跟 2 有关的，我们只取右边的奇数就一定不会重复，但是要小心溢出。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    i64 n;
    cin >> n;
    i64 ans = 0;
    for (int i = 1; i < 63; i++) {
        if ((1ll << i) <= n) {
            u128 x = 1ll << i, y = 0;
            u128 lo = 1, hi = sqrt(n) + 1;
            while (lo <= hi) {
                u128 mid = lo + (hi - lo) / 2;
                if (mid * mid * x <= n) {
                    lo = mid + 1;
                    y = mid;
                } else {
                    hi = mid - 1;
                }
            }
            ans += (y + 1) / 2;
        } else {
            break;
        }
    }
    cout << ans << "\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

给定一个含有障碍物的迷宫，可以花费 1 权重选择一个方向摧毁最近的两个障碍物，给定起点和终点，求到达终点需要消耗的最少权重。

题解

到达周围的地方要么消耗 0 ，要么消耗 1，考虑 0-1 BFS，优先走消耗少的地方。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

constexpr int dx[] = {0, 0, 1, -1};
constexpr int dy[] = {1, -1, 0, 0};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> s(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] = " " + s[i];
    }
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    deque<array<int, 3>> q;
    q.push_front({a, b, 0});
    vector<vector<int>> dis(n + 1, vector<int>(m + 1, -1));
    while (!q.empty()) {
        auto [x, y, d] = q.front();
        q.pop_front();
        if (dis[x][y] != -1) {
            continue;
        }
        dis[x][y] = d;
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 2; j++) {
                int fx = x + dx[i] * j;
                int fy = y + dy[i] * j;
                if (1 <= fx && fx <= n && 1 <= fy && fy <= m) {
                    if (j == 1 && s[fx][fy] == '.') {
                        q.push_front({fx, fy, d});
                    } else {
                        q.push_back({fx, fy, d + 1});
                    }
                }
            }
        }
    }
    cout << dis[c][d] << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E

题意

给定 \(q\) 次询问，每次给定一个数 \(n\)，回答小于等于 \(n\) 的最大数 \(x\)，满足 \(x\) 只含有两个大于 1 的因数，且分解后 \(x\) 两个因数的幂都是偶数。

题解

设 \(x = p^{2a}\times q^{2b}\)，那么有 \(\sqrt{x} = p^a\times q^b\)，就排除了偶数的干扰，接下来只需要找范围内最大的满足只含有两个因数的数了。考虑在欧拉筛中处理出每个数的因数个数 \(pb_x\)，对于素数显然有 \(pb_x = 1\)，是合数的话先判断是不是同一个素数的幂，不是的话有 \(pb_x = pb_{y} + 1\)，\(y\) 是 \(x\) 除以它的最小因数的结果。然后进行一个简单的转移：如果当前数因数个数为 2，范围内最大值就是它了，否则从前一个数转移过来。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

// minp(x) 可以找到 x 大于 1 的最小质因子
vector<int> minp, primes, np, lst;
void sieve(int n) {
    minp.assign(n + 1, 0);
    np.assign(n + 1, 0);
    primes.clear();
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            np[i] = 1;
            primes.push_back(i);
        }
        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                np[i * p] = np[i];
                break;
            }
            np[i * p] = np[i] + 1;
        }
    }
    lst.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        lst[i] = np[i] == 2 ? i : lst[i - 1];
    }
}

void solve() {
    sieve(1e6);
    int q;
    cin >> q;
    while (q--) {
        i64 a;
        cin >> a;
        a = sqrt(a);
        a = lst[a];
        a *= a;
        cout << a << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F

题意

把一个环涂色，操作为：选择三个数 \(a,b,c\)，将所有 \(a+i\) 位置涂成 \(c\) 颜色，满足 \(0\le i<b\)，耗费 \(x_c + b\) 代价，求把环涂成给定颜色的最小代价。

题解

需要破环成链。

显然区间 dp，设 \(dp_{i,j}\) 表示将 \([i,j]\) 涂上指定颜色的最小代价，可以预处理单个位置的情况 \(dp_{i,i} = x_{c_i} + 1\)，我们发现唯一能比一个一个涂色更优的办法就是选择一大块区间满足首位颜色相同，把它们涂成一个颜色后再涂中间。也就是满足 \(c_m = c_r\) 的位置，有 \(dp_{l,r} = \min(dp_{l,m} + dp_{m+1,r-1} + r-m)\)。

需要注意一些实现细节，首先区间 dp 最外层是枚举区间长度的，顺序不能乱，其次如果枚举 \(m\in[l,r)\) 是可能出现 \(m+1 < r - 1\) 的，但是这里 \(m\) 又必须取到 \(r-1\)，否则对于 \(c_{r-1} = c_r\) 的情况无法更新到，由于初始状态及随后状态都是直接更新的，我们可以默认创建 dp 数组时里面都是 0 ，不能设为 inf。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n;
    cin >> n;
    vector<int> c(2 * n + 1), x(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        c[i + n] = c[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
    }
    vector dp(2 * n + 1, vector<i64>(2 * n + 1, 1e18));
    for (int i = 1; i <= 2 * n; i++) {
        dp[i][i] = x[c[i]] + 1;
    }
    for (int len = 2; len <= 2 * n; len++) {
        for (int l = 1, r = len; r <= 2 * n; l++, r++) {
            dp[l][r] = dp[l][r - 1] + dp[r][r];
            for (int m = l; m < r; m++) {
                if (c[m] == c[r] && m + 1 <= r - 1) {
                    dp[l][r] =
                        min(dp[l][r], dp[l][m] + r - m + dp[m + 1][r - 1]);
                }
            }
        }
    }
    i64 ans = 1e18;
    for (int l = 1; l <= n + 1; l++) {
        ans = min(ans, dp[l][l + n - 1]);
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}