C++博客-huicpc0860

hdu 3401 Trade

huicpc0860 — Mon, 16 Aug 2010 13:40:00 GMT

#include <stdio.h>
#define N 2001
#define inf 10000000
#define max(a,b) ((a)>(b)?(a):(b))
int f[N][N],q[N],id[N];
int main(){
    int t,n,maxp,w,ap,bp,as,bs;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&maxp,&w);
        for(int i=0;i<n;++i){
            scanf("%d%d%d%d",&ap,&bp,&as,&bs);
            for(int j=0;j<=maxp;++j)f[i][j]=-inf;
            if(i<=w)for(int j=0;j<=as;++j)f[i][j]=-ap*j;
            if(i>0)for(int j=0;j<=maxp;++j)f[i][j]=max(f[i][j],f[i-1][j]);
            if (i==0||i<=w) continue;
            for(int j=0,l=0,r=-1;j<=maxp;++j){
                int tmp=f[i-w-1][j]+j*ap;
                while(l<=r&&q[r]<tmp)--r;
                q[++r]=tmp,id[r]=j;
                while(l<=r&&id[l]+as<j)++l;
                f[i][j]=max(f[i][j],q[l]-j*ap);
            }
            for(int j=maxp,l=0,r=-1;j>=0;--j){
                int tmp=f[i-w-1][j]+j*bp;
                while(l<=r&&q[r]<tmp)--r;
                q[++r]=tmp,id[r]=j;
                while(l<=r&&id[l]-bs>j)++l;
                f[i][j]=max(f[i][j],q[l]-j*bp);
            }
        }
        int ans=0;
        for(int i=0;i<=maxp;++i)ans=max(ans,f[n-1][i]);
        printf("%d\n",ans);
    }
    return 0;
}

huicpc0860 2010-08-16 21:40 发表评论

hdu 2993 MAX Average Problem

huicpc0860 — Mon, 09 Aug 2010 12:24:00 GMT

#include <stdio.h>
using namespace std;
#define N 100010
#define max(x,y) ((x)>(y)?(x):(y))
typedef long long  LL;
int s[N];
struct point {
    int x, y;
    point(){}
    point(int x,int y):x(x),y(y){}
}p[N];
point operator - (const point &a, const point &b) { return point(a.x-b.x, a.y-b.y); }
LL operator ^ (const point &a, const point &b) { return (LL)a.x*b.y - (LL)a.y*b.x; }
inline int get(){
    int s=0;
    char c;
    while(c=getchar(),c!=' '&&c!='\n')s=s*10+c-'0';
    return s;
}
int main() {
    int n,k;
    s[0]=0;
    while (~scanf("%d ",&n)){
        k=get();n++;
        for(int i=1;i<n;++i){
            s[i]=get();
            s[i]+=s[i-1];
        }
        double ans=0;
        for(int i=k,m=-1,f=0;i<n;++i){
            point now(i-k,s[i-k]);
            while(f<m&&(p[m]-p[m-1]^now-p[m-1])<0)--m;
            p[++m]=now;
            while(f<m&&(LL)(s[i]-p[f].y)*(i-p[f+1].x)<(LL)(s[i]-p[f+1].y)*(i-p[f].x))f++;
            ans=max(ans,double(s[i]-p[f].y)/(i-p[f].x));
        }
        printf("%.2lf\n",ans);
    }
}

huicpc0860 2010-08-09 20:24 发表评论

poj 1133 stars

huicpc0860 — Sun, 01 Aug 2010 12:05:00 GMT

摘要: #include #include #include using namespace std;const double eps=1e-8;int so,mo,br;inline int dcmp(double... 阅读全文

huicpc0860 2010-08-01 20:05 发表评论

poj 1271 Nice Milk

