poi2007

序:为什么写poi,zy说poi都是思路题目,不像hnoi妈的数据结构队。。。。。

1.bzoj1102

题目大意:定义了一个山谷和山峰,求他们数量。

题解:这种题bfs咯,在bfs的时候记录一下相邻的比我大的有多少,比我小的有多少,然后更新答案;

代码:

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define maxn 2000
 7 using namespace std;
 8 const int dx[8]={-1,0,1,-1,1,-1,0,1};
 9 const int dy[8]={-1,-1,-1,0,0,1,1,1};
10 int n,summ,sumn,ansm,ansn;
11 int lis[maxn*maxn][3];
12 int a[maxn][maxn];
13 bool vis[maxn][maxn];
14 int read()
15 {
16     int x=0; char ch; bool bo=0;
17     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) bo=1;
18     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘);
19     if (bo) return -x; return x;
20 }
21 void bfs(int x,int y)
22 {
23     int t=1,h=1; lis[1][1]=x; lis[1][2]=y; sumn=summ=0; vis[x][y]=1;
24     while (h<=t)
25     {
26         int aa=lis[h][1],bb=lis[h][2];
27         for (int i=0; i<8; i++)
28         {
29             int xx=aa+dx[i],yy=bb+dy[i];
30             if (xx<1 || xx>n || yy<1 || yy>n) continue;
31             if (a[xx][yy]==a[aa][bb] && !vis[xx][yy])
32             {
33                 ++t; lis[t][1]=xx; lis[t][2]=yy;
34                 vis[xx][yy]=1;
35             }
36             else
37             {
38                 if (a[xx][yy]<a[aa][bb]) summ++;
39                 if (a[xx][yy]>a[aa][bb]) sumn++;
40             }
41         }
42         h++;
43     }
44     if (!summ && !sumn) ansm++,ansn++;
45     else if (summ && sumn) return;
46     else if (summ) ansm++;
47     else ansn++;
48 }
49 int main()
50 {
51     memset(vis,0,sizeof(vis));
52     n=read();
53     for (int i=1; i<=n; i++)
54     for (int j=1; j<=n; j++)
55     a[i][j]=read();
56     ansn=ansm=0;
57     for (int i=1; i<=n; i++)
58         for (int j=1; j<=n; j++)
59         if (!vis[i][j]) bfs(i,j);
60     printf("%d %d\n",ansm,ansn);
61 }

2.bzoj1103

题目大意:给你一颗树(全是土路),然后有两个操作,一个将一条土路改为公路,另外一个是求一个点到根的路径上土路的数目。

题解:dfs序+线段树维护

代码:

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cstdio>
 5 #include<cmath>
 6 #define maxn 2000005
 7 using namespace std;
 8 int tot,n,m,tmp;
 9 int pre[maxn],now[maxn],v[maxn],dis[maxn],fa[maxn],in[maxn],out[maxn];
