Codeforces Round 987 (Div. 2)

考试众多，一直延续到期末周，目前就维持状态. (还要给新生出题本场链接

A.Penchick and Modern Monument

数出最多出现的数字有多少，即可

void solve(){
    int n;
    cin >> n;
    // int pos = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    std::map<int,int>cnt;
    for(int i = 1; i <= n; i++){
        cnt[a[i]]++;
    }
    int max = -1;
    for(auto it : cnt){
        if(it.second > max)max = it.second;
    }
    cout << n - max << endl;
}

B.Penchick and Satay Sticks

按照题意把大的和小的进行交换，最后如果不是递增的排列就输出NO，反之输出YES

void solve(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    for(int i = 2;i <= n;i++){
        if(a[i] - a[i - 1] == -1){
            std::swap(a[i],a[i - 1]);
        }
    }
    for(int i = 1;i <= n;i++){
        if(a[i] != i){
            cout << "NO" << endl;
            return;
        }
    }
    cout  << "YES" << endl;
}

C.Penchick and BBQ Buns

分析题目得到，如果n为偶数，全部为1即可，如果n为奇数个的话，则一个数需要出现三遍，其中出现的位置i,j,k需要满足(j - i) + (k - j) = (k - i)且都是完全平方数可以构造出一个奇数个的字符串，发现长度为27，因此小于27就不可能了

void solve(){
    int n;
    cin >> n;
    int a[] ={2, 1, 3, 3, 2, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 1, 10, 10, 11, 11, 12, 12, 13, 13, 1};
    if(!(n%2)){
        for(int i = 1;i <= n/2;i++){
            cout << i << ' ' << i << ' ';
        }
        cout << endl;
    }else{
        if(n < 27){
            cout << -1 << endl;
        }
        else{
            n -= 27;
            for(auto x:a) cout << x << ' ';
            int tmp = 14;
            for(int i = 1;i <= n/2;i++){
                cout << tmp << ' ' << tmp << ' ';
                tmp++;
            }
            cout << endl;
        }
    }
        
}

D. Penchick and Desert Rabbit

分析题意可知，互相跳的块都相互连通，因此主要考虑每个连通块里的最大值，因此选择维护单调递增栈，每个点与之前比他大的点相连，更新该点数值为连通块最大值入栈。

void solve(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++){
        fa[i] = i;
    }
    std::stack<int> st;
    for(int i = 1;i <= n;i++){
        int max = a[i];
        while(!st.empty() && a[i] < a[st.top()]){
            merge(st.top(),i);
            max = std::max(max,a[st.top()]);
            st.pop();
        }
        a[i] = max;
        st.push(i);
    }
    for(int i = 1;i <= n;i++){
        cout << a[find(i)] << " ";
    }
    cout << endl;
}