Codeforces Round 793 (Div. 2)

https://codeforces.com/contest/1682

A. Palindromic Indices

题目解析

从字符串的中心寻找有多少个连续相同的字符。

参考代码

int main() {
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        string s;
        cin >> s;
        int l = n / 2, r = n / 2;
        while(l - 1 >= 0 and s[l - 1] == s[n / 2]) l--;
        while(r + 1 < n and s[r + 1] == s[n / 2]) r++;
        cout << (r - l + 1) << endl;
    }
    return 0;
}

B. AND Sorting

题目解析

略

参考代码

int main() {
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> arr(n);
        for(auto& it: arr) cin >> it;
        vector<int> brr(arr);
        sort(itr(brr));
        int ans = INT_MAX;
        for(int i = 0; i < n; ++i){
            if(arr[i] != brr[i]){
                ans &= (arr[i] & brr[i]);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

C. LIS or Reverse LIS?

题目解析

观察可以发现，LIS 和 RerverseLIS(RLIS) 可以共享一个数字，比如：1 2 3 2 1，共享的是 3； 3 2 1 2 3 共享的是 1； 3 1 2 1 3共享的是2。
当然 LIS 和 RLIS 无法共享多个数字。 因为 LIS 要求严格递增， RLIS 要求严格递减。

那么对于出现过超过 $1$ 次的数字，可以在 LIS 和 RLIS 中各选择一个。
对于只出现过 $1$ 次的数字，可以选择共享一个数字，其余的数字平均分配到 LIS 和 RLIS 中。

参考代码

int main() {
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> arr(n);
        for(auto& it: arr) cin >> it;
        sort(itr(arr));
        vector brr(arr);
        brr.erase(unique(itr(brr)), brr.end());
        map<int, int> mp;
        for(auto& it: arr) mp[it]++;
        int one = 0, two = 0;
        for(auto& c: brr) {
            if(mp[c] == 1) one++;
            else two++;
        }
        cout << two + (one + 1) / 2 << endl;
    }
    return 0;
}

D. Circular Spanning Tree

题目解析

节点总数是 $n$ 。

首先分析全为 $0$ 和全为 $1$ 的情况。

如果全为 $0$ ，每个节点都需要有偶数个节点和它相连，又因为叶子节点只有 $1$ 个相连的节点，所以没有叶子节点，所以不存在。

如果全为 $1$ ，考虑节点的度的总和。如果节点总数是奇数，那么度的总和也是奇数，就无法构成一棵树。
如果节点总数是偶数，那我们可以画一个简单的方案，把所有节点都连接起来。

随便选择一个节点，然后把其他的节点都与它相连。因为节点总数是偶数，所以选择的那个节点相连的节点数是奇数（ $n - 1$ ）。

然后既包含 $0$ ，也包含 $1$ 的情况。

当然，也需要 $1$ 的节点数目是偶数个。
然后我们可以环形地，把每个 $1$，和它顺时针的 $0$ 先连接起来，并且把每个连接起来的部分，视作一个整体。如下图所示。

然后每个整体都是只有顺时针的最后一个位置不满足条件。这就等于上面分析的全1的情况。
我们任意选择一个整体，把它的顺时针最后一个节点，与其他的整体的顺时针最后一个节点相连。

参考代码

int main() {
    fastIO();
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        string s;
        cin >> s;
        int cnt = 0;
        for(int i = 0; i < n; ++i){
            if(s[i] == '1') ++ cnt;
        }
        if(cnt % 2 == 1 or cnt == 0){
            cout << "NO\n";
            continue;
        }
        if(cnt == n){
            cout << "YES\n";
            for(int i = 2; i <= n; ++i){
                cout << 1 << " " << i << "\n";
            }
            continue;
        }
        cout << "YES\n";
        vector<PII> ans;
        vector<int> ones;
        for(int i = 0; i < n; ++i){
            if(s[i] == '1'){
                ones.push_back(i);
            }
        }
        vector<int> backs;
        for(auto& it: ones){
            int rb = it;
            while(s[(rb + 1) % n] == '0'){
                ans.push_back({rb, (rb + 1) % n});
                rb = (rb + 1) % n;
            }
            backs.push_back(rb);
        }
        for(auto& it: backs){
            if(it != backs.front()){
                ans.push_back({backs.front(), it});
            }
        }
        for(auto& it: ans){
            cout << it.first + 1 << " " << it.second + 1 << "\n";
        }
    }
    return 0;
}