Discussion Detail

2025 练习赛 1
【题解】2025 练习赛 1
Csvoner SU @ 2025-10-21 16:27:19

题目编号	对应比赛
A	语法比赛
B
C		CSP-J
D
E			CSP-S
F
G

语法 A. D+DD

难度：没有难度，简单数学计算。

算法：数学，模拟。

核心是判断 12 * d == n，并满足 n 所在区间。

C++ 代码：

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

int main()
{
    int n;
    cin >> n;
    
    int d = n / 12;
    
    if (1 <= d && d <= 9 && d * 12 == n)
        cout << d;
    else
        cout << "404";
    
    return 0;
}

语法 B. 传递计算器

难度：循环，条件判断。

算法：数学，模拟。

改编自角谷猜想，按题意模拟即可。

C++ 代码：

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

int n, x;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> x;
    
    int now = x;
    int ans = 1;
    while (now % 10 != 3)
    {
        if (x % 2 == 0)
            x = x / 2;
        else
            x = x * 3 + 1;
        now += x;
        ans ++ ;
    }
    
    cout << ans << "\n";
    
    return 0;
}

CSP-J C. 发现蒂位

难度：循环、数组。

算法：数学，模拟。

这段代码解决的是在一个 $n×m$ 的网格中，找出一个位置，使得该位置到 $k$ 个给定特殊点的曼哈顿距离不超过 $2$ 的特殊点数量最多。具体步骤如下：

输入处理：读取网格尺寸 $n$ 、 $m$ 和特殊点数量 $k$ ，以及每个特殊点的坐标。
遍历网格：对于网格中的每个位置 (i,j)，检查它是否是最佳位置。
特殊点检查：对于每个位置 (i,j)，遍历所有特殊点：
- 如果 (i,j) 本身是特殊点，直接跳过（贡献为 $0$ ）。
- 否则，计算特殊点到 (i,j) 的曼哈顿距离，若距离 ≤2，则计数增加。
更新答案：在所有位置中，记录满足条件的特殊点数量的最大值。

C++ 代码：

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

int n, m, k;
int x[105], y[105];

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i ++ )
        cin >> x[i] >> y[i];
    
    int ans = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            int now = 0;
            for (int o = 1; o <= k; o++)
            {
                if (x[o] == i && y[o] == j)
                {
                    now = 0;
                    break;
                }
                if (abs(x[o] - i) + abs(y[o] - j) <= 2)
                    now ++ ;
            }
            ans = max(ans, now);
        }
    
    cout << ans << '\n';
    
	return 0;
}

CSP-J D. 找最大值

难度：最简单的方法也是最笨的方法。

算法：数据结构，STL 或数组模拟。

当然可以用链表、STL-vector、STL-list 来实现，这里给出最笨的做法-数组模拟实现：查询区间最大值、在指定位置插入元素、修改单个元素值以及删除指定区间元素。

C++ 代码：

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

int n, m;
int a[205];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        cin >> a[i];
    
    while (m -- )
    {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1)
        {
            int ans = a[x];
            for (int i = x + 1; i <= y; i ++ )
                ans = max(ans, a[i]);
            cout << ans << "\n";
        }
        if (op == 2)
        {
            // a[x+1]~a[n] 往后挪一位
            for (int i = n; i >= x + 1; i -- )
                a[i + 1] = a[i];
            // y 放在 a[x+1]
            a[x + 1] = y;
            // 位数 +1 
            n ++ ;
        }
        if (op == 3)
        {
            a[x] = y;
        }
        if (op == 4)
        {
            // 删了 len 个数
            int len = y - x + 1;
            // a[y+1]~a[n] 往前挪到 a[x] 开头的位置
            // 也就是往前挪 len 位
            for (int i = y + 1; i <= n; i ++ )
                a[i - len] = a[i];
            n -= len;
        }
    }
    
    return 0;
}

CSP-S E. 奇变偶不变

难度：入门算法。

算法：差分数组，模拟。

题目要求处理一个数组，对指定区间内的奇数元素进行+1操作（偶数保持不变），经过多次操作后计算最终数组的和。

关键观察
- 操作特性：每次操作只影响区间内的奇数元素，将其变为偶数
- 操作可交换性：操作的顺序不影响最终结果
- 操作幂等性：同一个元素被多次操作时，只有第一次操作（如果它是奇数）会产生影响
高效解法
- 使用差分数组技术来标记被操作覆盖的区间：
- 差分标记：对于每个区间[l, r]，在l处标记+1，在r+1处标记-1
- 前缀和计算：通过计算差分数组的前缀和，得到每个位置被操作覆盖的次数
- 条件修正：对于被至少一次操作覆盖且初始值为奇数的元素，将其值+1

C++ 代码：

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

typedef long long LL;

LL n, m;
LL a[100000 + 5];
LL f[100000 + 5]; // 记录括号数量，左括号正数、右括号负数

