Codeforces Round 962 (Div. 3) a~d题解_codeforces round 962 (div. 3)题解

Dashboard - Codeforces Round 962 (Div. 3) - Codeforces

A：

        题意：

        给出腿的数量，要求最少的动物数量

        思路：

        鸡2条腿，牛4条腿，那么我们尽可能的让牛的数量多，这样动物数量才会少

        代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void sl()
{
	int n;
	cin >> n;
	int sum = n/4; // 看最多有几头牛
	n %= 4;
	cout << sum + n/2 << endl;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int T;
	cin >> T;
	while(T--) sl();
	return 0;
}

B：

        题意：

        给出n，k，将n*n的矩阵缩小k倍

        代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int a[1005][1005];
void sl()
{
	int n,m;
	char ch;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			cin >> ch;
			a[i][j] = ch-'0';
		}
	}
	for (int i = 1; i <= n/m; ++i)
	{
		for (int j = 1; j <= n/m; ++j)
		{
			cout << a[(i-1)*m+1][(j-1)*m+1]; // 循环时写i+=k,j+=k也可以
		}
		cout << endl;
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int T;
	cin >> T;
	while(T--) sl();
	return 0;
}

C：

        题意：

        给出两个长度相同字符串，有q次询问，求区间[l，r]内需要修改多少个字母才能使得a,b的[l，r]区间相等，并且一个查询的操作不会影响到其他查询的操作

        思路：

        区间查询，并且不会影响后续的操作，可以看出，这是一道静态区间查询的题目，我们只需统计[l，r]内的字母的个数，找出有多少个不相等的即可，由此可以联想到前缀和，用26个字母的前缀和（类似桶的思想），跑一遍的话复杂度也就O(26n)

        代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int ga[30][200010],gb[30][200010];
void sl()
{
	map<char,int> mpa,mpb;
	int n,q;
	string a,b;
	cin >> n >> q;
	cin >> a >> b;
	for (int i = 1; i <= n; ++i)
	{
		for (char ch = 'a'; ch <= 'z'; ++ch) 
		{
			ga[ch-'a'+1][i] = ga[ch-'a'+1][i-1];
			gb[ch-'a'+1][i] = gb[ch-'a'+1][i-1];
		}
		ga[a[i-1]-'a'+1][i]++; //前缀和
		gb[b[i-1]-'a'+1][i]++;
	}
	for (int i = 1; i <= q; ++i)
	{
		int l,r;
		cin >> l >> r;
		int sum = 0;
		for (char ch = 'a'; ch <= 'z'; ++ch)
		{
			sum += abs(ga[ch-'a'+1][r] - ga[ch-'a'+1][l-1] - gb[ch-'a'+1][r] + gb[ch-'a'+1][l-1]);
		}
		cout << (sum + 1)/2 << endl; 
        // 两个字母不相同的话可以将这个字母改成另外那个字母，这样的次数是一次，尽可能少
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int T;
	cin >> T;
	while(T--) sl();
	return 0;
}

D：

        题意：

        给定两个整数 n 和 x ，条件是ab+ac+bc≤n 和 a+b+c≤x ，求正整数三胞胎 ( a,b,c ) 的个数。

        思路：

        分类讨论：（1）a=b=c的情况，可以暴力枚举一遍

        （2）a = b , a != c的情况，暴力枚举一遍，将结果乘3，由条件得a*a <= n，并且a*a + 2ac <= n，同时需要排除a=b=c的情况，加多了3次就要减去3次

        （3）a != b, b != c, a != c的情况，这样a，b暴力枚举，并且要求a<b<c，然后将结果乘6即可

a,b,c都暴力枚举的话会超时，最坏是1e18了，a,b暴力的话也会1e12,所以我们还需要剪枝一下，不满足的直接break

        代码：

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void sl()
{
	int n,x,c;
	cin >> n >> x;
	long long ans = min(int(sqrt(n/3)),int(x/3)); // 第一种情况
	for (int a = 1; a*a <= n; ++a) // 第二种情况
	{
		c = min((n - a*a) / (2*a) , x-2*a);
		if (a*a + 2*a*c > n) break;
		if (c > 0) ans += 3*c;
		if (c >= a) ans -= 3;
	}
	for (int a = 1; a <= x; ++a) // 第三种情况
	{
		for (int b = a+1; b <= x-a; ++b)
		{
			c = min((n - a*b) / (a+b) , x-a-b);
			if (c > b) ans += 6*(c-b);
			else break; // 小剪枝，不会超时
		}
	}
	cout << ans << endl;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int T;
	cin >> T;
	while(T--) sl();
	return 0;
}