CZSC 2024 第一次题解

2024-08-18 12:59:00

说明

本篇文章是举行在2024年8月18日的 CZSC2024第一次的题解

比赛页：https://www.luogu.com.cn/contest/188106

T1点：https://www.luogu.com.cn/problem/T484700

T2修剪树枝：https://www.luogu.com.cn/problem/T488675

T3取模：https://www.luogu.com.cn/problem/T485663

T4填数游戏：https://www.luogu.com.cn/problem/T488688

概览

暴力打满：80+16+20+32=148pts
优秀：100+40+36+48=224pts

相对水平推测（以完全零基础为基准）：

河北NOIP三等：50pts
河北NOIP二等：100pts
河北NOIP一等：150pts
CCF六级：224pts
CCF七级/河北省队：300pts

绝对水平推测（以选手完全学习信竞后的水平为基准）：

河北NOIP三等：200pts
河北NOIP二等：348pts
河北NOIP一等：400pts

简要题解

T1 直接记录一个点有没有被连接就行，每次操作的时候去判断并记录，顺便统计答案。
T2 先从小到大排序，枚举剪刀硬度的同时枚举树枝硬度，一个个匹配，这就是最优的选择方案。
T3 直接找规律，规律找到后拿高斯求和公式直接计算即可。
T4 先考虑分数全正且相同的情况，再考虑全正但不同的情况，负数情况同理。然后考虑单调递增的情况，然后再考虑先负后正的情况。这些特殊情况都是不难考虑的。于是你发现，所有的一般情况都是上述特殊情况的组合。

T1 点

概览

本题考察选手最基本的 C++ 语法，但不落俗套，需要选手有少量的思考。题目以图论为背景，看似是超纲的，但实际上只需要稍加观察即可找到突破口。

需要选手有基本的C++语法知识。

难度：入门

详细考察点：C++ 基本语法、题目转化、时间复杂度分析

算法一

不难发现，当 $n$ 为 $3$ 时，第一条边加入时必然就剩一个孤立点。如果再加一条边，必然是不存在孤立点了。再加一条边，仍然是不存在孤立点。

所以只需要根据 $m$ 的大小输出即可。参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m;
	cin>>n>>m;
	if(m==1){
		cout<<1;
	}
	if(m==2){
		cout<<1<<endl<<0;
	}
	if(m==3){
		cout<<1<<endl<<0<<endl<<0;
	}
	return 0;
}

以上代码可通过测试点 $1\sim2$ ，期望得分 $8pts$ 。

算法二

对于满足 $y=x+1$ 性质的测试点，结合题目说不会重复地将两点相连，我们考虑，数据大致应该是这样：先把点 $1$ 和点 $2$ 连接，再把点 $2$ 和点 $3$ 连接，再把点 $3$ 和点 $4$ 连接......，直到将点 $n-1$ 与点 $n$ 连接。实际上 $m=n-1$ 。我们发现，第一条边加入后，立刻有两个点变为了非孤立点，孤立点数量为 $n-2$ 。此后，每加入一条边，都会让孤立点减少一个。

然后我们紧接着再看对于满足 $x=1$ 性质的测试点，结合题目说不会重复地将两点相连，我们考虑，数据大致应该是这样：先把点 $1$ 和点 $2$ 连接，再把点 $1$ 和点 $3$ 连接，再把点 $1$ 和点 $4$ 连接......，直到将点 $1$ 与点 $n$ 连接。实际上 $m=n-1$ 。我们发现，孤立点数量的变化和上述情况是相同的。

综上，所以我们只需要从 $n-2$ 倒着输出到 $0$ 即可，参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=n-2;i>=0;i--){
		cout<<i<<endl;
	} 
	return 0;
}

以上代码可以通过测试点 $15\sim20$ 。期望得分 $24pts$ 。结合算法一可获得 $32pts$ 。

算法三

我们还可以开一个数组 $tag$ ， $tag[i]$ 表示点 $i$ 连接了多少个边。当给点 $u$ 和 $v$ 连边的时候只需要 $tag[u]++$ ， $tag[v]++$ 。如果 $tag[i]=0$ ，则说明点 $i$ 没有与任何边连接，也就是点 $i$ 为孤立点。

我们可以有这样的代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int tag[200005];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		tag[x]++;
		tag[y]++;
		int ans=0;
		for(int i=1;i<=n;i++){
			if(tag[i]==0){
				ans++;
			}
		}
		cout<<ans<<endl;
	} 
	return 0;
}

分析时间复杂度，应该是 $O(mn)$ 的，只能通过测试点 $1\sim20$ ，期望得分 $80pts$ 。

算法四（正解）

我们需要注意到这样的两点

一个点不是孤立点后，无论再怎样加边，都不可能再变回孤立点
随着添加边数的增加，孤立点数量一定是单调不增的