int main()
{
    cin >> n >> m;
    for (LL i = 1; i <= n; i ++ )
        cin >> a[i];
    
    for (LL i = 1; i <= m; i ++ )
    {
        LL l, r;
        cin >> l >> r;
        f[l] ++ ;
        f[r + 1] -- ;
    }
    LL now = 0; // 当前括号数量
    LL ans = 0;
    LL cnt  = 0;
    for (LL i = 1; i <= n; i ++ )
    {
        now += f[i];
        if(now > 0) cnt ++ ;
        if (now > 0 && a[i] % 2 == 1) a[i] ++ ;
        ans += a[i];
    }
    
    cout << ans;
    
	return 0;
}

CSP-S F. 好数

难度：不好做的 dp。

算法：数位 dp，组合数学。

我们需要计算给定好数在所有好数中的排名。好数的定义是其数字序列从左到右非递减或非递增（包括所有一位数）。

关键洞察

好数分类：好数可以分为三类：
- 非递减数（如 123, 112, 999）
- 非递增数（如 321, 211, 999）
- 数字相同的数（如 111, 222, 999） - 这类数同时满足非递减和非递增条件
容斥原理：
- 总好数 = 非递减数 + 非递增数 - 数字相同的数
- 这样可以避免重复计数同时满足两种条件的数

我们将问题分解为两部分：

计算位数小于给定数字的好数：
- 使用组合数学公式直接计算
- 非递减数：C(8+k, k)
- 非递增数：C(9+k, k) - 1
- 数字相同的数：9个（1-9组成的k位相同数字）
- 总数为：C(8+k, k) + C(9+k, k) - 10
计算位数等于给定数字的好数：
- 使用数位动态规划统计：
  - 非递减且≤给定数字的个数
  - 非递增且≤给定数字的个数
  - 数字相同且≤给定数字的个数
- 应用容斥原理得到最终结果

时间复杂度：O(T × L)，其中T是测试用例数量，L是数字的最大位数

空间复杂度：O(L)，主要用于数位DP的状态存储

C++ 代码：

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

const int MAX = 30;
LL C[MAX + 1][MAX + 1];

