プログラマーのステップアップのアルゴリズム練習(二十四)

前言
すでに3ヶ月もアルゴリズムの文章を更新していないので、大工場の仕事環境は一歩一歩迫っていて、すべての人をますます忙しくさせます.残りの学習時間は、技術の予研、知識の面の広大さ、底の原理の理解などに用いられ、ゆっくりとアルゴリズムは娯楽の時間を占めて遊ぶしかない.これは非常に不安定で、結局4列で鶏を食べ、5列の王者を食べなければならない.今回いくつかの難題を更新し、他の問題はアルゴリズム文集を参照してください.
本文
1. Vladik and fractions
タイトルリンク
1つの数字nを与えて、3つの異なる正の整数を求めて、要求:2/n=1/x+1/y+1/z.存在しない場合は、-1を出力します.データ範囲:1<=n<=1 e 4 x,y and z(1
Examples input 3 output 2 7 42 input 7 output 7 8 56
テーマ解析:テーマは構造問題に属する.第2の例は構想を与えた:2/n=1/n+1/(n+1)+1/n(n+1)この公式に対して、基本的にすべてのnはすべて解くことができる;特に,n=1の場合,解がない場合がある.
2.Chloe and pleasant prizes
テーマリンクテーマ大意:nノードの木、1はルート;各ノードの重み値a[i];現在、木の中から2つのノードu、vを選択し、u、vと父の辺を切断し、2つのサブツリーを形成し、条件を満たすことが要求されている:1、2つのサブツリーは重ならない;2、2つのサブツリーノードの重み値と最大値.存在する場合は、ウェイト値と;出力-1は存在しません.
データ範囲:(1<=n<=2 e 5,−1 e 9
Examples input 8 0 5 -1 4 3 2 6 5 1 2 2 4 2 5 1 3 3 6 6 7 6 8 output 25 input 4 1 -5 1 1 1 2 1 4 2 3 output 2 input 1 -1 output Impossible
1つのノードに2つのサブツリーが存在する限り、解があることがわかりやすい.解がある場合、2つの最適サブツリーT 1とT 2は、いずれも点Pのサブツリーである点Pが必然的に存在する.最適サブツリーの値を維持する:dp[i]はiノードがルートであるサブツリー、サブツリーの重み値和を表す.同時に状態遷移を行う際に、新しい配列を維持する:top[i]はiノードがルートであるツリーを表し、そのすべてのサブツリーのうち、サブツリーの重み値と最大値を表す.では、ノードuおよびサブノードvについては、top[u]=max(dp[u],top[v])がある.(dp[u]はノードuをルートとするサブツリーの重み値和を表し、top[v]はuのサブツリーの最大重み値和である).また、ノードuについては、複数のサブノードvがあれば、最大2つのtop[v]を保持するだけでよい.

void dfs(int u, int fat) {
    dp[u] = a[u];
    multiset childs;
    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        if (v != fat) {
            dfs(v, u);
            dp[u] += dp[v];
            tops[u] = max(tops[u], tops[v]);
            childs.insert(tops[v]);
            if (childs.size() == 3) {
                childs.erase(childs.begin());
            }
            if (childs.size() == 2) {
                ans = max(ans, *childs.begin() + *(++childs.begin()));
            }
        }
    }
    tops[u] = max(tops[u], dp[u]);
}

3.Hongcow Builds A Nation
テーマリンクテーマ大意:図、n個の点、m個の辺を与え、そのうちk個の点がキーである.1、キー間にパスが存在しないこと、2、自環、多重辺は存在できない.質問、最大何辺まで加算できますか.
データ範囲:(1次にk個の数字で、k個のキーを示します.次にm対数値(u,v)であり、uとvの間にエッジが存在することを示す.
Examples input 4 1 2 1 3 1 2 output 2 input 3 3 1 2 1 2 1 3 2 3 output 0
テーマの解析:追加したエッジはキー間のパスを生成することができなくて、それでは1つの考え方を変えることができます:キーとすでにつながっている点に対して、1つのキーに縮小します;では、全部でkつのキーがあり、いくつかの独立点があります.sum[i]は、y=max(sum[i])と仮定して、キーiの点の数(縮点)を表す.この場合、エッジを増やすことができます.キーは自分の内部で完全な図に構築されます.すべての独立点は完全図に構成されている.独立したポイントセットと最大のキーの2つが接続されています.
最後に、既存のエッジをすべて減算します.
4.Vladik and cards
タイトルリンクタイトル大意:いくつかのカードが1行に並んでいて、上に数字が1~8があって、今最も長いサブシーケンスを見つけて、満足します:1、すべての同じ数字のカードの数とc[i]、i,j∈[1,8],|c[i]-c[j]|<=1;2、同じ数字のカードは連続しなければならない.例えば[1,1,2,2]は合法であり、[1,2,2,1]は合法ではない.最長のサブシーケンスを求める.データ範囲:(1
Examples input 3 1 1 1 output 1 input 8 8 7 6 5 4 3 2 1 output 8
テーマ解析:サブシーケンス、nは小さくて、状態も少なくて、動的な計画のように見えます.問題は、各カードはxとx+1枚を選択しなければならず、これはdp過程で制御できないことである.私たちは最も少ないx枚の選択だけを考慮して、x枚が実行可能であれば、x-1枚が実行可能で、単調性を持っていることを簡単に知っています.そこで、xの大きさを二分で決定することができ、現在の問題は最小長xを与え、xの解があるかどうかを迅速に求めることができるかどうかである.各数字がx/x+1の状態のみであり、0/1で表すことができ、1~8の数字状態が圧縮された後、255の状態があることが容易に分かる.dp[i][j]は前i個を表し、状態j(0101、1は対応するビット数を表す数字が選択された)の中でx+1を選択した最大数である.状態遷移:dp[k][t]+1][j|(1まとめ
タイトルのコードは【こちら】です.何もしないうちに、難題を解決し、達成感を楽しんでみましょう.