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,共享的是 33 2 1 2 3 共享的是 13 1 2 1 3共享的是2
当然 LIS 和 RLIS 无法共享多个数字。 因为 LIS 要求严格递增, RLIS 要求严格递减。

那么对于出现过超过 11 次的数字,可以在 LIS 和 RLIS 中各选择一个。
对于只出现过 11 次的数字,可以选择共享一个数字,其余的数字平均分配到 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

题目解析

节点总数是 nn

首先分析全为 00 和全为 11 的情况。

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

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

红色节点是1

随便选择一个节点,然后把其他的节点都与它相连。因为节点总数是偶数,所以选择的那个节点相连的节点数是奇数( n1n - 1 )。

然后既包含 00 ,也包含 11 的情况。

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

红色节点是1,蓝色节点是0

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

红色节点是1,蓝色节点是0

参考代码

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;
}

Codeforces Round 793 (Div. 2)
https://dianhsu.com/2022/05/23/cf1682/
作者
Dian Hsu
发布于
2022年5月23日
许可协议