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;
 }
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);
}
}
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... 閱讀全文
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;
}
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("");
}
}
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巧妙之處，用于標(biāo)記是否被更新，答案再減去n即可
update(map[i],t);
}
}
printf("%d\n",(9901*20+sum(n)-n)%9901);
}
return 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++)//下標(biāo)重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;
}
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... 閱讀全文
#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;
}
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;
}
|