2018.2.24 POI 模拟赛

考试

本次考试排名:Rank15(一般)
本次考试题目推荐:[POI2006]ORK-Ploughing(贪心优化搜索),[POI2007]POW-The Flood(贪心与并查集)(蛮好的思维题).

1.[POI2006]Kra-The Disks

题面描述

一个框，告诉你每一层的宽度。
向下丢给定宽度的木块。
木块会停在卡住他的那一层之上，异或是已经存在的木块之上。
询问丢的最后一个木块停在第几层。

输入格式

第一行两个整数 n 和 m ( 1<= n, m<= 300 000) 表示水管包含的圆筒数以及盘
子总数.
第二行给出 n 个整数 r1, r2,...,rn ( 1 <=ri<= 1 000 000 000 for 1<= i<= n) 表示水管从上到下所有圆筒的直径. 第三行给出 m 个整数 k1, k2,..., km ( 1<= kj<= 1000 000 000 for 1<= j<= m) 分别表示 Johnny 依次扔下去的盘子直径.

输出格式

一个整数输出最后一个盘子掉在了哪一层,如果盘子不能扔进水管,那么打印 0.

数据范围

已体现在输入格式中

题解

首先不难思考到，若越上层的砖块越短，那么对下面砖块的影响越大，因而考虑输入时便将所有的砖块一直向上取Min,从而构成单调不上升序列
方法一:O(N*logN) 分治
对于每一个盘子二分查找(这也是我考场写的方法)
方法二:O(N) 模拟
考虑从下往上一个砖块与当前砖块进行判断，由于每个砖块要不就作为圆盘承纳者，要不就跳过，因而每个砖块最多被扫一次(考场时yy错了)

int find(int x,int now)
{
    int l=1,r=now,ans=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(a[mid]<x)ans=mid,r=mid-1;
        else l=mid+1;
    }
    if(!ans)return now;
    else return ans-1;
}
int main()
{
    n=read();m=read();now=n;
    a[0]=1e9+5;
    for(int i=1;i<=n;i++)a[i]=min(read(),a[i-1]);
    int x;bool flag=0;
    while(m--)
    {
        x=read();
        if(flag)continue;
        int k=find(x,now);
        now=k-1;
        if(k==0){flag=1;}
    }
    if(flag)puts("0");
    else printf("%d\n",now+1);
    return 0;
}

2.[POI2007]POW-The Flood

题面描述

AKD 市处在一个四面环山的谷地里。最近一场大暴雨引发了洪水,AKD 市全被 水淹没了。Blue Mary,AKD 市的市长,召集了他的所有顾问(包括你)参加一 个紧急会议。经过细致的商议之后,会议决定,调集若干巨型抽水机,将它们放 在某些被水淹的区域,而后抽干洪水。 你手头有一张 AKD 市的地图。这张地图是边长为 m*n 的矩形,被划分为 m*n 个 1*1 的小正方形。对于每个小正方形,地图上已经标注了它的海拔高度以及它 是否是 AKD 市的一个组成部分。地图上的所有部分都被水淹没了。并且,由于 这张地图描绘的地面周围都被高山所环绕,洪水不可能自动向外排出。显然,我 们没有必要抽干那些非 AKD 市的区域。 每个巨型抽水机可以被放在任何一个 1*1 正方形上。这些巨型抽水机将持续地抽 水直到这个正方形区域里的水被彻底抽干为止。当然,由连通器原理,所有能向 这个格子溢水的格子要么被抽干,要么水位被降低。每个格子能够向相邻的格子 溢水,“相邻的”是指(在同一高度水平面上的射影)有公共边。

输入格式

第一行是两个数 m,n(1<=m,n<=1000). 以下 m 行,每行 n 个数,其绝对值表示相应格子的海拔高度;若该数为正,表 示他是 AKD 市的一个区域;否则就不是。 请大家注意:所有格子的海拔高度其绝对值不超过 1000,且可以为零.

输出格式

只有一行,包含一个整数,表示至少需要放置的巨型抽水机数目

数据范围

已体现在输入格式中

题解

