NOIP2013 提高組: 貨物輸送経路の最大最小辺問題
問題概要
無向グラフが与えられ、各辺には重みが付与されています。クエリでは2頂点間の経路における最小辺重みの最大値を求める必要があります。グラフは非連結の可能性があり、効率的な解法が求められます。
解法アプローチ
最適経路は最大ボトルネック生成木(MBST)上に存在します。MBSTはKruskal法を重み降順で適用して構築します。非連結グラフ対応のため、Union-Find ...
7月1日 17:43 投稿
2010年NOIP普及組 課題解説
問題1: 数字の出現回数のカウント
与えられた区間 $[L, R]$ 内のすべての整数について、数字「2」が合計で何回現れるかを求める問題です。
输入例:
2 22
出力例:
6
解法:
各区間内の整数を1つずつ走査し、各数字を10進数桁ごとに分解して「2」の出現回数をカウントします。
#include <iostream>
using namespace std;
int main() {
int left, right;
...
7月1日 16:28 投稿