Codeforces Round #956 (Div. 2) and ByteRace 2024（A~D题解）

这次比赛也是比较吃亏的，做题顺序出错了，先做的第三个，错在第三个数据点之后，才做的第二个（因为当时有个地方没检查出来）所以这次比赛还是一如既往地打拉了

那么就来发一下题解吧

A. Array Divisibility

题意：对于1<=k<=n，对于每个k其倍数下标之和一定为k的倍数

思路：直接从1赋值到n就行，也是水题一个

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n;
signed main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cout<<i<<" ";
		}
		cout<<"\n";
	}
	return 0;
} 

B. Corner Twist

题意：就是给你两个数组，问你两个数组能否按照题上所说的方法相互转换得到

思路：将整个大矩阵拆成2*2的小矩阵，然后每次只要让左上角那个和下面的变成一样就可以，然后我们最后原本只需要检查最后一列和最后一行是否相同就可以（ps：我写的是逐一比较，因为比较好写）（错了一次是因为比较的时候内层循环写成n了）

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,m;
char a[505][505];
char b[505][505];
signed main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>b[i][j];
            }
        }
        for(int i=1;i<=n-1;i++)
        {
            for(int j=1;j<=m-1;j++)
            {
                int cha = ((b[i][j]-'0')-(a[i][j]-'0')+3)%3;
                if(cha==1)
                {
                    a[i][j]=(a[i][j]+1)%3+'0';
                    a[i+1][j+1]=(a[i+1][j+1]+1)%3+'0';
                    a[i+1][j]=(a[i+1][j]+2)%3+'0';
                    a[i][j+1]=(a[i][j+1]+2)%3+'0';
                }
                else if(cha==2)
                {
                    a[i][j]=(a[i][j]+2)%3+'0';
                    a[i+1][j+1]=(a[i+1][j+1]+2)%3+'0';
                    a[i+1][j]=(a[i+1][j]+1)%3+'0';
                    a[i][j+1]=(a[i][j+1]+1)%3+'0';
                }
            }
        }
        int flag=1;
        for(int i=1;i<=n;i++)
        {
        	for(int j=1;j<=m;j++)
        	{
        		if(a[i][j]==b[i][j])
        		{
        			continue;
				}
				else
				flag=0;
			}
		}
		if(flag==0)
		{
			cout<<"NO"<<"\n";
		}
		else
		{
			cout<<"YES"<<"\n";
		}
    }
    return 0;
}

 C. Have Your Cake and Eat It Too

题意：就说有一个蛋糕 ，被分成了许多块，然后三个人对每部分的蛋糕都有一个自己的价值，但是所有块的价值总和是一定的，然后问你如何划分这个区间，才能满足每个区间都大于(tot+2)/3

思路：对六种情况分别贪心即可，先让两边的取到比sum大的位置，然后再看中间的是否比sum大，是的话就直接输出，如果都不满足，最后就只能输出-1了

#include<bits/stdc++.h>
using namespace std;
#define int long long 
signed main()
{
    int t;
    cin>>t;
 
    while(t--)
	{
        int n;
        cin >> n;
        int a[n+1], b[n+1], c[n+1];
        int sum = 0;
        for(int i = 1;i<=n;i++)
		{
            cin >> a[i];
            sum += a[i];
        }
        sum = (sum+2)/3;//题中说了上限除法 
        for(int i = 1;i<=n;i++)
		{
            cin >> b[i];
        }
        for(int i = 1;i<=n;i++)
		{
            cin >> c[i];
        }
        vector<int> p1(n+5), p2(n+5), p3(n+5);//正序前缀和 
        vector<int> s1(n+5), s2(n+5), s3(n+5);//倒序前缀和 
        for(int i = 1; i <= n; i++)
		{
            p1[i] = p1[i-1] + a[i];
            p2[i] = p2[i-1] + b[i];
            p3[i] = p3[i-1] + c[i];
        }
        for(int i = n; i >= 1; i--)
		{
            s1[i] = s1[i+1] + a[i];
            s2[i] = s2[i+1] + b[i];
            s3[i] = s3[i+1] + c[i];
        }
        //a b c 
        int i = 1, j = n;
        while(p1[i-1] < sum && i <= n)
		{
            i++;
        }
        while(s3[j+1] < sum && j >= 1)
		{
            j--;
        }
        if(i <= j && p2[j]-p2[i-1] >= sum)
		{
            cout << 1 << ' ' << i-1 << ' ' << i << ' ' << j << ' ' << j+1 << ' ' << n << endl;
            continue;
        }
        // a c b
        i = 1, j = n;
        while(p1[i-1] < sum && i <= n)
		{
            i++;
        }
        while(s2[j+1] < sum && j >= 1)
		{
            j--;
        }
        if(i <= j && p3[j]-p3[i-1] >= sum)
		{
            cout << 1 << ' ' << i-1 << ' ' << j+1 << ' ' << n << ' ' << i << ' ' << j << endl;
            continue;
        }
        // b  c a
        i = 1, j = n;
        while(p2[i-1] < sum && i <= n)
		{
            i++;
        }
        while(s1[j+1] < sum && j >= 1)
		{
            j--;
        }
        if(i <= j && p3[j]-p3[i-1] >= sum)
		{
            cout << j+1 << ' ' << n << ' ' << 1 << ' ' << i-1 << ' ' << i << ' ' << j << endl;
            continue;
        }
        // b a c
        i = 1, j = n;
        while(p2[i-1] < sum && i <= n)
		{
            i++;
        }
        while(s3[j+1] < sum && j >= 1)
		{
            j--;
        }
        if(i <= j && p1[j]-p1[i-1] >= sum)
		{
            cout << i << ' ' << j << ' ' << 1 << ' ' << i-1 << ' ' << j+1 << ' ' << n << endl;
            continue;
        }
        // c a b
        i = 1, j = n;
        while(p3[i-1] < sum && i <= n)
		{
            i++;
        }
        while(s2[j+1] < sum && j >= 1)
		{
            j--;
        }
        if(i <= j && p1[j]-p1[i-1] >= sum)
		{
            cout << i << ' ' << j << ' ' << j+1 << ' ' << n << ' ' << 1 << ' ' << i-1 << endl;
            continue;
        }
        //  c b a
        i = 1, j = n;
        while(p3[i-1] < sum && i <= n)
		{
            i++;
        }
        while(s1[j+1] < sum && j >= 1)
		{
            j--;
        }
        if(i <= j && p2[j]-p2[i-1] >= sum)
		{
            cout << j+1 << ' ' << n << ' ' << i << ' ' << j << ' ' << 1 << ' ' << i-1 << endl;
            continue;
        }
        cout << -1 << endl;
    }
 
    return 0;
}

