发新随笔
发新文章 管理

2010年8月16日

#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;
}

posted @ 2010-08-16 21:40 huicpc0860 阅读(284) | 评论 (1)编辑 收藏

2010年8月9日

#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);
    }
}
posted @ 2010-08-09 20:24 huicpc0860 阅读(602) | 评论 (0)编辑 收藏

2010年8月1日

     摘要: #include <stdio.h>#include <math.h>#include <algorithm>using namespace std;const double eps=1e-8;int so,mo,br;inline int dcmp(double...  阅读全文
posted @ 2010-08-01 20:05 huicpc0860 阅读(238) | 评论 (0)编辑 收藏

2010年7月27日

#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;
}
posted @ 2010-07-27 18:46 huicpc0860 阅读(220) | 评论 (0)编辑 收藏

2010年7月23日

#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(
"");
    }
}

posted @ 2010-07-23 18:51 huicpc0860 阅读(141) | 评论 (0)编辑 收藏

2010年7月16日

#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;
}

posted @ 2010-07-16 18:06 huicpc0860 阅读(77) | 评论 (0)编辑 收藏

2010年7月15日

#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;
}

posted @ 2010-07-15 20:26 huicpc0860 阅读(221) | 评论 (0)编辑 收藏

2010年7月14日

     摘要: #include <stdio.h>#include <algorithm>#include <math.h>#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...  阅读全文
posted @ 2010-07-14 21:39 huicpc0860 阅读(167) | 评论 (0)编辑 收藏
 
#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;
}

posted @ 2010-07-14 12:47 huicpc0860 阅读(75) | 评论 (0)编辑 收藏

2010年6月21日

//搜索入门 
#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;
}

        
        
posted @ 2010-06-21 22:38 huicpc0860 阅读(68) | 评论 (0)编辑 收藏
CALENDER
<2019年2月>
272829303112
3456789
10111213141516
17181920212223
242526272812
3456789

常用链接

留言簿

随笔分类

随笔档案

搜索

  •  

最新随笔

最新评论


Powered By: 博客园
模板提供沪江博客