2024每日一题(1.1至1.26)

发表于 2024-01-10 更新于 2024-07-19 分类于题解阅读次数：本文字数： 4.6k 阅读时长 ≈ 17 分钟

Life's a little bit messy. We all make mistakes. No matter what type of animal you are, change starts with you. — Zootopia

1月1日 FEB

思路：

考虑在首尾的时候等差为其他为
求出上界和下界
一个的贡献为或者
- 扫描字符串，遇到上界，遇到或，上界和下界都
- 如果全是，那么答案一定是
扫描字符串
- 找到连续的串，上下界的变化情况如下：
  - 如果串的两边字符不相同并且串的长度为奇数下界
  - 如果串的两边字符相同并且串的长度为正偶数下界
  - 如果串的两边字符相同并且串的长度为正数上界

时间复杂度：

转载：这篇题解写的很不错

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    s = ' ' + s;

    bool f = true;
    int l = 0, r = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == s[i - 1] && s[i] != 'F') {
            l++, r++;
        }
        if (s[i] != 'F') f = false;
        else r++;
    }

    if (f) r--;
    int cnt = 2;
    if (s[1] == 'F' || s[n] == 'F') cnt = 1;

    for (int i = 1; i <= n; ) {
        while (s[i] == 'F' && i <= n) {
            i++;
        }
        int j = i + 1;
        while (s[j] == 'F' && j <= n) {
            j++;
        }
        int len = j - i - 1;

        if (s[i] == s[j]) {
            if (len % 2 == 0 && len) {
                l++;
            }
            if (len) r++;
        } else {
            if (j <= n && len & 1) {
                l++;
            }
        }
        i = j;
    }

    std::vector<int> ans;
    for (int i = l; i <= r; i += cnt) {
        ans.emplace_back(i);
    }

    std::cout << ans.size() << "\n";
    for (int i : ans) {
        std::cout << i << "\n";
    }

    return 0;
}

1月2日填充

思路：

题目要求如何填充，使得字符串中不重叠的和串数量最多
可以发现，如果相邻的两位本来就是，或者那么答案直接加

注意：为了使得答案不重不漏，每次找到一个合法串时，要将序列下标加

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string s;
    std::cin >> s;

    int ans = 0;
    for (int i = 0; i + 1 < s.size(); i++) {
        if (s[i] == s[i + 1] || s[i] == '?' || s[i + 1] == '?') {
            ans++;
            i++;
        }
    }
    std::cout << ans << "\n";

    return 0;
}

1月3日管道

思路：

同2023年第十四届蓝桥杯大赛软件类省赛Python大学B组真题的D题

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, len;
    std::cin >> n >> len;

    std::vector<std::array<int, 2>> a(n);
    for (int i = 0, x, l; i < n; i++) {
        std::cin >> a[i][0] >> a[i][1];
    }

    int l = 0, r = 2E9;
    while (l < r) {
        int mid = l + r >> 1;
        auto check = [&](int x) {
            std::vector<std::array<int, 2>> seg;
            for (int i = 0; i < n; i++) {
                if (x >= a[i][1]) {
                    seg.push_back({a[i][0] - (x - a[i][1]), a[i][0] + (x - a[i][1])});
                }
            }
            std::sort(seg.begin(), seg.end());
            if (seg[0][0] > 1 || !seg.size()) {
                return false;
            }
            int right = seg[0][1];
            for (int i = 1; i < seg.size(); i++) {
                if (right + 1 < seg[i][0]) {
                    return false;
                }
                right = std::max(right, seg[i][1]);
            }
            return right >= len;
        };
        if (!check(mid)) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    std::cout << l << "\n";
    
    return 0;
}

1月4日小苹果

思路：

找规律，可以发现每次拿走的数量一定是
然后发现每次拿走后，的位置变化一定是从
最后判断一下第一次的位置即可

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    bool f = false;
    int sum = 0, ans = -1;
    for (int i = 0; n > 0; i++, sum++) {
        if ((n - 1) % 3 == 0 && !f) {
            ans = sum + 1;
            f = true;
        }
        int x = (n + 2) / 3;
        n -= x;
    }
    std::cout << sum << " " << ans << "\n";

    return 0;
}

1月5日公路

思路：