所以我们在算法三的基础上进行改进，我们定义变量 $ans$ 表示当前孤立点数量，初始时 $ans=n$ 。当给点 $u$ 和 $v$ 连边的时候，如果 $tag[u]=0$ ，说明点 $u$ 原来是孤立点，现在不是了（有边相连了）， $ans--$ 即可。点 $v$ 同理。

参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
#define _ 200005
using namespace std;
int tag[_];
int main(){
	ios::sync_with_stdio(false);
	int n,m;cin>>n>>m;
	int ans=n;
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		if(!tag[x]) ans--;
		if(!tag[y]) ans--;
		tag[x]++;tag[y]++;
		cout<<ans<<endl;
	}
	return 0;
}

时间复杂度 $O(m)$ ，可以通过所有测试点，期望得分 $100pts$ 。

T2 修剪树枝

概览

本题需要选手考虑到剪刀和树枝对应的最佳方案。

需要选手有一定的思考但代码量不高。

难度：普及- 到普及/提高- 之间

详细考察点：C++ 基本语法、排序算法、贪心算法、双指针、时间复杂度分析

算法一

八仙过海各显神通了

可能通过了测试点 $1\sim 8$ ，期望得分 $32pts$ 。

算法二

考虑 $n=1$ 的情况，显然答案要么是 $0$ 要么是 $1$ 。我们只需要找到所有树枝中坚硬程度最小的树枝，判断能否使用这唯一的剪刀剪掉即可。如果硬度最小的树枝都剪不了，其他的树枝也就别想了。

参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int a[200005],b[200005];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	sort(b+1,b+m+1);
	if(a[1]>=b[1]) cout<<1;
	else cout<<0;
	return 0;
}

以上代码可以通过测试点 $9$ ，期望得分 $4pts$ 。当然你还可以使用 $O(n)$ 的方法，遍历一遍数组 $b$ 找到最小值。

接着我们考虑 $m=1$ 的情况，我们只需要找到坚硬程度最大的剪刀，判断能不能剪掉这唯一的树枝即可。如果硬度最大的剪刀都剪不了，其他的剪刀也就别想了。

参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int a[200005],b[200005];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	sort(a+1,a+n+1);
	if(a[n]>=b[1]) cout<<1;
	else cout<<0;
	return 0;
}

以上代码可以通过测试点 $10$ ，期望得分 $4pts$ 。

两个代码结合起来可以获得 $8pts$ 。

算法三

考虑特殊性质 $A$ ，因为所有的 $a_i$ 都相同，我们设这个相同的值为 $k$ 。然后我们可以扫一下 $b$ 序列，求出有多少个树枝坚硬程度小于等于 $k$ ，我们假设有 $x$ 个。然后我们就知道了有 $x$ 个树枝可以被剪掉。

但你还需要比较一下 $x$ 和 $n$ 哪个大，因为一个剪刀只能用一次。

参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int a[200005],b[200005];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	int x=0,k=a[1];
	for(int i=1;i<=m;i++){
		if(k>=b[i]) x++;
	}
	cout<<min(x,n);
	return 0;
}

以上代码可以通过测试点 $11$ ，期望得分 $4pts$ 。结合算法二可获得 $12pts$ 。

考虑特殊性质 $B$ ，和上述的做法差不多，代码如下：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int a[200005],b[200005];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	int x=0,k=b[1];
	for(int i=1;i<=n;i++){
		if(a[i]>=k) x++;
	}
	cout<<min(x,m);
	return 0;
}

以上代码可以通过测试点 $12$ ，期望得分 $4pts$ 。两份代码结合起来可获得 $8pts$ ，再结合算法二可获得 $16pts$ 。

算法四

我们继续考虑，如果想剪更多的树枝，那么应该当然是柿子找软的捏，尽量从树枝硬度比较小的开始处理。所以我们可能要把数组 $b$ 从小到大排序。

然后我们考虑怎么去利用我们手上的剪刀。我们显然是不能把一个硬度很大的剪刀去剪硬度很小的树枝，因为夸张点说这属于大炮轰蚊子，会造成浪费的，我们最好是让剪刀利用地刚刚好。我们把硬度大的剪刀留在后面，先利用硬度小的剪刀，硬度较小的树枝只需要让硬度较小的剪刀去干就好了。所以我们也对数组 $a$ 从小到大排序。

然后我们从第一个剪刀开始枚举，看看当前枚举的剪刀能不能利用上。从硬度最小的树枝开始，从小到大去看看当前枚举到的剪刀能不能剪当前枚举到的树枝。这样就能做到硬度较小的剪刀能剪去硬度较小的树枝，利用的情况应该是刚刚好的。

