Codeforces Round#656(Div.3)まとめ

テーマリンクの感じ:今回は全部で4つの問題を作りました.自分の思考はまだそんなに柔軟ではないと感じています.A題で30分も詰まった(恥ずかしい).20分前に見たA問題は考えがあっても考えがないと感じて、いっそBを直接見て、2分ACになって、それからまた2分Aを見て、やはり書けなくて、またCを見て、10分ACになって、この時に目Dを見て、出すべきことが速くないと感じて、それから落ち着いてAを見て、何分ACをよく分析しました.この時はまだ1時間で、まず一目見ましたE題、1つの図論題、最初の考えは集判環を調べることでしたが、半分まで書いて私がいくつかの細部を処理できないことに気づいて、それからDを見ることを放棄しました.D問題は私に貪欲な感じがして、分析してみると、現在の決定が次の決定に影響を与えることが分かったので、貪欲は否定しました.では暴力とdpしか残っていませんが、dpではすべての状況を遍歴することは避けられません.dpより直接暴力をして、検索を書いて、データの量が少し大きくて、タイムアウトを恐れています.10分間解析したところ,停止条件まで再帰すると,2 e 5のデータ量は20層以上再帰することが多く,この複雑さは許容でき,O(n l o g n)O(nlogn)O(nlogn)O(nlogn)の複雑さはACに渡されることが分かった.すぐにD題の良い水を感じます...そしてそのまま寝ました.まとめ:一部の図論題は系統的な訓練がないためかもしれませんが、多くの細部は私には処理できません.それから時間の複雑さの分析も重要です.分析しなければ、そのD問題は私には提出しません.少し分析してみると可能です.
A題
あなたに3つの数x,y,zをあげます.3つの数a,b,cを求めさせます.条件は、x=max(a,b)、y=max(a,c)、z=max(b,c)である.この3つの数が存在してyesを出力してこれらの本を出力して、さもなくばno構想:小さい分析の1波、出力の順序が任意なため、私達は自分の意志で構造するだけでいいので、xyzを大きいから小さいまで並べ替えます.まずxはab最大値,yはac最大値であり,いずれもaを含み,aが最大であると仮定するので,xはyに等しいに違いない.bとcは必ずaより小さいので、zをbに与えると、cは任意に最小値を取ればいいので、1を取ればokになります.最初はこの問題に引っかかっても自分で分析できなかっただろう.

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        if((x>y&&x>z)||(y>x&&y>z)||(z>x&&z>y))
        {
            cout<<"NO"<<endl;
            continue;
        }
        if(x<y) swap(x,y);
        if(x<z) swap(x,z);
        if(y<z) swap(y,z);
        int a,b,c;
        a=x;b=z;c=1;
        cout<<"YES"<<endl;
        cout<<a<<" "<<b<<" "<<c<<endl;
    }
    return 0;
}

B題
あなたに2つのすでに互いに挿入した数字のシーケンスをあげて、あなたに最も原始的なその数字のシーケンスを求めさせます.考え方:これは簡単です.これらの数字のシーケンスが固定されているので、左から右にスキャンして、現れたことのない数字について答えに投げて、この数字が現れたことをマークします.

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
int a[N],ans[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        map<int,int>f;
        int n,cnt=0;
        cin>>n;
        for(int i=1;i<=2*n;i++) cin>>a[i];
        for(int i=1;i<=2*n;i++)
        {
            if(!f[a[i]])
            {
                f[a[i]]=1;
                ans[++cnt]=a[i];
            }
            if(cnt==n) break;
        }
        for(int i=1;i<=cnt;i++) cout<<ans[i]<<" ";
        cout<<endl;
    }
    return 0;
}

C題
あなたに1つのシーケンスをあげて、少なくともどれだけの接頭辞の要素を取り除いて1つの“良いシーケンス”を得ることができますかを聞きます.「良いシーケンス」は、1つのシーケンスの左右から毎回数を取ることができ、1つの非減算シーケンスを取り出すことができれば「良いシーケンス」と定義されます.構想:まずどのようなシーケンスが良いシーケンスと呼ぶことができるかを分析し、まずこのシーケンスがb 1,b 2,...bm...bnであると仮定する.では、bmは最大の要素であり、左から右に非減算シーケンス、bmからbnに非増幅シーケンスであるに違いない.なぜか、b 2を仮定すると

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
int a[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        int right=n;
        while(a[right-1]>=a[right]&&right>=1) right--;
        //cout<
        while(a[right-1]<=a[right]&&right>=1) right--;
        int ans=right-1;//                   。
        if(ans==-1) ans=0;
        cout<<ans<<endl;
    }
    return 0;
}

D題
説明しにくいですね.まず文字列をあげて、最小限の操作で彼を「a-良い文字列」にします.では、「a-良い文字列」とは何でしょうか.前半は全部aで、後半は「(a+1)-良い文字列」を選択して、順番に押していきます.具体的にはテーマの説明を見てみましょう.考え方:一見欲張りに見えるが、現在最も必要な文字を持つ側を指定文字に変えるたびに、これはだめで、後効性がないことを満たしていない.だからdpと暴力を考えて、しかし私达はすべてdpも1种の比较的に优雅な暴力と言えることを知っていて、dpより直接深く探します.だから私たちはすべての状況を列挙することができて、最後に最小値を取ればいいです.具体的にはコードがはっきり書いてあります.この問題は私たちに教えてくれたのは構想ではなく、複雑度の分析であり、分析しないのは一見タイムアウトコードに似ているが、実際にはそうではない.2 e 5のデータ量は、1回に半分ずつ再帰され、最大20層以上のnlognの複雑さは完全に可能である.

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
char s[N];
int solve(int l,int r,char m)
{
    if(l==r)
    {
        if(s[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(s[i]==m) left++;
    for(int i=mid+1;i<=r;i++) if(s[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()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        char m='a';
        cin>>n;
        for(int i=1;i<=n;i++) cin>>s[i];
        int ans=solve(1,n,m);
        cout<<ans<<endl;
    }
    return 0;
}

E題
nつの頂点mの辺の図をあげて、その中のいくつかの辺は逆方向ではありませんて、残りの辺は方向があって、あなたにすべての辺に対して1つの方向を与えて、最終図が自環を形成することができないことを要求します.問題解