已结束 OI 开始于: 2025-8-17 9:00 3 小时主持人:

T1 三角形

考察等差数列求和+求余

如果是一个边长 $k$ 的完整三角形，那么字符的数量是 $k+(k-1)+(k-2)+...+1$ ，可以用等差数列求和公式得到 $k*(k+1)/2$ ，但是本题问的是第 $a$ 行的某一个字符，那么我们可以算出前 $a-1$ 行有多少个字符（也可以等差数列求和），然后再加上 $b$ （因为我们要求本行第 $b$ 个字符）就知道这个字符是整个三角形的第几个字符了。

由于 A~Z 是不断循环的 26 个字母，所以我们对 26 求余，将余数转化成字母即可获得答案。

#include <iostream>
using namespace std;
#define ll long long
int main(){
	ll n, a, b;
	cin >> n >> a >> b;	
	ll need = (n * (n + 1) - (n - a + 2) * (n - a + 1) ) / 2 - 1 + b; // 算出第 a 行第 b 列是第 need 个字符
	cout << (char)('A' + need % 26) << endl; // 把 need 转化成对应的字母
}

T2 切数字

考察递归进行决策类问题的枚举。

由于数字大小最多 $10^{18}$ ，每一个位置都可以切或者不切，所以我们可以使用递归来进行枚举。

定义 dfs 函数，参数 dep 表示递归深度，参数 sum 表示目前所有被切出来的数字之和，now 表示目前还没被切的数字大小。

对于每一个位置而言，如果不切，则当前数字和下一个数字连起来；否则将 now 加入到 sum 中并更新 now。（例如数字 156，刚开始看到 1，如果不切，那么 1 和 5 合并成 15，如果切，则获得单独的一个 1，将切下来的 1 加入到总和中，然后 now 变成 5，5 去和下一个数字看是否切/结合）

所有递归完成后，考虑有多少个不同的总和（代码中使用了 set 进行去重，实际上可以放入 int 数组中排序，排序后统计有多少个不同数字）

#include <iostream>
#include <set>
using namespace std;
string s;
set<int>ans;
void dfs(int dep, int sum, int now){
	if(dep == s.size()){
		ans.insert(sum + now);
		return;
	}
	int w = s[dep] - '0';
	dfs(dep + 1, sum, now * 10 + w);
	dfs(dep + 1, sum + now, w);
}
int main(){
	cin >> s;
	dfs(0, 0, 0);
	cout << ans.size() << endl;
}

T3 合并

考察找规律和取模

易错点

最后输出答案时，剩两个数字 $l,r$ ，需要求它们的平方和，正确写法应为 (l*l+r*r)%mod。典型错误 1：l*l+r*r%mod——即认为求余运算的优先级低于加法；典型错误 2：l*l%mod+r*r%mod——即认为两个小于 mod 的数字求和结果仍然小于 mod。这些写法将获得 30 分。
给定 $a$ 个数字 $b$ 并求和，其中数据范围 $1 \leq n \leq 10^{18}, 1 \leq a \leq n, 1 \leq b \leq 100$。正确写法 a%mod*b%mod。典型错误：a*b%mod——即认为一个 $10^{18}$ 的数字乘以 100 仍然在 long long 范围内。这种写法将获得 60 分。

题解

本题实际上为找规律，最后合并成两个数字（我们称为左、右两个数字），通过找规律解答：左边的数字是由多少个数字合并而成的，右边的数字是由多少个数字合并而成的。

找规律本质是代值法，即我们假设 $n=5$ ，看看最后几个数字合并成左数字，几个数字合并成右数字。再假设 $n=6,7,8,9...$ ，一直尝试，在尝试的过程中感受其变化过程，直到找到规律为止。

std

