ACGO第15次欢乐赛题解

信奥-张兴晨

2023-12-25 15:34:02

发布于：浙江

203阅读

0回复

0点赞

ACGO欢乐赛15题目解析

T1 zxc的探险计划

题目大意

一条数轴上有两个整数，从原点出发每次移动一格，最少几次移动能到达两个整数。

题目思路

题目本身比较好理解，只需要注意不同的情况即可。

初步的想法是，如果a、b两个数字在原点同侧，只需要先到距离原点近的，再到远的即可；如果a、b两个数字在原点两侧则只需要依次到达两个数字即可。
进而我们想到，其实无论什么情况，都可以认为是先到两者距离原点近的，在经过两点之间的长度到达另一点。如此做法就可以避免判断，简化代码，直接计算即可。

代码演示

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	cin >> a >> b;
	cout << min(abs(a),abs(b)) + abs(a - b);
	return 0;
}

T2 子序列转换

题目大意

给定一个序列，通过对原始序列进行操作，判断最终能否变成一个不下降序列。

题目思路

首先要针对题目的核心操作进行分析，经过分析后发现，操作其实就是将选中序列 $[a_i,a_j]$ 倒置，因此我们可以想到冒泡排序或者选择排序，当 $k$ 大于等于 $2$ 时，经过操作一定是可以达到目标的，并且如果 $k$ 为1，序列本身成不下降序列也是满足要求的。

时间复杂度分析

该算法的时间复杂度主要就是单层循环，因此是 $O(n)$ 的复杂度。

代码演示

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

void solve()
{
	int n,k;
	cin >> n >> k ;
	int last = 0;
	int f = true;
	for(int i = 1 ; i <= n ; i ++ )
	{
		int x ; cin >> x;
		if(x < last) f = false;	
		last = x;
	} 
	if(f)
	{
		cout << "YES" << endl;
		return ;
	}
	k > 1 ? cout << "YES" << endl : cout << "NO" << endl;
}

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
	
	return 0;
}

T3 捞薯条

题目大意

$n$ 箱薯条，选择 $\frac{n}{k}$ 辆卡车来运输，每辆卡车运输连续的 $k$ 箱薯条，求在所有可行的情况下，卡车最大载重和最小载重的差值。

题目思路

根据题意，每辆卡车必须装满 $k$ 箱，且卡车数是 $\frac{n}{k}$ ，所以卡车数辆必须是 $n$ 的约数。所以枚举每一个 $i$ ，代表车辆装载连续的 $i$ 箱，然后求出当下情况载重的最大差值。
考虑到要多次计算连续的一段的和，所以可以使用前缀和进行优化，降低计算区间和的时间复杂度。

时间复杂度分析

该算法的时间复杂度主要集中在枚举每个 $n$ 的约数，然后统计序列中每段连续的 $n$ 个数，然后求极差。解决问题函数时间复杂度在有前缀和优化后几乎等于 $O(n)$ 。

代码演示

#include<bits/stdc++.h>
using namespace std;
long long arr[1000005];
void solve()
{
	int n;
	cin >> n;
	for(int i = 1 ; i <= n ; i ++ )cin >> arr[i];
	for(int i = 1 ; i <= n ; i ++)
	{
		arr[i] += arr[i-1];
	}
	long long answer = 0 ;
	for(int i = 1 ; i <= n ; i ++ )
	{
		if(n % i || n / i < 2)continue;
		long long mi = 1e18 + 7 ;
		long long mx = -1;
		for(int k = i ; k <= n ; k += i )
		{
			
			mx = max(mx,arr[k] - arr[k - i]);
			mi = min(mi,arr[k] - arr[k - i]);
		}
		answer = max(mx - mi , answer);
	}	
	cout << answer << endl;
}

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}

T4 或矩阵

题目大意

当前有一个矩阵 $M$ ，需要判定当前矩阵是否存在可以通过指定方式变换而来。变换的方式是 $M_{(i,j)}$ 是由 $a_i$ | $a_j$ 所得。

题目思路

根据题意，如果存在一个序列 $a$ 按照指定方式变换成目标矩阵，那我们可以分析得到如下操作:

$a_i$ 这个位置只会影响到 $M_{(i,j)}$ 和 $M_{(i,j)}$ ,所以我们将 $a_i$ 转换为二进制，并且假设每一位上都是 $1$ 。

因为 $a_i$ 上最多只能存在格子 $M_{(i,j)}$ 和格子 $M_{(i,j)}$ 二进制下存在的1，所以把两个格子的数值依次跟 $a_i$ 进行&运算即可。最后验证是否可以变成指定矩阵即可。

代码演示