会发现从到 ,我们需要找到尽可能小的花费去走尽可能多的路程，这样会使得总花费最小
只需要开一个前缀和数组来维护从一个小的位置到一个更小的位置的区间即可

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, d;
    std::cin >> n >> d;

    std::vector<i64> v(n + 1);
    for (int i = 1; i < n; i++) {
        std::cin >> v[i];
    }

    for (int i = 1; i <= n; i++) {
        v[i] += v[i - 1];
    }

    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    i64 ans = 0, lst = 0;
    for (int i = 1; i <= n; i++) {
        int j = i;
        while (a[j] >= a[i] && j <= n) {
            j++;
        }
        i64 cur = v[j - 1] - v[i - 1];
        i64 t = (cur - lst + d - 1) / d;
        ans += t * a[i];
        lst += t * d - cur;
        i = j - 1;
    }
    std::cout << ans << "\n";

    return 0;
}

1月8日蜗牛

思路：

可以将dp状态分为两种
1. : 不使用传送门
2. : 使用传送门
状态转移的过程：
- 不用传送门, 那么状态可以通过不用传送门和使用了传送门两种状态转移过来
- 用传送门, 那么状态也需要通过不用传送门和使用了传送门两种状态转移过来
  - 需要爬到传送的出发点开始传送
  注：如果上一次传送的降落点大于这一次传送的出发点，那么就是往下走那么， , 否则，

时间复杂度：

这有一篇题解讲的非常详细，可以参考一下

constexpr int inf = 0x3f3f3f3f;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(2);
    
    int n;
    std::cin >> n;

    std::vector<int> x(n);
    for (int i = 0; i < n; i++) {
        std::cin >> x[i];
    }

    std::vector<int> a(n), b(n);
    for (int i = 0; i + 1 < n; i++) {
        std::cin >> a[i] >> b[i];
    }

    std::vector dp(n + 1, std::vector<double> (2, inf));
    dp[0][0] = x[0]; dp[0][1] = a[0] * 1.0 / 0.7 + x[0];
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + x[i] - x[i - 1];
        dp[i][0] = std::min(dp[i][0], dp[i - 1][1] + b[i - 1] / 1.3);
        dp[i][1] = dp[i][0] + a[i] / 0.7;
        dp[i][1] = std::min(dp[i][1], dp[i - 1][1] + abs(b[i - 1] - a[i]) / (b[i - 1] >= a[i] ? 1.3 : 0.7));
    }
    std::cout << dp[n - 1][0] << '\n';

    return 0;
}

1月9日互质数的个数

思路：

中与互质的数的个数被称为欧拉函数，记为

若在算数基本定理中，，则:

那么分母，这个数即为

可以将，然后可以发现在中也出现过，所以这个数一定可以被整除

时间复杂度：

constexpr i64 P = 998244353;
template <class T>
constexpr T qpow(T a, T b, T p) {
    T res = 1;
    for (; b; b /= 2) {
        if (b % 2) {
            res = res * a % p;
        }
        a = a * a % p;
    }
    return res;
}

template <class T>
constexpr T inv(T a, T b) {
    return qpow(a, P, P - 2);
} 

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    i64 a, b;
    std::cin >> a >> b;

    if (a == 1) {
        std::cout << 0 << "\n";
        return 0;
    }

    i64 t = qpow(a, b - 1, P);

    i64 res = a, x = a;
    for (int i = 2; i * i <= x; i++) { // 分解质因数
        if (x % i == 0) {
            while (x % i == 0) {
                x /= i;
            }
            res = res / i * (i - 1);
        }
    }
    if (x > 1) res = res / x * (x - 1);

    std::cout << res * t % P << "\n";

    return 0;
}

1月10日平均

思路：

贪心，先将整个序列按价值从小到大排序，然后用表存储一下
每次将大于平均数的那部分从最小值开始加入答案中即可

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i] >> b[i];
    }

    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);

    std::sort(p.begin(), p.end(), 
        [&](int i, int j) {
            return b[i] < b[j];
        });
        
    std::vector<int> g[10];
    for (int i = 0; i < n; i++) {
        g[a[p[i]]].push_back(b[p[i]]);
    }

    i64 ans = 0;
    int avg = n / 10;
    for (int i = 0; i < 10; i++) {
        int m = g[i].size();
        if (m <= avg) continue ;
        for (int j = 0; j < m - avg; j++) {
            ans += g[i][j];
        }
    }
    std::cout << ans << "\n";

    return 0;
}