10 int lazy[maxn],sum[maxn],st[maxn];
11 int read()
12 {
13     int x=0; char ch; bool bo=0;
14     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) bo=1;
15     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘);
16     if (bo) return -x; return x;
17 }
18 void insert(int a,int b){++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b;
19 }
20 void dfs()
21 {
22      int top=0;
23      st[++top]=1; fa[1]=0;
24      while (top)
25      {
26          int x=st[top]; top--;
27          if (!in[x])
28          {
29              in[x]=++tmp;
30              st[++top]=x;
31             for (int p=now[x]; p; p=pre[p])
32             {
33                 int son=v[p];
34                 if (son==fa[x]) continue;
35                 st[++top]=son; dis[son]=dis[x]+1; fa[son]=x;
36             }
37         }
38         else out[x]=++tmp;
39      }
40  }
41 void updata(int k,int val){lazy[k]+=val; sum[k]+=val;}
42 void pushdown(int k)
43 {
44     if (!lazy[k]) return;
45     sum[k*2]+=lazy[k]; sum[k*2+1]+=lazy[k];
46     lazy[k*2]+=lazy[k]; lazy[k*2+1]+=lazy[k];
47     lazy[k]=0;
48 }
49 void change(int k,int l,int r,int x,int y,int val)
50 {
51     if (x<=l && r<=y) {updata(k,val); return; }
52     int mid=(l+r)>>1;
53     if (x<=mid) change(k*2,l,mid,x,y,val);
54     if (y>mid) change(k*2+1,mid+1,r,x,y,val);
55 }
56 int query(int k,int l,int r,int pos)
57 {
58     pushdown(k);
59     if (l==r && r==pos) return sum[k];
60     int mid=(l+r)>>1;
61     if (pos<=mid) return query(k*2,l,mid,pos);
62     else return query(k*2+1,mid+1,r,pos);
63 }
64 void changeroad(int x,int y)
65 {
66     if (fa[y]==x) swap(x,y);
67     change(1,1,tmp,in[x],out[x],-1);
68 }
69 void askans(int x)
70 {
71     int k=query(1,1,tmp,in[x]);
72     printf("%d\n",dis[x]+k);
73 }
74 int main()
75 {
76     //freopen("meg.in","r",stdin);
77     //freopen("meg.out","w",stdout);
78     n=read();
79     for (int i=1; i<n; i++){int x=read(),y=read(); insert(x,y); insert(y,x);}
80     tmp=tot=0;
81     memset(sum,0,sizeof(sum));
82     memset(dis,0,sizeof(dis));
83     memset(in,0,sizeof(in));
84     memset(out,0,sizeof(out));
85     memset(fa,0,sizeof(fa));
86     dfs();
87     //for (int i=1; i<=n; i++) cout<<" "<<dis[i]<<" "<<in[i]<<" "<<out[i]<<endl;
88     m=n+read()-1;
89     for (int i=1; i<=m; i++)
90     {
91         char ch[5];
92         scanf(" %s",ch+1);
93         if (ch[1]==‘A‘) {int x=read(),y=read(); changeroad(x,y);}
94         else {int x=read(); askans(x);}
95     }
96  } 

注:会爆栈,写人工栈。

3.bzoj1104

题目大意:

    你手头有一张AKD市的地图。这张地图是边长为m*n的矩形,被划分
    为m*n个1*1的小正方形。对于每个小正方形,地图上已经标注了它的海拔高度以及它是否是AKD市的一个组成部分
    。地图上的所有部分都被水淹没了。并且,由于这张地图描绘的地面周围都被高山所环绕,洪水不可能自动向外排
    出。显然,我们没有必要抽干那些非AKD市的区域。每个巨型抽水机可以被放在任何一个1*1正方形上。这些巨型抽
    水机将持续地抽水直到这个正方形区域里的水被彻底抽干为止。当然,由连通器原理,所有能向这个格子溢水的格
    子要么被抽干,要么水位被降低。每个格子能够向相邻的格子溢水,“相邻的”是指(在同一高度水平面上的射影
    )有公共边。

题解:

  显然,如果一个点和许多点相邻并且此点的海拔最高,那么和它相连的点势必是可以抽干它的,于是我们可以把每个点作为关键点排序,那么对于一个点,则向它的四周bfs如果,遇到一个比他小的则不需要更新答案并且向下扩展,如果没有比他小的,则答案+1,退出;

代码:

 1 #include<cstring>
 2 #include<cstdlib>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<algorithm>
 7 #define N 1100
 8 using namespace std;
 9 struct node{int x,y,d;}A[N*N],p[N*N];