D. Swap Dilemma

 

 

题意：就是说给你两个数组，然后每次再a数组选两个坐标，b数组选两个坐标，然后各自再各自的数组交换，然后问你最后两个数组能不能变成一样的

思路：这题我想到了两种做法

逆序对法

（1）逆序对的方法，众所周知，在大学有一门神奇的科目叫做线性代数，线性代数里面讲过一个东西叫做逆序对，只有逆序对的个数为同一奇偶性，才有可能相同，因为a，b数组每次都要变换一次，所以他们的奇偶性一定是都会在每一次变化，所以我们需要统计奇偶性，然后来判断，当然了，在之前还需要判断元素种类是否相同，如果个数不同一定为no

#include<bits/stdc++.h>
using namespace std;
#define int long long
int mergeSort(vector<int> &nums, int left, int right) 
{
    if (left >= right) {
        return 0;
    }
 
    int mid = left + (right - left) / 2;
    int count = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);
 
    vector<int> tmp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
 
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
            count += mid - i + 1; // 计算逆序数
        }
    }
 
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
 
    for (int p = 0; p < tmp.size(); ++p) {
        nums[left + p] = tmp[p];
    }
 
    return count;
}
 
int solve(vector<int> &nums) 
{
    if (nums.size() <= 1) {
        return 0;
    }
    return mergeSort(nums, 0, nums.size() - 1);
}
 
void solve()
{
	map<int,int> mp;
    int n;
    cin >> n;
    vector<int> a(n+2);
    vector<int> b(n+2);
    for (int i=1;i<=n;i++) 
	cin >> a[i];
    for (int i=1;i<=n;i++)
    {
    	cin >> b[i];
    	mp[b[i]]=i;
	}
    for(int i=1;i<=n;i++)
    {
    	if(mp.count(a[i])==0)
    	{
    		cout<<"NO\n";
    		return ;
		}
	}
    int ans1=solve(a),ans2=solve(b);
    if (ans1%2 ==ans2%2) 
	cout << "YES\n";
    else 
	cout << "NO\n";
}
signed main()
{
    int t;
    cin >> t;
    while (t--) 
	solve();
    return 0;
}

 交换次数法

（2）那么来讲另一种比较简单的方法，交换次数来判断，因为题目上所说每次两个数组都要交换，那么我们就只交换一个，然后统计变成另一个的次数为多少，是偶数就是yes是奇数就是no

当然了，在之前也是需要判断种类是否相同的

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[200005], b[200005];
map<int, int> mp;
void solve()
{
	mp.clear();
    int n;
    cin >> n;
    for (int i=1;i<=n;i++) 
	cin >> a[i];
    for (int i=1;i<=n;i++)
	{
        cin >> b[i];
        mp[b[i]]=i;
    }
    int ans = 0;
    for (int i=1;i<=n;i++)
	{
        if (b[i] == a[i]) 
		continue;
        if (mp.count(a[i]) == 0)
		{
            cout << "NO\n";
            return;
        }
        int p=mp[a[i]];
        swap(b[i],b[p]);
        mp[b[i]]=i;
        mp[b[p]]=p;
        ans+=1; 
    }
    if (ans%2 == 0) 
	cout << "YES\n";
    else 
	cout << "NO\n";
}
signed main()
{
    int t;
    cin >> t;
    while (t--) 
	solve();
    return 0;
}