Codeforces Round 962 (Div. 3)

A题 Legs

题目：

农夫约翰的农场又迎来了美好的一天。

农夫约翰到达他的农场后，他数了数 n条 腿。众所周知，只有鸡和牛生活在农场，鸡有 2 条腿，而牛有 4 条腿 。

假设农场主约翰计算了所有动物的腿，他的农场上能有的最小动物数量是多少？

输入

第一行包含单个整数 t ( 1 <= t <= 10^3 )ー测试用例的数量。

每个测试用例包含一个整数 n ( 2 <= n <= 2 * 10^3 ，n 是偶数 )。

输出

对于每个测试用例，输出一个整数，即农场主约翰可以在他的农场上养的动物的最小数量。

解题思路：

很简单的问题，类似于小学的鸡兔同笼问题，主要是贪心的思想，数量优先给牛，剩下的给鸡。

AC代码：

#include<iostream>
using namespace std;
int n,t,sum;
int main(){
	cin>>t;
	while(t--){
		sum=0;
		cin>>n;
		sum+=n/4;
		sum+=n%4/2;
		cout<<sum<<endl;
	}
	return 0;
}

B题 Scale

题目：

Tina有一个包含 n 行和 n 列的正方形网格。网格中的每个单元格都是 0 或 1 。Tina希望将网格减少因子 k （k 是 n 的除数）。

为此，Tina将网格拆分为 k * k 个不重叠的单元块，以便每个单元恰好属于一个块。然后，Tina用与块中的单元的值相等的单个单元来替换每个单元块。

保证同一块中的每个单元都具有相同的值。例如，以下演示显示了以因子 3 减少的网格。

输入

第一行包含 t（ 1 <= t <= 100 ）–测试用例的数量。

每个测试用例的第一行包含两个整数 n 和 k （ 1 <= n <= 1000 ， 1 <= k <= n ，

k 是 n的除数）—网格的行数和列数，以及Tina想要减少网格的因子。以下 n 行中的每一行都包含描述网格单元格的 n 字符。

每个字符为 0 或 1 。 k 块保证每个 k 具有相同的值。保证所有测试用例的 n 之和不超过 1000 。

输出

对于每个测试用例，在新行上输出减少因子 k 的网格。

解题思路：

emmm，好像没看懂

看了样例，理解了一会，才知道所缩小的因子就是行和列每隔k就输出一次即可。

AC代码：

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int t,n,k;
int main(){
    cin>>t;
    while(t--){
    	string s;
    	vector<string>v;
        cin>>n>>k;
        for(int i=0;i<n;i++){
            cin>>s;
            v.push_back(s);
        }
        for(int i=0;i<n;i+=k){
            for(int j=0;j<n;j+=k){
                cout<<v[i][j];
            }
            cout<<endl;
        }
    }
    return 0;
}

C题 Sort

题目：

给出两个字符串 a 和 b ，长度为 n 。然后，您(被迫)回答q 个问题。对于每个查询，您都会得到一个由 l 和 r 限定的范围。在一个操作中，您可以选择整数 i ( l <= i <= r )

并设置 ai = x ，其中 x 是所需的任何字符。输出必须执行的最小操作数，以便 sorted(a[l..r]) = sorted(b[l..r]) 。您对一个查询执行的操作不会影响其他查询。

对于任意字符串 c ，sorted(c[l..r]) 表示由按字典顺序排序的字符 cl+1, ... , cr 组成的子字符串。

输入

第一行包含 t ( 1 <= t <= 1000 )–测试用例的数量。

每个测试用例的第一行包含两个整数 n 和 q ( 1 <= n, q <= 2 * 10^5 )

–两个字符串的长度和查询次数。

下一行包含长度为 n 的 a 。

保证 a 只包含小写拉丁字母。

下一行包含长度为 n 的 b 。

它保证 b 只包含小写拉丁字母。以下 q 行包含两个整数 l 和 r ( 1 <= l <= r <= n )–查询的范围。

保证所有测试用例的 n 和 q 之和不超过 2 * 10^5 。

输出

对于每个查询，输出一个整数，即需要在新行中执行的最小操作数。

注意

对于第一个查询， sorted(a[1..5]) =ABCDE和 sorted(b[1..5]) = ABCDE，因此不需要任何操作。

对于第二个查询，您需要设置 a1 = E。然后，sorted(a[1..4]) = sorted(b[1..4]) = BCDE。

解题思路：

