10
10
2015
0

[BZOJ1007] [HNOI2008] 水平可见直线

想了一下,又看看黄大神的blog,然后就水掉了这题……

具体请看hzwer's blog:点击此处

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

int n,flg[50005],ST;

struct Node{
double a,b;
int i;
}a[50005],s[50005];

int cmp(Node sa,Node sb){
if(fabs(sa.a-sb.a)<=0.0000001)return sa.b<sb.b;
return sa.a<sb.a;
}

double SetX(Node x,Node y){
return (y.b-x.b)/(x.a-y.a);
}

void Insert(int x){
while(ST){
    if(fabs(s[ST].a-a[x].a)<=0.0000001)ST--;
    else if(ST>1 && SetX(a[x],s[ST-1])<=SetX(s[ST],s[ST-1])){
        ST--;
    }
    else break;
}
s[++ST]=a[x];
}

int main(){
freopen("1007.in","r",stdin);
freopen("1007.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%lf %lf",&a[i].a,&a[i].b);
    a[i].i=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)Insert(i);
for(int i=1;i<=ST;i++)flg[s[i].i]=1;
for(int i=1;i<=n;i++)if(flg[i])printf("%d ",i);
return 0;
}
Category: BZOJ | Tags: OI
10
9
2015
0

[BZOJ1968] [Ahoi2005] COMMON 约数研究

喜闻乐见的良心大水题……(这种题居然放在bzoj上)

以下是代码,不用解释了吧

#include<cstdio>

int n,ans=0;
int main(){
freopen("1968.in","r",stdin);
freopen("1968.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)ans+=n/i;
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI
10
4
2015
0

[BZOJ1592] [Usaco2008 Feb] Making the Grade 路面修整

嗯……这题是做两遍dp,设f[i][j]为前i个点的路面当高度为j(已经离散化)后所能付出的最小代价,则状态转移方程为:

f[i][j]=min(f[i][j-1],f[i-1][j]+abs(j-a[i]))

我作死用了滚动数组……

#include<cstdio>
#include<algorithm>
using namespace std;

int n,a[2005],f[2][2005],g[2][2005],b[2005];

int absd(int h){
return h>0?h:-h;
}

int cmp(int sa,int sb){
return sa>sb;
}

int main(){
freopen("1592.in","r",stdin);
freopen("1592.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    b[i]=a[i];
}
sort(b+1,b+n+1);
f[1][0]=f[0][0]=2147483647;
for(int i=1;i<=n;i++){
    int now=i%2,pre;
    pre=now^1;
    for(int j=1;j<=n;j++){
        f[now][j]=min(f[now][j-1],f[pre][j]+absd(b[j]-a[i]));
    }
}
g[0][0]=g[1][0]=2147483647;
for(int i=1;i<=n;i++){
    int now=i%2,pre;
    pre=now^1;
    for(int j=1;j<=n;j++){
        g[now][j]=min(g[now][j-1],g[pre][j]+absd(b[n+1-j]-a[i]));
    }
}
printf("%d\n",min(g[n%2][n],f[n%2][n]));
return 0;
}
Category: BZOJ | Tags: OI

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com