huicpc0860 — Tue, 27 Jul 2010 10:46:00 GMT

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
const double eps=1e-8;
double h,ans,cake;
struct point {
    double x,y;
    point (){}
    point (double x,double y):x(x),y(y){}
    void get(){scanf("%lf%lf",&x,&y);}
};
struct poly{
    point p[21];
    int n;
    void get(){for(int i=0;i<n;i++)p[i].get();p[n]=p[0];}
}sg;
int dcmp(double x){
    return (x>eps)-(x<-eps);
}
double cross(point o,point p,point q){
    return (p.x-o.x)*(q.y-o.y)-(p.y-o.y)*(q.x-o.x);
}
point lineinter(point a,point b,point c,point d){
    double u=cross(a,b,c),v=cross(b,a,d);
    return point((c.x*v+d.x*u)/(u+v),(c.y*v+d.y*u)/(u+v));
}
double dis(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void push(point a,point b,point &c,point &d){
    double x=a.y-b.y,y=b.x-a.x,t=h/dis(a,b);
    c=point(a.x+x*t,a.y+y*t);
    d=point(b.x+x*t,b.y+y*t);
}
void cut(point a,point b,poly tg,poly &g){
    push(a,b,a,b);
    g.n=0;
    for(int i=0;i<tg.n;i++){
        int u=dcmp(cross(a,b,tg.p[i])),v=dcmp(cross(a,b,tg.p[i+1]));
        if(u>=0)g.p[g.n++]=tg.p[i];
        if(u*v<0) g.p[g.n++]=lineinter(a,b,tg.p[i],tg.p[i+1]);
    }
    g.p[g.n]=g.p[0];
}
double area(poly g){
    double sum=0;
    for(int i=2;i<g.n;i++)
        sum+=cross(g.p[0],g.p[i-1],g.p[i]);
    return 0.5*sum;
}
void dfs(int i,int step,poly g){
    if(step+i<sg.n)dfs(i+1,step,g);
    cut(sg.p[i],sg.p[i+1],g,g);
    if(step==1)ans=max(ans,cake-area(g));
    else dfs(i+1,step-1,g);
}
int main(){
    int k;
    while(scanf("%d%d%lf",&sg.n,&k,&h),sg.n||k||h){
        sg.get();
        cake=area(sg);
        ans=0;
        k=min(k,sg.n);
        if(k&&h)dfs(0,k,sg);
        printf("%.2lf\n",ans);
    }
    return 0;
}

huicpc0860 2010-07-27 18:46 发表评论

poj 3347 Kadj Squares

huicpc0860 — Fri, 23 Jul 2010 10:51:00 GMT

#include <stdio.h>
#include <math.h>
#define max(a,b) (a>b?a:b)
int n;

struct seg {
    double l, r, t;
} a[50];

int main() {
    while (scanf("%d", &n), n) {
        for (int i = 0; i < n; i++) {
            scanf("%lf", &a[i].t);
            a[i].l = 0.0;
            for (int j = 0; j < i; j++)
                a[i].l = max(a[i].l, a[j].r - fabs(a[i].t - a[j].t) / 2);
            a[i].r = a[i].l + a[i].t;
        }
        for (int i = 1; i < n; i++)
            for (int j = 0; j < i; j++)
                if (a[i].l < a[i].r) {
                    if (a[i].t > a[j].t && a[i].l < a[j].r)
                        a[j].r = a[i].l;
                    else if (a[i].t < a[j].t && a[j].r > a[i].l)
                        a[i].l = a[j].r;
                }
        for (int i = 0; i < n; i++)
            if (a[i].l < a[i].r)printf("%d ", i + 1);
        puts("");
    }
}

huicpc0860 2010-07-23 18:51 发表评论

bupt 1849 Counting Sequences

huicpc0860 — Fri, 16 Jul 2010 10:06:00 GMT

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct point{
    int x,y;
}p[100010];
int c[100010],n,d,a[100010],map[100010],t;
bool cmp(point p0,point p1){
    return p0.x<p1.x;
}
int lowbit(int x){
    return x&(-x);
}
int sum(int x){
    int s=0;
    while(x){
        s=(s+c[x])%9901;
        x-=lowbit(x);
    }
    return s;
}
int update(int x,int y){
    while(x<=n){
        c[x]=(c[x]+y)%9901;
        x+=lowbit(x);
    }
}
int find(int x,bool y){
    int l=1,r=n,m,ans=-1;
    if(y){
        while(l<=r){
            m=(l+r)>>1;
            if(p[m].x>=x){
                ans=m;
                r=m-1;
            }
            else l=m+1;
        }
    }else{
        while(l<=r){
            m=(l+r)>>1;
            if(p[m].x<=x){
                ans=m;
                l=m+1;
            }
            else r=m-1;
        }
    }
    return ans;
}
int main(){
    while(scanf("%d%d",&n,&d)!=EOF){
        memset(c,0,sizeof(c[0])*(n+1));
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            p[i].x=a[i];
            p[i].y=i;
        }
        sort(p+1,p+n+1,cmp);
        for(int i=1;i<=n;i++)map[p[i].y]=i;
        for(int i=1;i<=n;i++){
            int l=find(a[i]-d,1),r=find(a[i]+d,0);
            if(l+1&&r+1&&l<=r){
                t=(9901+sum(r)-sum(l-1)+1)%9901;//+1巧妙之处，用于标记是否被更新，答案再减去n即可
                update(map[i],t);
            }
        }
        printf("%d\n",(9901*20+sum(n)-n)%9901);
    }
    return 0;
}