1月11日三国游戏

思路：

贪心，考虑三种情况
- 当最大，枚举的情况，将收益从大到小排序，如果中途出现小于等于则为目前最大数量
- 当最大，枚举的情况，将受益从大到小排序，如果中途出现小于等于则为目前最大数量
- 当最大，枚举的情况，将受益从大到小排序，如果中途出现小于等于则为目前最大数量

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> A(n), B(n), C(n);
    for (int i = 0; i < n; i++) {
        std::cin >> A[i];
    }
    for (int i = 0; i < n; i++) {
        std::cin >> B[i];
    }
    for (int i = 0; i < n; i++) {
        std::cin >> C[i];
    }

    auto get = [&](auto A, auto B, auto C) -> int {
        std::vector<i64> c(n + 1);
        for (int i = 0; i < n; i++) {
            c[i] = A[i] - B[i] - C[i];
        }
        std::sort(c.begin(), c.end(), std::greater());
        for (int i = 0; i < n; i++) {
            c[i + 1] += c[i];
            if (c[i + 1] <= 0) return i;
        }
        return n;
    };

    int res = std::max({get(A, B, C), get(B, A, C), get(C, A, B)});

    std::cout << (res == 0 ? -1 : res) << "\n";

    return 0;
}

1月12日松散子序列

思路：

同2023年第十四届蓝桥杯大赛软件类省赛Python大学B组真题的C题

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string s;
    std::cin >> s;

    int n = s.size();

    std::vector dp(n, std::vector<int>(2));
    dp[0][1] = s[0] - 'a' + 1;
    for (int i = 1; i < n; i++) {
        dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = dp[i - 1][0] + s[i] - 'a' + 1;
    }
    std::cout << std::max(dp[n - 1][0], dp[n - 1][1]) << "\n";

    return 0;
}

1月15日保险箱

思路：

考虑三种情况的状态
- 不进位，可以表示为
- 加法进位，可以表示为
- 减法退位，可以表示为
考虑状态的转移
- 不进位时
- 加法进位时
- 减法进位时

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::string x, y;
    std::cin >> x >> y;

    x = ' ' + x;
    y = ' ' + y;

    auto get = [&](char x) {
        return x - '0';
    };

    std::vector dp(n + 1, std::vector<int>(3)); // 0 1 2 分别表示不进位，加法进位，减法进位
    dp[n][0] = abs(get(x[n]) - get(y[n])); // 如果A比B大就加，否则就减
    dp[n][1] = get(y[n]) - get(x[n]) + 10; // A比B小，加
    dp[n][2] = get(x[n]) - get(y[n]) + 10; // A比B大，减

    for (int i = n - 1; i > 0; i--) {
        int a = get(x[i]), b = get(y[i]);
        dp[i][0] = dp[i + 1][0] + abs(a - b); // 如果后面不进不退，同上
        dp[i][0] = std::min(dp[i + 1][1] + abs(a - b + 1), dp[i][0]); // 如果后面进位了，那里就要A[i]就会变成A[i]+1
        dp[i][0] = std::min(dp[i + 1][2] + abs(a - b - 1), dp[i][0]); // 如果后面退位了，那里就要A[i]就会变成A[i]-1

        dp[i][1] = dp[i + 1][0] + b - a + 10; 
        dp[i][1] = std::min(dp[i + 1][1] + b - a + 9, dp[i][1]); 
        dp[i][1] = std::min(dp[i + 1][2] + b - a + 11, dp[i][1]);

        dp[i][2] = dp[i + 1][0] + a - b + 10; 
        dp[i][2] = std::min(dp[i + 1][1] + a - b + 11, dp[i][2]); 
        dp[i][2] = std::min(dp[i + 1][2] + a - b + 9, dp[i][2]);
    }
    std::cout << std::min({dp[1][0], dp[1][1], dp[1][2]}) << "\n";

    return 0;
}

1月16日棋盘

思路：

