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

这场本来赛中卡了D，按理说是要掉分的

A - Three Pairwise Maximums

题意：x=max(a,b)，y=max(a,c)，z=max(b,c)，现在给定x,y,z，求a,b,c。
思路：我们假设a>b>c，那么显然x==y>z，所以可以看出不管a,b,c大小关系如何，x,y,z中必有两个一样，并且大于等于剩下的那个数字，所以只需要让公共的那个值设为大的值，另外两个设为小的值即可。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=15+5;
const int MAX_M=30+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        int a,b,c;
        cin>>a>>b>>c;
        if(a!=b&&b!=c&&a!=c)
            cout<<"NO"<<endl;
        else
        {
   
            int x,y;
            if(a==b)
            {
   
                x=a;
                y=c;
            }
            if(a==c)
            {
   
                x=a;
                y=b;
            }
            if(b==c)
            {
   
                x=b;
                y=a;
            }
            if(x<y)
            {
   
                cout<<"NO"<<endl;
            }
            else
            {
   
                cout<<"YES"<<endl;
                if(a==x&&b==x)
                {
   
                    cout<<x<<' '<<y<<' '<<y<<endl;
                }
                else if(a==x&&c==x)
                {
   
                    cout<<y<<' '<<x<<' '<<y<<endl;
                }
                else if(b==x&&c==x)
                {
   
                    cout<<y<<' '<<y<<' '<<x<<endl;
                }
            }
 
        }
    }
}

B - Restore the Permutation by Merger

题意：两个同样的n序列，相互穿插在一起，给定穿插后的串，求原串。
思路：因为顺序不变，序列中字母也不会重复，所以直接取第一次出现的字母放在序列末尾即可。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=100+5;
const int MAX_M=30+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        vector<int>ans;
        map<int,int>vis;
        int a;
        int n;
        scanf("%d",&n);
        int i;
        for(i=1;i<=2*n;i++)
        {
   
            scanf("%d",&a);
            if(!vis[a])
            {
   
                ans.pb(a);
                vis[a]=1;
            }
        }
        for(i=0;i<ans.size();i++)
        {
   
            printf("%d%c",ans[i],i==ans.size()-1?'\n':' ');
        }
    }
}

C - Make It Good

题意：给定一个序列，通过删除前缀，使其每次从开头或结尾拿出一个字符放在新的串的结尾，最后使该串不递减。求删除最短前缀的长度。
思路：首先这个删除后序列要想满足这个不递减的条件，必然要以中间某个字符为界限，从第一个到他，和最后一个到他都是不递减的，然后由于只删前缀，所以我们可以从后往前遍历，找到第一个不满足不递减条件的字符，那么这个位置就可以看做那个届，然后从头开始遍历到这个届，如果遇到递减的字符，那么这个字符之前的就都要删掉。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int MAX_M=30+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
int a[MAX_N];
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        int n;
        scanf("%d",&n);
        int i;
        for(i=1; i<=n; i++)
            scanf("%d",&a[i]);
        int pos=0;
        for(i=n-1; i>=1; i--)
        {
   
            if(a[i]<a[i+1])
            {
   
                pos=i;
                break;
            }
        }
        if(pos==0)
        {
   
            cout<<0<<endl;
            continue;
        }
        //cout<<a[pos]<<endl;
        int ans=0;
        for(i=2; i<=pos; i++)
        {
   
            if(a[i]<a[i-1])
            {
   
                ans=i-1;
            }
        }
        cout<<ans<<endl;
    }
}

D - a-Good String

题意：不太好描述，诸如aaaabbcd,aaaabbdc,bbdcaaaa这样的串是好串，现在给定一些串，问最少改多少字符可以形成好串。
思路：dfs暴力就完了，顺便吐槽下，用暴力和前缀和记录的时间cf测出来居然是一样的，都只有46ms，太神奇了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int MAX_M=30+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
char s[MAX_N];
int ans=INF;
void dfs(int l,int r,char c,int sum)
{
   
    //cout<<l<<' '<<r<<endl;
    if(l==r)
    {
   
        if(s[l]!=c)
            sum++;
        ans=min(ans,sum);
        return;
    }
    int tmp=0;
    int i;
    int mid=(l+r)/2;
    for(i=l;i<=mid;i++)
    {
   
        if(s[i]!=c)
            tmp++;
    }
    //cout<<tmp<<endl;

    dfs(mid+1,r,c+1,sum+tmp);
    tmp=0;
    for(i=mid+1;i<=r;i++)
    {
   
        if(s[i]!=c)
            tmp++;
    }
    //cout<<tmp<<endl;
    dfs(l,mid,c+1,sum+tmp);
}
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        ans=INF;
        int n;
        scanf("%d",&n);
        scanf("%s",s+1);
        if(n==1)
        {
   
            if(s[1]=='a')
                cout<<0<<endl;
            else
                cout<<1<<endl;
            continue;
        }
        dfs(1,n,'a',0);
        cout<<ans<<endl;
    }
}

E - Directing Edges

题意：给定n个点和m条边组成的图，这m条边中有些是有向的，有些是无向的，现在要求你给这些无向边加上方向，使其不存在环。
思路：看到成环要想到拓补排序（虽然本菜鸡根本没想到），先把有向边进行拓补排序，顺便判断下是不是已经成环了，然后无向边的两点根据拓补链中的先后，前面的指向后面的。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int MAX_M=30+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
vector<int>edge[MAX_N],ans;;
vector<P>e;
int in[MAX_N];
int n,m;
int vis[MAX_N];
int tuob()//拓补排序
{
   
    //cout<<in[3]<<endl;
    queue<int>q;
    int i;
    for(i=1; i<=n; i++)
    {
   
        if(in[i]==0)
            q.push(i);
    }
    while(!q.empty())
    {
   
        int x=q.front();
        //cout<<x<<endl;
        ans.pb(x);
        vis[x]=ans.size();
        q.pop();
        for(auto i:edge[x])
        {
   
            in[i]--;
            if(in[i]==0)
                q.push(i);
        }
    }
    //cout<<in[3]<<endl;
    if(ans.size()==n)
        return 1;
    else
        return 0;
}
int main()
{
   
    int t;
    cin>>t;
    while(t--)
    {
   
        me(in,0);
        me(vis,0);
        ans.clear();
        e.clear();
        int i;
        scanf("%d%d",&n,&m);
        for(i=0;i<=n;i++)
            edge[i].clear();
        for(i=1; i<=m; i++)
        {
   
            int op,l,r;
            scanf("%d%d%d",&op,&l,&r);
            if(op)
            {
   
                edge[l].pb(r);
                in[r]++;
            }
 
            else
            {
   
                e.pb(P(l,r));
            }//cout<<in[3]<<endl;
        }
        //sort(in+1,in+1+n);
        if(!tuob())
            cout<<"NO"<<endl;
        else
        {
   
            for(auto i:e)
            {
   
                if(vis[i.fi]<vis[i.se])
                {
   
                    edge[i.fi].pb(i.se);
                }
                else
                    edge[i.se].pb(i.fi);
            }
            cout<<"YES"<<endl;
            for(i=1; i<=n; i++)
            {
   
                for(auto j:edge[i])
                {
   
                    cout<<i<<' '<<j<<endl;
                }
            }
        }
    }
}