Codeforces Round #793 (Div. 2)

CF系列题解

Codeforces Round #793 （Div. 2）

• 题目
• • A. Palindromic Indices
  • • 原题链接
    • 题意
  • 题解
  • • 思路
    • 代码
  • B. AND Sorting
  • • 原题链接
    • 题意
  • 题解
  • • 思路
    • 代码
  • C. LIS or Reverse LIS?
  • • 原题链接
    • 题意
  • 题解
  • • 思路
    • 代码
  • D. Circular Spanning Tree
  • • 原题链接
    • 题意
  • 题解
  • • 思路
    • 代码

---

题目 A. Palindromic Indices 原题链接

A. Palindromic Indices

题意

给定一个回文字符串，问删掉多少个字符后其仍是回文字符串。

题解 思路

直接删除中间相同的连续一段即可。

代码

#include 

using namespace std;

using i64 = long long;

void solve()
{
    int n;
    cin >> n;

    string s;
    cin >> s;

    int mid = n / 2;
    int i = mid, j = mid;
    int ans = 0;
    while (i >= 0 && s[i] == s[mid]) {
        ans ++ ;
        i -- ;
    }
    while (j < n && s[j] == s[mid]) {
        ans ++ ;
        j ++ ;
    }

    cout << ans - 1 << "n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T -- ) {
        solve();
    }

    return 0;
}

B. AND Sorting 原题链接

B. AND Sorting

题意

对于一个乱序排列 [ 0 , n − 1 ] [0,n-1] [0,n−1]，每次可以交换两个满足 a i & a j = X a_i & a_j=X ai​&aj​=X 的数，问要使得原排列有序的 X X X 的最小值。

题解 思路

其实本质上就是吧下标和数值不同的数交换，我们可以将这些数 与 一下，即为答案。

证明：首先对于所有 与 起来的数，其结果一定小于等于其最小值且与上任意的目标值都为这个数，即我们可以一直用该值与其他数交换直至序列有序。

代码

#include 

using namespace std;

using i64 = long long;

void solve()
{
    int n;
    cin >> n;

    vector a(n);
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    vector b;
    for (int i = 0; i < n; i ++ ) {
        if (a[i] != i) {
            b.push_back(i);
        }
    }

    int ans = b[0];
    for (int i = 1; i < b.size(); i ++ ) ans &= b[i];

    cout << ans << "n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T -- ) {
        solve();
    }

    return 0;
}

C. LIS or Reverse LIS? 原题链接

C. LIS or Reverse LIS?

题意

给定一个序列，问将其重新排列后的最长严格上升子序列和最长严格下降子序列中最小的那个尽可能大。

题解 思路

对于出现次数大于 2 2 2 的数，我们直接前一个后一个，其对答案的贡献为 1 1 1，其余的即为出现次数为 1 1 1 的数的个数我们记为 c n t cnt cnt，那么这些数的贡献为 c n t / 2 cnt/2 cnt/2（上取整）。

证明略。

代码

#include 

using namespace std;

using i64 = long long;

void solve()
{
    int n;
    cin >> n;

    vector a(n);
    map cnt;
    for (int i = 0; i < n; i ++ ) {
        cin >> a[i];
        cnt[a[i]] ++ ;
    }

    int res = 0;
    int ans = 0;
    for (auto [x, c] : cnt) {
        if (c >= 2) {
            ans ++ ;
        } else {
            res ++ ;
        }
    }
    cout << ans + (int)ceil(res / 2.0) << "n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T -- ) {
        solve();
    }

    return 0;
}

D. Circular Spanning Tree 原题链接

D. Circular Spanning Tree

题意

给定一个 01 字符串，构造一棵树，满足 s[i]='0' 的点度数为偶数，满足 s[i]='1' 的点度数为奇数，且该树 [ 1 , n ] [1,n] [1,n] 是一个环形，树边之间不能有交点。

即左边不合法而右边合法。

题解 思路

参考文章（严格鸽Orz）

从度数的角度出发，显然一棵树的度数和为偶数，且其中叶子节点的度数一定为奇数且为 1 1 1，因此能构成树，s 中 '1' 的个数首先需要大于 0 0 0（即存在叶子节点）且要为偶数。

构造思路：

1. 首先对与奇数的节点，我们可以把奇数节点变为叶子节点（其中奇数点为黄色）
   
2. 选择一个根然后把不同链结合起来
   

代码

#include 

using namespace std;

using i64 = long long;

void solve()
{
    int n;
    cin >> n;

    string s;
    cin >> s;

    int odd = 0, even = 0;
    for (int i = 0; i < n; i ++ ) {
        if (s[i] == '0') {
            even ++ ;
        } else {
            odd ++ ;
        }
    }

    if (odd == 0 || odd % 2) {
        cout << "NOn";
        return;
    }

    cout << "YESn";
    vector node; // 记录需要最后连接的点
    vector st(n); // 保证每个偶数点只在一条链中
    for (int i = 0; i < n; i ++ ) {
        if (s[i] == '1') {
            int j = (i + 1) % n;
            int k = i;
            while (!st[j] && s[j] == '0') {
                st[j] = true;
                cout << k + 1 << " " << j + 1 << "n";
                j = (j + 1) % n;
                k = (k + 1) % n;
            }
            node.push_back(((j - 1) % n + n) % n);
        }
    }
    for (int i = 1; i < node.size(); i ++ ) {
        cout << node[i] + 1 << " " << node[0] + 1 << "n";
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T -- ) {
        solve();
    }

    return 0;
}