差分，奇数为，偶数为

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    std::vector g(n + 2, std::vector<int>(n + 2));
    auto add = [&](int x1, int y1, int x2, int y2, int w) {
        g[x1][y1] += w;
        g[x2 + 1][y1] -= w;
        g[x1][y2 + 1] -= w;
        g[x2 + 1][y2 + 1] += w;
    };

    for (int i = 0; i < m; i++) {
        int x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;

        add(x1, y1, x2, y2, 1);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            std::cout << (g[i][j] & 1);
        }
        std::cout << "\n";
    }

    return 0;
}

1月17日翻转

思路：

发现当一个位置变化两次等于没有变化，而且当前位置的状态取决于前面一个位置的状态
那么可以发现，如果头和尾不一样，就不可能相同，因为每次改变只能是中间的那个字符
当不一样时，直接改变即可，如果出现了一个不同的位置，但它的两边却是相同的，就说明不可能完全一样

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int D;
    std::cin >> D;

    while (D--) {
        std::string s, t;
        std::cin >> s >> t;

        if (s[0] != t[0] || s.back() != t.back()) {
            std::cout << "-1\n";
            continue ;
        }

        int res = 0, f = false;
        for (int i = 1; i + 1 < s.size(); i++) {
            if (s[i] != t[i]) {
                if (t[i] != t[i - 1] && t[i] != t[i + 1]) {
                    res++;
                    t[i] ^= 1;
                } else {
                    f = true;
                }
            }
        }

        if (f) {
            std::cout << "-1\n";
        } else {
            std::cout << res << "\n";
        }
    }

    return 0;
}

1月18日仓库规划

思路：

直接枚举比较即可

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    std::vector<int> a[n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x;
            std::cin >> x;
            a[i].push_back(x);
        }
    }    

    auto check = [&](auto a, auto b) {
        for (int i = 0; i < m; i++) {
            if (b[i] <= a[i]) {
                return false;
            }
        }
        return true;
    };

    for (int i = 0; i < n; i++) {
        std::set<int> st;
        for (int j = 0; j < n; j++) {
            if (check(a[i], a[j])) {
                st.insert(j + 1);
            }
        }
        std::cout << *st.begin() << "\n";
    }

    return 0;
}

1月19日消除游戏

思路：

使用双链表，每次删除一个节点，时间复杂度为，双链表删除节点的原理就是将右指针移到后面的后面一个元素

当出现某一次没有点满足条件，即为最终串

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string s;
    std::cin >> s;

    int n = s.size();

    s = '@' + s + '@';

    std::vector<int> vis(n + 2), l(n + 2), r(n + 2);
    for (int i = 1; i <= n; i++) {
        l[i] = i - 1;
        r[i] = i + 1;
    }

    std::vector<int> p;
    auto check = [&](int x) {
        if (s[l[x]] == '@' || s[r[x]] == '@') return ;
        if (s[l[x]] == s[x] && s[r[x]] != s[x]) {
            p.push_back(r[x]);
            p.push_back(x);
        }
        if (s[l[x]] != s[x] && s[r[x]] == s[x]) {
            p.push_back(l[x]);
            p.push_back(x);
        }
    };

    for (int i = 1; i <= n; i++) {
        check(i);
    }

    while (p.size()) {
        std::vector<int> t;
        auto remove = [&](int x) {
            l[r[x]] = l[x];
            r[l[x]] = r[x];
            vis[x] = true;
        };
        for (auto x : p) {
            if (vis[x]) continue ;
            remove(x);
            t.push_back(l[x]);
            t.push_back(r[x]);
        }
        p.clear();
        for (auto f : t) {
            if (!vis[f]) {
                check(f);
            }
        }
    }

    bool f = false;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            std::cout << s[i];
            f = true;
        }
    }

    if (!f) std::cout << "EMPTY\n";

    return 0;
}

1月22日因数平方和

思路：

数论分块可以在的时间复杂度内求解问题
对于常数，使得式子 = 成立的最大满足的值为，即值所在分块的右端点为
为当前这一个分块中数的平方和，为块中相同值的数量

附：

时间复杂度：

转载：这篇题解写的不错，还有一个整除分块的讲解