#include <iostream>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
int main(){
	ll n, k;
	cin >> n >> k;
	ll ans = 1;
	while(ans < n){
		ans *= 2;
	}
	ans /= 2; // ans 表示左边需要几个数字，这个是找出来的规律
	ll l = 0, r = 0, num = 0, a, b;
	for(int i = 1; i <= k; i++){
		cin >> a >> b;
		if(num == ans){ // 所有数字都合并给右边
			r = (r + a % mod * b) % mod;
		}else if(num + a <= ans){ // 所有数字都合并给左边
			l = (l + a % mod * b) % mod;
			num += a; // 记录左边有多少个数字
		}else{ // a 个数字 b 需要拆分，一部分给左边，一部分给右边
			ll now = ans - num;
			l = (l + now % mod * b) % mod;
			num = ans; // 赋值成 ans 表示左边数字已经合并好了，其余数字给右边，之后进入第一个 if
			r = (r + (a % mod - now + mod) % mod * b) % mod;
		}
	}
	cout << (l * l % mod + r * r) % mod << endl;
}

T4 插班生

考察求贡献的思想以及前缀和。

20pt：

简单模拟，枚举插班生的位置，然后算出此时每个人的听课认真度，求和即可。

20pt std

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
int a[maxn], n;
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= n; i++){
		int ans = 0;
		for(int j = 1; j <= n; j++){
			if(j == i)	continue;
			ans += max(0, a[j] - n + abs(i - j));
		}
		cout << ans << " ";
	}
}

60pt：

首先考虑问题的简化版——假设每个人的听课认真度可以变为负数。那么当插班生位于位置 $i$ 时，位置 $i-1$ 的人的听课认真度一定会减少 $n-1$ ，位置为 $i-2$ 的人的听课认真度一定会减少 $n-2$ （能够看出插班生左边的人减少的听课认真度是一个等差数列，右边同理）。我们就可以很容易地算出插班生位于每一个位置时的全班听课认真度的总和（用初始听课认真度的总和减去左右两边等差数列求和）。

但是直接用这样的做法来做这道题显然是错误的，因为每个人的听课认真度最小是 0，我们直接减去等差数列的和会导致多减一些值。于是让我们考虑到底多减了多少。首先让我们定义 ans[i] 是插班生位于位置 i 时的总答案（所有人的听课认真度之和）。

假设某一个人的位置为 2，听课认真度为 3，n 为 7。那么插班生坐在位置 3 时，他的听课认真度原本会减少 $n-1=6$ ，但是由于他的认真度只有 3，所以最多只会减少 3。所以直接用上述等差数列求和会导致 ans[3] 多减了 $6-3=3$ 。同理，假设插班生坐在位置 4，他的听课认真度会减少 $n-2=5$ ，但是由于最多减少 3，所以用等差数列求和会导致 ans[4] 多减了 2。不难发现，假设这个人位置为 $i$ ，则他会使得 ans[i+1] 多减 3，ans[i+2] 多减 2，ans[i+3] 多减 1——这是一个等差数列。如果我们能够算出每一个 ans[i] 被多减了多少，答案就能够算出来了。我们发现每一个点对答案的贡献都是等差数列，如果给定位置 i 和这个人的听课认真度，我们能够用 for 循环 O(n) 更新这些等差数列，但是显然这样会超时。

请务必理解上述思路的含义再往下看题解，上述思路详见下方代码。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
int a[maxn], n, ans[maxn], sum = 0;
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		sum += a[i];
		for(int j = 1; j <= n; j++){
			if(j == i)	continue;
			if(a[i] - (n - abs(i - j)) > 0)	continue;
			ans[j] += (n - abs(i - j)) - a[i]; // 记录多减的值 
		}
	}
	// 每个位置用 sum - a[i] - 左右等差数列求和 + 多减的值 
	for(int i = 1; i <= n; i++)
		cout << sum - a[i] - (i-1) * i / 2 - (n-i) * (n-i+1) / 2 - 2 * (n - i) * (i - 1) + ans[i] << " ";
}

所以我们考虑用前缀和维护等差数列，算出最终的答案。

对于 60 分而言，有 $a_i > n$ ，不会减成负数，所以我们无需记录多减的值，可以快速地算出答案。

100pt

具体来说，假设我有一个 pre 数组，初始全部为 0，我将 pre[1] += 1，然后对 pre 数组求前缀和，发现整个数组都被加了 1。如果我将 pre[i] += 1，将 pre[j+1] -= 1 $(i <= j)$ ，再对 pre 数组求前缀和，相当于 [i,j] 全部加了 1。也就是说假设我要将数组中连续的一段全部加 q，可以通过先打标记，最后求前缀和的方式实现。而现在的任务是我们需要将数组中的连续一段全部加上一个等差数列。

