0x08 总结与练习

1：前面已经搞好了。

2：poj2965 这种开关问题一个点要么点一次要么不点，枚举所有点的方案实行即可

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

char ss[];

int main()

{

    int d=,tp=;

    for(int i=;i<=;i++)

    {

        scanf("%s",ss+);

        for(int j=;j<=;j++,tp++)

            if(ss[j]=='+')d+=(<<tp);

    }

    int max_line=(<<)-,ans=,zt;

    for(int i=;i<=max_line;i++)

    {

        int k=d,sum=;

        for(int j=;j<=;j++)

        {

            if((i&(<<j))>)

            {

                sum++;

                int h=j/;

                for(int _=;_<=;_++)k^=(<<(h*+_));

                int l=j%;

                for(int _=;_<=;_+=)k^=(<<(l+_));

                k^=(<<(h*+l));

            }

        }

        if(k==)

        {

            if(ans>sum)

                ans=sum, zt=i;

        }

    }

    printf("%d\n",ans);

    int x=,y=;

    for(int j=;j<=;j++)

    {

        if((zt&(<<j))>)printf("%d %d\n",x,y);

        y++;if(y==)y=,x++;

    }

    return ;

}

poj2965

3、4、10：手残码农题真心不想做，准备NOIP的时候再做吧

5：poj 3714 平面最近点对问题，分治解决，对于当前已有的最小值确定mid上下左右一个四边形的范围，合并区间时就判定这个四边形范围里面的点即可，闻说这个点数是不会超过8个的。具体实行是在确定了横坐标范围后，把这些点取出，判定时将其按纵坐标排序，一个个求值，这个复杂度是n(logn)^2，假如用归并排序顺便把纵坐标排序会少一个log，但是实际上并没有快多少。至于kdtree。。以后再说

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

struct point{double x,y;int z;}a[],t[];

bool cmp(point p1,point p2){return p1.x<p2.x;}

int tt[];

bool cmp2(int n1,int n2){return a[n1].y<a[n2].y;}

double getdis(int n1,int n2)

{

    return sqrt( (double((a[n1].x-a[n2].x)*(a[n1].x-a[n2].x))) + (double((a[n1].y-a[n2].y)*(a[n1].y-a[n2].y))) );

}

double fenzi(int l,int r)

{

    if(l==r)return (double(<<));

    int mid=(l+r)/;

    double mmin=min(fenzi(l,mid),fenzi(mid+,r));

    int i=l,j=mid+,p=l;

    while(i<=mid&&j<=r)

    {

        if(a[i].y<=a[j].y)t[p++]=a[i++];

        else               t[p++]=a[j++];

    }

    while(i<=mid)t[p++]=a[i++];

    while(j<=r)  t[p++]=a[j++];

    for(int i=l;i<=r;i++)a[i]=t[i];

    int len=;tt[++len]=mid;

    for(int i=l;i<=r;i++)

        if(( double(abs(a[i].x-a[mid].x)) )<mmin)tt[++len]=i;

    for(int i=;i<=len;i++)

        for(int j=i+,clc=;j<=len&&clc<=;j++,clc++)

                if(a[tt[i]].z!=a[tt[j]].z)

                    mmin=min(mmin,getdis(tt[i],tt[j]));

    return mmin;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n;

        scanf("%d",&n);

        for(int i=;i<=n;i++)

            scanf("%lf%lf",&a[i].x,&a[i].y), a[i].z=;

        for(int i=n+;i<=n*;i++)

            scanf("%lf%lf",&a[i].x,&a[i].y), a[i].z=;

        sort(a+,a+*n+,cmp);

        printf("%.3lf\n",fenzi(,*n));

    }

    return ;

}

poj3714

6：bzoj1271 这道是好题啊！突破口一定是在只有一个是奇数这个条件里面的，那么就是奇偶性的不同，这个时候并没有想到前缀和。知道这个以后就二分答案，看看前缀和是奇数还是偶数就行了。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

