Codeworks round 649 (Div. 2) ABC problem solution

A. XXXXX

Topic link ：A. XXXXX
The question ： Find the array a[ ] The largest subarray of , And this subarray can only Delete a few from the beginning ( It could be zero or all ) Element or Delete a few from the end ( It could be zero or all ) Elements ., Make the subarray unusable x to be divisible by .
Answer key **： We can know if a number can be x to be divisible by , Then subtract one that cannot be x This number cannot be divided by x Divided by .**
There are three situations ：1.a[ ] Array sum cannot be x to be divisible by , The answer for n;
2.a[ ] The sum of arrays cannot be x Divide by whole and there is something in the array that cannot be x Divisible number , The answer for n Subtract the smallest element that includes this number , namely n-min(i,n-1+1)(i Subscript for this number );
3. The answer for 0.

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;
int n,x;
int a[N];
long long int sum;
int main()
{
    
	int t;
	scanf("%d",&t);
	while(t--){
    
	scanf("%d%d",&n,&x);
	int f=0,b=100000,i,sum=0;
	for(i=1;i<=n;i++) {
    
		scanf("%d",&a[i]);
		sum+=a[i];// Finding the sum of arrays 
		if(a[i]%x!=0){
    
				b=min(i,b);
				// Record the minimum distance from the beginning of such a number 
				b=min(b,n-i+1);
				// Record the minimum distance from the end of such a number 
				f=1;
		}
	
	}
	if(sum%x!=0) cout<<n<<endl;
	// Case one 
	else if(f) cout<<n-b<<endl;
	// The second case 
	else cout<<-1<<endl;
	// The third case 
	}
return 0;
 } 

B. Most socially-distanced subsequence

Topic link ：B. Most socially-distanced subsequence
The question ： Find the array p[ ] The subsequence , This subsequence can delete some ( May be zero or all ) Elements .|s1−s2|+|s2−s3|+…+|sk−1−sk| And as large as possible .p At least the length 2.
In all these subsequences , Choose a length ,k, The smaller the better. .
Answer key ： It's not hard to see In a monotonic array , The difference between the beginning and the end of the array is equal to the sum of the differences of the elements in this array .
So this problem can be regarded as finding the beginning and end of each monotonic interval in the whole array .
You can use it here Difference to judge monotony . Greater than 0 Single increase , Less than 0 Is a single minus .
Code ;

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;
int n,x;
int a[N],b[N],c[N];
int check(int x){
    
	if(x>0) return 1;
	else return 0;
}// Use the difference array to judge the monotonicity of elements 
int main()
{
    
    int t;
    scanf("%d",&t);
    while(t--){
    
    	x=0;
    	scanf("%d",&n);
    	scanf("%d",&a[0]);
       b[0]=a[0]; 
    	for(int i=1;i<n;i++) {
    
    		scanf("%d",&a[i]);
    		b[i]=a[i]-a[i-1];
    		// Differential array calculation 
		}
		int t=1;
		c[x++]=a[0];
		for(int i=2;i<n;i++){
    
			if(check(b[i])==check(b[i-1])) continue;
			// Judge whether it is a monotonous beginning or end 
			else t++,c[x++]=a[i-1];
			// If so, save it 
		}
		 t++,c[x++]=a[n-1];
		// Add the end of the monotone interval 
		cout<<t<<endl;
		for(int i=0;i<x;i++) cout<<c[i]<<" ";
		// Output the answer 
		cout<<endl;
	}
return 0;
 } 

C. Ehab and Prefix MEXs

Answer key ： hold a The number appearing in is recorded with another array subscript , Then fill in the numbers that have never appeared and b Array , because a It must be an ordered array , So we have to make a special judgment , If a Array a[i]>a[i-1], Need to put a[i-1] Put it in b[i] It's about , The purpose is to guarantee b[i] Array MEX Will not be a[i-1]！！！

#include <bits/stdc++.h>
using namespace std;
int a[100005],b[100005];
bool ex[100005];
int main()
{
    
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	memset(b,-1,sizeof(b));
	for (int i=1;i<=n;i++)
	{
    
		if (a[i]!=a[i-1])
		{
    
			b[i]=a[i-1];
			ex[b[i]]=1;
		}
	}
	ex[a[n]]=1;
	int m=0;
	for (int i=1;i<=n;i++)
	{
    
		while (ex[m])
		m++;
		if (b[i]==-1)
		{
    
			b[i]=m;
			ex[m]=1;
		}
		printf("%d ",b[i]);
	}
}