Codeforces Round #656 (Div. 3)A~E题解

发布于 2020-07-19  0 次阅读


A. Three Pairwise Maximums

思路:

将a, b, c非递减排序后得,x=b,y=z=c
若y 不等于 z则无解,否则a=1, b=x, c=y是一组解

AC Code:

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const double pi = acos(-1.0);
#define INF 0x7f7f7f
// #define TDS_ACM_LOCAL
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int t;
    cin>>t;
    while(t--){
        int x, y, z;
        cin>>x>>y>>z;
        if(x>y) swap(x,y);
        if(x>z) swap(x,z);
        if(y>z) swap(y,z);
        if(y==z)
        {
            cout<<"YES"<<endl;
            cout<<"1 "<<x<<" "<<y<<endl;
        }   
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

B. Restore the Permutation by Merger

思路:

第二次遇到相同的就输出

AC Code:

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const double pi = acos(-1.0);
#define INF 0x7f7f7f
// #define TDS_ACM_LOCAL
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int t;
    cin>>t;
    while(t--){
        int n, a, p[55]={0};
        cin>>n;
        for(int i=0; i<2*n; i++){
            cin>>a;
            p[a]++;
            if(p[a]==2)
                cout<<a<<" ";
        }
        cout<<endl;
    }
    return 0;
}

C. Make It Good

思路:

满足题目要求的很明显
1、全程不变
2、全程非递减或者非递增
3、具有一个极大值的峰顶
解:从右到左搜索峰顶(>=),再从峰顶往左搜峰底(<=)

AC Code:

#include<cstdio>
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
const double pi = acos(-1.0);
#define INF 0x7f7f7f
// #define TDS_ACM_LOCAL
#define mem(a,b) memset(a , b , sizeof(a))
#define FOR(i, x, n) for(int i = x;i <= n; i++)
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int t;
    cin>>t;
    while(t--){
        int n, a[200009]={0};
        cin>>n;
        for(int i=0; i<n; i++)
            cin>>a[i];
        int k=n-1;
        while(a[k-1]>=a[k]&&k>=1)
            k--;
        while(a[k-1]<=a[k]&&k>=1)
            k--;
        cout<<k<<endl;
    }
    return 0;
}

D. a-Good String(二分、递归)

思路:

因为n=2^k,所以n为2的倍数,可以一直二分到只有一个字符
使用递归二分的方法,每次分别计算当前子串的左边和右边变成c需要的操作次数,将各种情况下的次数求和取最小即可

AC Code:

#include<cstdio>
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
const double pi = acos(-1.0);
#define INF 0x7f7f7f
// #define TDS_ACM_LOCAL
#define mem(a,b) memset(a , b , sizeof(a))
#define FOR(i, x, n) for(int i = x;i <= n; i++)

inline void read(int &x) {
	char ch = getchar(); int f = 1; x = 0;
	while (!isdigit(ch) && ch^'-') ch = getchar();
	if (ch == '-') f = -1, ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	x *= f;
}

char s[131080];
int t, n, ans;

int solve(int l, int r, char c){                                         //字符c按照abcd...排序
    if(l==r)    return s[l]==c? 0:1;                                     //最后一位数时不需要变返回0,否则1
    int mid=(l+r)>>1, left=0, right=0;                                   //求得当前子串的左右分别需要改变的字符的数量
    FOR(i, l, mid)  left+=(s[i]==c? 0:1);                                //判断当前字符是否需要进行改变
    FOR(i, mid+1, r)    right+=(s[i]==c? 0:1);
    return min(left+solve(mid+1, r, c+1), right+solve(l, mid, c+1));     //采用递归的方法求改变的最小值
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    read(t);
    while (t--)
    {
       read(n);
       scanf("%s", s+1);
       ans=solve(1, n, 'a');
       cout<<ans<<endl;
    }
    return 0;
}

E. Directing Edges

思路:

因为题目要求无环,所以使用toposort(拓扑排序),以已知的有向边计算入度进行拓扑排序
检测是否所有的点都在拓扑序列中,有剩余的点说明有环
因为先去除的点排在前面,后去除的点排在后面,所以从前面向后面添加边是不会对拓扑序列造成影响
所以将无向边变成有向边的时候按照前面的点到后面的点连向就行

AC Code:

#include<cstdio>
#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define pb push_back
#define mp make_pair
#define X first
#define Y second
const int N=200009;
// #define TDS_ACM_LOCAL

int tx, n, m, a[N], in_degree[N];
int t, x, y;
vector<pair<int,int>> ma[N];
vector<int>topo;

inline void read(int &x) {
	char ch = getchar(); int f = 1; x = 0;
	while (!isdigit(ch) && ch^'-') ch = getchar();
	if (ch == '-') f = -1, ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	x *= f;
}

void toposort(){
    topo.clear();                                //拓扑序列初始化
    queue<int>q;                                 //存点的队列
    for(int i=1; i<=n; i++)                      //将入度为0的点放入队列中
        if(!in_degree[i])
            q.push(i);
    while(q.size()){
        x=q.front();
        q.pop();
        topo.pb(x);                             //将点放入拓扑序列中
        for(int i=0; i<ma[x].size(); i++){      //将该点能到达的有向边全部删除(即可到达点的入度减1
            y=ma[x][i].X, t=ma[x][i].Y;
            if(t){
                if(!--in_degree[y])
                    q.push(y);
            }
        }
    }
}

void solve(){
    read(n), read(m);
    for(int i=1; i<=n; i++) {        //初始化每个点的入度和图
        in_degree[i]=0;
        ma[i].clear();
    }
    while(m--){
        read(t), read(x), read(y);
        if(t){                       //为有向边,记录x->y,并且标记为有向边,同时入度加1
            ma[x].pb(mp(y,t));
            in_degree[y]++;
        } 
        else{                        //为无向边,记录x->y,y->x,并且标记为无向边
            ma[x].pb(mp(y,t));
            ma[y].pb(mp(x,t));
        }
    }
    toposort();
    if(topo.size()!=n){              //拓扑序列没有包含所有点,说明有环
        cout<<"NO"<<endl;
        return ;
    }
    else{
        cout<<"YES"<<endl;
        for(int i=0; i<n; i++)       //记录拓扑序列的点的先后顺序
            a[topo[i]]=i;
        for(int i=1; i<=n; i++){
            for(int j=0; j<ma[i].size(); j++){        //输出所有的边
                y=ma[i][j].X, t=ma[i][j].Y;
                if(t)                                 //有向边直接输出
                    cout<<i<<" "<<y<<endl;
                else{                                 //无向边按照在拓扑序列出现的先后顺序输入
                    if(a[i]<a[y])
                        cout<<i<<" "<<y<<endl;
                }
            }
        }
    }
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    read(tx);
    while (tx--) solve();
    return 0;
}

平平无奇的在校大学生