CZSC 2024 第二次 题解

T1 序列

算法一

题目说啥你干啥，直接暴力就可以了。注意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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=19260817;
int n,m;
int k[30004],a[30004];
int ans;
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>k[i];
	for(int i=1;i<=n;i++) cin>>a[i];
	ans=0;
	for(int i=1;i<=n;i++){
		int all=1;
        // 直接开循环去算次方
		for(int j=1;j<=k[i];j++){
			all=(all*a[i])%mod;
		}
		ans=(ans+all)%mod;
	}
	cout<<ans<<endl;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
        // 修改
		a[x]=y;
		ans=0;
        // 再重新算一下
		for(int j=1;j<=n;j++){
			int all=1;
            for(int l=1;l<=k[j];l++){
                all=(all*a[j])%mod;
            }
            ans=(ans+all)%mod;
		}
		cout<<ans<<endl;
	}
	return 0;
}

时间复杂度 $O(mnk)$ ，可通过测试点 $1\sim 8$ 、 $11\sim 13$ 、 $16\sim20$ 期望得分 $64pts$

算法二（正解）

实际上，你每次修改之后都重新扫一下数组，计算一下答案，这个操作是多余的，换句话说，是有待优化的。

我们可以有个更快的解决方案：我们假设上次的答案为 $ans$ ，位置 $x$ 对应的权重为 $k$ ，位置 $x$ 原来是 $z$ ，现在要修改为 $y$ 。那么我们可以考虑这么操作：先把 $ans$ 减去 $z^k$ （即把原来的数字对答案的贡献减掉），然后再把 $ans$ 加上 $y^k$，然后得到的 $ans$ 就是新的答案了。

参考代码：

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
#define _ 30004
using namespace std;
const int mod=19260817;
int k[_],a[_],ans;
// 简单起见，你可以把求次方封装成一个函数
inline int f(int x,int w){
	int res=1;
	for(int i=1;i<=w;i++) res*=x,res%=mod;
	return res;
}
signed main(){
	ios::sync_with_stdio(false);
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>k[i];
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) ans+=f(a[i],k[i]),ans%=mod;
	cout<<ans<<endl;
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
        // 先减
        // 你注意减法取模，是(a-b+mod)%mod
		ans=(ans-f(a[x],k[x])+mod)%mod;
        // 别忘了也要把a数组更改一下
		a[x]=y;
        // 再加
		ans=(ans+f(a[x],k[x]))%mod;
		cout<<ans<<endl;
	}
	return 0;
}

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

更多

本题求一个数的 $n$ 次方部分是直接用循环做的。时间复杂度是 $O(n)$ 的。实际上，我们有一个叫做“快速幂”的算法，能做到 $O(logn)$ 的复杂度求解，非常快速。这个算法不难，感兴趣的同学可以去学一下。

T2 Caiwen家的饭

算法一

还是题目让你干什么你就干什么，直接暴力，开 long long 和注意取模都别忘了。

参考代码（李锦玉同学赛时代码）：

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;
int n;
int a[1000006];
const int mod=19260817;
signed main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			ans=(ans+a[i]*a[j]%mod)%mod;
		}
	}
	cout<<ans;
	return 0;
}

时间复杂度 $O(n^2)$，可以通过测试点 $1\sim15$，期望得分 $60pts$。

算法二（正解）

首先我们重新审视一下这个问题。去掉题目的包装，本题就是让求这 $n$ 个数两两相乘，最后再相加。

比如 $n=5$，就是

$$a_1a_2+a_1a_3+a_1a_4+a_1a_5+a_2a_3+a_2a_4+a_2a_5+a_3a_4+a_3a_5+a_4a_5$$

我们分一下组：

$$(a_1a_2+a_1a_3+a_1a_4+a_1a_5)+(a_2a_3+a_2a_4+a_2a_5)+(a_3a_4+a_3a_5)+(a_4a_5)$$

把每一组的公共项提出来：

$$a_1(a_2+a_3+a_4+a_5)+a_2(a_3+a_4+a_5)+a_3(a_4+a_5)+a_4(a_5)$$

你发现了吗，后面括号里的部分分别是从$a_2$ 加到 $a_5$，从$a_3$ 加到 $a_5$，从$a_4$ 加到 $a_5$...

如果我们直接去计算，需要开两层循环，时间复杂度必定是 $O(n^2)$ 的，但你考虑怎么优化。对于这种需要反复求一段连续区间内所有数之和的问题，我们的解决方案一定是三个字：前缀和！