constexpr int P = 1E9 + 7;
template <typename T>
T qpow(T a, T b) {
    T res = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = (i64)res * a % P;
        }
        a = (i64)a * a % P;
    }
    return res % P;
}

template <typename T>
T inv(T a) {
    return qpow(a, P - 2);
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    auto get = [&](int x) {
        return (i64)x * (x + 1) % P * (2 * x + 1) % P * inv(6) % P;
    };

    int l = 1, r, res = 0;
    for (int i = 1; i <= n; i = r + 1) {
        int cnt = n / i;
        r = n / cnt;

        res = ((res + 1LL * cnt * (get(r) - get(i - 1))) % P + P) % P;
    }
    std::cout << res << "\n";

    return 0;
}

1月23日质因数个数

思路：

质因数分解模板题

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    i64 n;
    std::cin >> n;

    int res = 0;
    for (i64 i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            res++;
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) res++;

    std::cout << res << "\n";

    return 0;
}

1月24日爬树的甲壳虫

思路：

用的思想，每次有的概率失败，那么有的概率成功，期望的尝试次数为
从高度为到需要花费的时间为
那么转移方程为

时间复杂度：

constexpr int P = 998244353;
template <typename T> 
T power(T a, T b) {
    T res = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = res * a % P;
        }
        a = a * a % P;
    }
    return res % P;
}

template <typename T>
T inv(T a) {
    return power(a, 1LL * P - 2);
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> x(n + 1), y(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> x[i] >> y[i];
    }

    i64 ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = (ans + 1) * y[i] % P * inv(1LL * y[i] - x[i]);
        ans = ans % P;
    }
    std::cout << ans << "\n";

    return 0;
}

1月25日子串分值

思路：

乘法原理，每个字符的贡献为前一个相同字符的位置与当前位置的差与当前位置和后一个位置的差相乘，即
需要设置两个哨兵分别在字符位置的最前面和最后面

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string s;
    std::cin >> s;

    int n = s.size();

    std::array<std::vector<int>, 26> a {};
    for (int i = 0; i < n; i++) {
        if (!a[s[i] - 'a'].size()) a[s[i] - 'a'].push_back(0);
        a[s[i] - 'a'].push_back(i + 1);
    }

    i64 res = 0;
    for (int i = 0; i < 26; i++) {
        if (a[i].size()) {
            a[i].push_back(n + 1);
            int m = a[i].size();
            for (int j = 1; j + 1 < m; j++) {
                int l = a[i][j] - a[i][j - 1], r = a[i][j + 1] - a[i][j];
                res += 1LL * l * r;
            }
        }
    }
    std::cout << res << "\n";

    return 0;
}

1月26日超级胶水

思路：

可以发现顺着乘就行，与顺序无关

证明：两堆石子合并的时候，消耗就是两个石子堆的重量相乘，这样可以看成一个石子堆中所有的小石子乘另一个石子堆中所有的小石子，之后两个石子堆合成一个石子堆。我们往下继续思考，可以发现，两个小石子(不管在什么位置)合并操作就是一次乘法操作，每个小石子之间都会合并一次，所以最终的结果就是每个不同石子重量乘的和。

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    i64 lst = 0, res = 0;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        if (!i) {
            lst = x;
        } else {
            res += lst * x;
            lst += x;
        }
    }
    std::cout << res << "\n";

    return 0;
}

1月1日 FEB

1月2日 填充

1月3日 管道

1月4日 小苹果

1月5日 公路

1月8日 蜗牛

1月9日 互质数的个数

1月10日 平均

1月11日 三国游戏

1月12日 松散子序列

1月15日 保险箱

1月16日 棋盘

1月17日 翻转

1月18日 仓库规划

1月19日 消除游戏

1月22日 因数平方和

1月23日 质因数个数

1月24日 爬树的甲壳虫

1月25日 子串分值

1月26日 超级胶水

1月2日填充

1月3日管道

1月4日小苹果

1月5日公路

1月8日蜗牛

1月9日互质数的个数

1月10日平均

1月11日三国游戏

1月12日松散子序列

1月15日保险箱

1月16日棋盘

1月17日翻转

1月18日仓库规划

1月19日消除游戏

1月22日因数平方和

1月23日质因数个数

1月24日爬树的甲壳虫

1月25日子串分值

1月26日超级胶水