Codeforces Round #793 (Div. 2)

A. Palindromic Indices

题目大意：给定若干个回文字符串，判断每个字符串可以删除哪些位置上字符，使得最终的字符串还是回文字符

思路：从字符串的中间开始向外扩展，统计总共有多少个相同的字符，分长度为奇偶进行讨论

• AC 代码
  • 注意 这里取的mid值是字符串向下取整 ```cpp

    include

    using namespace std;

int main(){

int t;cin >> t;
while(t -- ){
    int n; cin >> n;
    string s; cin >> s;
    int mid = (s.size() - 1) / 2;
    if(s.size() & 1){
        int cnt = 1;
        while(mid - cnt >= 0 && s[mid - cnt] == s[mid + cnt] && s[mid - cnt] == s[mid]) cnt ++;
        cout << (cnt - 1) * 2 + 1 << endl;
    }else{
        int cnt = 1;
        while(mid - cnt >= 0 && s[mid - cnt] == s[mid + 1 + cnt] && s[mid - cnt] == s[mid]) cnt ++;
        cout << (cnt - 1) * 2 + 2 << endl;
    }
}
return 0;

}

<a name="aBphG"></a>
##### B. AND Sorting
题目大意：给定一个保证无序的数组元素，每次交换两个数让数组变得有序，条件是：交换的两个数进行与运算的值  = X 时才可以交换， 即   a[i] & a[j] == X  时可以交换 a[i] 和 a[j] ，问 X 最大可以取多少？
思路：本题非常巧妙的发现，所有的数组元素只要是没在自己位置上的都一定会进行一次交换<br />这个数换回自己位置的方式，可以通过 &X 或者 & 自己位置的那个数<br />在另一个位置上的数换回自己位置的方式同理<br />综上， X需要同时 满足 &所有的数<br />所有 最终与出来的结果就是最终答案<br />AC 代码
```cpp
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int main(){
    int t;cin >> t;
    while(t -- ){
        int n;
        cin >> n;
        for(int i = 0;i < n;i ++ ) cin >> a[i];
        int ans = 0x7fffffff;
        for(int i  = 0;i < n;i ++ ) if(a[i] != i) ans &= a[i];
        cout << ans << endl;
    }
    return 0;
}

C. LIS or Reverse LIS?

题目大意： 给一个数组，取这个数组的任意组合方式。 答案输出 这个数组最长子序列和逆向的最长子序列取一个min值为最终结果

思路：容易想到 这个题的正向和逆向的最长子序列取最小的最大值的排列方式最好按照 两边均分的方式
如果有重复的数，那它的最大贡献为1，如果是单数，两个单数最多才能贡献1个结果，特殊的，总数为奇数的时候一个单点也可以作为一个贡献，那就是作为两个子序列的公共端点，可以证明两个公共子序列最多有一个重复点，统计这些点的个数即可

• AC 代码
  • 这个题要注意的点：unordered_map被卡掉了。。。map能过 ```cpp

    include

    include

    include

    include

    include

    using namespace std; const int N = 2e5 + 10;

int a[N]; int main(){

int t;cin >> t;
while(t -- ){
   int n; cin >> n;
   map<int, int> up;
   map<int, int> sum;
   for(int i = 0;i < n;i ++ ) cin >> a[i], sum[a[i]] ++;
   int sec = 0, sol = 0;
   for(int i = 0;i < n;i ++ ){
       if(!up[a[i]] && sum[a[i]] >= 2){
           sec ++; 
           up[a[i]] = 1;
       }
       else if(sum[a[i]] == 1) sol ++;
   }
   cout << sec + (sol + 1) / 2 << endl;
} 
return 0;

} ```