int n;

struct node

{

    LL l,r,d;

}a[];

bool check(LL tp)

{

    LL sum=;

    for(int i=;i<=n;i++)

        if(a[i].l<=tp)sum+=(min(a[i].r,tp)-a[i].l)/a[i].d+;

    return (sum%==);

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        for(int i=;i<=n;i++)

            scanf("%lld%lld%lld",&a[i].l,&a[i].r,&a[i].d);

        LL l=,r=,ans=-;

        while(l<=r)

        {

            LL mid=(l+r)/,u;

            if(check(mid)==true)

            {

                r=mid-;

                ans=mid;

            }

            else l=mid+;

        }

        if(ans==-)printf("Poor QIN Teng:(\n");

        else

        {

            LL c=;

            for(int i=;i<=n;i++)

                if(a[i].l<=ans&&ans<=a[i].r&&(ans-a[i].l)%a[i].d==)c++;

            printf("%lld %lld\n",ans,c);

        }

    }

    return ;

}

bzoj1271

7：poj3179 这题明显就得写个二维前缀和嘛。。相应的就离散化一下。二分答案，然后两个for一个枚举行一个枚举列的后界，前界尽量往前，这个while往前走就好。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

int n,C;

struct node{int x,y;}a[];

int lsxlen,lsylen,lsx[],lsy[];

void LSH()

{

    lsxlen=;

    for(int i=;i<=n;i++)lsx[++lsxlen]=a[i].x;

    sort(lsx+,lsx+lsxlen+);

    lsxlen=unique(lsx+,lsx+lsxlen+)-lsx-;

    for(int i=;i<=n;i++)

         a[i].x=lower_bound(lsx+,lsx+lsxlen+,a[i].x)-lsx;

    lsylen=;

    for(int i=;i<=n;i++)lsy[++lsylen]=a[i].y;

    sort(lsy+,lsy+lsylen+);

    lsylen=unique(lsy+,lsy+lsylen+)-lsy-;

    for(int i=;i<=n;i++)

         a[i].y=lower_bound(lsy+,lsy+lsylen+,a[i].y)-lsy;

}

int sum[][];

int getsum(int x,int y,int u,int v)

{

    return sum[x][y]-sum[x][v-]-sum[u-][y]+sum[u-][v-];

}

bool check(int mid)

{

    int rl=;

    for(int rr=;rr<=lsxlen;rr++)

    {

        while(lsx[rr]-lsx[rl]>=mid)rl++;

        int cl=;

        for(int cr=;cr<=lsylen;cr++)

        {

            while(lsy[cr]-lsy[cl]>=mid)cl++;

            if(getsum(rr,cr,rl,cl)>=C)return true;

        }

    }

    return false;

}

int main()

{

    scanf("%d%d",&C,&n);

    for(int i=;i<=n;i++)

        scanf("%d%d",&a[i].x,&a[i].y);

    LSH();

    memset(sum,,sizeof(sum));

    for(int i=;i<=n;i++)sum[a[i].x][a[i].y]++;

    for(int i=;i<=lsxlen;i++)

        for(int j=;j<=lsylen;j++)

            sum[i][j]+=sum[i-][j]+sum[i][j-]-sum[i-][j-];

    int l=,r=,ans;

    while(l<=r)

    {

        int mid=(l+r)/;

        if(check(mid)==true)

        {

            ans=mid;

            r=mid-;

        }

        else l=mid+;

    }

    printf("%d\n",ans);

    return ;

}

poj3179

8：bzoj1465 bzoj1045: [HAOI2008] 糖果传递&&bzoj3293: [Cqoi2011]分金币

9：明显x、y分开做，y就是中位数，x的话我一开始也是想要从中位数左右延伸，但是fail掉了。。正确的做法是设排完序以后，起点是a，那么我们就是要求的sum=Σabs(a-(x[i]-i))。a就是(x[i]-i)这东西的中位数。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