注意可能还要开个数组来判断树枝是否已经被剪掉了。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
int a[200005],b[200005],ok[200005];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	sort(a+1,a+n+1);
	sort(b+1,b+m+1);
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(ok[j]!=0) continue;//说明已经树枝被剪掉了，跳过
			if(a[i]>=b[j]){
			    ok[j]=1;
				ans++;
				break;//能剪就剪，剪完之后该剪刀就不能用了，内层循环要跳出去 
			} 
		}
	}
	cout<<ans; 
	return 0;
}

以上代码的时间复杂度为 $O(nm)$ ，可以通过测试点 $1\sim10$ 期望得分 $40pts$ 。

算法五（正解）

算法四其实是有很多没必要的操作的。你观察一下就会发现，树枝一定是从硬度最小的树枝开始从小到大剪的。所以对于每个剪刀，你其实没必要每次都从头枚举 $b$ 数组，你只需要从上回循环跳出的位置继续枚举即可。

实际上你并不需要继续枚举，你只需要判断一下就行，因为当前可以剪的硬度最小的树枝你都剪不掉，硬度更大的树枝更剪不掉了。

具体参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define int long long
#define _ 200005
using namespace std;
int a[_],b[_];
signed main(){
	ios::sync_with_stdio(false);
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	sort(a+1,a+n+1);
	sort(b+1,b+m+1);
	int p=1,ans=0;//p用来记录当前枚举到的b数组的位置
	for(int i=1;i<=n;i++){
		if(a[i]>=b[p]){
			ans++;
			p++;//b[p]这个树枝被剪了，让p+1，下回循环就判断b[p+1]了
			if(p>m) break;//p都比m大了，直接跳出循环
		}
	}
	cout<<ans;
	return 0;
}

时间复杂度 $O(n)$ ，可以通过所有测试点，期望得分 $100pts$ 。

其他验题者代码：

范铭轩：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
int a[N],b[N];

int main(){
	int n,m;
	cin>>n>>m;
	for(int i = 1;i <= n;++ i) cin>>a[i];
	for(int i = 1;i <= m;++ i) cin>>b[i];
	sort(a + 1,a + n + 1);
	sort(b + 1,b + m + 1);
	int x = 1,y = 1,ans = 0;
	while(x <= n && y <= m){
		while(x <= n && a[x] < b[y]) x ++;
		if(x > n) break;
		ans ++;
		x ++;
		y ++;
	}
	cout<<ans;
	return 0;
}

王添翼：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;

const int N = 2e5;
int a[N+10] , b[N+10];
int n , m , ans , ap , bp;

signed main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    sort( a + 1 , a + n + 1 );
    for(int i = 1;i <= m;i ++) cin >> b[i];
    sort( b + 1 , b + m + 1 );
    ap = 1 , bp = 0;
    while( ap != n+1 and bp != m ){
        if( a[ap] >= b[bp+1] ){
            ap ++ , bp ++;
        }
        else{
            ap ++;
        }
    }
    cout << bp << endl;
    return 0;
}

路浩祥

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
int n,m,a[200005],b[200005],ans;
int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for (int i=1;i<=m;i++)
		scanf("%d",&b[i]);
	sort(a+1,a+n+1);
	sort(b+1,b+m+1);
	int i = 1, j = 1, count = 0; 
    while (i <= n && j <= m) 
	{
        if (a[i] >= b[j]) 
		{
            count++;
            i++;
            j++;
        } 
		else i++;
    }
	printf("%d",count);
	return 0;
}

T3 取模

概览

本题的突破点在于选手能否发现所谓的"完全取模"的规律，在规律找到之后如何使用代码来更好地计算也是个挑战。

需要选手具有较高的思维水平。

难度：普及/提高-。题目可以放在NOIP中的第一题位置作为签到题。

详细考察点：C++ 基本语法、找规律、前缀和算法、高斯求和公式、取模运算、时间复杂度分析

算法一

题目怎么说你就怎么做。

注意取模，还有 #define int long long 这些东西。都是课上讲的。

参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=19260817;
void solve(){
	int l,r,m,n;
	cin>>l>>r>>m>>n;
	int ans=0;
	for(int i=l;i<=r;i++){
		int x=i;
		for(int j=n;j>=m;j--){
			x%=j;
		}
		ans+=x;
		ans%=mod;
	}
	cout<<ans<<endl;
}
signed main(){
	int T;cin>>T;
	for(int i=1;i<=T;i++) solve();
	return 0;
}

时间复杂度 $O(Trn)$ 仅能通过测试点 $1\sim3$ ，期望得分 $12pts$ 。

算法二

考虑特殊性质 $A$ ，我们直到如果一个数对比他还大的数取模，就等于他本身了，因此这种性质下，就相当于把 $[l,r]$ 区间内的所有数组都加起来。

我们有下面这几个方案

做法一

直接开循环求和，我们练习题做过类似的。