10 int n,m,a[N][N],num,ans,tail,step[4][2];
11 bool b[N][N],v[N][N];
12 bool cmp(node x,node y)
13 {
14     if(x.d<y.d) return 1;
15     return 0;
16 }
17 int main()
18 {
19     step[0][0]=1;step[0][1]=0;
20     step[1][0]=-1;step[1][1]=0;
21     step[2][0]=0;step[2][1]=1;
22     step[3][0]=0;step[3][1]=-1;
23     scanf("%d%d",&n,&m);
24     for(int i=1;i<=n;i++)
25         for(int j=1;j<=m;j++)
26         {
27             scanf("%d",&a[i][j]);
28             if(a[i][j]>0) A[++num].x=i,A[num].y=j,A[num].d=a[i][j];
29             a[i][j]=abs(a[i][j]);
30         }
31     sort(A+1,A+num+1,cmp);
32     ans=0;
33
34     for(int i=1;i<=num;i++)
35     {
36         if(b[A[i].x][A[i].y]) continue;
37         bool bo=0;
38         tail=1;p[1].x=A[i].x;p[1].y=A[i].y;
39         v[A[i].x][A[i].y]=1;
40         for(int j=1;j<=tail;j++)
41         {
42             int x=p[j].x,y=p[j].y,xx,yy;
43             for(int k=0;k<4;k++)
44             {
45                 xx=x+step[k][0];yy=y+step[k][1];
46                 if(xx>n || xx<1 || yy>m || yy<1 || a[xx][yy]>A[i].d) continue;
47                 if(v[xx][yy]) continue;
48                 if(b[xx][yy]) {bo=1;continue;}
49                 p[++tail].x=xx;p[tail].y=yy;
50                 v[xx][yy]=1;
51             }
52         }
53         if(bo==0) ans++;
54         for(int j=1;j<=tail;j++)
55         {
56             int x=p[j].x,y=p[j].y;
57             b[x][y]=1;v[x][y]=0;
58         }
59     }
60     printf("%d\n",ans);
61     return 0;
62 }

4.bzoj1105

题目大意:

    Blue Mary是一个有名的石头收藏家。迄今为止,他把他的藏品全部放在他的宫殿的地窖中。现在,他想将他
    的藏品陈列在他的花园中。皇家花园是一个边长为1000000000单位的平行于坐标轴的正方形。对于每个石头,Blue
      Mary都有一个他想放置的坐标,然后将他告诉他的属下。不幸的是,他忘了告诉他们坐标的顺序(比如无法分辨(
    x,y)和(y,x))。属下们,就自己决定了每个石头的具体位置。为了保护他的藏品,Blue Mary决定建造一个篱笆来
    保护他们。为了美学的需要,篱笆也被设计为平行于坐标轴的矩形。如果花园的布局知道了,那么就可以知道最短
    长度的篱笆的布局。他的属下们需要变换石头的坐标使得篱笆的长度最少。每个石头只能从(x,y)变换为(y,x),由
    于每个石头的重量不一样。属下们希望他们移动的石头的重量和最少。

题解:

  显然他们应该以直线y=x为分界线,所以分四种情况讨论(自己想想吧)

代码:

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define inf 0x7fffffff
 7 #define maxn 1000005
 8 #define ll long long
 9 using namespace std;
10 int n;
11 int a[maxn],b[maxn],c[maxn];
12 int lx,rx,ry,ly;
13 bool bo[maxn],v[maxn];
14 ll ans;
15 int read()
16 {
17     int x=0; char ch; bool bo=0;
18     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) bo=1;
19     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘);
20     if (bo) return -x; return x;
21 }
22 void find(int lx,int rx,int ly,int ry)
23 {
24     int tmp=0;
25     for (int i=1; i<=n; i++)
26     {
27         if (lx<=a[i] && a[i]<=rx && ly<=b[i] && b[i]<=ry)
28         {
29             bo[i]=0;
30         }
31         else
32         if (lx<=b[i] && b[i]<=rx && ly<=a[i] && a[i]<=ry)
33         {
34             tmp+=c[i];
35             bo[i]=1;
36         }
37         else return ;
38     }
39     if (tmp<ans)
40     {
41         ans=tmp;
42         memcpy(v,bo,sizeof(bool)*(n+1));
43     }
44 }
45 int main()
46 {
47     n=read(); lx=ly=ans=inf; rx=ry=-inf;
48     for (int i=1; i<=n; i++)
49     {
50         a[i]=read(); b[i]=read(); c[i]=read();
51         int minn=min(a[i],b[i]),maxnn=max(a[i],b[i]);
52         lx=min(lx,minn); rx=max(rx,minn); ly=min(ly,maxnn); ry=max(ry,maxnn);
53     }
54     //cout<<rx<<" "<<lx<<" "<<ry<<" "<<ly<<endl;
55     printf("%lld ",2ll*(rx-lx+ry-ly));
56     find(lx, rx, ly, ry);
57     find(lx, ry, ly, rx);
58     find(ly, rx, lx, ry);
59     find(ly, ry, lx, rx);
60     printf("%lld\n",ans);
61     for (int i=1; i<=n; i++)
62         printf("%d",v[i]);
63  } 