LL a[],b[];

LL myabs(LL x){return x<?-x:x;}

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        scanf("%lld%lld",&a[i],&b[i]);

    sort(a+,a+n+);

    sort(b+,b+n+);

    for(int i=;i<=n;i++)a[i]-=i;

    sort(a+,a+n+);

    LL sum=;

    for(int i=;i<=n;i++)

        sum+=myabs(a[i]-a[(n+)/]);

    for(int i=;i<=n;i++)

        sum+=myabs(b[i]-b[(n+)/]);

    printf("%lld\n",sum);

    return ;

}

poj1723

11：poj1050这题暴力二维前缀和n^4可A。。。。但是我还是正直的写个个n^3，f[i][j][k]表示现在枚举到第i行，列的区间是j~k的最大值，那么就相当于每一种列的情况都做一次O(n)的一维最大子串。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

int a[][],f[][][];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            scanf("%d",&a[i][j]);

    int ans=-;

    memset(f,,sizeof(f));

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=n;j++)

        {

            int sum=;

            for(int k=j;k<=n;k++)

            {

                sum+=a[i][k];

                f[i][j][k]=max(f[i-][j][k]+sum,sum);

                ans=max(ans,f[i][j][k]);

            }

        }

    }

    printf("%d\n",ans);

    return ;

}

poj1050

12：hdu4864 这题超级好题！！！！想了我超久，下午一个小时+晚上两个小时，看到那个价值的算法，肯定觉得会有问题对吧，我发现其实这个价值根本没用，因为价值的大小是按照耗时，耗时相等按照等级排的。思考的时候我类比一下贪心的第1题，那题是一个权，两个限制，现在是两个权，两个限制，不管怎样肯定是先排序，然后在此基础上卡另外一个限制贪心，我写的时候是让机器去找任务，这里就出问题了！不管按照什么排序，怎样的贪心法都会被反例掉，因为在这题里面，机器是为任务服务的，所以应该是任务去找机器，排序过后权值由大到小，一个个找完以后，x区间是单调延伸，前面的机器必然满足x比往后枚举的任务的x大，相当于问题只在于y，那么只需要贪心选择全部中尽量小的即可。再来分析一下正确性，当前任务占用机器，必然比后面的任务占用的机器要多，对于机器被占用，可以视作对答案的贡献均为1，所以可以心安理得的占用机器。对于机器而言，假如不影响当前任务影响后面，那一个替代他的机器一定比他还要优秀，它能影响了当前，肯定在先前也可以影响那个后一种情况中被前一个机器影响的任务。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<set>

using namespace std;

struct node

{

    int x,y;

}a[],b[];

bool cmp(node n1,node n2)

{

    if(n1.x==n2.x)return n1.y>n2.y;

    return n1.x>n2.x;

}

multiset<int>s;

multiset<int>::iterator o;

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        for(int i=;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);

        for(int i=;i<=m;i++)scanf("%d%d",&b[i].x,&b[i].y);

        sort(a+,a+n+,cmp);sort(b+,b+m+,cmp);

        s.clear();

        int ans=,tp=;long long val=;

        for(int i=;i<=m;i++)

        {

            while(tp<=n&&a[tp].x>=b[i].x)s.insert(a[tp].y),tp++;

            if(!s.empty())

            {

                if(*--s.end()>=b[i].y)

                {

                    int k=*s.lower_bound(b[i].y);

                    int c=s.count(k);s.erase(k);

                    for(int j=;j<c;j++)s.insert(k);

                //    for(o=s.begin();o!=s.end();o++)printf("%d\n",*o);

                    ans++;val+=b[i].x*+*b[i].y;

                }

            }

        }

        printf("%d %lld\n",ans,val);

    }

    return ;

}

hdu4864 （因为y的范围只有100所以可以暴力枚举，我没想就搞了个set，跑得还比暴力慢-_-!）

巴特西

0x08 总结与练习

最新文章

热门文章