*[topcoder]LittleElephant AndIntervalsDiv 1
1327 ワード
http://community.topcoder.com/stat?c=problem_statement&pm=12822&rd=15707
初めてC++で提出しました.大変でした.まず、後ろから前に掃くことができると思います.最後のカバーの色だけ有効です.それから線分で作りたいです.mapで線分を記録します.そして勉強になりました.boundは要素が挿入されている位置を探して、**it==この要素を返します.endかもしれません.cp博士は普通パワーを得て境界を処理します.同時に+-を使います.ここはmapを使うのがよくないです.前の問題はmergeを使わないからです.ここでmergeを作るなら、大きな線分が連続してmergeの多い線分になるかもしれません.そして、問題解を見て、線分は全く使わないことに気づきました.小さいボールは一つのA[i]で表して、シンプルな線分で染色すればいいです.最後に1 LL＜countでpowを作ります.
初めてC++で提出しました.大変でした.まず、後ろから前に掃くことができると思います.最後のカバーの色だけ有効です.それから線分で作りたいです.mapで線分を記録します.そして勉強になりました.boundは要素が挿入されている位置を探して、**it==この要素を返します.endかもしれません.cp博士は普通パワーを得て境界を処理します.同時に+-を使います.ここはmapを使うのがよくないです.前の問題はmergeを使わないからです.ここでmergeを作るなら、大きな線分が連続してmergeの多い線分になるかもしれません.そして、問題解を見て、線分は全く使わないことに気づきました.小さいボールは一つのA[i]で表して、シンプルな線分で染色すればいいです.最後に1 LL＜countでpowを作ります.
#include <set>
#include <vector>
using namespace std;
class LittleElephantAndIntervalsDiv1
{
public:
long long getNumber(int M, vector <int> L, vector <int> R);
};
long long LittleElephantAndIntervalsDiv1::getNumber(int M, vector <int> L, vector <int> R)
{
vector<int> color(M+1, -1);
for (int i = 0; i < L.size(); i++)
{
for (int j = L[i]; j <= R[i]; j++)
{
color[j] = i;
}
}
set<int> result;
for (int i = 1; i <= M; i++)
{
if (color[i] != -1)
{
result.insert(color[i]);
}
}
return 1LL << result.size();
}