5.bzoj1106

题目大意:

    一个叫做立方体大作战的游戏风靡整个Byteotia。这个游戏的规则是相当复杂的,所以我们只介绍他的简单规
    则:给定玩家一个有2n个元素的栈,元素一个叠一个地放置。这些元素拥有n个不同的编号,每个编号正好有两个
    元素。玩家每次可以交换两个相邻的元素。如果在交换之后,两个相邻的元素编号相同,则将他们都从栈中移除,
    所有在他们上面的元素都会掉落下来并且可以导致连锁反应。玩家的目标是用最少的步数将方块全部消除。

题解:

    它只有两个,如果他有多个怎么写呢?(我猜可以写dp哦),我们从左读到右,显然,我们如果是第二次遇到这个点就把他们合并;

    为什么:

    例如:1.123321那么先合并两个2一定比先合并两个1更优所以发现如果两对元素的位置是嵌套关系的话先删掉中间那对更优

       2.12123456712 合并1和先合并2没影响。

    SO:就可以了,虽然证明不严谨。。。。。

代码:

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<cmath>
 6 #define maxn 50005
 7 using namespace std;
 8 int c[maxn*2],n;
 9 long long ans;
10 int cz[maxn*2];
11 int read()
12 {
13     int x=0; char ch; bool bo=0;
14     while (ch=getchar(),ch<‘0‘||ch>‘9‘) if (ch==‘-‘) bo=1;
15     while (x=x*10+ch-‘0‘,ch=getchar(),ch>=‘0‘&&ch<=‘9‘);
16     if (bo) return -x; return x;
17 }
18 int lowbit(int x)
19 {
20     return -x&x;
21 }
22 void modify(int k,int val)
23 {
24     for (int i=k; i<=2*n; i+=lowbit(i))
25         c[i]+=val;
26 }
27 int query(int x)
28 {
29     int kk=0;
30     for (int i=x; i; i-=lowbit(i))
31         kk+=c[i];
32     return kk;
33 }
34 int main()
35 {
36     n=read();
37     for (int i=1; i<=2*n; i++)
38     {
39         int x=read();
40         if (cz[x])
41         {
42             ans+=query(i-1)-query(cz[x]);
43             modify(cz[x],-1);
44
45         }
46         else
47         {
48             cz[x]=i;
49             modify(i,1);
50         }
51     }
52     printf("%lld\n",ans);
53     return 0;
54 }

代更---------------------

时间: 06-06

poi2007的相关文章

【BZOJ 1103】 [POI2007]大都市meg

