注意事项

请注意！：

  1. 题解仅代表个人看法，不代表最优解

  2. 每道题都会附上ac代码，但是仅作参考，要看懂后再了解代码。补题不要直接抄代码！禁止自欺欺人！

  3. 只提供题解，不提供题目信息
  4. ac代码为C++版本，如果遇到不懂的语法请自行百度
  5. ac代码中的循环经常用到了for(int i = 1;i<=n;i++) ，这种在for的括号中int i的操作只有大于等于C++11标准才可以使用，编译错误时请检查自己编译使用的标准。

A.数位分解

对于一个数x，

  1. 使用 x % 10 (% 是取余数) ，就可以得到他的最后一位
  2. 使用 x /= 10 (除以十并取整数)，就可以舍掉他的最后一位

使用while(x) 来进行循环

1
2
3
4
5
6
7
8
9
10
11
#include<iostream>
using namespace std;
int main(){
	int x;
	cin>>x;
	while(x){
		cout<< x % 10 <<" ";
		x = x / 10;
	}
	return 0;
}

B.大小写字母互换

对于一个小写字符ch, 使用代码ch = ch - ('a' - 'A');能够使他转换为大写字母， 相反对于大写字母，则需要使用代码ch = ch + ('a' - 'A');

本题读入的数据中存在空格，因此需要使用 gets()函数来读入。

使用string.h 库文件中的 strlen() 函数来获取字符串的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<string.h>
using namespace std;
int main(){
	char str[85];
	gets(str);
	for(int i = 0 ;i< strlen(str);i++){
		if('a'<=str[i] && str[i]<='z') 
			str[i] -= ('a'-'A');
		else if('A'<=str[i] && str[i]<='Z') 
			str[i] += ('a'-'A');
	}
	cout<<str;
	return 0;
}

C.八进制转十进制

给出的数据规模很小，直接根据进制公式计算即可。

下面通过一个例子来介绍计算公式

$13579_{(8)} = 1 8^4 + 38^3 + 58^2 + 78^1 + 9*8^0$

可以发现式子是可以用循环表示的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
using namespace std;
int main(){
	int x;
	cin>>x;
	int p = 1;//p = 8 ^ i
	int ans = 0;
	for(int i = 0;x > 0;i++){
		ans += (x % 10) * p;//x % 10 数位分离
		p = p * 8;//令p一直保持为 8 ^ i
		x = x / 10;//数位分离的操作
	}
	cout<<ans;
	return 0;
}

D. 西西务者

使用数组存下所有的数据，然后排序后选择其中的中间部分计算平均值即可，数据的总和会超过int的范围，注意使用longlong来存储中间区域的裁判的分数和。

数组占用的空间大，建议放在全局区。（也就是main函数的上面）

输入数据多，建议使用scanf读入数据（最好不要用cin，否则可能会读入超时）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e6;
int dat[MAXN*5 + 5];
int main(){
	int n;
	cin>>n;
	for(int i =1;i<=n * 5;i++){
		scanf("%d",&dat[i]);
	}
	sort(dat+1,dat+n*5+1);//C++中的排序函数，需要包含algorithm库
	long long sum = 0;//一定要初始化
	for(int i = n + 1;i<=n * 4;i++){
		sum += dat[i];
	}
	printf("%.1lf",(double)sum / (n * 3)); //转换为double再计算才会有小数,%.1lf为保留一位小数输出double类型数据
	return 0;
}

E.睡大觉

本题使用的算法知识： 1.前缀和 2.二分查找 。 如果没有学过上述内容，建议前往(OI Wiki )，或者CSDN 等平台先行了解。

设每次开始睡觉（或结束睡觉）为一个时间点，使用前缀和数组qz记录从刚开始到某个时间点一共睡了多长时间，因此有以下方程：

$qz[i] = qz[i-1]$(i为偶数)

$qz[i] = qz[i-1] + a[i] - a[i-1]$ (i为奇数)

请根据题意“第i个数为奇数表示睡醒，为偶数表示睡着”认真理解上述公式。

数据处理完毕后，对于每组询问 l , r。 我们可以先计算出从刚开始到 $l$ 一共睡了多长时间（设为$timeL$），以及从刚开始到$r$ 一共用了多长时间（设为$timeR$） ，而从l到r的睡眠时间即为$timeR - timeL$。

下面探讨如何找到从刚开始到时间$x$ 的总睡眠时间：
使用int ind = lower_bound(a+1,a+1+n,x) - a - 1; 来找到从x往左数的第一个时间点的下标ind。（$low_bound()$能够从a数组中二分找到第一个大于x的索引，减去首地址a即为下标，再减去a变为第一个小于x的下标）

  1. 如果ind为奇数，那么代表$[ind,x]$ 这段时间是醒着的。那么直接返回 $qz[ind]$即可。

  2. 如果ind为偶数，那么代表$[ind,x]$ 这段时间是睡着的，那么返回 $qz[ind] + (x - ind)$