参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=19260817;
void solve(){
	int l,r,m,n;
	cin>>l>>r>>m>>n;
	int ans=0;
	for(int i=l;i<=r;i++){
		ans+=i;
		ans%=mod;
	}
	cout<<ans<<endl;
}
signed main(){
	int T;cin>>T;
	for(int i=1;i<=T;i++) solve();
	return 0;
}

时间复杂度 $O(Tr^2)$ 仅能通过测试点 $4$ ，期望得分 $4pts$

做法二

当 $l=1$ 的时候，就相当于从 $1$ 一直加到 $r$ ，有高斯的求和公式：

\frac{r(r+1)}{2}

就可以做到时间复杂度 $O(T)$ 。

参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=19260817;
void solve(){
	int l,r,m,n;
	cin>>l>>r>>m>>n;
	int ans=0;
	ans=r*(r+1)/2;
	ans%=mod;
	cout<<ans<<endl;
}
signed main(){
	int T;cin>>T;
	for(int i=1;i<=T;i++) solve();
	return 0;
}

可以通过测试点 $5\sim6$ ，期望得分 $8pts$ 。

做法三

那么 $l$ 不等于 $1$ 开始呢，求和公式是不是就用不上了？其实是还可以用上，我们考虑一种前缀和的思想，我们令 $sum_i$ 为从 $1$ 加到 $i$ ，那么区间 $[l,r]$ 内所有数字相加即为 $sum_r-sum_{l-1}$ 。

参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=19260817;
void solve(){
	int l,r,m,n;
	cin>>l>>r>>m>>n;
	int ans=0;
	int sum1=r*(r+1)/2;sum1%=mod;
	int sum2=(l-1)*l/2;sum2%=mod;
	ans=(sum1-sum2+mod)%mod;
	cout<<ans<<endl;
}
signed main(){
	int T;cin>>T;
	for(int i=1;i<=T;i++) solve();
	return 0;
}

以上代码可以通过测试点 $4\sim8$ ，期望得分 $20pts$ 。

算法三

先考虑特殊性质 $D$ 。由于每组之间的 $m$ 和 $n$ 都相同，我们可以预处理一下。先计算从 $1$ 到 $2\times10^6$ 中每个数完全取模后的结果，放到数组 $pre$ 。中，然后每组数据，只需要从 $pre[l]$ 加到 $pre[r]$ 即可求出答案。

但这样如果不算上预处理，光处理询问，时间复杂度就是 $O(Tr)$ 的，并不能给我们很多分数。

这种对一个数列多次询问区间总和的问题，我们可以使用前缀和算法。这样复杂度就到了 $O(T)$ 了。

但我们再考虑预处理，每个数组都完全取模，时间复杂度要到达 $O(2\times10^6\times n)$ ，依然不能给我们很多分数。

我们继续考虑，如果一个数对 $n$ 取模之后，得到的数仍然落在 $[m,n]$ 这个区间上，那么后续完全取模之后必然为 $0$ ，因为你必然会对他本身取模的。反之完全取模后就直接是仅对 $n$ 取模后的结果。所以其实所谓的完全取模只需取模一次再判断一下就可以了。这样时间复杂度就到了 $O(2\times 10^6)$ .

参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=19260817;
int pre[2000006],sum[2000006];
int flag=0;//是否已经预处理过了 
void solve(){
	int l,r,m,n;
	cin>>l>>r>>m>>n;
	if(flag==0){
		for(int i=1;i<=2000000;i++){
			if(i%n>=m) pre[i]=0;
			else pre[i]=i%n;
		}
        //这里是前缀和预处理
		for(int i=1;i<=2000000;i++){
			sum[i]=(sum[i-1]+pre[i])%mod;
		}
		flag=1;
	} 
	cout<<(sum[r]-sum[l-1]+mod)%mod<<endl;
}
signed main(){
	int T;cin>>T;
	for(int i=1;i<=T;i++) solve();
	return 0;
}

以上代码可以通过测试点 $13\sim 16$ ，期望得分 $16pts$ 。

算法四

考虑性质 $C$ ，若 $m$ 和 $n$ 相同，则相当于把 $[l,r]$ 上所有的数字对 $m$ 取模后相加。数字从 $1$ 开始依次对 $m$ 取模，我们能发现存在规律。比如 $m=3$ 时，

$1\%3=1$
$2\%3=2$
$3\%3=0$
$4\%3=1$
$5\%3=2$
$6\%3=0$
$7\%3=1$
......

最后结果，应该是从 $1$ 增长到 $m-1$ ，然后是 $0$ ，这样的片段不断重复。又比如 $m=5$ 时是这样的

12340 12340 12340 12340 12340 12340..

我们将 12340 这样的称为一个块，发现块长度就为 $m$ ，块内所有数字之和为 $\frac{m(m-1)}{2}$ 。

