Kalindrome Array
Title Link:
Kalindrome Array - Rock Valley | The New Ecology of Computer Science Education ()
headline translation
For a length of\(m\) sequences\(b\)We call\(b\) is "palindromic" if and only if for all\(i\in[1,m]\)All of them.\(b_i=b_{m-i+1}\). In particular, the empty sequence is also palindromic.
For a sequence, we call it 'cute' if and only if and when the following conditions are satisfied:
- existential number\(x\)such that a number of values in the deletion sequence are equal to\(x\) The sequence is palindromic after the elements of the (After deleting elements, the remaining elements are concatenated)
Note that you don't need to delete all values equal to the\(x\) elements, and, optionally, you can choose not to remove any elements.
Example:
- \([1,2,1]\) is lovely because you don't need to delete any of the numbers, its a palindrome in itself.
- \([3,1,2,3,1]\) Is lovely because you can choose\(x=3\)and then deletes all values equal to\(3\) element that turns it into a palindrome.
- \([1,2,3]\) Then it is not cute.
Now Blue gives a length of\(n\) sequences\(a\), she wants you to help her determine if its cute.
This question has multiple sets of data, and the number of data sets is\(t\)that will be given at the beginning of the input. For each set of data, if the sequence given\(a\) It's cute. Output, please.YESOtherwise outputNO。
Title Data Satisfaction:\(1 \leq t \leq 10^4\)，\(1 \leq n \leq 2\times10^5\)，\(1 \leq a_i \leq n\)，\(1 \leq \sum n \leq 2\times10^5\)。
Title Description
An array $ [b_1, b_2, \ldots, b_m] $ is a palindrome, if $ b_i = b_{m+1-i} $ for each $ i $ from $ 1 $ to $ m $ . Empty array is also a palindrome.
An array is called kalindrome, if the following condition holds:
- It's possible to select some integer $ x $ and delete some of the elements of the array equal to $ x $ , so that the remaining array (after gluing together the remaining parts) is a palindrome.
Note that you don't have to delete all elements equal to $ x $ , and you don't have to delete at least one element equal to $ x $ .
For example :
- $ [1, 2, 1] $ is kalindrome because you can simply not delete a single element.
- $ [3, 1, 2, 3, 1] $ is kalindrome because you can choose $ x = 3 $ and delete both elements equal to $ 3 $ , obtaining array $ [1, 2, 1] $ , which is a palindrome.
- $ [1, 2, 3] $ is not kalindrome.
You are given an array $ [a_1, a_2, \ldots, a_n] $ . Determine if $ a $ is kalindrome or not.
input format
The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the array.
The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — elements of the array.
It's guaranteed that the sum of $ n $ over all test cases won't exceed $ 2 \cdot 10^5 $ .
output format
For each test case, print YES if $ a $ is kalindrome and NO otherwise. You can print each letter in any case.
Sample #1
Sample Input #1
4
1
1
2
1 2
3
1 2 3
5
1 4 4 1 4
Sample Output #1
YES
YES
NO
YES
draw attention to sth.
In the first test case, array $ [1] $ is already a palindrome, so it's a kalindrome as well.
In the second test case, we can choose $ x = 2 $ , delete the second element, and obtain array $ [1] $ , which is a palindrome.
In the third test case, it's impossible to obtain a palindrome.
In the fourth test case, you can choose $ x = 4 $ and delete the fifth element, obtaining $ [1, 4, 4, 1] $ . You also can choose $ x = 1 $ , delete the first and the fourth elements, and obtain $ [4, 4, 4] $ .
Thoughts Explained:
We start with a special case: when the original sequence is a palindrome, there is no need to delete any numbers, it is "cute" in itself.
At this point, we just need to write to determine if a sequence of strings is a palindrome sequence.
We use the double pointer method to determine the palindrome sequence of arrays
bool ishuiwen(int n, int b[])
{
//If i and n-i+1 are different, it must not be a huiwen sequence.
for (int i = 1; i <= n; i++) {
if (b[i] ! = b[n - i + 1]) return false;
}
return true; }
}
We then come to the universal case, also using the double-pointer approach, starting at both ends of the array and checking for different elements at symmetric locations, the
According to the meaning of the question, when we meet different elements, we can arbitrarily delete one of the elements to the array [3,1,2,3,1], for example, we delete a number, we if we delete all the values equal to this number after the value of the number, if it is an iambic pentameter, then delete some of the value of this number must be an iambic pentameter. For example, here the 3 and 1 position is different, if we delete some 3 after the sequence is an iambic sequence, then we delete all the 3 after the sequence must be an iambic sequence, and vice versa, i.e.: if we delete all the 3 after the sequence is not an iambic sequence, then we delete some number of 3 to get the sequence is certainly not an iambic sequence, this because of the nature of the iambic sequence This is because of the nature of the palindromic sequence, a sequence if it is a palindrome, then the corresponding position of the elements must be an even number of times, we talk about the number of times the number of deletions, the number of times the number of occurrences of 0 times, is also an even number of times.
After we know this, we just need to traverse the array with double pointers, and when we come across elements that are not in the same position, we try to delete all the elements that are equal to the value of this element. For example, here we have 3 and 1 in symmetric positions with different values, we just need to try to delete all the 3s and check if it is a palindrome, or delete all the 1s and check if it is a palindrome, and the string is "cute" if only one of the cases satisfies the palindrome. As long as one of them satisfies the palindrome, the string is "cute".
Here we need to use a new array to store the new array after the deleted elements, defined as tmp.
Other details to note are described in detail in the comments.
Code:
#include<iostream>
#include<cstring>
using namespace std.
// It's a good habit to preprocess the maximum value of n
const int N = 2e5 + 10;
int a[N], tmp[N].
// Check if a sequence of numbers is a huiwen sequence
bool ishuiwen(int n, int b[])
{
for (int i = 1; i <= n; i++) {
if (b[i] ! = b[n - i + 1]) return false;
}
return true; }
}
// Check if the new sequence obtained by deleting the number x from the a array is a palindrome sequence.
bool check(int x, int n)
{
// as the subscript of the new array tmp
int index = 0; for (int i = 1; i
for (int i = 1; i <= n; i++) {
//If the element in a is not equal to x, I copy the value in a to tmp
//Here I'm using ++index, because it's customary to start with 1 in acm mode, so I'm rounding off the 0's and not using it
if (a[i] ! = x) tmp[++index] = a[i];
}
// check if the new sequence is a huiwen sequence
return ishuiwen(index, tmp);
}
void solve() {
int n; cin >> n;
// It's a good habit to empty the a array every time you enter a test sample
memset(a, 0, sizeof(a)); memset(tmp, 0, sizeof(tmp)); } void solve()
for (int i = 1; i <= n; i++) cin >> a[i];
//If the original array is a huiwen sequence, output YES directly, and go to the next round of the loop
if (ishuiwen(n, a)) {
cout << "YES" << endl;
return;
}
// double pointer to check which positions of the symmetric sequence have different values
int l = 1, r = n, x = 1, y = r;
while (l <= r) {
//If you check for dissimilar values, just record them and exit the lookup
if (a[l] ! = a[r]) {
x = a[l], y = a[r].
break.
}
l++; r--; }
}
// just delete the value at one position to turn it into a palindrome sequence, then the a array is "cute"
if (check(x, n) || check(y, n)) {
cout << "YES" << endl.
}
else cout << "NO" << endl;
endl; return;
}
int main()
{
int t; cin >> t; while (t--) solve(); cin >> endl; return; }
while (t--) solve(); }
t; cin >> t; while (t--) solve(); return 0;
}