需要注意的是：

  1. 答案可能会超出int的范围，建议使用long long。

  2. 使用cin cout可能会超时，建议使用scanf和printf

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<iostream>
using namespace std;
const long long MAXN = 2e5+5;
long long a[MAXN];//原始数据
long long qz[MAXN];//前缀数组
long long n; 
long long getnum(long long x){//获取从开始到x的睡眠时间
	long long ind = (lower_bound(a+1,a+1+n,x) - a) ;
	ind--;
	if(ind % 2 == 0LL){
		return x - a[ind] + qz[ind];
	}else return qz[ind];
}
signed main(){
	scanf("%lld",&n);
	for(long long i = 1;i<=n;i++){
		scanf("%lld",&a[i]);
		if(i % 2 == 0) qz[i] = qz[i - 1];
		else qz[i] =qz[i-1] + a[i] - a[i-1];
	}
	long long q;
	scanf("%lld",&q);
	while(q--){
		long long l ,r;
		scanf("%lld %lld",&l,&r);
		printf("%lld\n",getnum(r) - getnum(l));
	}
	return 0;
}

F.ZZUacm 欢迎你

直接输出即可

1
2
3
4
5
6
#include<iostream>
using namespace std;
int main(){
	cout<<"hello zzuacm";
	return 0;
}

G. 区间和的和

注意使用int会溢出！！！

本题两种思路：

方案一、使用前缀和数组。

$qz[i]$ 表示从第$1$个数到第$i$个数的总和。计算出前缀和数组后 $q[i+k-1] - qz[i-1]$就能表示 $[i,i+k-1]$ 的总和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
const int MAXN = 1e6+5;
long long qz[MAXN];
int main(){
	int n,k;
	cin>>n>>k;
	long long num;
	qz[0] = 0;
	for(int i = 1;i<=n;i++){
		scanf("%lld",&qz[i]);
		qz[i] += qz[i-1];
	}
	long long ans = 0;//一定要初始化
	for(int i = 1;i+k-1<=n;i++){
		ans += qz[i + k -1] - qz[i-1];
	}
	cout<<ans;
	return 0;
}

方案二、使用滑动窗口

如果用$a[i]$ 表示第i个数，用 $sum(L,R)$ ( $R = L +k-1$) 表示从第L个数到第R个数的总和。

那么可以发现 对于任意的L和R。都有$sum(L+1,R+1) = sum(L,R) - a[L] + a[R]$ ，因此可以使用一个变量sum来记录当前k个数的总和，然后窗口每向右移动一下，就使用上述公式来更新sum的值。然后让ans每次都加上sum即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
const int MAXN = 1e6+5;
long long a[MAXN];
int main(){
	int n,k;
	cin>>n>>k;
	a[0] = 0;
	for(int i = 1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	long long sum = 0;
	for(int i = 1;i<k;i++){
		sum += a[i];
	}
	long long ans = 0;
	for(int i = k;i<=n;i++){//i遍历右端点
		sum = sum + a[i] - a[i-k];
		ans += sum;
	}
	cout<<ans;
	return 0;
}

H. Sum of Maximum Weights

压轴题！！

本题考察的算法知识： 并查集及其优化策略，树

题目要求每两点之间的 “最短路径的最大权值 ”的和 ， 我们可以对边按照权值排序，这样每次处理都会是比之前都要大的权值。

每次处理一条边，考虑这个边的起点$u$和终点$v$。他们一定在不同的组（并查集中的组），设为$U$组和$V$组, 并且这两组分别有$sizeU$和$sizeV$个成员。那么U组中任意一个成员，到V组中的任意一个成员，他路径的最大权值都是e（e为当前边的权值）。这样我们就可以让$ans = ans + size[u]size[v]e$ 来计算这两组成员之间互相连通产生的 最大权值的和。 然后就可以将这两组合并。

依次对每条边考虑上述情况，就可以得到总共的最大权值的和。

注意：本题使用int记录答案会导致数据溢出。

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
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N = 2e6+5;
const int M = N*2;
int a[N],b[N];
int fa[N];//并查集的father数组
int size[N];//并查集中记录该组数据的数量
int getf(int u){//并查集中的寻找祖先函数get_father
	return u == fa[u] ? u : fa[u] = getf(fa[u]);
}
struct edge{
	int u,v,e;//从u到v有一条权值为e的边
} e[N];//存储边的关系
bool cmp(edge x,edge y){//edge结构体的比较函数
	return x.e < y.e;
}
signed main(){
	int n;
	cin>>n;
	for(int i = 1;i<n;i++){
		scanf("%lld %lld %lld",&e[i].u,&e[i].v,&e[i].e);
	}
	for(int i = 1;i<=n;i++){//并查集的初始化
		fa[i] = i;
		size[i] = 1;
	}
	sort(e+1,e+n,cmp);
	int ans = 0;
	for(int i = 1;i<n;i++){
		edge t = e[i];
		int u = t.u, v = t.v, e = t.e;
		u = getf(u),v = getf(v);//找到祖先
		if(size[u] < size[v]){//将并查集中的较小树作为较大树的子树
			swap(u,v);
		}
		ans += size[u] * size[v] * e;//计算ans
		//合并
		fa[u] = v;
		size[v] += size[u];
	}
	cout<<ans<<endl;
}

I. 区间偶数和

设$a[i]$表示第$i$个数，循环判断，如果$l\le i \le r $ 并且$a[i]$ 为偶数，令答案加上$a[i]$即可。

需要使用long long来避免int造成的溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;
int main(){
	int n,l,r;
	cin>>n>>l>>r;
	long long num;
	long long ans  = 0;//一定要初始化
	for(int i = 1;i<=n;i++){
		scanf("%lld",&num);
		if(l <= i && i <= r && num % 2 == 0){
			ans += num;
		}
	}
	cout<<ans;
	return 0;
}

J. 矩阵

注意：由于01之间没有空格，因此无法使用读入数字的方法读取数据，应该使用读入字符的方法读取

设$mp[i][j]$表示第$i$行第$j$列数字。可以发现，对于原矩阵,$mp[i][j]$在经过旋转90°，旋转180°，旋转270° 之后，他们会分别到$mp[j][n+1-i],mp[n+1-i][n+1-j],mp[n+1-j][i]$ 这些位置。

我们说$mp[i][j],mp[j][n+1-i],mp[n+1-i][n+1-j],mp[n+1-j][i]$，这四个位置是相关联的。如果让矩阵在旋转的过程中原封不动，那么就应该令每组”相关联的“ 的四个字符变为同一个数字。考虑要尽可能少地改变数字，我们改变出现次数少的数字。（即如果出现了1个1和3个0，那么就把1变成0）

不重不漏地遍历所有的”关联组“ 即可。（也可以遍历所有的数字，这样的话每个关联组都会被重复调用四次，因此最后需要令$ans/=4 $）

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
#include<iostream>
using namespace std;
char mp[105][105];
int main(){
	int n;
	cin>>n;
	int ans =0;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=n;j++){
			cin>>mp[i][j];
		}
	}
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=n;j++){
			int cnt = 0;
			if(mp[i][j] == '0') cnt++;
			if(mp[j][n+1-i] == '0') cnt++;
			if(mp[n+1-i][n+1-j] == '0') cnt++;
			if(mp[n+1-j][i] == '0') cnt++;
			ans += min(cnt,4-cnt);
		}
	}
	cout<<ans/4;
	return 0;
}

