SCOI 2007

2024-02-19 21:14:40

BZOJ 1066 蜥蜴（网络流）

Description

在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃
到边界外。每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石
柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不
变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个
石柱上。

Input

输入第一行为三个整数r，c，d，即地图的规模与最大跳跃距离。以下r行为石竹的初始状态，0表示没有石柱
，1~3表示石柱的初始高度。以下r行为蜥蜴位置，“L”表示蜥蜴，“.”表示没有蜥蜴。

Output

输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。

Sample Input

5 8 2
00000000
02000000
00321100
02000000
00000000
…
…
…LLLL…
…
…

Sample Output

HINT

100%的数据满足：1<=r, c<=20, 1<=d<=4

我只能说：只是一道神级好题
建边十分巧妙
可以看出来这是一道最大流
用最大流求出能逃出的蜥蜴数量can
读入时统计总数量sum
答案即为sum-can
~~好吧上面是废话~~
建边：
1.总共802个点，源点为0，汇点为801,1~ 400为石柱底部，401~800为石柱顶部，石柱的具体建边方式见下
2.对于每个石柱，令它的顶部为底部的编号+400，容量为它的高度，意为：对于一个高度为k的石柱，它最多能让k个蜥蜴通过，这是显然的。
3.对于每个石柱，从源点连一条边到该石柱，容量为1，意为：可以有且最多有1条蜥蜴一开始能在该石柱上
4.对于两个可以互相到达的石柱a与b，即两个石柱的欧式距离小于d，将a石柱的顶部与b石柱的底部连边，容量为infinity，意为：任意蜥蜴都可以通过这个a石柱到达b石柱
5.对于每个可以从该石柱跳出边界的石柱，从该石柱连一条边到汇点，容量为infinity，意为：任意蜥蜴都可以通过这个石柱到达逃出去
然后跑一边dinic即可