huicpc0860 2010-07-16 18:06 发表评论

hdu 3433 A Task Process

huicpc0860 — Thu, 15 Jul 2010 12:26:00 GMT

#include <stdio.h>
#include <algorithm>
using namespace std;
int cas,tim,n,x,y,a[60],b[60],f[210];
int main(){
    scanf("%d",&cas);
    for(int tim=0;tim<cas;){
        scanf("%d%d%d",&n,&x,&y);
        for(int i=1;i<=n;i++)//下标重1开始
            scanf("%d%d",&a[i],&b[i]);
        int l=0,r=a[1]*x+b[1]*y,m;
        while(l<=r){
            m=(l+r)>>1;
            for(int i=1;i<=x;i++)f[i]=-999999999;
            f[0]=0;
            for(int i=1;i<=n;i++)
                for(int v=x;v>=0;v--){
                    f[v]+=m/b[i];//新入工人要更新
                    for(int j=0;j<v;j++) if (m>=(v-j)*a[i])
                        f[v]=max(f[v],f[j]+(m-a[i]*(v-j))/b[i]);
                }
            if(f[x]>=y)r=m-1;//最左逼近
            else l=m+1;
        }
        printf("Case %d: %d\n",++tim,l);
    }
    return 0;
}

huicpc0860 2010-07-15 20:26 发表评论

hdu 3437 Garden

huicpc0860 — Wed, 14 Jul 2010 13:39:00 GMT

摘要: #include #include #include #define zero(x) if(dcmp(x)==0)x=0#define cross(p0,p1,p2) ((p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y... 阅读全文

huicpc0860 2010-07-14 21:39 发表评论

poj 2155 Matrix

huicpc0860 — Wed, 14 Jul 2010 04:47:00 GMT

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define lowbit(x) (x&(-x))
bool c[1010][1010];
int n;
bool sum(int x,int y){
    bool s=0;
    while(x){
        int yy=y;
        while(yy){
            s^=c[x][yy];
            yy-=lowbit(yy);
        }
        x-=lowbit(x);
    }
    return s;
}
void update(int x,int y){
    while(x<=n){
        int yy=y;
        while(yy<=n){
            c[x][yy]=!c[x][yy];
            yy+=lowbit(yy);
        }
        x+=lowbit(x);
    }
}
int main(){
    int t,x,y,xx,yy,m;
    char s[2];
    scanf("%d",&t);
    while(t--){
        memset(c,0,sizeof(c));
        scanf("%d%d",&n,&m);
        while(m--){
            scanf("%s",s);
            if(s[0]=='C'){
                scanf("%d%d%d%d",&x,&y,&xx,&yy);
                update(++xx,++yy);
                update(x,yy);
                update(xx,y);
                update(x,y);
            }else{
                scanf("%d%d",&x,&y);
                printf("%d\n",sum(x,y));
            }
        }
        puts("");
    }
    return 0;
}

huicpc0860 2010-07-14 12:47 发表评论

poj 1011 Sticks

huicpc0860 — Mon, 21 Jun 2010 14:38:00 GMT

//搜索入门
#include <stdio.h>
#include <algorithm>
using namespace std;
int length,a[64],n,sum;
bool ok,v[64]={0};
void dfs(int i,int size,int step){
    if(size==length)i=0,size=0,step--;
    if(step==0)ok=1;
    for(int old=-1;!ok&&i<n;i++)
        if(!v[i]&&a[i]!=old&&(size+a[i])<=length){
            v[i]=1;
            old=a[i];
            dfs(i+1,size+a[i],step);
            v[i]=0;
            if(size==0)return;
        }
}
bool cmp(int x,int y){return x>y;}
int main(){
    while(scanf("%d",&n),n){
        sum=0,ok=0;
        for(int i=0;i<n;i++){scanf("%d",&a[i]);sum+=a[i];}
        sort(a,a+n,cmp);
        for(length=a[0];!ok&&length<=sum;length++)
            if(sum%length==0){
                dfs(0,0,(sum/length)-1);
                if(ok)printf("%d\n",length);
            }
    }
    return 0;
}