假设我有一个 pre 数组，我将 pre[1] += 1，然后对 pre 数组求前缀和，求得的值放到 pre2 数组，我发现 pre2 数组全部加了 1，然后再对 pre2 数组求前缀和，则发现整个数组变成了一个等差数列。如果我将 $pre[i] += 1，pre[j] -=1, pre2[j] -= j-i+1$ ，则相当于将 [i,j] 加上了一个形如 1，2，3，4 的等差数列。

想一想：为什么要对 pre2[j] -= j-i+1

想一想：假设等差数列的首项不是 1，而是 d，即一个形如 d,d+1,d+2,d+3 的等差数列，那么应该怎么办呢？

#include <iostream>
using namespace std;
const int maxn = 1e5 + 5;
#define ll long long
ll pre[maxn], suf[maxn], pre2[maxn], suf2[maxn], a[maxn];
int main(){
	int n;
	cin >> n;
	ll sum = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		sum += a[i];
	}
	for(int i = 1; i <= n; i++){ // 考虑每个点对左边的贡献
		// a[i]  很大，不会使答案多减，直接跳过 
		if(a[i] >= n - 1)	continue;
		// d 是等差数列的首项，l 是等差数列的起点 
		ll l = i - (n - a[i] - 1), d = 0;
		if(l < 1){
			d = - l + 1;
			l = 1;
		}
		pre[l]++;
		pre[i]--;
		pre2[l] += d;
		pre2[i] -= d + (i - l);// 想一想，为什么是 i-l 而不是 i-l+1
	}
	for(int i = n; i >= 1; i--){ // 考虑每个点对右边的贡献
		if(a[i] >= n - 1)	continue;
		ll r = i + (n - a[i] - 1), d = 0;
		if(r > n){
			d = r - n;
			r = n;
		}
		suf[r]++;
		suf[i]--;
		suf2[r] += d;
		suf2[i] -= d + (r - i);
	}
	for(int i = 1; i <= n; i++){
		pre[i] = pre[i-1] + pre[i];
		pre2[i] += pre[i] + pre2[i-1];
	}
	for(int i = n; i >= 1; i--){
		suf[i] = suf[i+1] + suf[i];
		suf2[i] += suf[i] + suf2[i+1];
	}
	for(long long i = 1; i <= n; i++){ // 在这一步中 suf2[i] + pre2[i] 相当于上述代码的 ans[i]
		cout << sum - a[i] - (i-1) * i / 2 - (n-i) * (n-i+1) / 2 - 2 * (n - i) * (i - 1) + suf2[i] + pre2[i]  << " ";
	}
}