首先你需要看懂题目并将样例手玩出来，你要明白对于两个城市的路径之间若存在一条极高的山峰，那么就相当于将两个城市分隔开。也就是你必须要在这两座城市中都放一台抽水机。那么我们开始考虑将所有点按海拔排序并插入，将当前点与其周围的点连边，如果周围城市已存在抽水机的话则不需添加。
那么当且仅当：只有该点为城市且周围的并查集中没有抽水机则在该城市放一台抽水机(贪心)，然后修改。有些细节要注意：先将所有相同点权与其周围点合并，再来看是否修改(并查集)。
可以用排序，也可以打BFS

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int _=1005;
inline int read()
{
    char ch='!';int z=1,num=0;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')z=-1,ch=getchar();
    while(ch<='9'&&ch>='0')num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
    return z*num;
}
struct hand{int v,x,y,c;}a[_*_];
struct some{int fa;bool ji;}b[_*_];
bool cmp(hand A,hand B){return A.v<B.v;}
int m,n,len;
int find(int x)
{
    if(b[x].fa!=x)b[x].fa=find(b[x].fa);
    return b[x].fa;
}
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
void work(int i)
{
    int x=a[i].x,y=a[i].y,t1=(x-1)*n+y;
    b[t1].fa=t1;
    for(int op=0;op<4;op++)
    {
        int Dx=x+dx[op],Dy=y+dy[op];
        if(Dx<1||Dx>m||Dy<1||Dy>n)continue;
        int t2=(Dx-1)*n+Dy;
        int T1=find(t1),T2=find(t2);
        if(T1!=T2&&T1&&T2)
        {
            b[T2].ji|=b[T1].ji;
            b[T1].fa=T2;
        }
    }
}
int main()
{
    m=read();n=read();
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int x=read();
            if(x<=0)a[++len]=(hand){-x,i,j,0};
            else a[++len]=(hand){x,i,j,1};
        }
    }
    sort(a+1,a+1+len,cmp);
    int ans=0;
    for(int i=1;i<=len;i++)
    {
        int l=i;
        work(i);
        while(a[i].v==a[i+1].v)
        {
            i++;
            work(i);
        }
        for(int j=l;j<=i;j++)
        {
            int x=a[j].x,y=a[j].y,t=(x-1)*n+y;
            int tt=find(t);
            if(!b[tt].ji&&a[j].c)
            {
                ans++;
                b[tt].ji=1;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

3.[POI2007]MEG-Megalopolis

在经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员 Blue Mary也开始骑着摩托车传递邮件了。不过,她经常回忆起以前在乡间漫步的情景。昔日,乡下有依次编号为 1..n 的 n 个小村庄,某些村庄之间有一些双向的土路。从每个村庄都恰好有一条路径到达村庄 1(即比特堡)。并且,对于每个村庄,它到比特堡的路径恰好只经过编号比它的编号小的村庄。另外,对于所有道路而言,它们都不在除村庄以外的其他地点相遇。在这个未开化的地方,从来没有过高架桥和地下铁道。随着时间的推移,越来越多的土路被改造成了公路。至今,BlueMary还清晰地记得最后一条土路被改造为公路的情景。现在,这里已经没有土路了——所有的路都成为了公路,而昔日的村庄已经变成了一个大都市。Blue Mary想起了在改造期间她送信的经历。她从比特堡出发,需要去某个村庄,并且在两次送信经历的间隔期间,有某些土路被改造成了公路.现在 Blue Mary 需要你的帮助:计算出每次送信她需要走过的土路数目。(对于公路,她可以骑摩托车;而对于土路,她就只好推车了。)

输入格式

第一行是一个数 n.
以下 n-1 行,每行两个整数 a,b(1<=a 连接着村庄 a 和村庄 b.
以下一行包含一个整数 m,表示 Blue Mary 曾经在改造期间送过 m 次信。
以下 n+m-1 行,每行有两种格式的若干信息,表示按时间先后发生过的 n+m-1
次事件:若这行为 A a b(1<=a 若这行为 W a, 则表示 Blue Mary 曾经从比特堡送信到村庄 a.

输出格式

有 m 行,每行包含一个整数,表示对应的某次送信时经过的土路数目。

数据范围

输入保证:
对于 70%数据:1<= N , M <=50
对于所有数据:1<= N , M <=100000;

题解

这个题目应该比较裸了吧(连树剖都不用)身旁有大佬使用$LCT$，可是我并不会，想想这个题目也不要维护链，只需要维护子树，应而只需要用树状数组维护子树信息了

void dfs(int u,int fa)
{
    dfn[u]=++tot;
    for(int e=head[u];e;e=a[e].next)
    {
        int v=a[e].to;
        if(v==fa)continue;
        dfs(v,u);
    }
    zi[u]=tot;
}
int c[_];
void update(int x,int k){while(x<=n){c[x]+=k;x+=lowbit(x);}}
int query(int x){int ans=0;while(x){ans+=c[x];x-=lowbit(x);}return ans;}
int main()
{
    n=read();
    int a,b,x;
    for(int i=1;i<n;i++)
    {
        a=read();b=read();
        link(a,b);link(b,a);
    }
    dfs(1,0);
    for(int i=2;i<=n;i++)
    {
        update(dfn[i],1);
        update(zi[i]+1,-1);
    }
    m=read();
    m+=n-1;
    char ch;
    while(m--)
    {
        cin>>ch;
        if(ch=='W')
        {
            x=read();
            printf("%d\n",query(dfn[x]));           
        }
        else
        {
            a=read();b=read();
            if(a>b)swap(a,b);
            update(dfn[b],-1);
            update(zi[b]+1,1);
        }
    }
    return 0;
}

4.[POI2006]ORK-Ploughing

我们知道，如果我们选定了以横向为主，或者纵向为主，
那么就有尽可能减少另一个方向上耕地的次数

所以分开贪心，但是本质相同，所以接下来只考虑纵向为主

既然确定了以纵向为主，那么就要尽可能减少横向操作的次数
所以，只要能够纵向耕地，就不考虑横向耕地
可是，如果到了某个时候，纵向无法耕了
此时必须横向耕
但是我们不知道应该从上面开始还是下面开始

为了解决这个问题
我们假设上面最多耕的次数是有限次
换种想法，我们假设上面至少耕这么多次
既然上面的次数确定，那么下方的耕地次数越少越好
所以耕地的优先级：
左-右-上-下
只要能够耕就一定耕
这样，枚举-贪心的做法(是不是很玄学)就可以做啦
横向、纵向分别算一遍
时间复杂度O((n+m)^2)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int _=2005;
inline int read()
{
    char ch='!';int z=1,num=0;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')z=-1,ch=getchar();
    while(ch<='9'&&ch>='0')num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
    return z*num;
}
int K,m,n;
int ans=1e9,g[_][_],f[_][_];
int work1(int st)
{
    int s1=1,s2=1,t1=n,t2=m,cnt=0;
    int sum=0;
    while(s1<=t1&&s2<=t2)
    {
        cnt++;
        //左
        sum=g[t1][s2]-g[s1-1][s2];
        if(sum<=K){s2++;continue;}
        //右
        sum=g[t1][t2]-g[s1-1][t2];
        if(sum<=K){t2--;continue;}
        //上
        sum=f[s1][t2]-f[s1][s2-1];
        if(sum<=K&&s1<st){s1++;continue;}
        //下
        sum=f[t1][t2]-f[t1][s2-1];
        if(sum<=K){t1--;continue;}
        cnt=1e9;break;
    }
    return cnt;
}
int work2(int st)
{
    int s1=1,s2=1,t1=n,t2=m,cnt=0;
    int sum=0;
    while(s1<=t1&&s2<=t2)
    {
        cnt++;
        //上
        sum=f[s1][t2]-f[s1][s2-1];
        if(sum<=K){s1++;continue;}
        //下
        sum=f[t1][t2]-f[t1][s2-1];
        if(sum<=K){t1--;continue;}
        //左
        sum=g[t1][s2]-g[s1-1][s2];
        if(sum<=K&&s2<st){s2++;continue;}
        //右
        sum=g[t1][t2]-g[s1-1][t2];
        if(sum<=K){t2--;continue;}
        cnt=1e9;break;
    }
    return cnt;
}
int main()
{
    K=read();m=read();n=read();
    int x;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            x=read();
            f[i][j]=f[i][j-1]+x;
            g[i][j]=g[i-1][j]+x;
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans=min(ans,work1(i));
    }//限制上方最多移动到第i行
    for(int i=1;i<=m;i++)
    {
        ans=min(ans,work2(i));
    }//限制左方最多移动到第j列
    cout<<ans<<endl;
    return 0;
}

本次题解报告完成于3.1，今后一定要继续坚持!