然后我们应该是可以通过简单的数学计算来求出位于 $[l,r]$ 区间内这些数字之和了。不过需要注意的是，有可能是这样的：

也就是询问的区间包含了不完整的块。这种情况下处理起来不太方便。

我们再回想之前算法二中做法三的做法以及性质 $B$ 给我们的提示，我们不难发现，处理 $[1,r]$ 这种区间，也就是左端点是 $1$ 开头的，是比较简单的，因为这样你只需要考虑右边那个完整的块了。至于要求 $[l,r]$ 的答案，只需要求出 $[1,r]$ 的答案和 $[1,l-1]$ 的答案再一减就好了。

对于 $[1,r]$ 这种区间， $\left \lfloor \frac{r}{m} \right \rfloor$ 为包含了多少个块。然后 $r\%m$ 即为最后那个不完整的块的长度，记为 $k$ ，于是那个不完整的块内的数字求和为 $\frac{k(k+1)}{2}$ 。

对于 $[1,l-1]$ 区间同理。

参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=19260817;
void solve(){
	int l,r,m,n;
	cin>>l>>r>>m>>n;
	int sum=m*(m-1)/2%mod;
	int cnt1=r/m;
	int k1=r%m;
	int sum1=(cnt1*sum%mod+k1*(k1+1)/2%mod)%mod;
	
	int cnt2=(l-1)/m;
	int k2=(l-1)%m;
	int sum2=(cnt2*sum%mod+k2*(k2+1)/2%mod)%mod;
	cout<<(sum1-sum2+mod)%mod<<endl;
}
signed main(){
	int T;cin>>T;
	for(int i=1;i<=T;i++) solve();
	return 0;
}

以上代码可以通过测试点 $9\sim 12$ ，期望得分 $16pts$ 。

算法五（正解）

考虑性质 $C$ 的时候我们试了几个数找出了规律，对于一般规律我们应该也是可以的。我们先假设 $m=3，n=5$ ，然后从 $1$ 开始一个一个看：

$1$ 完全取模后为 $1$
$2$ 完全取模后为 $2$
$3$ 完全取模后为 $0$
$4$ 完全取模后为 $0$
$5$ 完全取模后为 $0$
$6$ 完全取模后为 $1$

然后你发现完全取模后的序列大概是

12000 12000 12000 ...

这样的。

然后如果取 $m=4，n=6$ ，那么大概是这样的

123000 123000 123000 ...

然后你发现，块长度还是 $n$ 。但从第 $m-1$ 个数开始完全取模就为 $0$ 了，所以我们只需要在算法四代码的基础上稍加修改即可。

参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=19260817;
signed main(){
	ios::sync_with_stdio(false);
	int T;cin>>T;
	while(T--){
		int l,r,m,n;cin>>l>>r>>m>>n;
		l--;//给l-1，这样后面直接拿l计算即可
		if(m<=1){//判断一种特殊情况
			cout<<0<<endl;
			continue;
		}
		int sum=m*(m-1)/2%mod; //一个块中所有的数之和
		
		int v=r/n*sum%mod;//完整块内所有数之和
		int v_=min(m-1,r%n);//判断余下的块长度，如果余下的块长比m-1还大，那么就取m-1即可，因为第m个数开始为0
		v+=v_*(v_+1)/2;v%=mod;//这里用了求和公式
		
        //同理
		int u=l/n*sum%mod;
		int u_=min(m-1,l%n);
		u+=u_*(u_+1)/2;u%=mod;
		//
		cout<<(v-u+mod)%mod<<endl;		
	}
	return 0;
}

以上代码可通过全部测试点，期望得分 $100pts$ 。

以下是其他验题人的代码：

王添翼

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include <typeinfo>
#include<string>
#define int long long
using namespace std;

const int p = 19260817;

int guss( int l , int r ){
    return ((l+r)*(r-l+1)/2) %p;
}

signed main(){
    int t;
    cin >> t;
    int l , r , m , n;
    while( t -- ){
        cin >> l >> r >> m >> n;
        int ans = 0;
        int z = r/n - l/n;

        if( z ){
            int lm = l % n , rm = r % n;
            if( lm < m ){
                ans += guss( lm , m-1 ) % p;
                ans %= p;
            }
            ans += (guss( 1 , m-1 ) * (z-1) % p);
            ans %= p;
            ans += (guss( 1 , min( rm , m-1 ) ) %p);
            ans %= p;
        }
        else{
            ans += (guss( l % n , min( r%n , m-1 ) )%p);
            ans %= p;
        }
        ans %= p;
        cout << (ans>0?ans:0) << endl;
    }
    return 0;
}

