序文
ブルーブリッジカップは、企業と大学をつなぐ主要な大会として、主要大学で高く評価されており、大学期間中の受賞も非常に高く、個人の能力を高く評価しています。ブルーブリッジカップ大会の大会も熾烈です。賞品を獲得するには、優れた能力だけでなく、正しい方法で知識のポイントや難しい部分を理解する必要があります。これらは勝つための基本的な必需品です。以下の著者は、過去3年間のブルーブリッジカップグループBの質問の知識ポイントと難しさを分析しています。
難易度分析
これらの質問は、難易度が低、中、高の3つのレベルに大別されます。難易度が低いのはサブ質問であり、ほとんどが空欄の質問です。回答するときにのみ回答を送信する必要があります。
まず、難易度の低い質問についてお話ししましょう。この種の質問は、通常、空白を埋めるために数字または文字列を送信するだけで済みます。これらはすべて、受験者の一般的な論理的思考能力と、一般的な数学およびプログラミングの応用に関するものです。
中程度の難易度が最大の割合であり、個別の空欄の質問と多数のプログラミングの質問で構成されています。この難易度の質問は、受験者の時間を多く消費し、対応するプログラミングの質問に障害があるため、試験の各質問にスコアが付けられます。ギャップ。この障害は通常、時間の複雑さの最適化に反映されます。時間の複雑さが低いほど、この質問のスコアは高くなります。たとえば、19年間でグループBの5番目の質問を取り上げて、増加するトリプレットを説明します。トピックは次のとおりです。
与えられた3つの整数配列
A = [A1, A2, ... AN],
B = [B1, B2, ... BN],
C = [C1, C2, ... CN]，
トリプル（i、j、k）がいくつ満たすかを数えてください。
1 <= i, j, k <= N
Ai < Bj < Ck
この質問を見て、激しく解決するために3層のforループが頭に浮かびましたが、これはスコアの3分の1しか得られません。完全なスコアを取得したい場合は、時間の複雑さを抑えた別のサイクルが必要です。この質問はフルポイントを取得するには、2つの2レベルのforループを使用します。
最後に、難しい質問があります。これらの質問は、一般的に国内および国際大会に参加している学生のために用意されています。これらの質問の特徴は難しいです。しかし、それを解決することは不可能ではありません。アルゴリズムの包括的な使用と問題の包括的な分析には、限られた時間内に問題を完了する機会があります。たとえば、2020年のシミュレーションコンテストでは、9番目の質問シーケンスが重要です。この質問にはDFSとBFSの習熟度が必要であり、これに基づいて、メモリ検索を使用するとサンプルデータの80％を渡すことができます。
知識分析
著者は18年、19年のBグループ、20年のシミュレーション質問を数えました。基本的に、最初の2つの質問は単純なサブアイテム、5と6の質問は中難易度、最後の3つの質問は高難易度の質問であると判断できます。
難易度の低いトピックは、さまざまな単位変換、時間変換、統計的予測、その他の難易度の低い知識などの知識ポイントをカバーしているため、それらについては詳しく説明しません。
中程度の難易度は、論理的思考を必要とする多くの問題をカバーし、さまざまなアルゴリズムの要件は高くありません。この難易度の問題のほとんどは、暴力的な列挙によって解決できますが、forループには3つ以上の層があり、最適化する必要があります。次に、19年の迷路のように、DFSとBFSの2つの検索アルゴリズムも頻繁にテストされます。ハッシュテーブルとダブルポインタも一般的なテストであり、さまざまな並べ替えアルゴリズムと貪欲なアルゴリズムもあります。これらはトピックのこの部分によく登場します。
難しいトピックの中には、DFSとBFSの2つの主要な検索アルゴリズムも頻繁に登場します。動的プログラミング、バックトラッキングアルゴリズムなどに加えて、分割と征服の戦略を含むトピックもあり、他の考え方と組み合わされています。 、フルスコアを取得するのは難しいため、最初の2つの難しい質問に焦点を当てる必要があります。
要約すると、各難易度の知識ポイントには主に次のものが含まれます。
（1）低：一般的な数学的知識と論理的思考
（2）中：列挙、DFS、BFS、ハッシュテーブル、ダブルポインター、貪欲なアルゴリズム、主要な並べ替えアルゴリズム
（3）高：DFS、BFS、動的プログラミング、バックトラッキングアルゴリズム、分割および征服戦略
総括する
普通の学生はブルーブリッジカップに参加して、低難易度と中難易度の問題を解決するために最善を尽くすことができます。それでは、中難易度の時間の複雑さの問題をどのように克服するのでしょうか。リートコードを探すだけです。時間の複雑さは最適ではなく、提出もされません。上記の演習は非常に効果的です。
END
チーフエディター|ワンナンラン
担当編集者|劉志波
Recommended Posts