题目
题意：给出一长度为n的数组，问该数组的最长子数组的和不能被x整除。子数组是原数组数组从前或从后删除0个或全部个元素。
解法：首先判断是否所有元素被x整除，则如果是该子数组不存在输出-1，然后判断整个数组的和是否被x整除，如果不能答案为n。如果能从前或从后找到一个不能整除x的元素，删除遍历到的x所有元素即满足条件。
int n , m ;
int a[maxn] ;
void solve(){
int sum = 0 , flag = 1;
cin >> n >> m ;
rep(i , 1, n){
cin >> a[i];
sum += a[i];
if(a[i] % m != 0) flag = 0 ;
}
if(flag){
cout << -1 << endl;
return;
}
if(sum % m != 0){
cout << n << endl;
return ;
}
int ma = -1 , l , r ;
rep(i , 1 , n){
if(a[i] % m != 0){
l = i ;
break;
}
}
red(i , n , 1){
if(a[i] % m != 0){
r = i ;
break;
}
}
cout << max(n - l , r-1) << endl;
}
B题意：给出一个n个数的排列，找到一个子序列的值最大且长短最短，假设序列为s1,s2,s3,s4,该序列的值为|s1-s2|+|s2-s3|+|s3-s4|。
解法：分析可知找出该序列的所有拐点（波峰或波谷），这些拐点组成的子序列值最大且最大。
const int maxn = 1e5+9;
int a[maxn];
void solve(){
int n ;
cin >> n ;
rep(i , 1 , n){
cin >> a[i];
}
vector<int>v;
v.pb(a[1]);
rep(i , 2 , n-1){
if((a[i] > v.back() && a[i+1] < a[i]) || (a[i] < v.back() && a[i] < a[i+1])){//波峰或波谷
v.pb(a[i]);
}
}
v.pb(a[n]);
cout << size(v) << endl;
for(auto i : v){
cout << i << " " ;
}
cout << endl;
}
C题意：给出一个长为n的a数组，0<=ai<=i(该条件保证了b数组存在)，对于 i (1<=i<=n) 有：MEX({b1, b2, …, bi})=ai.求b数组.mex是不存在集合中的最小自然数。
解法：可以发现ai != ai-1 , 时有bi = ai-1，可以填充b数组一部分，剩下的部分升序填充。
const int maxn = 1e5+9;
int a[maxn];
int b[maxn];
int vis[maxn];
void solve(){
int n ;
cin >> n ;
ME(b , -1);
rep(i , 1 , n){
cin >> a[i];
if(i > 1 && a[i] != a[i-1]){
b[i] = a[i-1];
vis[b[i]] = 1;//将该数加入mex集合
}
}
vis[a[n]] = 1 ;//加入集合
int m = 0 ;
int i = 1 ;
while(i <= n){
if(b[i]==-1){
while(vis[m]){//找到b集合的mex
m++;
}
b[i] = m ;//填充
vis[m] = 1;//加入
}
i++;
}
rep(i , 1 , n){
cout << b[i] << " " ;
}
cout << endl;
}