問題
http://community.topcoder.com/stat?c=problem_statement&pm=12822&rd=15707M個のボールがあり、１からMまで順番に番号がついている。
ボールの色は最初は白。
複数のステージが与えられ、各ステージiについてL[i]番目からR[i]番目までの色を
白か黒の好きな色どちらか一色に塗る。
このとき、色の塗り方は何通りあるか求める。
解き方
・色の塗り方なので、ボールの区切りの数を求め、その２＾（区切り数）が
答えになりそう？
・サンプルを見るとこれでは失敗。
→他の人のコードをみる。
・順番に色を塗っていく、という問題文の条件を見落としていた。
・各ボールについて順番に色をぬっていくときのステージ数を上書きしていく。
・最後に残った、各ボールのステージ数の場合の数について２の累乗をとってあげればよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class LittleElephantAndIntervalsDiv1 {
public: long long getNumber(int M, vector<int> L, vector<int> R) {
int n=L.size();
int p[M+1];
memset(p,0,sizeof(p));
FORE(i,0,n)FORE(j,L[i],R[i]+1)p[j]=i+1;
set<int> s;
FORE(i,0,M+1)if(p[i])s.insert(p[i]);
long long ret=1LL;
FORE(i,0,s.size())ret*=2;
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class LittleElephantAndIntervalsDiv1 {
public: long long getNumber(int M, vector<int> L, vector<int> R) {
int n=L.size();
int p[M+1];
memset(p,0,sizeof(p));
FORE(i,0,n)FORE(j,L[i],R[i]+1)p[j]=i+1;
set<int> s;
FORE(i,0,M+1)if(p[i])s.insert(p[i]);
long long ret=1LL;
FORE(i,0,s.size())ret*=2;
return ret;
}
};