不过这个题和你了解的前缀和可能稍微不一样，这个题可能要搞个后缀和。

我们先以 $O(n)$ 的时间复杂度求出后缀和 $suf[i]$ 表示从 $a_i$ 加到 $a_n$，然后再以 $O(n)$ 的时间复杂度去计算上式即可。

$$a_1\times suf_2+a_2\times suf_3+a_3\times suf_4+a_4\times suf_5$$

参考代码：

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
#define _ 1000006
using namespace std;
const int mod=19260817;
int suf[_],a[_],n;
signed main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=n;i>=1;i--) suf[i]=(suf[i+1]+a[i])%mod;
	int ans=0;
	for(int i=1;i<n;i++){
		ans+=a[i]*suf[i+1]%mod;
		ans%=mod;
	}
	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
#include<bits/stdc++.h>
#define int long long
#define mod  19260817
using namespace std;
int ai[1000006];
signed main(){
	ios::sync_with_stdio(false);
	int n,a=0,b=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>ai[i];
		ai[i]%=mod;
		a=(a+ai[i])%mod;
	}
	for(int i=1;i<=n;i++){
		b=(b+ai[i]*(a-ai[i]+mod)%mod)%mod;
	}
	cout<<b/2;
	return 0;
}

它的思路大概是，我们还是先假设 $n=5$，即先求

$$a_1a_2+a_1a_3+a_1a_4+a_1a_5+a_2a_1+a_2a_3+a_2a_4+a_2a_5+a_3a_1+a_3a_2+a_3a_4+a_3a_5+a_4a_1+a_4a_2+a_4a_3+a_4a_5$$

即求：

$$a_1(a_2+a_3+a_4+a_5)+a_2(a_1+a_3+a_4+a_5)+a_3(a_1+a_2+a_4+a_5)+a_4(a_1+a_2+a_3+a_5)$$

为了快速求解这个式子，它先求了这五个数之和 $a$。然后只需求：

$$a_1(a-a_1)+a_2(a-a_2)+a_3(a-a_3)+a_4(a-a_4)$$

不过它求完之后，和题目相比，相当于重复了，重复了一遍，所以最后需要再除2。

结合他的代码，好像问题不大，但这份代码是 WA 的，为什么呢？

实际上，如果一个取模的题遇到了除法，事情就变得复杂了，涉及到了一个叫做“逆元”的东西。这个我们之后会学，感兴趣的可以了解一下。上述代码最后不能直接除2，而是应该乘上在模数为19260817时2的逆元

T3 乒乓

这个题目有点迷惑性，首先你需要通过样例或者个人理解，看出来本题实际上是：

给你 $n$ 个数 $a_i$，和 $m$ 个询问，每个询问给出一个数 $b_i$ 问有多少个 $a_i$ 小于等于给定 $b_i$。

算法一

题目怎么说你就怎么做，直接暴力

参考代码（李锦玉同学赛时代码）：

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 n,m;
int a[100005],b[100005],ans[100005];
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(b[j]>=a[i]){
			ans[j]++;
		}
		}
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<" ";
	return 0;
}

时间复杂度 $O(nm)$，可以通过所有测试点 $1\sim 12$，期望得分 $48pts$。

算法二（正解）

我说第一步你要排序一下吧，况且题目的数据范围都有这个提示了

我们直接把输入的 $a_i$ 和 $b_i$ 分别排序一波。

然后现在请你在你的脑海中复现两个数列和两个指针，初始时两个指针都指向数列最左端：

每次下方的指针向前移动一下，表示处理一个询问，然后上方的指针也向右移动，确保上面指针指向的数永远不大于下方指针指向的数，直到不能再移动了。然后上面指针扫过的数的数量即为该询问的答案

以样例 2 为例

第一次：

询问 $b_i=1$ 的答案为 1

第二次：

询问 $b_i=1$ 的答案为 1

询问 $b_i=2$ 的答案为 3

询问 $b_i=2$ 的答案为 3

询问 $b_i=6$ 的答案为 6 同理，询问 $b_i=7$ 的答案为 6

然后我们就把答案都求出来了。我们发现，得益于这两个数列排好序了，是单调不降的 这两个指针只会往前走，不会往后走，程序跑一边，两个数列只会被扫一次，因此时间复杂度为 $O(n+m)$