赵玉航

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
#define MAXN 1000010
#define int long long
#define raed() read()
#define mp(x,y) make_pair(x,y)
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,l,r) for(int i=l;i>=r;i--)
#define lowbit(x) (x&(-x))
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define inf 0x3f3f3f3f
#define mod (int)(19260817)
#define PI 3.1415926535
#define test(s) freopen("s","r",stdin);
#define endl "\n"
using namespace std;
int a[MAXN];
int n;
inline void solve(int wtf)
{
	int l,r,m,n;
	int u,v;
	cin>>l>>r>>m>>n;
	int sum1=0;
	int sum2=0;
	u=(r+1)/n;
	v=(r+1)%n;
	sum1=u*(0+m-1)*m/2%mod+(0+min(m-1,v-1))*min(m,v)/2%mod;
	l--;
	swap(l,r);
	u=(r+1)/n;
	v=(r+1)%n;
	sum2=u*(0+m-1)*m/2%mod+(0+min(m-1,v-1))*min(m,v)/2%mod;
	cout<<((sum1-sum2)%mod+mod)%mod<<endl;
	return;
}
signed main()
{
	int T=1;
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>T;
	rep(i,1,T)
	    solve(i);
	return 0;
}

路浩祥

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#define ll long long
using namespace std;
const ll inf = 19260817;
ll sum(ll start, ll end)
{
	return ((start + end) * (end - start + 1) / 2) % inf;
}
int main()
{
	ios_base::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--)
	{
		ll l, r, m, n;
		cin >> l >> r >> m >> n;
		if (l>=m&&r<=n)
		{
			cout<<0<<endl;
		}
		else
		{ 
			ll ans = 0, k = r / n - l / n;
			if (k > 0)
			{
				ll lm = l % n, rm = r % n;
	
				if (lm < m)
				{
					ans += sum(lm, m - 1) % inf;
					ans %= inf;
				}
				ans += (sum(1, m - 1) * (k - 1) % inf);
				ans %= inf;
				ans += sum(1, min(rm, m - 1)) % inf;
				ans %= inf;
			}
			else
			{
				ans += sum(l % n, min(r % n, m - 1)) % inf;
				ans %= inf;
			}
			cout << ans% inf << endl;
		}
	}
	return 0;
}

T4 填数游戏

概览

本题直接从正面考虑，难度是很大的。实际上，本题需要选手根据测试点的特殊性质，先考虑特殊情况如何解决，从而想出一般情况的解决方法。

需要选手有很高的思维水平和一定的代码能力。

难度：普及+/提高。题目可以放在NOIP的第一题位置，作为难度不低的题目。

详细考察点：C++基本语法、前缀和算法、贪心算法、时间复杂度分析

算法一

当 $n=4$ 是，填数总共就这么几个情况：

1234
1243
1324
1342
1423
1432
2134
2143
2341
2314
2413
2431
4123
4132
....

（好吧，确实情况比较多，总共有 $24$ 种情况

你把每种情况都计算一下分数，最后输出最多的那个即可

代码略，上述做法可以通过测试点 $1\sim 3$ ，期望得分 $12pts$ 。

算法二

其实你可以考虑枚举全排列，然后看哪种情况下分数最高。应该有大佬知道怎么枚举全排列。

当然，这个我们课上没讲，这个是你之后学dfs的时候会学到，如果你不会的话就拿不到这个分数了。

参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int s[100005],p[100005];
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=1;i<=n;i++) p[i]=i;
	int ans=0;
	do{
		int _ans=0;
		for(int i=1;i<=n;i++){
			if(p[i]>i) _ans-=s[i];
			if(p[i]<i) _ans+=s[i]; 
		}
		ans=max(ans,_ans);
	}while(next_permutation(p+1,p+n+1));
	cout<<ans;
	return 0;
}

以上代码可以通过测试点 $1\sim 5$ ，期望得分 $20pts$

算法三

对于特殊性质 $AC$ ，我们很自然的想法就是如果每个格子都赚，即每个格子的分数都获得，那么答案应该是最优的。这也就意味着你必须给每个格子都填上一个比他编号小的数字。但你发现，格子 $1$ 永远是赚不了的。或者说，格子 $1$ 要么亏，要么不赚不亏。如果格子 $1$ 不赚不亏，那么就该轮到格子 $2$ 要么亏要么不赚不亏了。

然后你继续考虑，如果格子 $1$ 亏了，后面的格子一定可以都赚。比如 $n=5$ 时，我们可以这么填：

1	2	3	4	5
5	1	2	3	4

这样一定是最优答案。

所以我们只需要让一个格子亏，剩余格子都赚。参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int s[100005],p[100005];
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i];
	int ans=s[1]*(n-1)-s[1];
	cout<<ans;
	return 0;
}

以上代码可以通过测试点 $6\sim 7$ 和 $14\sim 15$ 。期望得分 $16pts$ 。

算法四

