Codeforces ラウンド #278 (ディビジョン 1) 問題解決 report_html/css_WEB-ITnose

質問 A: モンスターとの戦い

列挙 + 二分法

各要素のデータ範囲は 100 しかないため、列挙を使用し、血液量については二分法を使用し、結果が実行可能かどうかを判断できます。

コードは次のとおりです:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64const int INF=0x3f3f3f3f;int hy, ay, dy, hm, am, dm;int bin_search(int a, int d){        if(d>=am) return hy;        int low=0, high=100000, mid, ans, c;        c=(hm+(a-dm-1))/(a-dm);        while(low>1;                if((mid+am-d-1)/(am-d)>c) {                        ans=mid;                        high=mid-1;                }                else                        low=mid+1;        }        return ans>hy?ans:hy;}int main(){        int h, a, d, i, j, min1, z;        while(scanf("%d%d%d",&hy,&ay,&dy)!=EOF) {                min1=INF;                scanf("%d%d%d",&hm,&am,&dm);                scanf("%d%d%d",&h,&a,&d);                for(i=0;i  問題 B: ストリップ <br><p> </p> 線分ツリー + DP + 二等分 (またはウィンドウ スライディング) <p> </p> 私はこの問題に長い間取り組んできました。 。 。最後にAC。 。 <p> </p>基本的な考え方はDPです。 DP[i]は、1番目からi番目までの最小の割り切れる区間の数を表します。次に、各数値について、以前に到達できる左端の L を見つけます。L を検索するには、二分法またはスライディング ウィンドウ法を使用して列挙検索を実行できます。現在の列挙間隔が実行可能かどうかを判断する場合は、直線を使用します。セグメントツリーを使用して現在の間隔の最大値を検索します。状態遷移方程式 dp[i]=min(dp[L],....,dp[i-lenth])+1 から、間隔 dp[L]...dp[i-] の最大値を見つけます。 lenth] 値は、ログ時に別のセグメント ツリーを使用してクエリできます。したがって、2 つの線分ツリーを構築する必要があります。 <p> </p>私は最近コーディングスタイルを変更しました。 。本当に以前よりもずっと良くなりました。 。 。 <p> </p>コードは次のとおりです: <p> </p>
<p> </p>
<pre name="code" class="sycode">#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64const int INF=0x3f3f3f3f;#define lson l, mid, rt>1;        if(p=r) {                if(q==1) {                        q_minv=min(q_minv,minv[rt]);                        q_maxv=max(q_maxv,maxv[rt]);                } else                        q_mindp=min(q_mindp,mindp[rt]);                return ;        }        int mid=l+r>>1;        if(llmid) Query(q,ll,rr,rson);}int bin_search(int r){        int low=1, high=r, mid, ans=-1;        while(low>1;                q_maxv=-INF; q_minv=INF;                Query(1,mid,r,root);                //if(r==4)                //printf("%d %d\n",q_minv,q_maxv);                if(q_maxv-q_minvi) continue ;                q_mindp=INF;                //printf("%d %d\n",l,i-lenth);                Query(-1,l-1,i-lenth,root);                if(q_mindp==INF) continue ;                Update(-1,i,q_mindp+1,root);        }        q_mindp=INF;        Query(-1,n,n,root);        printf("%d\n",q_mindp==INF?-1:q_mindp);        return 0;}</algorithm></set></map></queue></ctype.h></math.h></stdlib.h></cstring></string></cstdio></iostream>