UESTC 1262 Memory暴力法

3107 ワード
ACM ICC. OJ uestc 法則を求める 暴力法
Memory
Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit  Status
小xと小hは良い盆友で、小hは小体から弱く病気が多く、しかもとても忘れっぽいので、自分が普段飲んでいるn本の薬を小xたちに保管しました.
ある日霧都のpm 2.5爆表により、小hの慢性呼吸器疾患が再発したが、小xが薬瓶を取り出したところ、異常が発見された.
小xは今n本の薬があって、1本の薬の中に無限の錠剤があって、1錠の薬の重量は厳格に1グラムに等しいです.しかし、あら探しの小xはn本の薬のうち2本の薬の錠剤が重量的に不合格であることを発見した.
はい、不合格の錠剤は正常な錠剤より0.1 g軽いです.
小xは現在電子称(具体的な重量を示すことができる)があり、時間が緊急であるため、小xは1本の薬からbi(1≦bi)を選択することにした.  つの錠剤を量って、それらの総和を量って、しかも一回だけ量って、それによって探します
この2本の不合格薬の番号を出します.
ここで、最小辞書順のシーケンスb( biからなる)はいくらですか.
Input
1行1個の整数n(2≦n≦52)
Output
1行n個の数字で、2つの間はスペースで区切られており、末尾にスペースがないことに注意してください.
Sample input and output
Sample Input
Sample Output 
3
1 2 3

Hint
若し  a1,a2..an  比  b1,b2..bn   辞書の順序が小さいと、必ず存在します.  j(1≤j≤n)    にさせる  aj  <  bj  すべてのi例の解釈:5.7 gと呼ぶと、1本目と2本目が不合格になる.5.6 gなら、1本目と3本目が不合格です.
5.5 gなら2本目と3本目が不合格です.
Source
第7回ACM趣味プログラミングコンテスト第3戦(公式戦)E
My Solution
構想はすでにi-1の条件を満たす数があって、更にiの数を加えて入って依然として満足して、任意の2つの数の和は他の2つの数と等しくありません.
前の試合の時はフィボナッチ数列かと思っていたのですが、先輩がフィブではないと宣言したのを終えて、確かに当時筆者自身もデータが大きい時にi-1個目とi個目の数がかなり違うと感じましたし、
何億もの差がある(n<=52)ので,jがFibのi番目の数よりも小さい可能性が高いが,条件も満たす.
当時は自分が漏らしたと思っていたので、確かによく反省しなければなりませんね.
それでは暴力法を使うのはやはり比較的に良い選択で、ほほほ、暴力法はもともととても良いです.
sum[i][j]はi番目の数とj番目の数の和を表す.どうせn<=52なら大丈夫
まずans[i]のiの各iを処理し、jからインクリメントし、サブブロックx=i sum[x][前の数]を更新し、マトリクス全体をforforでスキャンします.もちろん、x-1行までです.
时を止めて、自分の行をスキャンすることはできません.もし真ん中に直接returnが現れたら、これも関数が直接中にネストされているメリットで、1つのreturnが直接何層もジャンプしますfor.
また、sum[i][j]のほとんどのsum[i]の後ろの部分は処理されていないかもしれませんが、よくスキャンされますが、アルゴリズムを簡潔に理解するためには、ここでは気にしないでください.
memsetを覚えていればいいのに、どうせ0ばかりだから、掃除したほうが健康だ.私たちが探しているのは同じ和があるかどうかで、後ろの数の和はどうして0と等しいのだろうか.☺,(結局n<=52で、一発渡して、タイムアウトしてから直して、
速くないと普通はタイムアウトできないので、気にしないでください.
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int sum[56][56],ans[56],n;

inline bool judge(int x,int y)              //            ，       。
{
    for(int i=1;i<x;i++){
        sum[x][i]=y+ans[i];
        for(int k=1;k<x;k++){              //k    x，    
            for(int l=1;l<x;l++){          //     n，  ，          x ，    n     ，          
                if(sum[x][i]==sum[k][l]) return false;
                //cout<<sum[k][l]<<" ";
            }
            //printf("
");
        }
    }
    return true;
}

int main()
{
    scanf("%d",&n);
    memset(sum,0,sizeof(sum));
    if(n==2) printf("1 1");
    else if(n==3) printf("1 2 3");
    else{
        ans[1]=1;ans[2]=2;ans[3]=3;
        sum[1][2]=3;sum[1][3]=4;sum[2][3]=5;

        printf("1 2 3");
        for(int i=4;i<=n;i++){
            for(int j=ans[i-1]+1;;j++){
                if(judge(i,j)){
                    ans[i]=j;
                    printf(" %d",j);
                    break;
                }
            }
        }
    }
    return 0;
}

ありがとう