但新的问题又出现了，因为我们也把序列 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
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
#define int long long
#define _ 100005
using namespace std;
int a[_];
struct O{
	int v; // 存储 bi
	int index;  // 存储这是第几个询问
	int ans;  // 存储该询问的答案
} b[_];
bool cmp1(O x,O y){  // 第一次排序
	return x.v<y.v;  // 按 bi 排序
} 
bool cmp2(O x,O y){  // 第二次排序
	return x.index<y.index;  // 按询问出现顺序排序
}
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].v,b[i].index=i;
	sort(a+1,a+n+1);
	sort(b+1,b+m+1,cmp1);
	int ans=0,p=1;
	for(int i=1;i<=m;i++){  // 下方的指针往前移动
		while(a[p]<=b[i].v && p<=n) ans++,p++;  // 上方的指针往前移动，同时统计扫过了多少个数
		b[i].ans=ans;  // 记录答案
	}
	sort(b+1,b+m+1,cmp2);  // 再把询问的顺序换元
	for(int i=1;i<=m;i++) cout<<b[i].ans<<' ';
	return 0;
}

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

更多

本题问题的核心在于，如何快速地找到有多少个数小于等于某个数。

实际上，我们还可以采用二分查找的方法来解决这个问题。二分算法也是我们后面要学习的，各位感兴趣可以了解一下。

T4 变量

解决

这个题其实没有考算法，只考了语法，看你如何使用c++语法去解决。没有什么思维难度，就看你语法掌握的如何。

我们先一步一步来考虑

问题1：如何输入

本题的输入格式有点特别的，一般人也就输入一个数字 $n$，然后开个循环，后面的东西就就不知道怎么读入了。

注意观察，等号两边都有空格隔开。而c++中的输入是自动按空格分割数据的，所以我们每行赋值操作可以直接用cin读入。你读入三次，第二次读入的是等号，可以直接丢弃，于是我们把等号两边的数据都读入进来了

问题2：如何存

等号左边是一个字符串，这个好说。等号右边既可能是数字也可能是字符串。那该怎么搞？我们知道。即使是数字我们也能把他看成一个字符串存起来。

问题3：我怎么知道是把变量赋值给变量还是把数字赋值给一个变量

因为变量名都是小写英文字母，所以我们只需要判断读入的等号右边的那个字符串的第一个字符是不是数字就好了。判断方法可以通过比较ascii码实现。

问题4：”变量“的数据怎么存储

首先你需要注意到 $k\le 3$ ，这意味着变量名的长度最大为 $3$。我们不妨先搞个这样的对应关系：字符 a 对应数字 1，字符 b 对应数字 2，...以此类推。然后我们开个三维数组来存放一个变量的数据就好了。

问题5：我们之前把数字也拿字符串存储起来了，那么怎么把字符串类型转int类型

你开个循环，枚举字符串的字符。然后计算即可。

到此为止，我们先把代码给出来：

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 bu[27][27][27];
int main(){
	ios::sync_with_stdio(false);
	int n;cin>>n;
	while(n--){
		char a[4],b[30],c;  // c是读入进来的等号，可以直接丢弃
		memset(a,0,sizeof(a));  // 局部变量默认值为随机数据，我们需要清空一下
		memset(b,0,sizeof(b));
		cin>>a>>c>>b;
		if(b[0]>='0'&&b[0]<='9'){  // 判断等号右边是变量还是数字
            // 下面这两行代码是为了把一个字符串转为int类型，不理解的话你可以手动模拟一下
			int res=0,len=strlen(b);
			for(int i=0;i<len;i++) res*=10,res+=b[i]-'0';
			bu[a[0]-'a'+1][max(0,a[1]-'a'+1)][max(0,a[2]-'a'+1)]=res;
		}
		else bu[a[0]-'a'+1][max(0,a[1]-'a'+1)][max(0,a[2]-'a'+1)]=bu[b[0]-'a'+1][max(0,b[1]-'a'+1)][max(0,b[2]-'a'+1)];
	}
	return 0;
}

问题6：max(0,a[1]-'a'+1) 是什么意思?

由于变量名不一定是三个字符，也可能是一个字符或者两个字符。我们把左侧变量名存到了 char数组 中且初始值数组中的所有数据都被我们清空，变成0了。当变量名为两个字符时，a[2] 就为0了。当变量名为一个字符时，a[1] 和 a[2] 就为0了。如果我们还 a[1]-'a'+1 的话显然就变负数了。所以我们考虑这么设计：我们把两个字符也看作三个字符，只不过第三个字符是空白，我们将空白对应数字 0。于是就有了 max(0,a[1]-'a'+1)

