Codeforces Round#656 (Div. 3) 题解

¶Codeforces Round #656 (Div. 3)

¶A. Three Pairwise Maximums #构造

¶题目链接

¶题意

给定三个正整数$x,y,z$，要求找出正整数$a,b,c$，满足$x=max(a,b), y=max(a,c),z=max(b,c)$

¶分析

我们可以先将$x,y,z$降序排序得到$z\leq y\leq x$。由于$x$是$a,b,c$三者最值，且通过三个关系中$x$所代表的数字一定出现两次，可以推断出，$y=x$，如果最值没有出现两次，说明我们不可能构造出$a,b,c$。

既然题目让我们构造，构造且要满足$max(a,b)=max(a,c)$，那么不妨设$a$为最大值，即$a=x=y$。由于$z$能推出$b,c$关系，我们又不妨将$b$赋为$z$(三值中第二大)。三者最小值不易准确确定，直接将$c$赋值为1，作为三者中的最小值，十分稳妥。

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int MOD = 1e4 + 7;
int n, m, q;
int main(){
    scanf("%d", &q);
    while(q--){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        if(x<y) swap(x,y);
        if(x<z) swap(x,z);
        if(y<z) swap(y,z); //排序一下
        if(x != y) {
            printf("NO\n");
            continue;
        }
        else{
            printf("YES\n");
            printf("%d %d %d\n", x, z, 1);
        }
    }
    return 0;
}

¶C. Make It Good #贪心

¶题目链接

¶题意

“好数组”定义为，一个数组$b$，我们只从该数组最左边，或者最右边，将所有元素依次取出并放到$c$数组，该$c$数组是个不降序列，则称$b$数组为“好数组”。

现给定数组$a$，你需要从数组$a$的前几个元素删去，得到一个“好数组”。现要你求出删除的前几个元素至少需要多少。比如数组a={4 3 3 8 4 5 2}，你至少需要删除前面4个元素，得到的数组b={4 5 2}才是个好数组。

¶分析

不难分析，“好数组”中的元素关系必然是$b_1 \leq b2 \leq ... \leq b_{mx} \geq ... \geq b_k$，其中$b_{mx}$为数组$b$中最大值(不一定是数组$a$中最大值)，简单来说，我们就是要从$a$数组中找到“山峰”。

由于我们只能删除数组$a$中前面几个元素，因而后面元素受到的影响很少，于是我们用一右指针$hi$，从数组$a$的后面往前面遍历，只要$a[hi-1]\geq a[hi]$就往前进（相当于走上坡），一旦遇到$a[hi-1] \leq a[hi]$说明到达极值点。我们再继续往前面（往数组左端）遍历，只要$a[hi-1]\leq a[hi]$就往前进（相当于走下坡），一旦遇到$a[hi-1] \geq a[hi]$说明到达我们到达山底，即$a[1, ...hi-1]$的元素都需要删去，$a[hi, n]$方为好数组。敲代码时注意下边界。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
int n, m, q;
int a[MAXN];
int main(){
    scanf("%d", &q);
    while(q--){
        scanf("%d", &n);
        for(int i =1 ; i <= n; i++) scanf("%d", &a[i]);
        int hi = n;
        while(hi >= 1 && a[hi-1] >= a[hi]) hi--; //走上坡
        while(hi >= 1 && a[hi - 1] <= a[hi]) hi--; //走下坡
        if(hi - 1 >= 0) printf("%d\n", hi - 1);
        else printf("0\n");
    }
    return 0;
}

¶D. a-Good String #暴力深搜 #分治

¶题目链接

¶题意

“$a$-好串”定义为，不小于一个元素的串，满足以下其中一个条件即可：

• 若长度为1，且包含的字符恰好为$a$。
• 若长度大于1，且它的左半部分所有字符均为$a$，而另一半的串是“$a+1$-好串”($a+1$字符，即为字符a在字母表中下一个字符)
• 若长度大于1，且它的右半部分所有字符均为$a$，而另一半的串是“$a+1$-好串”

$t(\leq2\times 10^{5})$组询问，给定长度为$n(其中\sum n \leq 2\times 10^{5})$串，你可以对串中任意字符转变为其他任意字符，每个字符的转变作为一次操作，现要你求出将串转变为“$a-$好串”的最少次数

