Codeforces Round#656(Div.3)A,B,C,D,E(その他の補完対象)

A. Three Pairwise Maximums

簡単な問題ですが、長い間考えていたので、泣きました.条件を満たすx,y,zには絶対に2つの数が等しいし、もう1つの数よりも大きいので、私もなぜか説明しにくいので、、、、ちょっと我慢して、自分でサンプルを見て考えてみましょう.答えに向かってプログラミングするのは難しいです.私はあまり題意を書きたくありません.もともと理解しやすい英語の問題で、試合に出るのはすべて英語の問題なので、みんなは英語を読むのに慣れなければなりません.

void sove()
{
    int a[4];
    scanf("%d%d%d",&a[1],&a[2],&a[3]);
    sort(a+1,a+1+3);
    if(a[3]==a[2]&&a[3]>=a[1])
    {
        printf("YES
");
        printf("%d %d %d
",a[1],a[1],a[3]);
    }
    else
    {
        printf("NO
");
    }
}

2.B. Restore the Permutation by Mergerこれこそ問題にサインするべき姿で、問題の意味は言わないで、よく理解する方法は左から右まで記数をマークして、もし現れなかったら出力して、しかもマークして、現れたら直接スキップします

void sove()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=2*n;i++)
    {
        scanf("%d",&a[i]);
    }
    ms(vis,0);
    for(int i=1;i<=2*n;i++)
    {
        if(!vis[a[i]])
        {
            printf("%d ",a[i]);
            vis[a[i]]=1;
        }
    }
    printf("
");
}

3.C. Make It Good cの問題は他の人はすべて模擬したことがあって、私は特に2点を使ってやっと過ぎて、怒って、この問題はきっと2点を満たして、削除するのが多ければ多いほど、そんなに正しいかもしれないので、削除するのが少なければ少ないほど正しいことはできません.

bool check(int x)
{
    int l=x+1,r=n,ma=0;
    bool flage=true;
    while(r>=l)
    {
        if(a[l]>=a[r]&&ma<=a[r])
        {
            ma=a[r];
            r--;
        }
        else if(a[l]<a[r]&&a[l]>=ma)
        {
            ma=a[l];
            l++;
        }
        else
        {
            flage=false;
            break;
        }
    }
    return flage;
}
void sove()
{
    //int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int l=0,r=n-1,ans;
    while(r>=l)
    {
        int mid=(l+r)>>1;
        if(check(mid))
        {
            r=mid-1;
            ans=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    printf("%d
",ans);
}

4.D. a-Good Stringこの問題は暴力bfsで済むので、何も言うことはありません.コードに何か書けばわかるはずです.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x & -x
#define fi first
#define se second
#define bug cout<
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
using namespace std;
const int maxn = 2e5 + 50;
const int maxm = 1.5e5+50;
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;
const ll  lnf  = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e8;
const  double pi=3.141592653589;
char s[maxn],dp[30];
int dfs(int l,int r,char ch)
{
    //if(dp[num])return dp[num];
    if(l==r)    l==r      
    {
        return ch==s[l]?0:1;
    }
    int cnt1=0,ans=0,cnt2=0;
    for(int i=l;i<=(l+r)/2;i++)
    {
        if(ch!=s[i])//       ch    ，     cnt1++，cnt1         
        {
            cnt1++;
        }
    }
    for(int i=(l+r)/2+1;i<=r;i++)
    {
        if(ch!=s[i])//       ch    ，
        {
            cnt2++;
        }
    }
    return min(dfs(l,(l+r)/2,ch+1)+cnt2,dfs((l+r)/2+1,r,ch+1)+cnt1);//  cnt1 cnt2    ch+1，  ch='b'，  ch+1='c'
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        ms(dp,0);
        cin>>n>>s+1;
        printf("%d
",dfs(1,n,'a'));
    }
    return 0;
}

E.Directing Edges昨日の试合を终えてやっとトポロジーの顺位を见て、今日他の人の题解を见てトポロジーの顺位を使って、本当にこのように巧みですか???

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x & -x
#define fi first
#define se second
#define bug cout<
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
using namespace std;
const int maxn = 2e5 + 50;
const int maxm = 1.5e5+50;
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;
const ll  lnf  = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e8;
const  double pi=3.141592653589;
vector<int>ve[maxn];
int in[maxn],n,pxun[maxn];
bool toop_sort()//      
{
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        if(!in[i])
        {
            q.push(i);
        }
    }
    int ans=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        pxun[u]=ans++;//     
        for(int i=0;i<ve[u].size();i++)
        {
            int v=ve[u][i];
            in[v]--;
            if(!in[v])
            {
                q.push(v);
            }
        }
    }
    return ans==n;
}
int vis[maxn],din[maxn],dout[maxn];
void sove()
{
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        ve[i].clear();
        in[i]=0;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&vis[i],&din[i],&dout[i]);
        if(vis[i])
        {
            ve[din[i]].push_back(dout[i]);
            in[dout[i]]++;
        }
    }
    if(toop_sort())
    {
        printf("YES
");
    }
    else
    {
        printf("NO
");
        return;
    }
    for(int i=1;i<=m;i++)
    {
        if(vis[i]||pxun[din[i]]<pxun[dout[i]])//                             ；
        {
            printf("%d %d
",din[i],dout[i]);
        }
        else
        {
            printf("%d %d
",dout[i],din[i]);
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        sove();
    }
    return 0;
}