PROB: concom
7971 ワード
テーマはUSACOから来てテーマの翻訳はNOCOWを見ます
この問題を見て私はとても愚かで、私に自分で計算させて、私もどのように計算するべきか分かりません.そこで私はテストして、パッチを打って、更にテストして......最后に意外にもACになって、パッチは整理して、特にみっともないことはありません.
基本的な考え方は次のとおりです.題から新しい持株情報を読み込むと、parent->childの持株が多くなるため、parentの父親はparentを通じてchildを制御することができ、parentの各父親がchildを制御しているかどうかをチェックする必要がある. 読み込まれたparentがchildを制御している場合、parentはchildを通じてchildの子供を制御している可能性があります.(今から見れば、childが株を持っている限り(childがコントロールする必要はない)、parent->child->iの場合があるかもしれないが、なぜ私はコントロール関係だけを考えてACしたのか分からない.O"...すべてのtestが偶然か?それともより深い関係で等価か?) 検査の際、新たな制御関係が成立すれば、上記の2つの状況を静寂になるまで検査を続けます.
コード:
実行:
IQは申し訳ありませんが、午前中から午後を見ても、標答が何が正しいのか分かりませんでした.私は標答の考え方に従って自分で書いてみましたが、私から見れば標答と実質的な違いはありませんが、9番目の問題WAにありました.
それからついに1つの答えがあってすぐに理解しました:暴捜.直接占有率を読み込んだ後、すべてのi,jに対して、i制御jがあるかどうかをチェックします.このラウンドに新しい制御関係が追加されたら、新しい関係が発生しないまで検索します.コードはまるでbug-freeでいいですか!
複雑度:100社あれば、1ラウンドあたり100^3回の操作があり、100回検索しても我慢できます.nocowでこの同級生は最後の点0.248 sと言っていましたが、私は書くのが速くなりました.
コード:
効果:
直接占有率を読み込んだ後、コントロールする会社i,jのペアごとにdfsをします.私も大体理解している様子ですが・・・
iがjを制御していることが知られていると,iがjを制御することによって,j制御が保有するkの株式を加えることもできる.△一方、iをコントロールしていた会社はjをコントロールしていたが、これは考慮の範囲内ではなく、「iをコントロールしている会社はiをコントロールしている」と検索されたときに自然に考慮される.
もともとiがkに対して保有していた株式が50より大きくなれば、それはi,k層を循環して考えることになる.それにどうせ半分以上あるから、ここにはもう入れなくてもいい.i対kが保有している株式がさっき加算されてから50を超えたとしたら、iがkをコントロールしているのはさっき知っていたので、探し続けましょう.
1つの配列を使用すると、重複する問題が発生するはずですが、2つの配列で直接持ち株と直接+間接の複雑な持ち株を保存します.
コードもほとんどnocowのある同級生の答えに倣って書かれています.
ああやっと過ぎた、やはり暴捜より速い、最後のポイント0.014 secs.
最初の考え
この問題を見て私はとても愚かで、私に自分で計算させて、私もどのように計算するべきか分かりません.そこで私はテストして、パッチを打って、更にテストして......最后に意外にもACになって、パッチは整理して、特にみっともないことはありません.
基本的な考え方は次のとおりです.
コード:
/*
ID: ufoshen1
LANG: C++
TASK: concom
*/
#include
#include
const int maxN = 100;
int N; //
int queue[1000000][2], start, end; // control
int percent[maxN + 1][maxN + 1];
bool control[maxN + 1][maxN + 1];
bool update(int parent, int child){
// ， true
int perc = percent[parent][child];
for(int i = 1; i <= N; i ++){
if(control[parent][i]){
perc += percent[i][child];
}
}
if(perc > 50 && !control[parent][child]) return control[parent][child] = true;
return false;
}
void checkParent(int parent, int child){
//i->parent->child
for(int i = 1; i <= N; i ++){
if(control[i][parent] && !control[i][child]){
queue[end][0] = i;
queue[end ++][1] = child;
}
}
}
void checkChild(int parent, int child){
//parent->child->i
for(int i = 1; i <= N; i ++){
if(control[child][i] && !control[parent][i]){
queue[end][0] = parent;
queue[end ++][1] = i;
}
}
}
int main(){
FILE *fin = fopen("concom.in", "r");
FILE *fout = fopen("concom.out", "w");
int n, parent, child, perc;
fscanf(fin, "%d", &n);
for(int i = 0; i < n; i ++){
fscanf(fin, "%d %d %d", &parent, &child, &perc);
if(parent > N) N = parent;
if(child > N) N = child;
start = 0; end = 0;
percent[parent][child] = perc;
//parent child ， i->parent->child
checkParent(parent, child);
if(perc > 50){
control[parent][child] = true;
//parent child， parent->child->i
checkChild(parent, child);
}
while(end > start){
int newParent = queue[start][0], newChild = queue[start][1];
start ++;
if(update(newParent, newChild)){
//newParent newChild， parent->child->i i->parent->child
checkParent(newParent, newChild);
checkChild(newParent, newChild);
}
}
}
for(int i = 1; i <= N; i ++){
for(int j = 1; j <= N; j ++){
if(control[i][j] && i != j) fprintf(fout, "%d %d
", i, j);
}
}
return 0;
}
実行:
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 12036 KB]
Test 2: TEST OK [0.000 secs, 12036 KB]
Test 3: TEST OK [0.000 secs, 12036 KB]
Test 4: TEST OK [0.000 secs, 12036 KB]
Test 5: TEST OK [0.000 secs, 12036 KB]
Test 6: TEST OK [0.000 secs, 12036 KB]
Test 7: TEST OK [0.000 secs, 12036 KB]
Test 8: TEST OK [0.000 secs, 12036 KB]
Test 9: TEST OK [0.126 secs, 12036 KB]
All tests OK.
Your program ('concom') produced all correct answers! This is your
submission #10 for this problem. Congratulations!
あら捜し
IQは申し訳ありませんが、午前中から午後を見ても、標答が何が正しいのか分かりませんでした.私は標答の考え方に従って自分で書いてみましたが、私から見れば標答と実質的な違いはありませんが、9番目の問題WAにありました.
それからついに1つの答えがあってすぐに理解しました:暴捜.直接占有率を読み込んだ後、すべてのi,jに対して、i制御jがあるかどうかをチェックします.このラウンドに新しい制御関係が追加されたら、新しい関係が発生しないまで検索します.コードはまるでbug-freeでいいですか!
複雑度:100社あれば、1ラウンドあたり100^3回の操作があり、100回検索しても我慢できます.nocowでこの同級生は最後の点0.248 sと言っていましたが、私は書くのが速くなりました.
コード:
#include
#include
const int maxN = 100;
int N; //
int percent[maxN + 1][maxN + 1];
bool control[maxN + 1][maxN + 1];
int main(){
FILE *fin = fopen("concom.in", "r");
FILE *fout = fopen("concom.out", "w");
int n, parent, child, perc, flag = 1, total;
for(int i = 0; i <= maxN; i ++) control[i][i] = true; //
fscanf(fin, "%d", &n);
for(int i = 0; i < n; i ++){
fscanf(fin, "%d %d %d", &parent, &child, &perc);
if(parent > N) N = parent;
if(child > N) N = child;
percent[parent][child] = perc;
if(perc > 50) control[parent][child] = true; // 50%
}
while(flag){
flag = 0; //
for(int i = 1; i <= N; i ++){
for(int j = 1; j <= N; j ++){ // i j
if(control[i][j]) continue; // ，
total = 0;
for(int k = 1; k <= N; k ++){
if(control[i][k]) total += percent[k][j];
}
if(total > 50){
control[i][j] = 1;
flag = 1;
}
}
}
}
for(int i = 1; i <= N; i ++){
for(int j = 1; j <= N; j ++){
if(control[i][j] && i != j) fprintf(fout, "%d %d
", i, j);
}
}
return 0;
}
効果:
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 4224 KB]
Test 2: TEST OK [0.000 secs, 4224 KB]
Test 3: TEST OK [0.000 secs, 4224 KB]
Test 4: TEST OK [0.000 secs, 4224 KB]
Test 5: TEST OK [0.000 secs, 4224 KB]
Test 6: TEST OK [0.000 secs, 4224 KB]
Test 7: TEST OK [0.000 secs, 4224 KB]
Test 8: TEST OK [0.014 secs, 4224 KB]
Test 9: TEST OK [0.070 secs, 4224 KB]
All tests OK.
Your program ('concom') produced all correct answers! This is your
submission #21 for this problem. Congratulations!
dfs
直接占有率を読み込んだ後、コントロールする会社i,jのペアごとにdfsをします.私も大体理解している様子ですが・・・
iがjを制御していることが知られていると,iがjを制御することによって,j制御が保有するkの株式を加えることもできる.△一方、iをコントロールしていた会社はjをコントロールしていたが、これは考慮の範囲内ではなく、「iをコントロールしている会社はiをコントロールしている」と検索されたときに自然に考慮される.
もともとiがkに対して保有していた株式が50より大きくなれば、それはi,k層を循環して考えることになる.それにどうせ半分以上あるから、ここにはもう入れなくてもいい.i対kが保有している株式がさっき加算されてから50を超えたとしたら、iがkをコントロールしているのはさっき知っていたので、探し続けましょう.
1つの配列を使用すると、重複する問題が発生するはずですが、2つの配列で直接持ち株と直接+間接の複雑な持ち株を保存します.
コードもほとんどnocowのある同級生の答えに倣って書かれています.
#include
#include
#include
const int maxN = 100;
int N; //
int percent[maxN + 1][maxN + 1];
int cplxPercent[maxN + 1][maxN + 1];
void dfs(int i, int j){
for(int k = 1; k <= N; k ++){
if(cplxPercent[i][k] <= 50 && k != i){
//i -> j -> k
cplxPercent[i][k] += percent[j][k];
if(cplxPercent[i][k] > 50) dfs(i, k);
}
}
}
int main(){
FILE *fin = fopen("concom.in", "r");
FILE *fout = fopen("concom.out", "w");
int n, parent, child, perc, flag = 1, total;
fscanf(fin, "%d", &n);
for(int i = 0; i < n; i ++){
fscanf(fin, "%d %d %d", &parent, &child, &perc);
if(parent > N) N = parent;
if(child > N) N = child;
percent[parent][child] = perc;
}
memcpy(cplxPercent, percent, sizeof(percent));
for(int i = 1; i <= N; i ++){
for(int j = 1; j <= N; j ++){
if(cplxPercent[i][j] > 50) dfs(i, j);
}
}
for(int i = 1; i <= N; i ++){
for(int j = 1; j <= N; j ++){
if(cplxPercent[i][j] > 50 && i != j) fprintf(fout, "%d %d
", i, j);
}
}
return 0;
}
ああやっと過ぎた、やはり暴捜より速い、最後のポイント0.014 secs.