Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2013-12fa52e2
この記事にトラックバックする(FC2ブログユーザー)

UVa 12011 - Complete the Set (この記事を編集する[管理者用])

Source

Celebration for the 106th Anniversary of Fudan University (1905-2011) & Warmup for ACM/ICPC 2011 World Finals (2011-05-15) (blog)
UVa 12011

問題概要

0以上2^16未満の整数の集合が与えられる.
OR,AND演算で閉じるためには,最小でいくつの要素を追加すればよいかを求める問題.

解法

正しいのかどうかよく分からない回答で通った.
まず,入力の全部のORを取ってできる数字,ANDを取ってできる数字が入ってなければ追加する.
後は,全ての数字に対して作れるかどうかを判定する.
異なる2桁のビット情報を見て,それと一致するのがもともとの集合に含まれてなければ作れない,それ以外は作れる.
なので,全ての桁の組に対して出現するビット情報を最初にメモしておく.
O(16^2*2^16).

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2013-12fa52e2
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。