题目看上去很简单，C++给了5s,题意主要就是给两个字符串，每次给一个左右区间，分别在这两个字符串上截取出来，按照sort排序规则，看两个字符串相差哪几个，可以进行操作修改其值，最终达到sort相同的目的。刚开始的思路是模拟，按照题目给的l,r截取出来，sort一下看看是不是相同，不一样的就进行一次操作。但是忘记了重复这一个问题，所以就要考虑另一种做法，看了大佬的题解，思路是开26个桶，就是26个字母的出现次数，再加上一个维度表示在下标为i之前的出现次数，当要查询区间为l、r时,直接在遍历这26个桶，看一下每个字母在字符串a跟字符串b的出现次数，做一下差值，就是它们不相同的个数，由于只需要改一个字符串即可，最后答案/2，主要的思想跟前缀和差不多。

AC代码：

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int N = 200005;

void solve(){
	int n, q;
	cin >> n >> q;
	string s1, s2;
	cin >> s1 >> s2;
	s1 = " " + s1;
	s2 = " " + s2;

	vector<vector<int>>  a(n+1, vector<int>(100));//字符串a前i个字符，字母j出现的次数
	vector<vector<int>>  b(n+1, vector<int>(100));//字符串b前i个字符，字母j出现的次数

	for(int i = 1; i <= n; i++){
		a[i] = a[i-1];//加上前面统计的次数
		b[i] = b[i-1];
		a[i][s1[i]-'a']++;//更新当前字符的个数
		b[i][s2[i]-'a']++;
	}
	while(q--){
		int l,r;
		cin >> l >> r;
		int ans = 0;
		for(int i = 0; i < 26; i++){
			ans+=abs(a[r][i] - a[l-1][i] - (b[r][i] - b[l-1][i]));//两个字符串的字符差值
		}
		cout << ans / 2 << '\n';
	}
}

int main(){
	int T = 1;  cin >> T;
	
	while(T--)
	{
		solve();	
	}
	return 0;
}

D题 Fun

题目：

数数很有趣！ —SATYAM343

给定两个整数 n 和 x ，求正整数的三元组（ a,b,c ）的个数，使得 ab + ac + bc <= n 和 a + b + c <= x 。

请注意，（例如（ 1, 1, 2 ）和（ 1, 2, 1 ）被视为不同）和 a 、 b 、 c 必须严格大于 0 。

输入

第一行包含单个整数 t （ 1 <= t <= 10^4 ）—测试用例的数量。

每个测试用例包含两个整数 n 和 x （ 1 <= n,x <= 10^6 ）。

保证所有测试用例的 n 之和不超过 10^6 ，并且所有测试用例的 x 之和不超过 10^6 。

输出

输出单个整数-满足 ab + ac + bc <= n 和 a + b + c <= x 的正整数的三元组（ a,b,c ）的数目。

注意

在第一个测试用例中，三元组是（ 1, 1, 1 ）、（ 1, 1, 2 ）、（ 1, 2, 1 ）和（ 2, 1, 1 ）。

在第二个测试用例中，三元组是（ 1, 1, 1 ）、（ 1, 1, 2 ）、（ 1, 1, 3 ），（ 1, 2, 1) ，（ 1, 2, 2 ），（ 1, 3, 1 ）和（ 2, 1, 1 ）以及（ 2, 1, 2 ）和（ 3, 1, 1 ）。

解题思路：

题目说的很简单，主要就是两个式子，分别是ab + ac + bc <= n 和 a + b + c <= x，如果直接求，肯定会超时，有式子肯定就是数学问题了，考虑化简，ab+ac+bc<=n ab+(a+b)c<=n c<=(n-ab)/(a+b) 第二个式子a+b+c<=x c<=x-(a+b) 第一个式子我们将（a+b)与ab看成一个整体，如果a跟b知道了，那么（a+b)跟 ab就知道了，那么c也就知道了，第一个式子在最坏的情况下a*b=1，a+b=2,那么c<=（n-1）/2，c就有(n-1)/2种情况，再不寄一点a=2,b=1,则c<=(n-2)/3，也可以a=1,b=2因为（2，1，c)跟（1，2，c）是不一样的，我们这样可以去枚举a跟b，类似第二个式子最坏的情况下a=1,b=1,c<=x-2,c就有x-2种情况满足条件。再不寄的情况下a=2,b=1，c<=x-3。综上a,b,c要同时满足这两个式子，那么哪一个式子的限制条件大，我们就取谁。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin >> t;
    while(t--){
        int n, x;
        cin >> n >> x;
        long long ans = 0;
        for(long long a = 1; a <= n && a <= x; a++){
            for(long long b = 1; a*b <= n && a+b <= x; b++){
                ans += min(max(x-a-b,0LL),max(n-a*b,0LL)/(a+b));//涉及到减法，要与零取最大值，防止为负数
            }
        }
        cout << ans << "\n";
    }
    return 0;
}