月赛题解
【202607】月赛算法组题解
Kayla 竞赛教练 LV 4 SU @ 2026-8-7 17:37:35

A

先对原式进行约分化简： $a \div b(gcd(a,b)=1)$ 。

在十进制下如果分母 $b$ 仅包含 $2,5$ 这两个质因数则可以除尽。

拓展到 $k$ 进制，如果 $b$ 的质因数都是 $b$ 的因数，则可以除尽，否则为无限小数。

#include <iostream>
using namespace std;

typedef long long ll;

// 辗转相除法求最大公约数
ll gcd(ll x, ll y) {
    while (y) {
        ll tmp = x % y;
        x = y;
        y = tmp;
    }
    return x;
}

int main() {
    ll a, b, k;
    cin >> a >> b >> k;
    
    // 1. 约分，得到最简分母 m
    ll g = gcd(a, b);
    ll m = b / g;
    
    // 2. 不断用k的因子约掉m
    while (true) {
        ll d = gcd(m, k);
        if (d == 1) break;
        m /= d;
    }
    
    // m>1 代表无限小数输出Yes，否则No
    if (m > 1) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

B

因为有负数的存在，所以最后的结果不一定是连续的长为 $m+1$ 的一段，又要求必须合并 $m$ 次，所以最后数组长度会变为 $k=n-m$ ，其中每一部分都是若干次合并的结果，求这其中的最大值。

k=1:必须全部合并
k=2: 最后合并为 2 段，结果是前缀或者后缀
k>=3: 所有长度≤m+1 的连续子段最大和，使用单调队列维护

#include <iostream>
#include <vector>
#include <deque>
#include <climits>
#include <algorithm>
using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<ll> a(n + 1);
    vector<ll> pre(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }

    int K = n - m;
    ll ans = LLONG_MIN;

    if (K == 1)
    {
        ans = pre[n];
    }
    else if (K == 2)
    {
        // 枚举所有分割点，取左右两段的最大值
        for (int i = 1; i < n; i++)
        {
            ans = max(ans, pre[i]);
            ans = max(ans, pre[n] - pre[i]);
        }
    }
    else
    {
        // K >= 3，求长度不超过 m+1 的最大子数组和
        int max_len = m + 1;
        deque<int> q;
        q.push_back(0);
        for (int i = 1; i <= n; i++)
        {
            // 弹出窗口外的前缀下标：j < i - max_len
            while (!q.empty() && q.front() < i - max_len)
            {
                q.pop_front();
            }
            // 队首是窗口内最小前缀，计算当前最大子段和
            if (!q.empty())
            {
                ans = max(ans, pre[i] - pre[q.front()]);
            }
            // 维护单调递增队列
            while (!q.empty() && pre[i] <= pre[q.back()])
            {
                q.pop_back();
            }
            q.push_back(i);
        }
    }

    cout << ans << '\n';
    return 0;
}

C

计算出所有的联通块后，需要统计“本质相同”的联通块：可以将其旋转八方向后，都平移到左上角，将其最小字典序的结果作为id。

还有一种方法，将联通块内任意两个点之间的距离和作为id。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
using namespace std;

const int MAX = 105;
char grid[MAX][MAX];
bool vis[MAX][MAX];
int n, m;

// 八连通方向
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

// 8种坐标变换：旋转0/90/180/270度 + 水平翻转后的4种旋转
int trans[8][4] = {
    {1, 0, 0, 1},  {0, 1, -1, 0}, {-1, 0, 0, -1}, {0, -1, 1, 0},
    {1, 0, 0, -1}, {0, -1, -1, 0}, {-1, 0, 0, 1}, {0, 1, 1, 0}
};

// 点集平移到左上角 + 排序，做归一化
vector<pair<int, int>> normalize(vector<pair<int, int>> pts)
{
    int min_r = pts[0].first;
    int min_c = pts[0].second;
    for (auto &p : pts)
    {
        min_r = min(min_r, p.first);
        min_c = min(min_c, p.second);
    }
    for (auto &p : pts)
    {
        p.first -= min_r;
        p.second -= min_c;
    }
    sort(pts.begin(), pts.end());
    return pts;
}

// 生成8种朝向，取字典序最小的作为标准形状
vector<pair<int, int>> get_canonical(vector<pair<int, int>> pts)
{
    auto res = normalize(pts);
    for (int i = 1; i < 8; i++)
    {
        vector<pair<int, int>> t;
        for (auto &p : pts)
        {
            int nr = trans[i][0] * p.first + trans[i][1] * p.second;
            int nc = trans[i][2] * p.first + trans[i][3] * p.second;
            t.emplace_back(nr, nc);
        }
        auto cur = normalize(t);
        if (cur < res)
            res = cur;
    }
    return res;
}

// DFS收集整个徽章的所有点
void dfs(int x, int y, vector<pair<int, int>> &pts)
{
    vis[x][y] = true;
    pts.emplace_back(x, y);
    for (int d = 0; d < 8; d++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m)
            if (grid[nx][ny] == '1' && !vis[nx][ny])
                dfs(nx, ny, pts);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++)
            grid[i][j] = s[j - 1];
    }

    set<vector<pair<int, int>>> types;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (grid[i][j] == '1' && !vis[i][j])
            {
                vector<pair<int, int>> pts;
                dfs(i, j, pts);
                types.insert(get_canonical(pts));
            }
        }
    }

    cout << types.size() << endl;
    return 0;
}

