SCOI 2010ゲーム
1478 ワード
Description
最近あるゲームにはまって、彼は多くの装備を持っています.各装備には2つの属性があります.これらの属性の値は[1,10000]の間の数で表しています.彼がある装備を使う時、彼はこの装備のある属性しか使えません.そして各装備は一回までしか使えません.ゲームは最後まで進み、究極のボスに遭遇しました.この究極のボスはおかしいです.彼を攻撃する装備の属性値は1から連続して増加して攻撃しなければならないです.つまり、最初はある属性値が1の装備でボスを攻撃し、ある属性値が2の装備でボスを攻撃し、ある属性値が3の装備でボスを攻撃するしかないということです.今lxhgww彼が最大何回連続してボスを攻撃できるかを知りたいです.
Input
入力の最初の行は整数Nで、lxhgwwはN種の装備を持っています.次のN行はこのN種の装備についての説明です.1行に2つの数字があり、i番目の装備の2つの属性値を表しています.
Output
1行を出力して、1つの数字を含んで、lxhgwwが最大連続攻撃できる回数を表しています.
Sample Input
3 1 2 3 4 5
Sample Output
2
ベント
【データ範囲】30%のデータに対して、N<=1000は100%のデータに対して、N<=100000を保証します.
一目で二分割です.一つの二分割図のコースに注意してください.一番大きな整合の意味はこの点を選んだ後、その整合点ももう選ばれなくなりました.
似たような問題はHUNOI 2006スーパーヒーローです.
最近あるゲームにはまって、彼は多くの装備を持っています.各装備には2つの属性があります.これらの属性の値は[1,10000]の間の数で表しています.彼がある装備を使う時、彼はこの装備のある属性しか使えません.そして各装備は一回までしか使えません.ゲームは最後まで進み、究極のボスに遭遇しました.この究極のボスはおかしいです.彼を攻撃する装備の属性値は1から連続して増加して攻撃しなければならないです.つまり、最初はある属性値が1の装備でボスを攻撃し、ある属性値が2の装備でボスを攻撃し、ある属性値が3の装備でボスを攻撃するしかないということです.今lxhgww彼が最大何回連続してボスを攻撃できるかを知りたいです.
Input
入力の最初の行は整数Nで、lxhgwwはN種の装備を持っています.次のN行はこのN種の装備についての説明です.1行に2つの数字があり、i番目の装備の2つの属性値を表しています.
Output
1行を出力して、1つの数字を含んで、lxhgwwが最大連続攻撃できる回数を表しています.
Sample Input
3 1 2 3 4 5
Sample Output
2
ベント
【データ範囲】30%のデータに対して、N<=1000は100%のデータに対して、N<=100000を保証します.
一目で二分割です.一つの二分割図のコースに注意してください.一番大きな整合の意味はこの点を選んだ後、その整合点ももう選ばれなくなりました.
似たような問題はHUNOI 2006スーパーヒーローです.
#include
using namespace std;
const int Maxn=1000005;
struct Edge{
int cnt,h[Maxn],to[Maxn*2],next[Maxn*2];
inline void add(int x,int y){
next[++cnt]=h[x];to[cnt]=y;h[x]=cnt;
}
}e;
#define to e.to[p]
bool vst[Maxn];
int my[Maxn];
int top,s[Maxn];
bool findpath(int x){
for(int p=e.h[x];p;p=e.next[p])if(!vst[to]){
vst[to]=1;s[++top]=to;
if(!my[to]||findpath(my[to])){
my[to]=x;
return 1;
}
}
return 0;
}
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;++i){
int x,y;scanf("%d%d",&x,&y);
e.add(x,i),e.add(y,i);
}
for(int i=1;i<=10001;++i){
for(int j=1;j<=top;++j)vst[s[j]]=0;
top=0;
if(!findpath(i)){
cout<