《看了受制了》第三十四天，5道题，合计187道题

2023年10月4日

牛客国庆消消乐Day6 C Combination of Physics and Maths

题目大意

得到所有子矩阵的最大的可能。计算的方法是所有的和，再比上所选的值的最后一行的和。

题目理解

我们可以强行找到规律，比值大的加比值小的只会让比值减小，比值相同的加和比值不变。那么就可知道是单列的比值最大值为答案。并且答案可以是不完全的列，那么进行暴力枚举即可。

代码实现

ll n, m;
double a[N][N];
void solve()
{
    memset(a, 0, sizeof a);

	scanf("%lld%lld", &n, &m);

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			scanf("%lf", &a[i][j]);
    
    double res = 1;
	for(int i = 1; i <= m; i++)
	{
		double sum = 0;
		for(int j = 1; j <= n; j++)
		{
			sum += a[j][i];
			res = max(res, sum / a[j][i]);
		}
	}

	printf("%.9lf\n",res);
	return;
}

牛客七天消消乐Day6 Easy Construction

题目大意

找到一个1~n的排序序列，可以使得，存在i长度的连续子序列的和模n为k

题目理解

可以花时间推出如下规律：

• 当n为偶数时候，k必须要为n / 2
• 当n为奇数的时候,k必须要为0

利用上述规律，可以判断是否可以形成序列。
形成序列后：

• 奇数，我们就输出n后每次输出两个数，和为n的即可
• 偶数，我们就输出n和n / 2,然后每次输出两个数和为n

代码实现

const int N = 5010;
int a[N];

void solve()
{
	int n, k;
	cin >> n >> k;

	if(n % 2 == 1 && k == 0)
	{
		cout << n << " ";

		for(int i = 1, j = 1; i <= (n - 1) / 2; i++, j++)
			cout << j << " " << n - j << " ";
	}
	else if(n % 2 == 0 && k == n / 2)
	{
		cout << n << " " << n / 2 << " ";

		for(int i = 1, j = 1; i <= (n - 2) / 2; i++, j++)
			cout << j << " " << n - j << " ";
	}else cout << -1;

	return;
}

Div.3 Round881 A Sasha and Array Coloring

题目大意

可以给任意的数字图颜色，相同颜色的数字的权值是颜色最大值减去颜色最小值。问最后的权值最大是多少

题目理解

只图一个必然是0，那么我们只需要排个序，两两一组。然后加大的，减小的就行了。

代码实现

void solve()
{

	int n;
	cin >> n;
	vector<int> vec;
	for(int i = 1; i <= n; i++)
	{
		int b;
		cin >> b;
		vec.push_back(b);
	}

	sort(vec.begin(), vec.end());
	int res = 0;
	for(int i = 0, j = vec.size() - 1; i <= j; i++, j--)
		res += vec[j] - vec[i];

	cout << res << endl;
	return;
}

Div.3 Round881 B Long Long

题目大意

可以把长度为l到r的序列乘-1，问最后想让数列的和最大需要操作多少次。

题目理解

就是求，连续的非正数的段数，有多少段。然后所有数求和即可（负数要乘-1）

代码实现

void solve()
{
	ll sum = 0, res = 0;
	int n;
	cin >> n;
	vector<ll> vec;
	for(int i = 1; i <= n; i++)
	{
		int b;
		cin >> b;
		if(b <= 0) sum += -b;
		else sum += b;
		vec.push_back(b);
	}

	bool flag = false;
	for(int i = 0; i < (int)vec.size(); i++)
	{
		if(vec[i] < 0 && flag == false)
		{
			flag = true;
			res++;
		}else if(vec[i] > 0 && flag == true)
		{
			flag = false;
		}
	}
	cout << sum << " " << res << endl;
	return;
}

Div.3 Round881 C Sum in Binary Tree

题目大意

满二叉树，问你n的路径和。

题目理解

因为是满二叉树，那么就求和，每次 /=2即可。

代码实现

void solve()
{

	ll res = 0;
	ll n;
	cin >> n;
	while(n)
	{
		res += n;
		n /= 2;
	}

	cout << res << endl; 

	return;
}