对于特殊性质 $C$ ，我们的想法和算法三差不多，只不过这次可能直接让格子 $1$ 亏掉其他格子都赚，这样不一定能获得最高分数。因为可能你格子 $1$ 亏掉的分数太多了，得不偿失。

但是格子 $1$ 还是要么亏，要么不赚不亏。既然亏了可能不好，那我们就考虑格子 $1$ 不赚不亏。

格子 $1$ 不赚不亏之后，我们实际上就可以忽略到格子 $1$ ，仅看格子 $2$ 到 $n$ 了，格子 $2$ 也会有一模一样的顾虑，有可能格子 $2$ 亏掉的分也太多了，即使格子 $3$ 到格子 $n$ 都是赚的，也得不偿失。所以你也要考虑是不是格子 $2$ 也要不赚不亏。

然后就这么一直考虑下去....

参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int s[100005];
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i];
	int ans=0;
	for(int i=1;i<=n;i++){
		//枚举第i个格子开始亏了，第i个格子之前的格子都是不赚不亏的，第i个格子之后的格子都是赚的
		int _ans=0;
		_ans-=s[i];
		for(int j=i+1;j<=n;j++){
			_ans+=s[j];
		} 
		ans=max(ans,_ans);
	}
	cout<<ans;
	return 0;
}

以上代码时间复杂度为 $O(n^2)$ 可以通过测试点 $6\sim 9$ ，期望得分 $16pts$ 。

实际上，你内层循环是没必要的，可以使用类似于前缀和的优化，但在这题中，准确来说是后缀和。

我们令 $suf[i]$ 为从 $s[n]$ 一直加到 $s[i]$ （注意是倒着加的），直接把内层循环替换为 $_ans+=suf[i+1]$ 即可。

参考代码：(注意从现在开始就要开long long了)

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
#define int long long
using namespace std;
int s[100005],suf[100005];
signed main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i];
	int ans=0;
	for(int i=n;i>=1;i--){
		suf[i]=suf[i+1]+s[i];
	}
	for(int i=1;i<=n;i++){
		int _ans=0;
		_ans-=s[i];
		_ans+=suf[i+1];
		ans=max(ans,_ans);
	}
	cout<<ans;
	return 0;
}

以上代码时间复杂度为 $O(n)$ ，可以通过测试点 $6\sim 9$ 和 $14\sim 15$ 和 $18\sim 19$ 。期望得分 $32pts$ 。

算法五

考虑特殊性质 $B$ ，如果 $s$ 序列是从一个正数开始单调递增，那么所有格子的分数都为正数，这个我们已经考虑过了。如果从一个负数开始单调递增，我们又分成两种情况

序列都是负数
序列先负后正

都是负数的话好说，我们希望所有的格子都要是亏的，但发现最后一个格子要么不亏不赚，要么赚，后面的讨论就和算法四是一样的了。这回我们可能需要个 $pre[i]$ 表示从 $s[1]$ 正着加到 $s[i]$ 。

参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
#define int long long
using namespace std;
int s[100005],pre[100005];
signed main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i];
	int flag=0;//判断是不是所有数字都为负数
	for(int i=1;i<=n;i++){
		if(s[i]>0){
			flag=1;
			break;
		}
	} 
	if(flag==0){
		int ans=0;
		for(int i=1;i<n;i++){
			pre[i]=pre[i-1]+s[i];
		}
		for(int i=1;i<=n;i++){
			int _ans=s[i];
			_ans-=pre[i-1];
			ans=max(ans,_ans);
		}
		cout<<ans;
	}else{
		
	}
	return 0;
}

如果序列是先负后正呢？我宣称，这种情况下你一定可以找到一个填数方案，让分数为负的格子亏了，让分数为正的格子赚了，不信的话给你举个例子。

假如 $s$ 序列长这样：-5 -3 2 4 5，我们这样填：

1	2	3	4	5
4	5	1	2	3

再来，加入 $s$ 序列为 -5 -4 -3 -2 1 3，我们这样填

1	2	3	4	5	6
3	4	5	6	1	2

你只需要先从第一个正数那里填 $1$ 即可。

这种情况下，直接把所有数的绝对值相加即可。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
#define int long long
using namespace std;
int s[100005],pre[100005];
signed main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i];
	int flag=0;//判断是不是所有数字都为负数
	for(int i=1;i<=n;i++){
		if(s[i]>0){
			flag=1;
			break;
		}
	} 
	if(flag==0){
		int ans=0;
		for(int i=1;i<n;i++){
			pre[i]=pre[i-1]+s[i];
		}
		for(int i=1;i<=n;i++){
			int _ans=s[i];
			_ans-=pre[i-1];
			ans=max(ans,_ans);
		}
		cout<<ans;
	}else{
		int ans=0;
		for(int i=1;i<=n;i++) ans+=abs(s[i]);
		cout<<ans;
	}
	return 0;
}