/**************************************************************
    Problem: 1066
    User: wiiind
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:7164 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
int sta=0,end=801;
const int maxr=21,maxc=21;
int d;
const int maxe=500001;
int head[maxr*maxc<<1],nex[maxe],to[maxe],val[maxe];
int cnt=1;
char ch[maxc];
int mp[maxr][maxc];
int num[maxr][maxc];
int r,c;
int sum=0;
int can=0;
const int infinity=2147483647;
inline void add (int x,int y,int z){
    //printf ("%d:%d %d %d\n",cnt,x,y,z);
    nex[++cnt]=head[x];
    to[cnt]=y;
    val[cnt]=z;
    head[x]=cnt;
}
inline void ins (int x,int y,int z){
    add (x,y,z); add (y,x,0);
}
queue < int > que;
int op,opp,des;
int dep[maxr*maxc<<1];
bool bfs ()
{
    memset (dep,0,sizeof (dep));
    while (que.size())
        que.pop();
    que.push (sta);
    dep[sta]=1;
    while (que.size())
    {
        op=que.front();
        que.pop();
        for (int i=head[op];i;i=nex[i])
        {
            des=to[i];
            if (val[i]&&!dep[des])
            {
                que.push (des);
                dep[des]=dep[op]+1;
                if (des==end)
                    return 1;
            }
        }
    }
    return 0;
}
int dinic (int x,int flow)
{
    if (x==end) return flow;
    int rest=flow,k;
    for (int i=head[x];i&&rest;i=nex[i]){
        int v=to[i];
        if (val[i]&&dep[v]==dep[x]+1){
            k=dinic (v,min (rest,val[i]));
            if (!k) dep[v]=0;
            val[i]-=k; val[i^1]+=k;
            rest-=k;
        }
    }
    return flow-rest;
}
int n=0;
int rr[maxr*maxc],cc[maxr*maxc];
int main(){
    scanf ("%d%d%d",&r,&c,&d);
    for (register int i=1;i<=r;++i) for (int j=1;j<=c;++j) num[i][j]=(i-1)*c+j;
    for (register int i=1;i<=r;++i){
        scanf ("%s",ch);
        for (int j=1;j<=c;++j){
            mp[i][j]=ch[j-1]-'0';
            if (mp[i][j]){
                rr[++n]=i; cc[n]=j;
                ins (num[i][j],num[i][j]+400,mp[i][j]);
            }
        }
    }
    for (register int i=1;i<=r;++i){
        scanf ("%s",ch);
        for (int j=1;j<=c;++j) if (ch[j-1]=='L'){
                sum++;
                ins (sta,num[i][j],1);      
            }
    }
    for (register int i=1;i<=n;++i){
        int a1=rr[i],b1=cc[i];
        for (int a2=a1-d;a2<=a1+d;++a2) for (int b2=b1-d;b2<=b1+d;++b2) if (mp[a2][b2]&&((a1-a2)*(a1-a2)+(b1-b2)*(b1-b2)<=d*d)&&((a1!=a2)||(b1!=b2))){
            //printf ("%d %d %d %d\n",a1,b1,a2,b2);
            ins (num[a1][b1]+400,num[a2][b2],infinity);
        }
    }
    for (register int i=1;i<=d;i++) for (int j=d+1;j<=r-d;j++){
            ins (num[j][i]+400,end,infinity); ins (num[j][c-i+1]+400,end,infinity);
        }
    for (register int i=1;i<=d;i++) for(int j=1;j<=c;j++){
            ins (num[i][j]+400,end,infinity); ins (num[r-i+1][j]+400,end,infinity);
        }
    while (bfs()) while (opp=dinic (sta,infinity)) can+=opp;
    printf ("%d",sum-can);
    return 0;
}

BZOJ 1067 降雨量（线段树）

Description

我们常常会说这样的话：“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年，且对于任意
Y＜Z＜X，Z年的降雨量严格小于X年。例如2002，2003，2004和2005年的降雨量分别为4920，5901，2832和3890，
则可以说“2005年是自2003年以来最多的”，但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未
知，有的说法是可能正确也可以不正确的。

Input

输入仅一行包含一个正整数n，为已知的数据。以下n行每行两个整数yi和ri，为年份和降雨量，按照年份从小
到大排列，即yi＜yi+1。下一行包含一个正整数m，为询问的次数。以下m行每行包含两个数Y和X，即询问“X年是
自Y年以来降雨量最多的。”这句话是必真、必假还是“有可能”。

Output

对于每一个询问，输出true，false或者maybe。

Sample Input

6
2002 4920
2003 5901
2004 2832
2005 3890
2007 5609
2008 3024
5
2002 2005
2003 2005
2002 2007
2003 2007
2005 2008

Sample Output

false
true
false
maybe
false

HINT

100%的数据满足：1<=n<=50000, 1<=m<=10000, -10^9<=yi<=109, 1<=ri<=10^9

神仙题
推荐一篇题解

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cstdlib>
using namespace std;
const int SZ = 50010;
 
struct SGT
{
    int l, r, maxx;
}tree[SZ << 2];
map<int, int> mp;
int num[SZ], year[SZ], n, m;
 
void update(int now)
{
    tree[now].maxx = max(tree[now << 1].maxx, tree[now << 1 | 1].maxx);
}
 
void build(int now, int l, int r)
{
    tree[now].l = l;
    tree[now].r = r;
    if(l == r)
    {
        tree[now].maxx = num[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(now << 1, l, mid);
    build(now << 1 | 1, mid + 1, r);
    update(now);
}
 
int ask(int now, int l, int r)
{
    if(l <= tree[now].l && tree[now].r <= r)
        return tree[now].maxx;
    int mid = (tree[now].l + tree[now].r) >> 1;
    int maxx = 0;
    if(l <= mid) maxx = max(maxx, ask(now << 1, l, r));
    if(r > mid) maxx = max(maxx, ask(now << 1 | 1, l, r));
    return maxx;
}
 
int check(int a, int b)
{
    int l = upper_bound(year + 1, year + 1 + n, a) - year;
    int r = lower_bound(year + 1, year + 1 + n, b) - year;
    r--;
    int maxx = ask(1, l, r);
    int xx = num[mp[a]], yy = num[mp[b]];
    if(yy && maxx >= yy) return 0;
    if(xx && yy > xx) return 0;
    if(xx && maxx >= xx) return 0;
    if(!xx || !yy) return -1;
    if(r - l + 1 < b - a - 1) return -1;
    return 1;
}
 
int main()
{
    scanf("%d", &n);
    int y, r;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d %d", &y, &r);
        mp[y] = i; num[i] = r; year[i] = y;
    }   
    build(1, 1, n);
    scanf("%d", &m);
    int a, b;
    for(int i = 1; i <= m; i++)
    {
        scanf("%d%d", &a, &b);
        int flag = check(a, b);
        if(flag == 1) puts("true");
        else if(flag == 0) puts("false");
        else puts("maybe");
    }
    return 0;
}

BZOJ 1068 压缩（区间DP）

Description

给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小
写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没
有M，则从串的开始算起）开始的解压结果（称为缓冲串）。 bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程

　　另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。

Input

输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。

Output

输出仅一行，即压缩后字符串的最短长度。

Sample Input

bcdcdcdcdxcdcdcdcd

Sample Output

HINT

在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。

【限制】

100%的数据满足：1<=n<=50 100%的数据满足：1<=n<=50

看了好久才看出来这是一道区间DP
~~又是一道我不想写题解的题~~
开一个数组f[maxl][maxl][0/1]表示最小值
前两个表示一段区间
0与1表示该段区间是否有M
考虑一段区间
1.是否有M
2.能否存在R，有就必用
具体实现如下

/**************************************************************
    Problem: 1068
    User: wiiind
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:1308 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int maxl=51;
int len;
char s[maxl];
int f[maxl][maxl][2];
bool check (int x,int y){
    if ((y-x+1)&1) return 0;
    int mid=(x+y)/2;
    for (register int i=1;i<=mid-x+1;++i) if (s[x+i-1]!=s[mid+i]) return 0;
    return 1;
}
int main(){
    scanf ("%s",s+1);
    len=strlen (s+1);
    for (register int i=len;i;--i) for (int j=i;j<=len;++j){
        f[i][j][0]=f[i][j][1]=j-i+1;
        for (int k=i;k<=j;++k) f[i][j][0]=min (f[i][j][0],f[i][k][0]+j-k);
        for (int k=i;k<=j;++k) f[i][j][1]=min (f[i][j][1],min (f[i][k][0],f[i][k][1])+min (f[k+1][j][0],f[k+1][j][1])+1);
        if (check (i,j)) f[i][j][0]=f[i][(i+j)/2][0]+1;
    }
    printf ("%d",min (f[1][len][0],f[1][len][1]));
    return 0;
}

BZOJ 1070修车（费用流）

Description

同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同
的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最
小。说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

Input

第一行有两个m,n，表示技术人员数与顾客数。接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人
员维修第i辆车需要用的时间T。

Output

最小平均等待时间，答案精确到小数点后2位。

Sample Input

2 2
3 2
1 4

Sample Output

1.50

HINT

数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)

又是一道精彩绝伦的建图题
将每个工人都拆成n个点
。。。
我不想写
推荐一篇题解

/**************************************************************
    Problem: 1070
    User: wiiind
    Language: C++
    Result: Accepted
    Time:312 ms
    Memory:4368 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=5001,maxm=50001;
int head[maxn];
int n,m;
int nex[maxm<<1],to[maxm<<1],fl[maxm<<1],val[maxm<<1],flow[maxn],dis[maxn],pre[maxn],last[maxn];
int cnt=1;
int sta,end;
template < class T > inline void read (T &x){
    x=0;char ch=getchar();
    while(!isdigit(ch)){ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
}
int mincost=0;
queue < int > que;
inline void add (int a,int b,int c,int d){
    nex[++cnt]=head[a];
    to[cnt]=b;
    fl[cnt]=c;
    val[cnt]=d;
    head[a]=cnt;
}
inline void ins (int a,int b,int c,int d){
    add (a,b,c,d); add (b,a,0,-d);
}
bool vis[maxn];
bool spfa (){
    memset (dis,0x7f,sizeof (dis)); memset (flow,0x7f,sizeof (flow)); memset (vis,0,sizeof (vis));
    que.push (sta);
    vis[sta]=1; pre[end]=-1; dis[sta]=0;
    while (!que.empty()){
        int op=que.front();
        que.pop();
        vis[op]=0;
        for (int i=head[op];i;i=nex[i]){
            if (!fl[i]) continue ;
            int v=to[i];
            if (dis[v]>dis[op]+val[i]){
                dis[v]=dis[op]+val[i];
                pre[v]=op; last[v]=i;
                flow[v]=min (flow[op],fl[i]);
                if (!vis[v]){
                    vis[v]=1;
                    que.push (v);
                }
            }
        }
    }
    return pre[end]!=-1;
}
void work (){
    while (spfa ()){
        int op=end;
        mincost+=dis[end]*flow[end];
        while (op!=sta){
            fl[last[op]]-=flow[end]; fl[last[op]^1]+=flow[end];
            op=pre[op];
        }
    }
}
int mp[601][601];
int main(){
    read (m); read (n);
    memset (head,-1,sizeof (head));
    int siz=n*m;
    for (register int i=1;i<=n;++i) for (int j=1;j<=m;++j) read (mp[i][j]);
    sta=0; end=siz+n+1;
    for (register int i=1;i<=m;++i) for (int j=1;j<=n;++j) ins (sta,(i-1)*n+j,1,0);
    for (register int i=1;i<=n;++i) for (int j=1;j<=m;++j) for (int k=1;k<=n;++k) ins ((j-1)*n+k,siz+i,1,k*mp[i][j]);
    for (register int i=1;i<=n;++i) ins (siz+i,end,1,0);
    work ();
    printf ("%0.2lf",(double)mincost/(double)n);
    return 0;
}

码农公寓

BZOJ 1066 蜥蜴（网络流）

Description

Input

Output

Sample Input

Sample Output

HINT

BZOJ 1067 降雨量（线段树）

Description

Input

Output

Sample Input

Sample Output

HINT

BZOJ 1068 压缩（区间DP）

Description

Input

Output

Sample Input

Sample Output

HINT

【限制】

BZOJ 1070修车（费用流）

Description

Input

Output

Sample Input

Sample Output

HINT

相关文章