Codeforces Round #278 (Div. 1) Problem solving report_html/css_WEB-ITnose

Question A: Fight the Monster

Enumerate into two points

Because the data range of each element is only 100, you can use enumeration, and use two points for blood volume, and then Determine whether the result is feasible.

The code is as follows:

#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<=high){                mid=low+high>>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<=200;i++){                        for(j=0;j<=200;j++){                                if(ay+i<=dm)continue ;                                z=bin_search(ay+i,dy+j);                                min1=min(min1,(z-hy)*h+i*a+j*d);                        }                }                printf("%d\n",min1);        }}

Question B: Strip

Line segment tree DP bisection (or window sliding)

I have been working on this question for a long time. . . Finally AC. .

The basic idea is DP. DP[i] represents the number of minimum divisible intervals from the first to the i-th. Then for each number, find the leftmost L that can be reached previously. To search for L, you can use the dichotomy method or the sliding window method to perform an enumeration search. When judging whether the current enumeration interval is feasible, use a line segment tree to search for the maximum value of the current interval. Query. State transition equation dp[i]=min(dp[L],....,dp[i-lenth]) 1; then find the maximum value for the interval dp[L]...dp[i-lenth] Another line segment tree can be used to query in logn time. Therefore, two line segment trees need to be built.

I have recently changed my coding style. . It really looks much better than before. . .

The code is as follows:

#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#define rson mid+1, r, rt<<1|1#define root 0, n, 1int minv[400000], maxv[400000], a[110000], q_minv, q_maxv, mindp[400000], q_mindp, s, n;void PushUp(int q, int rt){        if(q==1) {                minv[rt]=min(minv[rt<<1],minv[rt<<1|1]);                maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);        } else                mindp[rt]=min(mindp[rt<<1],mindp[rt<<1|1]);}void Update(int q, int p, int x, int l, int r, int rt){        if(l==r) {                if(q==1)                        minv[rt]=maxv[rt]=x;                else mindp[rt]=x;                return ;        }        int mid=l+r>>1;        if(p<=mid) Update(q,p,x,lson);        else Update(q,p,x,rson);        PushUp(q,rt);}void Query(int q, int ll, int rr, int l, int r, int rt){        if(ll<=l&&rr>=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(ll<=mid) Query(q,ll,rr,lson);        if(rr>mid) Query(q,ll,rr,rson);}int bin_search(int r){        int low=1, high=r, mid, ans=-1;        while(low<=high){                mid=low+high>>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_minv<=s) {                        ans=mid;high=mid-1;                }                else low=mid+1;        }        return ans;}int main(){        int lenth, ans, flag=0, l, i;        scanf("%d%d%d",&n,&s,&lenth);        for(i=1; i<=n; i++) {                scanf("%d",&a[i]);        }        memset(minv,INF,sizeof(minv));        memset(maxv,-1,sizeof(maxv));        memset(mindp,INF,sizeof(mindp));        Update(-1,0,0,root);        for(i=1;i<=n;i++){                Update(1,i,a[i],root);                l=bin_search(i);                if(l+lenth-1>i) 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;}