以上代码可通过测试点 $10\sim 11$ 和 $16\sim 17$ 期望得分 $16pts$ 。

算法六（正解）

实际上，并不需要分数序列单调递增，只需要分数序列是先负后正，就有算法五最后的神奇性质。

然后这个性质还能推广，也不一定是整个序列先负后正，序列的一部分是先负后正，这一部分就可以获得最大分数。

我们只考虑序列正负，对于任意 $s$ 序列，都是这种分布：全正——负正交替——全负。不信？举几个例子，比如 1 2 -3 -4 5 -6 7 -8 9 10 -11 -12 那么就可以分成这样 (1 2)(-3 -4 5)(-6 7)(-8 9 10)(-11 -12)。

中间三个部分直接绝对值相加即可，就是首尾的全正和全负序列有点棘手。

不过事实上，全正和全负的情况，我们在算法四和算法五已经说过怎么解决了。

参考代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define int long long
using namespace std;
int s[100005],n,ans,pre[100005],suf[100005];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i];
	int l=0,r=n+1;
	while(s[l+1]>0 && l+1<=n) l++; //找到前面全正部分的最后位置
	while(s[r-1]<0 && r-1>=1) r--; //找到后面全负部分的最靠前位置
	for(int i=l+1;i<=r-1;i++) ans+=abs(s[i]); //中间直接绝对值相加
	for(int i=l;i>=1;i--) pre[i]=pre[i+1]+s[i]; //预处理前缀和后缀
	for(int i=r;i<=n;i++) suf[i]=suf[i-1]-s[i];
	int _ans;
	_ans=0;
	for(int i=1;i<=l;i++) _ans=max(_ans,-s[i]+pre[i+1]); //类似算法四
	ans+=_ans;
	_ans=0;
	for(int i=n;i>=r;i--) _ans=max(_ans,s[i]+suf[i-1]);  //类似算法五
	ans+=_ans;
	cout<<ans;
	return 0;
}

其他验题人代码

范铭轩

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000005;
int a[N],ans,tot,cnt;

signed main(){
	int n;
	cin>>n;
	for(int i = 1;i <= n;++ i) cin>>a[i];
	int l = 1,r = n;
	bool flag = false;
	while(l <= n && a[l] > 0){
		tot += a[l];
		flag = true;
		l ++;
	}
	if(flag) tot -= (a[1] << 1);
	for(int i = 1;i < l - 1;++ i){
		cnt = max(cnt,tot);
		tot += a[i];
		tot -= (a[i + 1] << 1);
	}
	ans += cnt;
	tot = 0,cnt = 0;
	flag = false;
	while(r >= 1 && a[r] < 0){
		tot -= a[r];
		flag = true;
		r --;
	}
	if(flag) tot += (a[n] << 1);
	for(int i = n;i > r + 1;-- i){
		cnt = max(cnt,tot);
		tot -= a[i];
		tot += (a[i - 1] << 1);
	}
	ans += cnt;
	for(int i = l;i <= r;++ i) ans += abs(a[i]);
	cout<<ans;
	return 0;
}

路浩祥

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define int long long
using namespace std;
int t,n,r,c[200005];
int a,b;//标记分3段 
signed main()
{
	memset(c,0,sizeof(c));
	n=r=0;
	cin>>n;
//		for (int i=1;i<=n;i++)cin>>r;
	for (int i=1;i<=n;i++) scanf("%lld",&c[i]);
	//分段 
	a=0,b=n+1;
	while(c[a+1]>0) a++;
	while(c[b-1]<0) b--;
	//第一段（排名高且想进步）
	int ans1=0,sum=0;
	for (int i=a;i>1;i--)
	{
		sum+=abs(c[i]);
		ans1=max(ans1,sum-abs(c[i-1]));
	}
	//第二段（有进有退） 
	int ans2=0;
	for (int i=a+1;i<=b-1;i++)  ans2+=abs(c[i]);
	//第三段（排名低且想退步）
	int ans3=0;sum=0;
	for (int i=b;i<n;i++)
	{
		sum+=abs(c[i]);
		ans3=max(ans3,sum-abs(c[i+1]));
	}
	printf("%lld\n",ans1+ans2+ans3); 
	return 0;
}

最后更新于：2025-01-24 08:47:29

Caiwen

本文作者

一只蒟蒻，爱好编程和算法

CZSC 2024 第一次 题解

概览

T1 点

概览

算法一

算法二

算法三

算法四（正解）

T2 修剪树枝

概览

算法一

算法二

算法三

算法四

算法五（正解）

T3 取模

概览

算法一

算法二

算法三

算法四

算法五（正解）

T4 填数游戏

概览

算法一

算法二

算法三

算法四

算法五

算法六（正解）

CZSC 2024 第一次题解