1103: [POI2007]大都市meg Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1292  Solved: 660 [Submit][Status] Description 在经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员Blue Mary也开始骑着摩托车传递邮件了.不过,她经常回忆起以前在乡间漫步的情景.昔日,乡下有依次编号为1..n的n个小村庄,某些村庄之间有一些双向的土路.从每个村庄都恰好有一条路径到达村庄1(即比特

BZOJ 1098[POI2007]办公楼

题面: 1098: [POI2007]办公楼biu Time Limit: 20 Sec  Memory Limit: 162 MBSubmit: 1371  Solved: 641[Submit][Status][Discuss] Description FGD开办了一家电话公司.他雇用了N个职员,给了每个职员一部手机.每个职员的手机里都存储有一些同事的电话号码.由于FGD的公司规模不断扩大,旧的办公楼已经显得十分狭窄,FGD决定将公司迁至一些新的办公楼.FGD希望职员被安置在尽量多的办公楼当

bzoj1103[POI2007]大都市meg

bzoj1103[POI2007]大都市meg 题意: 一个n点树,根节点为1,初始时全部边为土路,共n-m+1次操作,每次可将一条边改为公路或求根节点到某个节点要几个多少土路.n,m≤250000 题解: 先求出DFS序,进入节点在时间点的权值为1,离开节点在时间点的权值为-1,如果把公路转成土路就将这条边的左端点的进入时间权值和离开时间权值都置为0,如果询问则输出节点进入时间前缀和.求前缀和及修改的操作可以用树状数组维护. 代码: 1 #include <cstdio> 2 #includ

BZOJ1098: [POI2007]办公楼biu

1098: [POI2007]办公楼biu Time Limit: 20 Sec  Memory Limit: 162 MBSubmit: 777  Solved: 326[Submit][Status] Description FGD开办了一家电话公司.他雇用了N个职员,给了每个职员一部手机.每个职员的手机里都存储有一些同事的电话号码.由于FGD的公司规模不断扩大,旧的办公楼已经显得十分狭窄,FGD决定将公司迁至一些新的办公楼. FGD希望职员被安置在尽量多的办公楼当中,这样对于每个职员来说都

[POI2007]洪水pow 题解

[POI2007]洪水pow 时间限制: 5 Sec  内存限制: 128 MB 题目描述 AKD市处在一个四面环山的谷地里.最近一场大暴雨引发了洪水,AKD市全被水淹没了.Blue Mary,AKD市的市长,召集了他的所有顾问(包括你)参加一个紧急会议.经过细致的商议之后,会议决定,调集若干巨型抽水机,将它们放在某些被水淹的区域,而后抽干洪水.你手头有一张AKD市的地图.这张地图是边长为m*n的矩形,被划分为m*n个1*1的小正方形.对于每个小正方形,地图上已经标注了它的海拔高度以及它是否是A

BZOJ 1100: [POI2007]对称轴osi

1100: [POI2007]对称轴osi Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 630  Solved: 243[Submit][Status][Discuss] Description FGD小朋友--一个闻名遐迩的年轻数学家--有一个小MM,yours.FGD小朋友非常喜欢他的MM,所以他很乐意帮助他的MM做数学作业.但是,就像所有科学的容器一样,FGD的大脑拒绝不停地重复思考同样的问题.不幸的是,yours是一个十分用功的学生,所

[bzoj1103][POI2007]大都市meg(树状数组+dfs序)

1103: [POI2007]大都市meg Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 2031  Solved: 1069[Submit][Status][Discuss] Description 在经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员Blue Mary也开始骑着摩托车传递邮件了.不过,她经常回忆起以前在乡间漫步的情景.昔日,乡下有依次编号为1..n的n个小村庄,某些村庄之间有一些双向的土路.从每个村庄都恰好有一条路径到

bzoj1103【POI2007】大都市meg

1103: [POI2007]大都市meg Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1544  Solved: 776 [Submit][Status][Discuss] Description 在经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员Blue Mary也开始骑着摩托车传递邮件了.不过,她经常回忆起以前在乡间漫步的情景.昔日,乡下有依次编号为1..n的n个小村庄,某些村庄之间有一些双向的土路.从每个村庄都恰好有一条路径

BZOJ 1099([POI2007]树Drz-9次线段树&amp;分类讨论+线段树与插入顺序维护2个参数)

1099: [POI2007]树Drz Time Limit: 15 Sec  Memory Limit: 162 MB Submit: 142  Solved: 55 [Submit][Status] Description CDQZ是一个偏远的小学校,FGD在学校里中了一排树.他却不喜欢这些树的顺序,因为他们高高矮矮显得那么参差不齐. FGD定义这些树的不整齐程度为相邻两树的高度差的和.设树高分别为h1,h2,h3,-,hn.那么不整齐程度定义为:|h1-h2|+|h2-h3|+--+|hn

BZOJ 1110: [POI2007]砝码Odw

1110: [POI2007]砝码Odw Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 547  Solved: 296[Submit][Status][Discuss] Description 在byteotian公司搬家的时候,他们发现他们的大量的精密砝码的搬运是一件恼人的工作.公司有一些固定容量的容器可以装这些砝码.他们想装尽量多的砝码以便搬运,并且丢弃剩下的砝码.每个容器可以装的砝码数量有限制,但是他们能够装的总重量不能超过每个容器的限制