T4 33DAI 代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[412345];
namespace subtask1
{
    void work()
    {
        for (int pos = 1; pos <= n; pos++)
        {
            int now = 0;
            for (int i = 1; i <= n; i++)
            {
                if (i != pos)
                {
                    now += max(0LL, a[i] - (n - abs(i - pos)));
                }
            }
            cout << now << " ";
        }
        cout << "\n";
    }
}
namespace subtask2
{
    int sum[412345];
    int cal[412345]; // cal[i]: 距离为 1~i 一共减少的数值
    void work()
    {
        sum[0] = 0;
        for (int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + a[i];
        cal[0] = 0;
        for (int dis = 1; dis <= n; dis++)
            cal[dis] = cal[dis - 1] + (n - dis);
        for (int pos = 1; pos <= n; pos++)
        {
            int now = 0;
            now += sum[pos - 1] - sum[0] - cal[pos - 1];
            now += sum[n] - sum[pos] - cal[n - pos];
            cout << now << " ";
        }
        cout << "\n";
    }
}
namespace subtask3
{
    /*
    n=10
    1   2   3   4   5   6   7   8   9   10
    pos -9  -8  -7  -6  -5  -4  -3  -2  -1
    -9  pos -9  -8  -7  -6  -5  -4  -3  -2
    -8  -9  pos -9  -8  -7  -6  -5  -4  -3
    -7  -8  -9  pos -9  -8  -7  -6  -5  -4
    -6  -7  -8  -9  pos -9  -8  -7  -6  -5
    -5  -6  -7  -8  -9  pos -9  -8  -7  -6
    -4  -5  -6  -7  -8  -9  pos -9  -8  -7
    -3  -4  -5  -6  -7  -8  -9  pos -9  -8
    -2  -3  -4  -5  -6  -7  -8  -9  pos -9
    -1  -2  -3  -4  -5  -6  -7  -8  -9  pos
    a[6] = 7
    1   2   3   4   5   (6)   7   8   9   10
    pos -9  -8  -7  -6  -5  -4  -3  -2  -1  ~
    -9  pos -9  -8  -7  -6  -5  -4  -3  -2  ~
    -8  -9  pos -9  -8  -7  -6  -5  -4  -3  ~
    -7  -8  -9  pos -9  -8  -7  -6  -5  -4  +1
    -6  -7  -8  -9  pos -9  -8  -7  -6  -5  +2
    -5  -6  -7  -8  -9  pos -9  -8  -7  -6  ~
    -4  -5  -6  -7  -8  -9  pos -9  -8  -7  +2
    -3  -4  -5  -6  -7  -8  -9  pos -9  -8  +1
    -2  -3  -4  -5  -6  -7  -8  -9  pos -9  ~
    -1  -2  -3  -4  -5  -6  -7  -8  -9  pos ~
    */
    int sum[412345];
    int cal[412345]; // cal[i]: 距离为 1~i 一共减少的数值
    int ans[412345]; // 不考虑 max(0,~) 时的答案
    int BASE = 200005;
    int minL;
    int aa[412345]; // 答案修正
    int d[412345];  // 答案修正
    int dd[412345]; // 答案修正
    void update(int l, int r, int st, int sub)
    {
        //cout << l << " " << r << " " << st << " " << sub << endl;
        minL = min(minL, l);
        int ed = st + (r - l) * sub;
        // aa[l]~a[r]    +st +(st+sub) +(st+2sub) ... +ed
        // d[l]~d[r+1]  +st +sub +sub ... +sub -ed
        // dd[l]~dd[r+2]+st +(sub-st) +0 ... +0 +(-ed-sub) + ed
        dd[l + BASE] += st;
        dd[l + 1 + BASE] += (sub - st);
        dd[r + 1 + BASE] += (-ed - sub);
        dd[r + 2 + BASE] += ed;
    }
    void work()
    {
        sum[0] = 0;
        for (int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + a[i];
        cal[0] = 0;
        for (int dis = 1; dis <= n; dis++)
            cal[dis] = cal[dis - 1] + (n - dis);
        for (int pos = 1; pos <= n; pos++)
        {
            int now = 0;
            now += sum[pos - 1] - sum[0] - cal[pos - 1];
            now += sum[n] - sum[pos] - cal[n - pos];
            ans[pos] = now;
            // cout << pos << "~" << ans[pos] << endl;
        }
        for (int i = 1; i <= n; i++)
        {
            // 最多减少 n - 1
            if (a[i] >= n - 1)
                continue;         // 无需修正
            int r = n - 1 - a[i]; // 需要修改的半径
            // i-r ~ i-1：+1 +2 ... +r
            update(i - r, i - 1, 1, 1);
            // i+1 ~ i+r: +r +(r-1) ... +1
            update(i + 1, i + r, r, -1);
        }
        for (int i = minL; i <= n; i++)
            d[i + BASE] = d[i - 1 + BASE] + dd[i + BASE];
        for (int i = minL; i <= n; i++)
            aa[i + BASE] = aa[i - 1 + BASE] + d[i + BASE];
        for (int i = 1; i <= n; i++)
            cout << ans[i] + aa[i + BASE] << " ";
        cout << "\n";
    }

}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    bool flag1, flag2;
    flag1 = flag2 = true;
    cin >> n;
    flag1 = (n <= 1000);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        flag2 = flag2 && a[i] >= n;
    }
    if (flag1)
        subtask1::work();
    else if (flag2)
        subtask2::work();
    else
        subtask3::work();
    return 0;
}

状态: 已结束
规则: OI
题目: 4
开始于: 2025-8-17 9:00
结束于: 2025-8-17 12:00
持续时间: 3 小时
主持人: 33DAI
参赛人数: 7

【CSP-J】0817练习赛