[POJ 3922]Now解題レポート

【テーマ説明】過去から帰ってきてから、あなたはまた未来に興味を持っています.あなたは時空ビザを取りに行きますが、未来に行ける人はIQが高い必要があると言われています.だから、IQをテストするためにゲームをする必要があります.ゲームのルールは以下の通りです:1.石の山の数がNの石の山があって、二人は交代で取って、最後に取れない人は負けます.あなたは先手で、最初のステップで石を全部取ることはできません.前の人選の石の数をXにすると、今回取った石の数はX*Kを超えてはいけません.あなたが勝つかどうか、そしてどのように勝つかを知る必要があります.【入力フォーマット】第1行の正の整数Tは、テストグループ数の下のT行を表しています.各行の2つの整数は、NとKを表しています.そうでなければ最小の第1ステップで取った石の数を出力し、中間にスペースがあることに注意【例】Sample Input 5 16 1 11 1 32 2 34 2 19 3 Sample Output Case 1:lose Case 2:1 Case 3:3 Case 4:lose Case 5:4【備考】10%のデータに対して、N<=100、K<=2が30%のデータに対して、N<=10^8、K<=3が100%のデータに対して、2<=N<10^8、K<=10^5、T<=200
この問題はとても良い問題で、私はそれをすることができて本当にラッキーです!その正確性を理解するために、私は国家合宿チームの論文を参照して、この問題が2002年から合宿チームの論文の中に現れていることを発見して、その時その時間の複雑度はO(N 3)(09年の合宿チームの論文の言う)で、それから09合宿チームの論文の中で、その時間の複雑度はO(N)まで推進しました;現在その時間複雑度はO(logK+1 KN)であり,この問題に対してこれは被カード定数の時間複雑度であることが分かった.しかしデータ水のため..
神題の問題解として、ネット上の問題解(推定はすべて写したもの)はTMが型で、全く分からない.私はここで比較的厳格な構想と証明を与えました(これは私が1日かけてやっと理解したのです).
まず、繁を簡にして、K=1の状況を考えます:構想がありませんか?時計を打つ!違うNを打って、最終的な答えはいくらですか.N=2 iでは必ず負けることが分かった.
そして、なぜなのか考えてみましょう.これは明らかにバイナリと関係があるので、私たちはバイナリを回して考えます:1つの数を減らして私たちはそれをいくつかの2 iを減らしたと見なします.では、私たちは高さから低さまでこれらの1を減らして、1つの1に対応する減算ビットが1であれば、直接減算します.一方、1つの1に対応する被減算ビットが0であれば、前の1の位置を0にすることに相当し、そこからこのビットまでが1になる.すなわち、0から減らすと1は小さくならず、全ての石を取るための必須条件は、石数の2進数のうちの1の総数が0である.ゲームである以上、Aが取るたびに、Bがどのように取っても、0位から減らすしかないはずだ.これは明らかに容易で、Aがlowbitを取るたびに、Bが減らした最低位は必ず1つ現れるので、Aは必ずlowbitを取ることができます.2 iがだめなのは、Aが初めてlowbitを取れず、状況が逆転したからだ.メーターを打つと、確かにlowbitで、私たちの結論を確認しました.
私たちがK=1を作ったら、1、時計を打つことを考えています.△時計をばかにしないでください.これはとても重要なテクニックです.2、4つのことを証明します:1ある取法によって、Aは毎回1つの値を取ることができます;そうしてBに取れない数を残したり、Aが石を全部取ったりします.②この値は石の数が正であれば必ず存在する.③この取り方は唯一です.(これは関係ないように見える問題ですが、後の証明でこの問題の本当のポイントであることがわかります)④Aは毎回必ずこの値を取ることができます.
そしてK=2の状況を考え始めました.打表発見、必敗態はフィボナッチ.この問題について説明します.(以下の記述では、フィボナッチ数列は1をはじめ2を次項とする)
まず紹介します.ジケンドフの引理です.任意の正の整数は、フィボナッチ数列のいくつかの不連続項(項を含む)の和として必ず表される.この定理は非常に玄妙に見えるが、実際には2つの簡単な事実の重ね合わせにすぎない.時には形式上の証明は必ず少なくないが、私は非形式の証明が定理の魂の所在を明らかにすることができると思って、大段の記号と論理の移転は往々にして最も肝心な突破が隠されている.明らかに1,2(フィボナッチ数列の最初の2つ)はフィボナッチ数列の項目で表すことができるので、1を設定してもいいです.i-1は、いずれもフィボナッチ数列のいくつかの項目で表すことができる.fjを最大i以下のフィボナッチ項とする.すなわち、fj≦ifi−2(最初の項は1、次の項は2)であるため、fi>2∗fi−2、すなわちフィボナッチ数列におけるいくつかの不連続項の比は2より大きい.つまり、フィボナッチの数列にない整数をフィボナッチのバイナリ=ジケンドフ分割の形式に書くことができ、K=1のようなことが起こります.すべてのジケンドフ分割の最小最小最小項目を取り出すだけです.次に,実際には任意の整数のジケンドフ分割が唯一であることを説明する.
3 iについては,フィボナッチ数列における数で分解しようとし,連続項を選択できないという原則に基づいているが,iがfjでしか分解できない場合,上述した数学的帰納法/DPの方法に基づいてジーケンドフ分解の一意性を証明しやすいことは明らかである.iがfjを選択しなければ,残りのfibonacci数で得られる最大の和は明らかにfj−1から前へジャンプして1(パリティを問わず1に達する)まで選択されるが,この最大和はいくらであるか.明らかに、これは1つの項目があるが、それに1つを加えるだけで、それはぱちぱちと1つの項目を合成する--fj、つまり、fjを選ばなければ、私たちは最大でfj−1しかできない.つまり、fjは私たちの唯一の選択であり、ジケンドフ分解の唯一の選択である.④(この命題はフィボナッチ数列にとって様々な証明方法があるが,ここでは高次元に広がりやすいものを紹介する)AとBのゲーム,Aの必勝を考えると,あるラウンドでBがyに直面し,yのジケンドフが最も小さいものをfiとし,今回Bがx,y−xのジケンドフが最も小さいものをfjとした.一方、fj>2 xであれば、fjが2倍より大きいxのジケンドフ分割の最大項、すなわちxのジケンドフ分割はy−xのジケンドフ分割と単純に合併してyを得ることができ、すなわちyのジケンドフ分割の最小項そして私たちはジケンドフの定理とその推論を高次元に広めようとした.ジーケンドフの定理の証明過程を考慮すると,fi=fi−1+fi−2をfi=fi−1+fk|Kすなわち,本来fiは2つのfi−1とその前の項を組み合わせたものであったが,現在ではfi−1と最小fi−1 Kに置き換えられている.上記の4点の証明は、ほとんど大きな変化をしなくても、新しい数列に完全に適用できることが簡単にわかります.しかも十分に厳格です.
最後に時間の複雑さの問題を分析してみましょう.これはほとんど明らかです.明らかに前の項目から後の項目まで、少なくともK+1 Kを乗じなければならないが、N以下のすべての項目を作る必要がある.だから最后の时间の复雑さはO(TlogK+1 KN)≒2∗108で、定数は飞ばされて、极限のデータの话はどのようにすべて1.0を调べますか?秒です.またコードが異常に簡単なため、定数最適化の空間が全くなく、非常に卵痛を引き起こす.でも.出題者の怠惰の法則によれば,出題者がランダムなデータを出す可能性はかなり大きい.ランダムデータであれば,2,0.5 sの差を少なくすることが望ましい.事実は、確かにそうです.の
もう一つの推数列の方法は2つの配列を作ることであり、実際にはこのような繰返しと互いに押し出すことができ、書くのが面倒である.ここではもう余計なことは言わない.
Code:

#include<cstdio>
int A[1000000];
inline int in(){
    char c=getchar();
    int x=0;
    while(c<'0'||c>'9')c=getchar();
    for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';
    return x;
}
int main(){
    int i,N,K,tot,p;
    A[1]=1;
    for(int T=in(),t=1;t<=T;++t){
        N=in(),K=in();
        for(tot=2,p=1;A[tot]<=N;){
            while((long long)A[p]*K<A[tot])++p;
            A[tot]=A[tot++]+A[p];
        }
        printf("Case %d: ",t);
        if(A[--tot]==N)puts("lose");
        else{
            while(N!=A[tot]){
                N-=A[tot];
                while(N<A[tot])--tot;
            }
            printf("%d
",N);
        }
    }
}

この問題が私に与えた収穫は:1奇妙なDP、ゲーム理論などに対して、時計を打って法則を探して、更に法則を証明しようとして、簡単に高次元に普及しました.②DPの証明への応用(DP->数学帰納法):第1項の成立を証明する;前のn項が成立すれば,次の項も成立することを証明する.③複雑な問題は手がつけにくいように見えるが、実際には簡単なことを考えておけば、どんなに複雑な問題でも解決できる.