¶分析

先将串中所有种字符进行前缀和统计，然后对于串的前后部分暴力搜索一下即可，因为递归下来，大约有$logn$种子串，层数大约为十多层，$O(nlogn)$复杂度能够通过$t$组询问。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
using namespace std;
typedef long long ll;
const int MAXN = 150000;
int q, n, sum[30][MAXN];
string str;
int dfs(int lo, int hi, int cur){
    int mid = (lo + hi) >> 1, len = hi - lo + 1;
    if(len <= 1) //边界情况
        return len - sum[cur][hi] + sum[cur][hi - 1];
    int pre = (len >> 1) - sum[cur][mid] + sum[cur][lo - 1];
    int lat = (len >> 1) - sum[cur][hi] + sum[cur][mid];
    int res = min(dfs(lo, mid, cur+1) + lat, dfs(mid+1, hi, cur+1) + pre);
    return res;
}
void preCal(){
    for (int i = 1; i <= 26; i++){
        for (int j = 0; j < str.length(); j++){
            sum[i][j + 1] = sum[i][j];
            if(str[j] - 'a' + 1 == i)
                sum[i][j + 1]++;
        }
    }
}
int main(){
    scanf("%d", &q);
    while(q--){
        scanf("%d", &n); cin >> str;
        preCal();
        printf("%d\n", dfs(1, n, 1));
    }  
}

¶E. Directing Edges #拓扑排序

¶题目链接

¶题意

给定一个图，里面既包含有向边，也包含无向边，并保证初始情况下的图不存在平行边与自环，现要你将图中所有无向边改变为有向边（方向自定义），使得图不存在任何一个有向环。如果无法保证不出现有向环，输出"NO"。否则需要你输出所有边的连接信息。

¶分析

容易知道，初始情况下的无向边并不会影响图是否存在有向环，应关注于当前的所有有向边所组成的图。如何判断是否存在有向环，利用拓扑排序算法即可，但别忘了要将拓扑序列存下来，这是用于判断无向边指向的方向。如果一条无向边中的顶点$a$的拓扑序小于顶点$b$，那么$a$应该指向$b$，反之，让$b$指向$a$。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 2e5+5;
int q, n, m;
struct Edge{ //用于输出
    int u, v;
} E[MAXN << 1];
struct BuildEdge{ //用于拓扑排序
    int to, nextNbr;
} BE[MAXN << 1];
int H[MAXN], tot = 0, InD[MAXN], num = 0;
int ans[MAXN];
void addEdge(int u, int v){
    tot++;
    BE[tot] = {v, H[u]};
    H[u] = tot;
}
bool ToSort(){
    queue<int> myque;
    int res = 0;
    for(int i = 1; i <= n; i++){
        if(InD[i] == 0){
            myque.push(i);
            ans[i] = ++res; //记录拓扑序
        }  
    }
    while(!myque.empty()){
        int cur = myque.front();
        myque.pop();
        for(int i = H[cur]; i >= 0; i = BE[i].nextNbr){
            int v = BE[i].to; InD[v]--;
            if(InD[v] == 0){
                myque.push(v);
                ans[v] = ++res; //记录拓扑序
            }
        }
    }
    return (res != n); //如果不相等，说明存在有向环
}
void Init(){ //初始化
    memset(H, -1, sizeof(H));
    memset(ans, 0, sizeof(ans));
    memset(InD, 0, sizeof(InD));
    tot = num = 0;
    for (int i = 1; i <= m; i++) BE[i] = {-1, -1};
}
int main(){
    scanf("%d", &q);
    while(q--){
        scanf("%d%d", &n, &m);
        Init();
        for (int i = 1, u, v, opt; i <= m; i++){
            scanf("%d%d%d", &opt, &u, &v);
            E[++num] = {u, v};
            if(opt == 1){ //有向边建图
                addEdge(u, v);
                InD[v]++;
            }
        }
        bool isLoop = ToSort();
        if(isLoop) printf("NO\n");
        else{
            printf("YES\n");
            for(int i = 1; i <= m; i++){
                int u = E[i].u, v = E[i].v;
                if(ans[u] < ans[v]) printf("%d %d\n", u, v);
                else printf("%d %d\n", v, u);
            }
        }
    }
    return 0;
}