K. 模拟类问题

方案一、使用一个数组来存储邻居关系，$gx[i][j]$ 表示$i$和$j$有邻居关系，之后遍历所有的关系，数出其中没有邻居关系的即可。

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<iostream>
#include<set>
using namespace std;
int dat[55][55];
int gx[55][55];//gx[i][j]表示i和j之间有邻居关系
int main(){
    int n,m;
    cin>>n>>m;
    int l,r;
    for(int i = 1;i<=m;i++){
        for(int j = 1;j<=n;j++){
            scanf("%d",&dat[i][j]);
        }
    }
    for(int i = 1;i<=m;i++){
        for(int j = 1;j<n;j++){
            gx[dat[i][j]][dat[i][j+1]] = gx[dat[i][j+1]][dat[i][j]] = 1;
        }
    }
    int ans = 0;
    for(int i = 1;i<=n;i++){
        for(int j = i+1;j<=n;j++){
            if(gx[i][j] == 0)
                ans ++;
        }
    }
    cout<<ans;
    return 0;
}

方案二、数据量很小，把数据存储起来后，暴力枚举每一对关系即可。

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
#include<iostream>
using namespace std;
int dat[55][55];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i = 1;i<=m;i++){
		for(int j = 1;j<=n;j++){
			scanf("%d",&dat[i][j]);
		}
	}
	int ans = 0;//记录答案
	for(int i = 1;i<n;i++){
		for(int j = i+1;j<=n;j++){//枚举每一对人
			int flag = 0;//flag记录是否找到了邻居关系
			for(int p = 1;p<=m;p++){
				for(int q = 1;q<n;q++){
					//如果第p行第q这对邻居恰好是i和j
					if((dat[p][q] == i && dat[p][q+1] == j) || (dat[p][q] == j && dat[p][q+1] == i))
						flag = 1;
				}
			}
			if(flag == 0) ans++;//如果没有找到邻居关系
		}
	}
	cout<<ans;
	return 0;
}

L. 找最大值

只考虑奇数，如果比当前的最大值大，就更新最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;
int main(){
	int mx = -1000000;//使最大值起初为无穷小
	int n;
	cin>>n;
	int num;
	for(int i = 1;i<=n;i++){
		cin>>num;
		if(num % 2 == 1 && mx < num){
			mx = num;
		} 
	}
	cout<<mx;
	return 0;
}