POJ1201
14600 ワード
Problem:Intervals Description:N個の区間をあげます.各区間にはCがあります.Cは区間に少なくともC個の数字が必要であることを示しています.今、すべての区間条件を満たすには少なくとも何個の数字が必要ですか.Solution_1:差分制約システム.まずこの問題を見て、これらの区間が重ならなければ、この問題は簡単です.しかし,そうではなく,区間や問題については,T[b]−T[a−1]>=Cと表現するのが好ましい.問題にはこのような条件がたくさんありますが、差分制約システムに似ているのではないでしょうか.そうすれば、0から区間の端点を求める最長の道に変換します.このような最も長い道はテーマの中の求めです.しかし、注意しなければならないのは、ここが最長の道を求めるのと、最短の道を求めるのとは異なり、これらの条件がある場合はだめです.このようにして、この図が連通していることを保証できないからです.問題から不等式を抽出しなければならない.そうだT[x]−T[x−1]>=0,T[x−1]−T[x]>=1である.これらの条件があれば,単純な差分制約が最長の道を求めることになり,spfaがよい.Solution_2:欲張り+樹状配列、またはさらに最適化してセットを追加して調べる.区間が順番に並べられた後,区間を1つずつ遍歴し,数値が区間右端点に置かれる方向ほど次の区間に覆われやすくなり,数値の数を減らすことができることを知っている.ここで木配列を用いるのは,[1,X]の区間を合計するためである.樹状配列は二分に基づいていることが知られているので,速度が速い.では、調査集はどうなっているのでしょうか.これも私がDiscussの中の1つの大神が使う最適化を見て、本当に目を開けて、そして集の新しい使い方を学びました.ここでは、重さの問題を解決するために集計を使用します.集計を使用しない場合は、この点に数字があるかどうかをused配列で識別する必要がありますが、集計を使用すると、searchのたびに前の点に掛けます.次のsearchでは、数字がなく、最後の点が直接見つかります.これにより,used配列を用いて後から先に遍歴する問題が完璧に解決された.
ここで注意したいのは、区間のソートですが、これまでは左端点を最初のキーワードとしてソートしていたので、ずっとWAです.その後、お風呂に入ったとき、左端の順で反例が出る可能性があることをふと思い出した.このようなデータのセットを見てください. 2 1 100 1 4 8 1
左端点で並べ替えて[1100],[4,8]を得た.上の解法では、100という点に数字を記入し、8という点に数字を記入します.これは明らかに最適ではない.右端点順に[4,8],[1100]を得た.私たちは8という点に数字を記入し、「1100」に1つの数字があることを調べたので、記入する必要はありません.そのため、最適な答えは1です.
Code(差分制約):
Code(欲張り+ツリー配列+used配列):
Code(欲張り+樹状配列+並検集):
ここで注意したいのは、区間のソートですが、これまでは左端点を最初のキーワードとしてソートしていたので、ずっとWAです.その後、お風呂に入ったとき、左端の順で反例が出る可能性があることをふと思い出した.このようなデータのセットを見てください.
左端点で並べ替えて[1100],[4,8]を得た.上の解法では、100という点に数字を記入し、8という点に数字を記入します.これは明らかに最適ではない.右端点順に[4,8],[1100]を得た.私たちは8という点に数字を記入し、「1100」に1つの数字があることを調べたので、記入する必要はありません.そのため、最適な答えは1です.
Code(差分制約):
#include 0 ,used[i]=false;
queue<int> que;
que.push(src);
de[src]=1;
used[src]=true;
dis[src]=0;
while(!que.empty()){
int pre=que.front();
que.pop();
used[pre]=false;
for(int i=head[pre];i+1;i=map[i].next){
int tmp=map[i].to;
if(dis[tmp]map[i].c){
dis[tmp]=dis[pre]+map[i].c;
if(!used[tmp]){
used[tmp]=true;
que.push(tmp);
++de[tmp];
if(de[tmp]>top)
return false;
}
}
}
}
return true;
}
int main()
{
while(cin>>m){
int a,b,c;
top=-INF;
but=INF;
I=0;
for(int i=0;i1;
while(m--){
scanf("%d%d%d",&a,&b,&c);
add_edge(a-1,b,c);
top=MAX(b,top);
but=MIN(a-1,but);
}
for(int i=but+1;i<=top;i++)
add_edge(i-1,i,0),
add_edge(i,i-1,-1);
spfa(but);
cout<return 0;
} Code(欲張り+ツリー配列+used配列):
#include return a.aint lowbit(int x)
{
return x&(-x);
}
void update(int x)
{
for(int i=x;i<=top;i+=lowbit(i))
++a[i];
}
int find(int x)
{
int sum=0;
for(int i=x;i>0;i-=lowbit(i))
sum+=a[i];
return sum;
}
int work()
{
memset(used,false,sizeof(used));
int ans=0;
for(int i=1;i<=m;i++){
int sum=find(++qu[i].b)-find(++qu[i].a-1);
if(sumint tmp=qu[i].c-sum;
ans+=tmp;
for(int j=qu[i].b;j>=qu[i].a&&tmp;j--)
if(!used[j])
update(j),used[j]=true,--tmp;
}
}
return ans;
}
int main()
{
while(~scanf("%d",&m)){
top=-1;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&qu[i].a,&qu[i].b,&qu[i].c),
top=MAX(qu[i].b+1,top);
memset(a,0,sizeof(a));
sort(qu+1,qu+m+1,cmp);
int ans=work();
printf("%d
",ans);
}
return 0;
} Code(欲張り+樹状配列+並検集):
#include return a.aint lowbit(int x)
{
return x&(-x);
}
void update(int x)
{
for(int i=x;i<=top;i+=lowbit(i))
++a[i];
}
int find(int x)
{
int sum=0;
for(int i=x;i>0;i-=lowbit(i))
sum+=a[i];
return sum;
}
int search(int x)
{
return x==p[x]? x:p[x]=search(p[x]);
}
int work()
{
for(int i=0;iint ans=0;
for(int i=1;i<=m;i++){
int sum=find(++qu[i].b)-find(++qu[i].a-1);
if(sumint tmp=qu[i].c-sum;
ans+=tmp;
for(int now=qu[i].b;tmp;--tmp){
now=search(now);
update(now);
p[now]=now-1;
--now;
}
}
}
return ans;
}
int main()
{
while(~scanf("%d",&m)){
top=-1;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&qu[i].a,&qu[i].b,&qu[i].c),
top=MAX(qu[i].b+1,top);
memset(a,0,sizeof(a));
sort(qu+1,qu+m+1,cmp);
int ans=work();
printf("%d
",ans);
}
return 0;
}