#include<bits/stdc++.h>
using namespace std;
long long mi[100005];
long long mp[1005][1005];
void solve()
{
	int n;
	cin >> n ;
	for(int i = 1 ; i <= n ; i ++ ) mi[i] = (1<<30)-1; 
	for(int i = 1 ; i <= n ; i ++ )
	{
		for(int j = 1 ; j <= n ; j ++ )
		{
			cin >> mp[i][j];
			if(i!=j)
			{
				mi[i] &= mp[i][j];
				mi[j] &= mp[i][j];
			}
		}
	}
	if(n == 1)
	{
		cout << "YES" << endl << "1" << endl;
		return;
	}
	for(int i = 1 ; i <= n ; i ++ )
	{
		for(int j = 1 ; j <= n ; j ++ )
		{
			if(i == j )continue;
			if((mi[i] | mi[j]) != mp[i][j])
			{
				cout << "NO" << endl;
				return ;
			}
		}
	}
	cout << "YES" << endl;
	for(int i = 1 ; i <= n ; i ++ )
	{
		cout << mi[i] << " " ;
	}
	cout << endl;
}

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}

T5 音乐先辈Yuilice

题目大意

根据序列中的 $a_i$ 得到 $2^{a_i}$ 记为 $A$ ，再找对应的 $a_j$ ，得到 $2^{a_j}$ 记为 $B$ ，如果 $A^B$ = $B^A$ ,则认为找到了一组答案。

题目思路

读入每个样例的乐谱数据数量 $n$ 。
使用 map 存储每个地址 $A$ 的出现次数。
遍历 map，对于每个地址 $A$ ，如果其出现次数大于等于2，计算能够组成的按键地址数量并累加。这个循环遍历map中的每个元素（即每个不同的 $a_i$ 及其出现次数）。如果某个 $a_i$ 出现了至少两次（i.second >= 2），那么它可以与自己组合成完整的地址。组合数可以通过组合公式 C(n, 2) = n(n-1) / 2计算，即从这些重复的 $a_i$ 中选择两个不同的进行组合。
特殊情况。对于 $a_i$ = $1$ 和 $a_j$ = $2$ ，它们对应的地址 $A$ = $2^1$ = $2$ 和 $B$ = $2^2$ = $4$ 满足$ A^B$ = $B^A$ 。因此，如果输入中有 $1$ 和 $2$ ，那么它们之间可以相互配对。配对的总数是它们出现次数的乘积。
输出最终的按键地址数量。

算法核心思想是通过 map 存储地址 $A$ 的出现次数，然后遍历 map 计算满足条件的按键地址数量。最后输出结果。

时间复杂度分析

该算法的时间复杂度主要取决于遍历和统计 map 的操作，因此是 $O(n)$ 的复杂度。

代码演示

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

void solve()
{
	int n;
	cin >> n;
	map<long long,long long>mp;
	for(int i = 1 ; i <= n ; i ++ )
	{
		int x;
		cin >> x;
		mp[x]++;
	}
	long long count = 0 ;
	for(auto i : mp)
	{
		if(i.second >= 2)count += (i.second - 1) * i.second / 2;
	}
	if(mp[1] >= 1 && mp[2] >= 1)count += mp[1] * mp[2];
	cout << count << endl;
}

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}

T6接力长跑

题目大意

再给定序列中，找满足条件的连续数值最大为多少。

题目思路

其中连续的数字要想累加，需要满足前后两个数的奇偶性想法才可以累加。同时因为学生们能力值存在负数，所以还需要考虑是否放弃该同学即前面内容。在整个过程中全程判断是否存在更优的情况，如果存在及时记录即可。该问题属于线性动态规划经典问题变形。

我们可以设定学生状态为 $dp[i]$ ，从而列出以下状态转移方程

$a_i$ % 2 != $a_{i-1}$ % 2 : $dp[i] = max(a[i],dp[i-1] + a[i])$

时间复杂度分析

该算法的时间复杂度主要集中在遍历序列中每一项，因此是 $O(n)$ 的复杂度。

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
int f[N];
int main(){
	int T;
	cin >> T;
	while(T--){
		int n;
		cin >> n;
		long long sum = 0, max_N = -1e7;
		long long a, last = 0;
		cin >> a;
		last = a;
		sum = a;
		max_N = a; 
		for(int i = 2;i <= n;i++){
			cin >> a;
			if(abs(last) % 2 != abs(a) % 2 || i == 1){
				sum = max(sum+a , a);
			}
			else{
				sum = a;
			}
			last = a;
			max_N = max(sum,max_N);
		}
		cout << max_N << endl;
	}

	return 0;
}