问题7：为什么使用char数组来存字符串而不是使用string类型？

如果我们用string类型的话，比如，如果这个字符串长度为1的话，我们直接 str[2] 的话可能就越界了。而使用char数组的话就可以规避这个问题

不过你也能使用string，你判断一下这个字符串长度，如果长度为 1 就 bu[a[0]-'a'+1][0][0]，如果长度为 2 就 bu[a[0]-'a'+1][a[1]-'a'+1][0]，长度为 3 同理。

问题8：为什么char数组的长度要开成这样？

a数组存变量，变量的长度最大为3，所以理论上 char a[3] 即可。但实际上你读入一个字符后，c++还会额外读入一个字符 '0'，这个字符是个空白字符，对应的ascii码为0，表示这个字符串结束了。当字符串长度为 3 时，直接cin读入到 char a[3] ，最后表示结束的那个特殊字符就存不下了。而 strlen 的函数获取字符串长度的原理就是扫一遍这个字符串，直到扫到了 '0' 这个表示结束的特殊字符，来计算字符串的长度。如果你最后那个特殊字符存不下，就导致 strlen函数出问题，就会导致整个程序出奇怪问题。所以我们需要把数组开大一些。

b数组即可能存变量名称，也可能存数字，你就尽可能开大一些就好了。

实际上，问题6中我们引入的那个”空白“你就可以理解为这个 '0'，表示空白字符

问题9：按字典序输出怎么搞？

我们上述的设计，把 a 对应 1，把 b 对应 2，....，以此类推，同时把”空白“对应数字0，比如

Unknown
1
2
3
4
5
a		对应 100
aa 		对应 110
ab		对应 120
abc		对应 123
bc		对应 230

我们发现，左边的字符是按字典序排序的，右边对应的数字也是从小到大排序的！

所以我们开三层循环，枚举每一位即可。枚举的顺序就是按字典序排序的。

问题10：我怎么知道哪些变量赋值了

由于题目中说了，给变量赋值的时候一定是把一个非负整数赋值，所以我们可以先考虑把上述代码中的 bu 数组初始时都设置为 -1，然后最后输出的时候判断一下，如果就为 -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
33
34
35
#include<bits/stdc++.h>
using namespace std;
int bu[27][27][27];
int main(){
	ios::sync_with_stdio(false);
	memset(bu,-1,sizeof(bu));  // 新加代码
	int n;cin>>n;
	while(n--){
		char a[4],b[30],c;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		cin>>a>>c>>b;
		if(b[0]>='0'&&b[0]<='9'){
			int res=0,len=strlen(b);
			for(int i=0;i<len;i++) res*=10,res+=b[i]-'0';
			bu[a[0]-'a'+1][max(0,a[1]-'a'+1)][max(0,a[2]-'a'+1)]=res;
		}
		else bu[a[0]-'a'+1][max(0,a[1]-'a'+1)][max(0,a[2]-'a'+1)]=bu[b[0]-'a'+1][max(0,b[1]-'a'+1)][max(0,b[2]-'a'+1)];
	}
    // 输出部分
	for(int i=0;i<27;i++){
		for(int j=0;j<27;j++){
			for(int k=0;k<27;k++){
				if(bu[i][j][k]!=-1){  // 判断变量是否赋值了
					string var="";  // 通过枚举的 i, j, k 计算对应的变量名称
					var+=(char)('a'+i-1);  // 变量名称的第一个字符
					if(j) var+=(char)('a'+j-1);  // j=0时说明是"空白"
					if(k) var+=(char)('a'+k-1);  // k=0时说明是"空白"
					cout<<var<<" = "<<bu[i][j][k]<<endl;
				}
			}
		}
	}
	return 0;
}

更多

我们知道，ascii码实际上告诉了我们一个字符其实对应了一个数字。而本题这一部分：

Unknown
1
2
3
4
5
a		对应 100
aa 		对应 110
ab		对应 120
abc		对应 123
bc		对应 230

貌似做到了把一个字符串对应了一个数字。

所以，我们是不是可以也让一个字符串对应一个数字呢？答案是可以的，这涉及到了哈希算法，我们之后也会学习，感兴趣的可以了解一下。

本题实际上还能有一个更简便的解法。使用map这个东西可以让我们很轻易地解决这个题。我们之后也会学习，感兴趣的可以了解一下。