// 预计算组合数表
void init() {
    for (int i = 0; i <= MAX; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
}

// 计算非递减且≤n的数字个数
LL calcDec(string s) {
    int len = s.size();
    // dp[位置][是否紧贴边界][最后一位数字]
    vector<vector<vector<LL>>> dp(len + 1, vector<vector<LL>>(2, vector<LL>(10, 0)));
    dp[0][1][0] = 1; // 初始状态
    
    for (int i = 0; i < len; i++) {
        for (int tight = 0; tight < 2; tight++) {
            for (int last = 0; last < 10; last++) {
                if (dp[i][tight][last] == 0) continue;
                
                int low = last; // 当前位最小数字（必须≥上一位）
                if (i == 0) low = 1; // 第一位不能为0
                int high = tight ? (s[i] - '0') : 9; // 最大数字
                
                for (int d = low; d <= high; d++) {
                    int newTight = tight && (d == high);
                    dp[i + 1][newTight][d] += dp[i][tight][last];
                }
            }
        }
    }
    
    LL ans = 0;
    for (int tight = 0; tight < 2; tight++) {
        for (int last = 0; last < 10; last++) {
            ans += dp[len][tight][last];
        }
    }
    return ans;
}

// 计算非递增且≤n的数字个数
LL calcInc(string s) {
    int len = s.size();
    // dp[位置][是否紧贴边界][最后一位数字]
    vector<vector<vector<LL>>> dp(len + 1, vector<vector<LL>>(2, vector<LL>(10, 0)));
    dp[0][1][9] = 1; // 初始状态，最后一位设为9
    
    for (int i = 0; i < len; i++) {
        for (int tight = 0; tight < 2; tight++) {
            for (int last = 0; last < 10; last++) {
                if (dp[i][tight][last] == 0) continue;
                
                int low, high;
                if (i == 0) {
                    low = 1; // 第一位不能为0
                    high = tight ? (s[i] - '0') : 9;
                } else {
                    low = 0;
                    high = min(last, tight ? (s[i] - '0') : 9); // 必须≤上一位
                }
                
                for (int d = low; d <= high; d++) {
                    int newTight = tight && (d == high);
                    dp[i + 1][newTight][d] += dp[i][tight][last];
                }
            }
        }
    }
    
    LL ans = 0;
    for (int tight = 0; tight < 2; tight++) {
        for (int last = 0; last < 10; last++) {
            ans += dp[len][tight][last];
        }
    }
    return ans;
}

// 计算数字相同且≤n的数字个数
LL calcSame(string s) {
    int len = s.size();
    LL ans = 0;
    // 检查每个数字1-9组成的相同数字串
    for (int d = 1; d <= 9; d++) {
        string t(len, '0' + d);
        if (t <= s) {
            ans++;
        }
    }
    return ans;
}

int main() {
    init();
    int T;
    cin >> T;
    
    while (T--) {
        string n;
        cin >> n;
        int len = n.size();
        LL total = 0;
        
        // 计算位数小于n的好数个数
        for (int k = 1; k < len; k++) {
            // 非递减数：C(8+k, k)
            // 非递增数：C(9+k, k) - 1  
            // 重复计算的相同数字：9个
            total += C[8 + k][k] + C[9 + k][k] - 10;
        }
        
        // 计算位数等于n的好数个数
        LL A = calcDec(n);  // 非递减数
        LL B = calcInc(n);  // 非递增数
        LL C = calcSame(n); // 相同数字（被重复计算）
        
        // 总排名 = 位数小的好数 + 位数相同的好数
        LL ans = total + A + B - C;
        cout << ans << '\n';
    }
    
    return 0;
}

CSP-S G. 劫富济贫

难度：更不好做的 dp。

算法：背包 dp。

问题分析

这道题的关键在于理解操作的本质：
- 每次操作减少1个麻烦，但可能产生多个新麻烦
- 产生的麻烦会在朋友间传播，形成连锁反应
- 目标是最大化总操作次数
核心思路

（1）定义状态：f[i] 表示操作史莱姆 i 一次所能带来的总操作次数（包括直接操作和间接传播）

（2）状态转移：
- 基础值：操作本身算1次
- 额外值：可以从朋友中选择一个子集，使得这些朋友的体重和小于当前史莱姆的体重，然后加上这些朋友的 f 值之和
（3）计算顺序：按体重从小到大计算，确保在计算某个史莱姆时，其所有体重较小的朋友的 f 值都已计算完成

（4）最终答案：总操作次数 = Σ(每个史莱姆的初始麻烦数 × 操作该史莱姆一次带来的总操作次数)

时间复杂度：O(T × L)，其中T是测试用例数量，L是数字的最大位数

C++ 代码：

// 顺手偷一下 atcoder cyy 的代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=5000;
int n,m;
int u[Maxn+5],v[Maxn+5];
int w[Maxn+5],a[Maxn+5];  // w存储体重，a存储初始麻烦数
vector<int> e[Maxn+5];    // 邻接表存储图
int f[Maxn+5],dp[Maxn+5]; // f[i]表示操作一次i能带来的总操作次数
int ans;

bool cmp(int x,int y) {
    return w[x]<w[y];  // 按体重从小到大排序
}

void work(int u) {
    f[u]=1;  // 基础操作：操作u本身算1次
    memset(dp,-1,sizeof(dp));
    dp[0]=0;
    
    // 背包DP：选择朋友集合，使得体重和小于w[u]，且f值之和最大
    for (int v:e[u]) {
        for (int c=w[u]-1;c>=0;c--) {
            if (dp[c]==-1) continue;
            if (c+w[v]>=w[u]) continue;  // 体重和必须严格小于w[u]
            dp[c+w[v]]=max(dp[c+w[v]],dp[c]+f[v]);
        }
    }
    
    // 找到最大的f值之和
    int res=0;
    for (int c=0;c<w[u];c++)
        res=max(res,dp[c]);
    f[u]+=res;  // 加上通过传播能带来的额外操作次数
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>w[i];  // 读入体重
    for (int i=1;i<=n;i++) cin>>a[i];  // 读入初始麻烦数
    
    for (int i=1;i<=m;i++) cin>>u[i]>>v[i];
    
    // 构建图：只从体重大的指向体重小的
    for (int i=1;i<=m;i++) {
        if (w[u[i]]>w[v[i]])
            e[u[i]].push_back(v[i]);
        else if (w[v[i]]>w[u[i]])
            e[v[i]].push_back(u[i]);
    }   
    
    // 按体重排序
    for (int i=1;i<=n;i++) u[i]=i;
    sort(u+1,u+n+1,cmp);
    
    // 按体重从小到大计算f值
    for (int i=1;i<=n;i++)
        work(u[i]);
    
    // 总操作次数 = 每个史莱姆的初始麻烦数 × 操作该史莱姆一次带来的总操作次数
    for (int i=1;i<=n;i++)
        ans+=f[i]*a[i];
    cout<<ans<<"\n";
    return 0;
}

No comments so far...

【题解】2025 练习赛 1

语法 A. D+DD

语法 B. 传递计算器

CSP-J C. 发现蒂位

CSP-J D. 找最大值

CSP-S E. 奇变偶不变

CSP-S F. 好数

CSP-S G. 劫富济贫

0 comments

Status

Development

Support

【题解】2025 练习赛 1

语法 A. D+DD

语法 B. 传递计算器

CSP-J C. 发现蒂位

CSP-J D. 找最大值

CSP-S E. 奇变偶不变

CSP-S F. 好数

CSP-S G. 劫富济贫

0 comments

Status

Development

Support

SIGN IN