【GPLT】L 2-025分で治める
タイトルの説明:
分けて治め、それぞれの撃破は兵家がよく使う策略の一つである.戦争では、まず敵の一部の都市を攻略し、残りの都市を孤立無援にし、それから頭を分けて撃破することを望んでいる.このため、参謀部はいくつかの打撃案を提供した.本題はプログラムを書いて、各案の実行可能性を判断してください.
説明を入力:
入力は、1行目に2つの正の整数NとM(いずれも10,000を超えない)を与え、それぞれ敵の都市の数(デフォルトの都市は1からN番号)と、2つの都市を接続するパスバー数である.その後、M行は、各行に1つの通路で接続された2つの都市の番号を与え、その間を1つのスペースで区切る.都市情報の後に参謀部の一連のスキーム、すなわち正の整数K(≦100)とその後のK行スキームが与えられ、各行は以下のフォーマットで与えられる.
このうち
出力の説明:
各シナリオについて、実行可能であれば
サンプルを入力:
出力サンプル:
問題解決の考え方:
私は最初はbool型2次元配列Edgeで隣接する都市情報を格納し、setで陥落した都市情報を記録し、isLonelyですべての都市が孤立しているかどうかを判断し、陥落していない都市が別の陥没していない都市と隣接している場合、isLonelyをfalseとマークしてすべての都市が孤立しているわけではないことを示した.しかし、コードを提出してから25分で15分しか取れず、テストポイント3、4にセグメントエラーが発生しました.これはつらいです.私はMAX 10005をdefineして、2次元配列EdgeのサイズをMAXにしました.提出した後、すべてのテストポイントにセグメントエラーが発生しました.これは、セグメントエラーが2次元配列によるものであることを示しています.先輩は2次元配列を変えてvectorに変えて隣接都市の情報を記録し、コードを提出してACにしたと言っています.set.count(X)=0とset.find(X)==set.end()の役割は同じ嗷であり,setにXがあるかどうかを判断するために用いられる.
ACコード:セグメントエラーコード:
ACコード:
分けて治め、それぞれの撃破は兵家がよく使う策略の一つである.戦争では、まず敵の一部の都市を攻略し、残りの都市を孤立無援にし、それから頭を分けて撃破することを望んでいる.このため、参謀部はいくつかの打撃案を提供した.本題はプログラムを書いて、各案の実行可能性を判断してください.
説明を入力:
入力は、1行目に2つの正の整数NとM(いずれも10,000を超えない)を与え、それぞれ敵の都市の数(デフォルトの都市は1からN番号)と、2つの都市を接続するパスバー数である.その後、M行は、各行に1つの通路で接続された2つの都市の番号を与え、その間を1つのスペースで区切る.都市情報の後に参謀部の一連のスキーム、すなわち正の整数K(≦100)とその後のK行スキームが与えられ、各行は以下のフォーマットで与えられる.
Np v[1] v[2] ... v[Np]
このうち
Np
はこの案で計画された都市数であり、後続のシリーズv[i]
は計画された都市番号である.出力の説明:
各シナリオについて、実行可能であれば
YES
を出力し、そうでなければNO
を出力する.サンプルを入力:
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 10
2 4
5
4 10 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2
出力サンプル:
NO
YES
YES
NO
NO
問題解決の考え方:
私は最初はbool型2次元配列Edgeで隣接する都市情報を格納し、setで陥落した都市情報を記録し、isLonelyですべての都市が孤立しているかどうかを判断し、陥落していない都市が別の陥没していない都市と隣接している場合、isLonelyをfalseとマークしてすべての都市が孤立しているわけではないことを示した.しかし、コードを提出してから25分で15分しか取れず、テストポイント3、4にセグメントエラーが発生しました.これはつらいです.私はMAX 10005をdefineして、2次元配列EdgeのサイズをMAXにしました.提出した後、すべてのテストポイントにセグメントエラーが発生しました.これは、セグメントエラーが2次元配列によるものであることを示しています.先輩は2次元配列を変えてvectorに変えて隣接都市の情報を記録し、コードを提出してACにしたと言っています.set.count(X)=0とset.find(X)==set.end()の役割は同じ嗷であり,setにXがあるかどうかを判断するために用いられる.
ACコード:セグメントエラーコード:
#include
using namespace std;
int main()
{
int N,M; // N, M
cin >> N >> M;
bool Edge[N+1][N+1];
memset(Edge,false,sizeof(Edge)); //
for(int i = 0; i < M; i++)
{
int x,y;
cin >> x >> y;
Edge[x][y] = Edge[y][x] = true;
}
int K; //K
cin >> K;
while(K--)
{
bool isLonely = true; //
int Np; // Np
cin >> Np;
set s; //
for(int i = 0; i < Np; i++)
{
int temp;
cin >> temp;
s.insert(temp);
}
for(int i = 1; i <= N; i++)
{
if(s.count(i) == 0) //
{
for(int j = 1; j <= N; j++)
{
if(Edge[i][j] && s.count(j) == 0) // ,
{
isLonely = false;
}
}
}
}
if(isLonely)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
return 0;
}
ACコード:
#include
using namespace std;
int main()
{
int N,M; // N, M
cin >> N >> M;
vector v[N+1];
for(int i = 0; i < M; i++)
{
int x,y;
cin >> x >> y;
v[x].push_back(y); // x y
}
int K; //K
cin >> K;
while(K--)
{
bool isLonely = true; //
int Np; // Np
cin >> Np;
set s; //
for(int i = 0; i < Np; i++)
{
int temp;
cin >> temp;
s.insert(temp);
}
for(int i = 1; i <= N; i++)
{
if(s.find(i) == s.end()) //
{
for(int j = 0; j < v[i].size(); j++)
{
if(s.find(v[i][j]) == s.end()) //
{
isLonely=false;
}
}
}
}
if(isLonely)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
return 0;
}