Codeforces Round #656 (Div. 3)题解

A.Three Pairwise Maximums

解题思路：

依照题意和样例，三个整数x,y,z必须有两个相同且都比第三个数大。
如果x==y则说明a为最大值，此时需要满足a>=z，如果不满足该条件，则无解，因为z=max(b，c)，我们不能确定b,c谁比较大，所以我们就假设两个数一样的即可。而当y == z和x == z同理。

#include<bits/stdc++.h>
using namespace std;
int a[3];
int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t; while (t--) {
        cin >> a[0] >> a[1] >> a[2];
        sort(a, a + 3);
        if (a[1] != a[2]) {
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;
        cout << a[0] << " " << a[0] << " " << a[2] << endl;
    }
}

B.Restore the Permutation by Merger

题目说是相对顺序插入的，所以我们可以直接遍历来做。

#include<bits/stdc++.h>
using namespace std;
int t, n, a;
int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> t; while (t--) {
        cin >> n; int b[55] = { 0 };
        for (int i = 0; i < 2 * n; ++i) {
            cin >> a;
            if (!b[a])
                cout << a << " ";
            b[a]++;
        }
        cout << endl;
    }
}

C.Make It Good

解题思路：
满足中间大两边小。
要找最长“好序列”，从后往前找，找到第一个不满足从后往前递增条件的元素，然后从这个元素往前找，找到开始升的那个元素就停止。最后答案就是n减去最长“好序列”长度。

#include<bits/stdc++.h>
using namespace std;
int a[200005];
int main()
{
    int t;
    cin >> t;
    while (t--)
    {   
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        int R = n;
        while (a[R - 1] >= a[R] && R >= 1) R--;
        while (a[R - 1] <= a[R] && R >= 1) R--;
        int ans = R - 1;
        if (ans == -1) ans = 0;
        cout << ans << endl;
    }
    return 0;
}

D. a-Good String

解题思路：
暴力枚举，取最小值

#include<bits/stdc++.h>
using namespace std;
char a[131073];
int t, n;
int solve(int l,int r,char m) {
    if (l == r) {
        if (a[l] == m)return 0;
        else return 1;
    }
    int mid = (l + r) >> 1, left = 0, right = 0,len = r - l + 1;
    for (int i = l; i <= mid; ++i) if (a[i] == m)left++;
    for (int i = mid + 1; i <= r; ++i) if (a[i] == m)right++;
    int ans = min(len / 2 - left + solve(mid + 1, r, m + 1), len / 2 - right + solve(l, mid, m + 1));
    return ans;
}
int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> t; while (t--) {
        char m = 'a';
        cin >> n;for(int i = 1;i <= n;++i){
            cin >> a[i];
        }
        cout << solve(1, n, m) << endl;
    }
}

E. Directing Edges

解题思路：
首先可以看出这是一道拓扑的题。但由于不太好维护得建图。建反方向的边，最后再拓扑排。但由于我太菜了，就没做出来。代码就放dalao们做的了。

#include<bits/stdc++.h>
using namespace std;
vector<int>e[200005];
int u[200005],v[200005];
int T,n,m;
int in[200005],tp[200005];
queue<int>q;
bool topsort(){
    int ct=0,tmp=0;
    for(int i=1;i<=n;i++) if(!in[i]) q.push(i),ct++,tp[i]=++tmp;
    while(!q.empty()){
        int U=q.front();q.pop();
        for(int V:e[U]){
            in[V]--;
            if(!in[V]) q.push(V),ct++,tp[V]=++tmp;
        }
    }
    return ct<n;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);memset(in,0,sizeof(in));
        for(int i=1;i<=n;i++) e[i].clear();
        for(int o,i=1;i<=m;i++){
            scanf("%d%d%d",&o,&u[i],&v[i]);
            if(o) in[v[i]]++,e[u[i]].emplace_back(v[i]);
        }if(topsort()) puts("NO");
        else{
            puts("YES");
            for(int i=1;i<=m;i++)
            if(tp[u[i]]<tp[v[i]]) printf("%d %d\n",u[i],v[i]);
            else printf("%d %d\n",v[i],u[i]);
        }
    }return 0;
}