Codeforces Round 915 (Div. 2)

Codeforces Round 915 (Div. 2)

Codeforces Round 915 (Div. 2)

A. Constructive Problems

题意：略。

思路：相邻的矩阵块可以接连修复，那么只需要政府修复矩阵中最长的边即可横/纵向覆盖全部矩阵。

AC code：

void solve(){
    int x, y; cin >> x >> y;
    cout << max(x, y) << endl;
}

B. Begginer’s Zelda

题意：在一颗无向图的树中，可以进行一次塞尔达操作，每次操作选择任意两个顶点，然后将连接两顶点间的点包括俩顶点全部压缩为一点，之前连接这些点的子节点全部直接连接压缩后的新节点。

最少需要多少次塞尔达操作可以使得该树只有一个顶点。

思路：我们只需要找到所有的叶子结点，即无向图中所有入度为1的结点，然后任选两个，两两进行塞尔达操作，最终结果向上取整。

AC code：

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i ++)
        d[i] = 0;

    for(int i = 0; i < n - 1; i ++){
        int u, v; cin >> u >> v;
        d[u] ++;
        d[v] ++;
    }

    int ans = 0;
    for(int i = 1; i <= n; i ++){
        if(d[i] == 1) ans ++;
    }
    cout << ans / 2 + (ans % 2 != 0) << endl;
}

C. Largest Subsequence

题意：给定长度为n的字符串，每次操作可以从中选出词性最大的子序列，然后向右循环移动一次，是否可以通过该操作使字符串达到从小到大的排序状态并输出最小操作数，或报告不可能。

思路：首先是选择词性最大的子序列，即字典序最大，我们需要考虑的是整个序列最大的字符所处的位置，当该字符移动到最后时，若序列仍不是最小序列则不可能通过该操作达成最小序列，因为最大字符为首的子序列词性一定是最大的，而不是一个字符串越长词性越大，当其移动到最后时整个字符串无法继续进行操作(选择一个字符循环操作无意义)。

现在是如何选择需要移动的最大的字符串。首先是记录每个字符串出现的次数，然后遍历字符串，找出字符的后面无比自己大的字符，这样的字符需要进入循环的子序列中进行操作，可以通过遍历比当前字符大的所有字符是否在后面出现即可，即26个小写字母中比自身大的字符是否在后面有出现。

然后选择后的子序列需要向右移循环操作，我们不需要一步步的进行操作，而是直接在原字符串中倒转选择的最大子序列，因为在选择的每个字符的后面都不存在比自身更大的字符，直接倒转可以最大可能的将靠前的大字符后移，靠后的小字符前移。

倒转操作后，判断操作后的序列是否是最小序列，若仍旧不是，则无法继续进行操作，输出-1；

否则，操作数即为选择的子序列的长度减去第一个相邻字符不重复的字符的位置，即循环操作时我们优先选择出现第一个相邻且不同的字符进行操作。同样的，若不存在这样的字符，则说明序列不需要操作，操作数为0。

具体详见代码。

AC code：

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

typedef long long LL;
typedef pair<char, int> PCI;
typedef pair<int, int> PII;
const int N = 3e5+10, M = 2001;
const int INF = 0x3f3f3f3f3f, mod = 998244353;
int T, n;
string s;
map<char, int> mp;

void solve(){
    cin >> n >> s;
    for(char c : s) mp[c] ++;

    vector<PCI> q;
    for(int i = 0; i < n; i ++){
        int flag = 0;
        mp[s[i]] --;
        for(char j = s[i] + 1; j <= 'z'; j ++){
            if(mp[j]){
                flag = 1;
                break;
            }
        }if(flag) continue;
        q.push_back({s[i], i});
    }
    int pos = q.size() - 1;
    for(int i = 0; i < q.size(); i ++){
        s[q[i].second] = q[pos].first;
        pos --;
    }
    for(int i = 0; i < n - 1; i ++){
        if(s[i] > s[i + 1]){
            cout << "-1" << endl;
            return;
        }
    }
    for(int i = 0; i < q.size() - 1; i ++){
        if(q[i].first != q[i + 1].first){
            cout << q.size() - (i + 1) << endl;
            return;
        }
    }
    cout << 0 << endl;
}

signed main(){
    fast();
    
    T = 1;
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}