＃648 (Div. 2)(A. Matrix Game、B. Trouble Sort、C. Rotation Matching)

Codeforces Round #648 (Div. 2)(A、B、C)

A. Matrix Game

The question ： There is one n That's ok m Columns of the matrix , Yes 0 and 1 Two states , Ashish and Vivek One step at a time will 0 Turn into 1,Ashish Go ahead , Every step needs to ensure that the current row and column are 0, Ask who wins in the end .
Answer key ： Just figure out how many behaviors there are 0 And how many are listed as 0, Finally, find the minimum value , Is the total number of steps you can take . In an odd number of Ashish win , conversely Vivek win .

#include<iostream>
#include<algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int t,n,m,sum;
int a[60][60];
int b[60];
int main()
{
    
	scanf("%d",&t);
	while(t--){
    
		scanf("%d%d",&n,&m);
		sum=0;
		int k=0,q=0;
		memset(b,0,sizeof b);
		for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		cin>>a[i][j];
			for(int i=0;i<n;i++){
    
				sum=0;
		 for(int j=0;j<m;j++){
    
		 	if(a[i][j]==0)  sum++;
		 	else if(a[i][j]==1&&b[j]==0) q++,b[j]=1;
		 }
		if(sum==m)   k++;		
			}
			k=min((m-q),k);
	if(k%2==0) cout<<"Vivek\n";
	else cout<<"Ashish\n";
	}
	return 0;
 } 

B. Trouble Sort

Poor English is really a hard injury , When I did it, I thought a,b The array must correspond to and b Arrays must be different .
In fact, the above problem is as long as b Array has 0 and 1 Just go , So just think about 3 All cases are 1 All for 0 Yes 1 Yes 0.

#include <iostream>
using namespace std;
typedef long long ll;
int k,q,w,t,n;
int a[505],b[505];
int main()
{
    
	cin>>t;
	while(t--){
    
		cin>>n;
		for(int i=0;i<n;i++)
		     cin>>a[i];
		     w=0;
			 q=0;
		for(int i=0;i<n;i++)
		  {
    
		      cin>>b[i];
		      if(b[i]==0)  q++;
		      else w++;
	}
	int t=1;
	if(q==n||q==0){
    
		for(int i=1;i<n;i++)
		if(a[i]<a[i-1]){
    
			t=0;
			break;
		}
		if(t) cout<<"Yes\n";
		else cout<<"No\n";
	}
	else cout<<"Yes\n";
	}
	return 0;
 }

C. Rotation Matching

outputstandard output
After the mysterious disappearance of Ashish, his two favourite disciples Ishika and Hriday, were each left with one half of a secret message.These messages can each be represented by a permutation of sizen.Let’s call themaandb.

Note that a permutation ofnelements is a sequence of numbersa1,a2,…,an, in which every number from1tonappears exactly once.

The message can be decoded by an arrangement of sequenceaandb, such that the number of matching pairs of elements between them is maximum.A pair of elementsaiandbjis said to match if:

i=j, that is, they are at the same index.
ai=bj
His two disciples are allowed to perform the following operation any number of times:

choose a numberkand cyclically shift one of the permutations to the left or rightktimes.
A single cyclic shift to the left on any permutationcis an operation that setsc1:=c2,c2:=c3,…,cn:=c1simultaneously.Likewise, a single cyclic shift to the right on any permutationcis an operation that setsc1:=cn,c2:=c1,…,cn:=cn−1simultaneously.

Help Ishika and Hriday find the maximum number of pairs of elements that match after performing the operation any (possibly zero) number of times.

Input
The first line of the input contains a single integern (1≤n≤2⋅105)— the size of the arrays.

The second line containsnintegersa1, a2, …, an (1≤ai≤n)— the elements of the first permutation.

The third line containsnintegersb1, b2, …, bn (1≤bi≤n)— the elements of the second permutation.

Output
Print the maximum number of matching pairs of elements after performing the above operations some (possibly zero) times.
Answer key : take b[] Each number in is related to a[] The positions of the same numbers in the correspond one by one , Calculate how many steps of displacement are needed to reach the corresponding , And record the corresponding number of steps at this time （ use ans[] To record the corresponding number at this time ）,** Pay attention to moving left y Bit and shift right （n-y） The bit result is the same ！！！** Last max Take the maximum value .

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <string>
#include <cmath>
using namespace std;
int a[200010],ans[200005];
int main()
{
    
	int n,x;
	scanf("%d",&n);
	for(int i = 0; i < n; i++)
	{
    
		scanf("%d",&x);
		a[x]=i;// Record a The subscript position of each number in the array 
	}
	int t=0;
	for(int i=1;i<=n;i++)
	{
    
		scanf("%d",&x);
		x=(a[x]-i+n)%n;// stay a[] And b[] Under the same conditions ,
		        // Calculate how many steps you need to move .
		ans[x]++;// The current number of steps corresponds to the number plus 1
		t=max(ans[x],t);// Taking the maximum 
	}
	cout<<t<<endl;
	return 0;
}