?
Example
Input
3
3 3
1 2 3
3 4
1 2 3
2 2
0 6
Output
2
3
-1
题意:最长子序列使该序列的和不能整除X。
思路:
(1)如果整个长度为n的数列的和不能整除x?, 则直接输出该序列长度n。
(2)!(1)情况下,只要分别从最左边和最右边找到一个数不能整除x,如果左右都没有,直接输出-1,否则输出max(n-mini,maxi-1)--->自己定义数。
题解:
#include<bits/stdc++.h> using namespace std; int t , n , x , a , mini = 1e9, maxi = 0 , sum ; int main() { ?? ?cin >> t ; ?? ?while(t--) ?? ?{ ?? ??? ?maxi = 0 ; ?? ??? ?mini = 1e9; ?? ??? ?sum = 0 ; ?? ??? ?cin >> n >> x ; ?? ??? ?for(int i = 1 ; i <= n ; i ++ ) ?? ??? ?{ ?? ??? ??? ?cin >> a ; ?? ??? ??? ?sum += a ; ?? ??? ??? ?if(a%x!=0) //判断是否可以整除x ?? ??? ??? ?{ ?? ??? ??? ??? ?mini = min(i,mini);//左 ?? ??? ??? ??? ?maxi = max(i,maxi);//右 ?? ??? ??? ?}? ?? ? ? ? ? } ?? ??? ?if(sum%x!=0) cout << n << endl; ?? ??? ?else if(sum%x==0&&(mini<1||maxi>n)) cout << -1 << endl; ?? ??? ?else cout << max(n-mini,maxi-1) << endl;? ?? ?} ?? ?return 0; }
|