D

题意简述

给定一个长度为 N 的排列 P。一次操作可以选择相邻两个位置 i 和 i+1，然后把这两个位置都变成它们的较小值：

P[i] = P[i+1] = min(P[i], P[i+1])

问经过任意次操作后，最终可能得到多少种不同的数组。

注意：题目数的是最终数组的种类，不是操作序列的种类。

关键观察

一次操作的本质是：

较小的值可以向相邻位置扩散，覆盖更大的值。

例如某个值 P[j] 想扩散到位置 i，那么从 j 到 i 的路径上不能出现比 P[j] 更小的值。

因为一旦遇到更小的值，操作中的 min 会让更小值覆盖它，它就无法继续扩散过去。

所以：

原位置 j 的值能影响位置 i
当且仅当 i 和 j 之间没有比 P[j] 更小的值。

每个值的可扩散范围

对每个位置 j，找到：

L[j]：j 左边最近的、值比 P[j] 小的位置
R[j]：j 右边最近的、值比 P[j] 小的位置

那么 P[j] 能扩散到的区间就是：

[L[j] + 1, R[j] - 1]

因为再往左或往右，就会被更小的值挡住。

反过来，对每个最终位置 i，可以维护一个集合：

reach[i] = 所有能够扩散到位置 i 的原始下标 j

最终数组第 i 位的值，只可能来自 reach[i] 中的某个原位置。

最终数组的顺序性质

最终数组中，每个保留下来的原始值都会形成一个连续区间。

如果两个原始位置满足：

a < b

并且它们的值都在最终数组中出现，那么来自 a 的区间一定在来自 b 的区间左边。

也就是说，最终数组从左到右看，每个位置的“来源下标”不会下降。

因此，若第 i 位来自原下标 j，第 i-1 位来自原下标 y，必须满足：

y <= j

这是 DP 转移的核心限制。

DP 设计

定义：

dp[i][j] = 前 i 个位置已经确定，并且第 i 个位置来自原下标 j 的方案数

其中 j 必须属于 reach[i]。

如果 j 不在 reach[i] 中，说明原位置 j 的值根本扩散不到位置 i，这种状态无效。

DP 转移

假设第 i 位来自原下标 j。

那么第 i-1 位可以来自任意原下标 y，只要满足：

y 属于 reach[i-1]
y <= j

所以有：

dp[i][j] = sum(dp[i-1][y])
           其中 y 属于 reach[i-1] 且 y <= j

最终答案为：

sum(dp[N][j])
其中 j 属于 reach[N]

滚动数组优化

因为 dp[i] 只依赖 dp[i-1]，所以不需要保存完整二维数组。

实际实现时只保留两层：

dp   ：上一位置的状态
ndp  ：当前位置的状态

每处理完一个位置，就令：

dp = ndp

这就是滚动数组。

转移加速

对于当前位置的某个来源下标 j，需要累加上一层中所有 y <= j 的方案数。

如果 reach[i-1] 和 reach[i] 都按下标有序，就可以用前缀和或双指针维护这个累加值。

这样每一层不需要反复从头枚举上一层所有状态。

为什么复杂度能过

一般情况下，一个位置可能被很多原始值影响，状态数可能较大。

但题目中的排列是随机排列。随机排列有一个重要性质：

从某个位置向左或向右看，能成为“新的更小值”的元素数量期望是 O(log N)

因此，每个位置的 reach[i] 的期望大小是 O(log N)。

所以总状态数期望为：

$O(N log N)$

使用双指针或前缀和转移后，整体期望复杂度也可以做到： $O(N log N)$

总结

较小值可以扩散，但不能跨过更小值。
每个原位置 j 能影响一个连续区间。
最终数组从左到右的来源下标不会下降。
用 dp[i][j] 表示第 i 位来自原下标 j。
转移时只累加上一位来源下标 <= j 的方案。
用滚动数组保存上一层和当前层。

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
const int mod=998244353;

int main(){
    IOS

    int n;
    cin>>n;
    vector<int> p(n+2);
    for(int i=1;i<=n;++i){
        cin>>p[i];
    }
    vector<int> l(n+1);
    for(int i=1;i<=n;++i){
        int j=i-1;
        while(p[i]<p[j]){
            j=l[j];
        }
        l[i]=j;
    }
    vector<int> r(n+1);
    for(int i=n;i>=1;--i){
        int j=i+1;
        while(p[i]<p[j]){
            j=r[j];
        }
        r[i]=j;
    }
    vector<vector<int>> a(n+1);
    a[0].push_back(0);
    for(int i=1;i<=n;++i){
        for(int j=l[i]+1;j<r[i];++j){
            a[j].push_back(i);
        }
    }
    vector<int> dp;
    dp.push_back(1);
    for(int i=1;i<=n;++i){
        a[i-1].push_back(n+1);
        int p=0;
        int cur=0;
        vector<int> ndp;
        for(auto &x:a[i]){
            while(a[i-1][p]<=x){
                cur=(cur+dp[p])%mod;
                ++p;
            }
            ndp.push_back(cur);
        }
        dp=ndp;
    }
    int ans=0;
    for(auto &x:dp){
        ans=(ans+x)%mod;
    }
    cout<<ans<<'\n';
    
    return 0;
}

目前还没有评论...

【202607】月赛算法组题解

A

B

C

D