24 条题解
-
2
ATHENS_ LV 9 @ 2017-10-13 23:11:19
先bfs，注意一个储水厂可到达的沙漠地区肯定是连续的，之后做区间覆盖就好了。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> #include <queue> using namespace std; const int maxn=505; int dx[]={1,-1,0,0}; int dy[]={0,0,-1,1}; int n,m,h[maxn][maxn],ans; bool vis[maxn],vist[maxn][maxn]; struct node{ int l,r; }e[maxn]; struct odd{ int x,y; }; queue <odd> q; bool cmp(const node &a,const node &b){ if(a.l<b.l)return 1; else if(a.l==b.l)return a.r<b.r; return 0; } void bfs(int x){ memset(vist,0,sizeof vist); odd st; st.x=1;st.y=x; q.push(st);vist[1][x]=1; while(!q.empty()){ odd u=q.front();q.pop(); if(u.x==n){ vis[u.y]=1; if(e[x].r<u.y)e[x].r=u.y; if(!e[x].l)e[x].l=u.y,e[x].r=u.y; else if(e[x].l>u.y)e[x].l=u.y; } for(register int i=0;i<4;++i){ int nx=u.x+dx[i]; int ny=u.y+dy[i]; if(nx<1||nx>n||ny<1||ny>m||h[nx][ny]>=h[u.x][u.y]||vist[nx][ny])continue; odd neww; neww.x=nx,neww.y=ny;q.push(neww);vist[nx][ny]=1; } } } int main(){ scanf("%d%d",&n,&m); for(register int i=1;i<=n;++i){ for(register int j=1;j<=m;++j){ scanf("%d",&h[i][j]); } } for(register int i=1;i<=m;++i){ bfs(i); } bool flag=0;int ct=0; for(register int i=1;i<=m;++i){ if(!vis[i])++ct,flag=1; } if(flag){ printf("0\n%d",ct); return 0; } sort(e+1,e+m+1,cmp); int idx=1,s=1,t,cnt=0; while(s<=m){ t=s; for(register int i=idx;i<=m;++i){ if(e[i].l<=t){ if(e[i].r>=t)s=e[i].r; } else { idx=i;break; } } cnt++;s++; } printf("1\n%d",cnt); return 0; } -
0
#include<bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,a,b) for(int i = a; i <= b; ++i) #define PER(i,a,b) for(int i = a; i >= b; --i) #define PB push_back #define MP make_pair #define fi first #define se second typedef long long LL; typedef double DB; const int maxn = 500; int n, m; int seg[maxn*maxn+5]; int hi[maxn+5][maxn+5]; int L[maxn+5][maxn+5], R[maxn+5][maxn+5]; struct Node { int l, r, id; Node() {} Node(int _l, int _r, int _id) : l(_l), r(_r), id(_id) {} bool operator<(const Node &a) { return l < a.l; } } fk[maxn+5]; void Min(int &a, int b) { a = min(a,b); } void Max(int &a, int b) { a = max(a,b); } const int walk[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}}; bool vi[maxn+5][maxn+5]; int bfs(int top) { queue<int> q; REP(i,1,top) q.push(1000 + seg[i]), vi[1][seg[i]] = 1; while(!q.empty()) { int x = q.front()/1000, y = q.front()%1000; q.pop(); for(int t = 0; t < 4; ++t) { int xx = x + walk[t][0]; int yy = y + walk[t][1]; if(xx<1 || xx>n || yy<1 || yy>m) continue; if(vi[xx][yy] || hi[xx][yy]>=hi[x][y]) continue; vi[xx][yy] = 1; q.push(xx*1000 + yy); } } int res = 0; REP(i,1,m) res += (vi[n][i]==0); return res; } int main() { scanf("%d%d", &n, &m); int top = 0; REP(i,1,n) REP(k,1,m) { scanf("%d", &hi[i][k]); seg[++top] = i*1000 + k; } sort(seg+1, seg+1+top, [&](int a, int b) { return hi[a/1000][a%1000]<hi[b/1000][b%1000]; } ); REP(i,1,top) { int x = seg[i]/1000, y = seg[i]%1000; if(x==n) L[x][y] = R[x][y] = y; else L[x][y] = m+10, R[x][y] = -1; for(int t = 0; t < 4; ++t) { int xx = x + walk[t][0]; int yy = y + walk[t][1]; if(xx<1 || xx>n || yy<1 || yy>m || hi[xx][yy]>=hi[x][y]) continue; Min(L[x][y], L[xx][yy]); Max(R[x][y], R[xx][yy]); } } REP(i,1,m) fk[i] = Node(L[1][i], R[1][i], i); sort(fk+1, fk+1+m); int pt = 1, now = 0; top = 0; priority_queue<pair<int,int>> q; while(now<m) { while(pt<=m && fk[pt].l<=now+1) { q.push( pair<int,int>(fk[pt].r, fk[pt].id) ); ++pt; } if(q.empty() || q.top().fi<=now) break; now = q.top().fi; seg[++top] = q.top().se; q.pop(); } if(now<m) { top = 0; REP(i,1,m) seg[++top] = i; } int cnt = bfs(top); if(cnt) printf("0\n%d\n", cnt); else printf("1\n%d\n", top); return 0; } -
0
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; const int INF=0x3f3f3f3f; const int LIM=503; struct Stage{ int l,r; Stage():l(INF),r(-INF){} inline bool operator < (Stage r) const { return l<r.l; } }S[LIM]; int n,m,M[LIM][LIM],f[LIM],cnt=0; bool vis[LIM][LIM],ans[LIM]; void dfs(int x,int y,int ori) { vis[x][y]=1; if(x==m){ ans[y]=1; S[ori].l=min(S[ori].l,y); S[ori].r=max(S[ori].r,y); } if(M[x+1][y]<M[x][y]&&x!=m&&!vis[x+1][y]) dfs(x+1,y,ori); if(M[x-1][y]<M[x][y]&&x!=1&&!vis[x-1][y]) dfs(x-1,y,ori); if(M[x][y+1]<M[x][y]&&y!=n&&!vis[x][y+1]) dfs(x,y+1,ori); if(M[x][y-1]<M[x][y]&&y!=1&&!vis[x][y-1]) dfs(x,y-1,ori); } int main() { scanf("%d%d",&m,&n); memset(f,63,sizeof f); f[0]=0; for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) scanf("%d",&M[i][j]); for(int i=1;i<=n;++i) { memset(vis,0,sizeof vis); dfs(1,i,i); } for(int i=1;i<=n;++i) if(!ans[i]) ++cnt; if(cnt) printf("0\n%d",cnt); else{ printf("1\n"); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j){ if(i>=S[j].l&&i<=S[j].r) f[i]=min(f[i],f[S[j].l-1]+1); } printf("%d",f[n]); } return 0; } -
0
TM这是我第一次接触区间覆盖问题。。。
不过搞清楚之后觉得这个提高组最后一题有点水啊。。。
测试数据 #0: Accepted, time = 0 ms, mem = 4144 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 4144 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 4140 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 4140 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 4144 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 4148 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 4152 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 4156 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 4168 KiB, score = 10
测试数据 #9: Accepted, time = 46 ms, mem = 4208 KiB, score = 10
Accepted, time = 91 ms, mem = 4208 KiB, score = 100 -
0
水题水一发
```c++
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int INF = 1000000000;
const int maxn = 500 + 10;struct Block {
int L, R;
bool operator < (const Block& rhs) const {
return L < rhs.L;
}
};int n, m;
int ans;
int vis[maxn];
int vis1[maxn][maxn];
int hg[maxn][maxn];
Block blocks[maxn];const int dr[] = { -1, 1, 0, 0};
const int dc[] = { 0, 0, 1, -1};void dfs (int r, int c, int n_block) {
if (r == n) {
if (!vis[c]) { vis[c] = 1; ans--;}
blocks[n_block].L = min(blocks[n_block].L, c);
blocks[n_block].R = max(blocks[n_block].R, c);
}
vis1[r][c] = n_block;
for (int d = 0; d < 4; d++)
if (hg[r][c] > hg[r+dr[d]][c+dc[d]] && vis1[r+dr[d]][c+dc[d]] != n_block)
dfs(r+dr[d], c+dc[d], n_block);
}int solve () {
int cnt = 0;
sort(blocks+1, blocks+m+1);
int L = 1, k = 1;
while (L <= m) {
cnt++;
int R = L;
for ( ; k <= m; k++) {
if (blocks[k].L > L) break;
R = max(R, blocks[k].R);
}
L = R + 1;
}
return cnt;
}int main ()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &hg[i][j]);for (int i = 1; i <= n; i++) hg[i][0] = hg[i][m+1] = INF;
for (int j = 1; j <= m; j++) hg[0][j] = hg[n+1][j] = INF;ans = m;
for (int i = 1; i <= m; i++) {
blocks[i].L = INF; blocks[i].R = -1;
if ((i == 1 || i == m) || (hg[1][i] >= hg[1][i-1] && hg[1][i] >= hg[1][i+1]))
dfs(1, i, i);
}if (ans > 0) printf("0\n%d\n", ans);
else printf("1\n%d\n", solve());
return 0;
}
``` -
0
everforever LV 10 @ 2016-06-30 17:51:51
其实只要一遍DFS就全求出来了。。。（然而区间覆盖写BFS用了临接表让我怀疑自己的脑袋。。。）
顺便问一下#2是什么为什么一直RE好不解。。。
#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 510
using namespace std;int n,m;
int map[MAXN][MAXN];int l[MAXN][MAXN],r[MAXN][MAXN];
int vis[MAXN][MAXN];
int can[MAXN];int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};void dfs(int x,int y)
{
if(vis[x][y])return ;
vis[x][y]=1;
for(int i=0;i<4;i++)
if(map[x][y]>map[x+xx[i]][y+yy[i]])
{
dfs(x+xx[i],y+yy[i]);
l[x][y]=min(l[x][y],l[x+xx[i]][y+yy[i]]);
r[x][y]=max(r[x][y],r[x+xx[i]][y+yy[i]]);
}
if(x==n)
{
l[x][y]=min(l[x][y],y);
r[x][y]=max(r[x][y],y);
}
}int pos=0;
int fst[MAXN],next[MAXN*MAXN],to[MAXN*MAXN],poi=0;
void add(int op,int ed)
{next[++poi]=fst[op],fst[op]=poi,to[poi]=ed;return ;}
void build()
{
for(int i=0;i<pos;i++)
for(int j=i+1;j<pos;j++)
{
if(l[1][can[j]]<=r[1][can[i]]+1)add(can[i],can[j]);
else break;
}
}int q[MAXN],inq[MAXN];
int dep[MAXN];
int bfs()
{
memset(dep,0x7f,sizeof(dep));
int t=0,h=0,now;
while(l[1][can[t]]==1&&t<pos)q[t]=can[t],dep[can[t]]=1,inq[can[t]]=1,t++;
while(t!=h)
{
now=q[h++],h%=MAXN;
if(r[1][now]==m)return dep[now];
for(int i=fst[now];i;i=next[i])
{
if(dep[to[i]]>dep[now]+1)
{
dep[to[i]]=dep[now]+1;
if(!inq[to[i]])q[t++]=to[i],inq[to[i]]=1,t%=MAXN;
}
}
}
return 0;
}int main()
{
scanf("%d%d",&n,&m);
memset(map,0x7f,sizeof(map));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&map[i][j]);
memset(l,0x7f,sizeof(l));
memset(r,0,sizeof(r));
for(int i=1;i<=m;i++)
dfs(1,i);int cnt=0;
bool flag=false;
for(int i=1;i<=m;i++)
{
if(!flag&&r[1][i]!=0)can[pos++]=i;
if(!vis[n][i])
{
flag=true;
cnt++;
}
}
if(flag)
printf("0\n%d\n",cnt);
else
{
build();
printf("1\n%d\n",bfs());
}return 0;
} -
0
详细题解http://blog.csdn.net/Balala_Energy/article/details/51227646
```c++
#include <iostream>
#include <cstdio>
#include <queue>
#include <climits>
using namespace std;
const int L=501;
const int INF=INT_MAX;
int n,m; int map[L][L]; int F[L],LEFT[L],RIGHT[L];//main
struct zk { int x,y; }; queue<zk> q; bool used[L][L];//bfs
bool LEFTused[L][L],RIGHTused[L][L];//dfs
void read()
{
int i,j;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
F[i]=INF;
F[1]=1;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
scanf("%d",&map[i][j]);
return;
}
bool bfs()
{
while(!q.empty()) q.pop();
zk temp; temp.y=1; int a,b,i;
for (i=1;i<=m;i++)
{
temp.x=i;
q.push(temp);
used[1][i]=1;
}
while(!q.empty())
{
temp=q.front();
a=temp.y; b=temp.x;
if (a>1&&!used[a-1][b]&&map[a][b]>map[a-1][b])
{
temp.y=a-1; temp.x=b;
q.push(temp); used[a-1][b]=1;
}
if (a<n&&!used[a+1][b]&&map[a][b]>map[a+1][b])
{
temp.y=a+1; temp.x=b;
q.push(temp); used[a+1][b]=1;
}
if (b>1&&!used[a][b-1]&&map[a][b]>map[a][b-1])
{
temp.y=a; temp.x=b-1;
q.push(temp); used[a][b-1]=1;
}
if (b<m&&!used[a][b+1]&&map[a][b]>map[a][b+1])
{
temp.y=a; temp.x=b+1;
q.push(temp); used[a][b+1]=1;
}
q.pop();
}
for (i=1;i<=m;i++)
if (!used[n][i])
return 0;
return 1;
}
void dfs1(int num,int x,int y,int front)
{
if(LEFTused[x][y]==1) return;
LEFTused[x][y]=1;
if(x==1) LEFT[y]=num;
if(x-1>=1&&front!=2&&map[x-1][y]>map[x][y]) dfs1(num,x-1,y,1);
if(x+1<=n&&front!=1&&map[x+1][y]>map[x][y]) dfs1(num,x+1,y,2);
if(y-1>=1&&front!=4&&map[x][y-1]>map[x][y]) dfs1(num,x,y-1,3);
if(y+1<=m&&front!=3&&map[x][y+1]>map[x][y]) dfs1(num,x,y+1,4);
return;
}
void dfs2(int num,int x,int y,int front)
{
if(RIGHTused[x][y]==1) return;
RIGHTused[x][y]=1;
if(x==1) RIGHT[y]=num;
if(x-1>=1&&front!=2&&map[x-1][y]>map[x][y]) dfs2(num,x-1,y,1);
if(x+1<=n&&front!=1&&map[x+1][y]>map[x][y]) dfs2(num,x+1,y,2);
if(y-1>=1&&front!=4&&map[x][y-1]>map[x][y]) dfs2(num,x,y-1,3);
if(y+1<=m&&front!=3&&map[x][y+1]>map[x][y]) dfs2(num,x,y+1,4);
return;
}
void dp()
{
int i,j;
for(i=2;i<=m;i++)
for(j=1;j<=m;j++)
{
if(LEFT[j]<=i&&RIGHT[j]>=i)
F[i]=min(F[i],F[LEFT[j]-1]+1);
else if(LEFT[j]>i)
break;
}
return;
}
void work()
{
int i,ans=0;
if (!bfs())
{
for (i=1;i<=m;i++)
if (!used[n][i])
ans++;
printf("0\n%d",ans);
}
else
{
for(i=1;i<=m;i++)
dfs1(i,n,i,0);
for(i=m;i>=1;i--)
dfs2(i,n,i,0);
dp();
printf("1\n%d",F[m]);
}
return;}
int main()
{
freopen("flow.in","r",stdin);
freopen("flow.out","w",stdout);
read();
work();
return 0;
}
``` -
0
feng_lingsong LV 9 @ 2015-10-24 21:59:28
第一次没有输入0和1直接爆零。。。。
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>using namespace std;
int n, m;
int h[5 05][505];
bool f0[505][505];
int l[505], r[505];
int f[505];
int q[500005], x[500005], y[500005];void bfs2(int i, int X, int Y) {
memset(x, 0, sizeof (x));
memset(y, 0, sizeof (y));
int now, end;
now = end = 0;
x[now] = X;
y[now] = Y;
while (now <= end) {
int x0, y0;
x0 = x[now];
y0 = y[now];
if (f0[x0][y0]) {
++now;
continue;
}
f0[x0][y0] = true;
if (x0 == n) {
l[i] = min(l[i], y0);
r[i] = max(r[i], y0);
}
if (h[x0][y0] > h[x0][y0 + 1] && y0 + 1 <= m) {
x[++end] = x0;
y[end] = y0 + 1;
}
if (h[x0][y0] > h[x0][y0 - 1] && y0 - 1 >= 1) {
x[++end] = x0;
y[end] = y0 - 1;
}
if (h[x0][y0] > h[x0 + 1][y0] && x0 + 1 <= n) {
x[++end] = x0 + 1;
y[end] = y0;
}
if (h[x0][y0] > h[x0 - 1][y0] && x0 - 1 >= 1) {
x[++end] = x0 - 1;
y[end] = y0;
}
++now;
}
}
void bfs1(int X, int Y) {
memset(x, 0, sizeof (x));
memset(y, 0, sizeof (y));
int now, end;
now = end = 0;
x[now] = X;
y[now] = Y;
while (now <= end) {
int x0, y0;
x0 = x[now];
y0 = y[now];
if (f0[x0][y0]) {
++now;
continue;
}
f0[x0][y0] = true;
if (h[x0][y0] > h[x0][y0 + 1] && y0 + 1 <= m) {
x[++end] = x0;
y[end] = y0 + 1;
}
if (h[x0][y0] > h[x0][y0 - 1] && y0 - 1 >= 1) {
x[++end] = x0;
y[end] = y0 - 1;
}
if (h[x0][y0] > h[x0 + 1][y0] && x0 + 1 <= n) {
x[++end] = x0 + 1;
y[end] = y0;
}
if (h[x0][y0] > h[x0 - 1][y0] && x0 - 1 >= 1) {
x[++end] = x0 - 1;
y[end] = y0;
}
++now;
}
}
void dfs2(int i, int x, int y) {
//printf("<<%d %d>>\n", x, y);
if (f0[x][y])
return ;
f0[x][y] = true;
if (x == n) {
l[i] = min(l[i], y);
r[i] = max(r[i], y);
}
if (h[x][y] > h[x][y + 1] && y + 1 <= m)
dfs2(i, x, y + 1);
if (h[x][y] > h[x][y - 1] && y - 1 >= 1)
dfs2(i, x, y - 1);
if (h[x][y] > h[x - 1][y] && x - 1 >= 1)
dfs2(i, x - 1, y);
if (h[x][y] > h[x + 1][y] && x + 1 <= n)
dfs2(i, x + 1, y);
}
void dfs1(int x, int y) {
if (f0[x][y])
return ;
f0[x][y] = true;
if (h[x][y] > h[x][y + 1] && y + 1 <= m)
dfs1(x, y + 1);
if (h[x][y] > h[x][y - 1] && y - 1 >= 1)
dfs1(x, y - 1);
if (h[x][y] > h[x - 1][y] && x - 1 >= 1)
dfs1(x - 1, y);
if (h[x][y] > h[x + 1][y] && x + 1 <= n)
dfs1(x + 1, y);
}
int main(int argc, const char *argv[]) {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
scanf("%d", &h[i][j]);
for (int i = 1; i <= m; ++i) {
bfs1(1, i);
}
int ans0 = m;
for (int i = 1; i <= m; ++i)
ans0 -= f0[n][i];
if (ans0) {
printf("0\n%d\n", ans0);
return 0;
}
for (int i = 1; i <= m; ++i) {
memset(f0, 0, sizeof (f0));
l[i] = 505;
bfs2(i, 1, i);
if (l[i] == 505) {
l[i] = 505;
r[i] = 505;
}
//printf("<%d %d>", l[i], r[i]);
}
for (int i = 1; i <= m; ++i) {
f[i] = 1000000000;
for (int j = 1; j <= m; ++j) {
if (l[j] <= i && i <= r[j])
f[i] = min(f[i], f[l[j] - 1] + 1);
}
}
printf("1\n%d\n", f[m]);
return 0;
} -
0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN = 500 + 10;int h[MAXN][MAXN], vis[MAXN][MAXN], l[MAXN], r[MAXN], f[MAXN], got_w[MAXN];
int n, m;
int d1[5] = {0, 1, 0, -1};
int d2[5] = {1, 0, -1, 0};struct Status{
int x, y;
}start;queue<Status> q;
bool check(Status now, Status old){
int s = now.x, t = now.y;
if(vis[s][t] || s<1 || s>n || t<1 || t>m)
return 1;
if(h[s][t] >= h[old.x][old.y])
return 1;
return 0;
}void init_Bfs(){
for(int i=1; i<=m; i++){
Status ne;
ne.x = 1;
ne.y = i;
q.push(ne);
vis[1][i] = 1;
}
while(!q.empty()){
Status old = q.front();
q.pop();
for(int i=0; i<4; i++){
Status now = old;
now.x += d1[i];
now.y += d2[i];
if(check(now, old))
continue;
vis[now.x][now.y] = 1;
q.push(now);
}
}
}void Bfs(int s){
start.x = 1;
start.y = s;
q.push(start);
vis[1][s] = 1;
while(!q.empty()){
Status old = q.front();
q.pop();
for(int i=0; i<4; i++){
Status now = old;
now.x += d1[i];
now.y += d2[i];
if(check(now, old))
continue;
vis[now.x][now.y] = 1;
q.push(now);
}
}
}int main()
{
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
scanf("%d", &h[i][j]);
init_Bfs();
for(int i=1; i<=m; i++)
if(vis[n][i])
got_w[i]++;
int ans = 0;
for(int i=1; i<=m; i++)
if(!got_w[i])
ans++;
if(ans){
printf("0\n%d", ans);
return 0;
}
for(int i=1; i<=m; i++){
memset(vis, 0, sizeof(vis));
Bfs(i);
r[i] = l[i] = 0;
for(int j=1; j<=m; j++){
if(vis[n][j] && !r[i] && !l[i]){
l[i] = j;
r[i] = j;
}
else if(vis[n][j] && !vis[n][j+1] && l[i]){
r[i] = j;
break;
}
}
}
for(int i=1; i<=m; i++)
f[i] = 0x7fffffff;
for(int i=1; i<=m; i++)
for(int j=1; j<=m; j++)
if(l[j] <=i && r[j] >= i)
f[i] = min(f[l[j]-1]+1, f[i]);
printf("1\n%d", f[m]);
return 0;
}
两次BFS + DP -
0
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 1<<30
using namespace std;
int n,m,ans,now;
int x1[5]={0,1,0,-1,0};
int y1[5]={0,0,1,0,-1};
int p[510][510],a[510][510];
int f[510];
struct qujian{
int l,r;
};
qujian g[510];
struct node{
int x,y;
};
node q[250100];
void bfs()
{
int head=0,tail=0;
for(int i=1;i<=m;i++){
p[1][i]=1;
q[++tail].x=1;
q[tail].y=i;
}
while(head<tail){
node u=q[++head];
for(int i=1;i<=4;i++){
node v;
v.x=u.x+x1[i];v.y=u.y+y1[i];
if(v.x>n||v.x<1||v.y>m||v.y<1) continue;
if(a[v.x][v.y]>=a[u.x][u.y]) continue;
if(p[v.x][v.y]) continue;
p[v.x][v.y]=1;
q[++tail]=v;
}
}
}
void bdfs(int x,int y)
{
p[x][y]=1;
if(x==n){
g[now].l=min(g[now].l,y);
g[now].r=max(g[now].r,y);
}
for(int i=1;i<=4;i++){
int xx=x+x1[i],yy=y+y1[i];
if(xx>n||xx<1||yy<1||yy>m) continue;
if(a[xx][yy]>=a[x][y]) continue;
if(!p[xx][yy])
bdfs(xx,yy);
}
}
int main()
{
freopen("flow.in","r",stdin);
freopen("flow.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
bfs();
int ans=0;
for(int i=1;i<=m;i++)
if(!p[n][i])
ans++;
if(ans){
printf("0\n");
printf("%d",ans);
return 0;
}
for(int i=1;i<=m;i++){
memset(p,0,sizeof(p));
now=i;
g[now].l=m+1;
g[now].r=0;
bdfs(1,now);
}
f[0]=0;
for(int i=1;i<=m;i++){
f[i]=inf;
for(int j=1;j<=m;j++)
if(i>=g[j].l&&i<=g[j].r)
f[i]=min(f[i],f[g[j].l-1]+1);
}
printf("1\n");
printf("%d",f[m]);
} -
0
qq872191552 LV 9 @ 2015-07-02 11:00:49
难得又做出一道提高组最后一题...... 从样例中其实可以做出一个猜想：如果底层城市全都能被供水，那么对于任意一个蓄水站，它能供水的底层城市应当是一片连续的区域。这个猜想应该很好证明正确性，因为如果一个蓄水站供水的底层城市不是一片连续区域，那么中间就会出现”空缺“，这个“空缺”显然不可能由其它蓄水站来填补。因此解决这道题的思路是，先BFS判断是否有解，如果有解，用2次DFS+1次DP求解。
BFS：假设每一个湖边城市都有蓄水站，找出所有能被供水的点并标记。如果底层全被标记，则有解。否则没有解，输出0和未 被标记的个数。
DFS：用来找一个蓄水站供水的左边界和右边界。对于左边界，从底层1号开始搜索，能从底层K到到顶层某位置，则此位置供 水的左边界就是K。搜索时，已经过的点都不要再次经过。因为通过这些点要么无法到达顶层，要么到达顶层的左边界已 经确定且一定比现有的更小（举图中例子来说，底层1号经过高度为7的点到达顶层1号，顶层1号供水左边界为1号，那 么底层2号搜索时就不要再经过这个高度为7的点，因为通过它能到达的顶层1号，边界为1号，比2号小）。 对于右边 界则从底层K号开始，方法是一样的。用left[i]和right[i]表示i号蓄水站供水的左边界和右边界。
DP：f[i]表示到底层i号为止需要的蓄水站数目，初始化f[0]=0，f[1]=1，其他为无穷大。
可以得到下面这个式子：
f[i]=min{f[left[v]-1]+1} （left[v]<=i，right[v]>=i）
想法也比较简单，v蓄水站供水范围为left[v]~right[v]，如果其中包含i，只需1个蓄水站就可对供水left[v]~i进行供水。那 么到i为止总共所需的蓄水站数量就为到left[v]前一个城市为止需要的蓄水站数量+1。当left[v]>i时直接跳出循环，去进行 i+1的循环（通过前面分析可知，left显然是一个不下降序列）。#include<stdio.h>
int map[501][501],bools[501][501],left[501]={0},right[501]={0};
int n,m;struct forbfs
{
int x,y;
}q[5001];int min(int a,int b)
{
if(a<b) return a;
else return b;
}void bfs( )
{
int head=0,tail=m;
int i,x,y;for(i=1;i<=m;i++)
{
q[i].x=1;
q[i].y=i;
bools[1][i]=1;
}while(head!=tail)
{head=(head+1)%5000;
x=q[head].x;
y=q[head].y;if(x-1>=1 && bools[x-1][y]==0 && map[x-1][y]<map[x][y])
{
bools[x-1][y]=1;
tail=(tail+1)%5000;
q[tail].x=x-1;
q[tail].y=y;
}if(x+1<=n && bools[x+1][y]==0 && map[x+1][y]<map[x][y])
{
bools[x+1][y]=1;
tail=(tail+1)%5000;
q[tail].x=x+1;
q[tail].y=y;}
if(y-1>=1 && bools[x][y-1]==0 && map[x][y-1]<map[x][y])
{
bools[x][y-1]=1;
tail=(tail+1)%5000;
q[tail].x=x;
q[tail].y=y-1;
}if(y+1<=m && bools[x][y+1]==0 && map[x][y+1]<map[x][y])
{
bools[x][y+1]=1;
tail=(tail+1)%5000;
q[tail].x=x;
q[tail].y=y+1;
}}
}void dfs1(int num,int x,int y,int front)
{
if(bools[x][y]==1) return;bools[x][y]=1;
if(x==1) left[y]=num;
if(x-1>=1 && front!=2 && map[x-1][y]>map[x][y]) dfs1(num,x-1,y,1);
if(x+1<=n && front!=1 && map[x+1][y]>map[x][y]) dfs1(num,x+1,y,2);
if(y-1>=1 && front!=4 && map[x][y-1]>map[x][y]) dfs1(num,x,y-1,3);
if(y+1<=m && front!=3 && map[x][y+1]>map[x][y]) dfs1(num,x,y+1,4);
}void dfs2(int num,int x,int y,int front)
{
if(bools[x][y]==1) return;bools[x][y]=1;
if(x==1) right[y]=num;
if(x-1>=1 && front!=2 && map[x-1][y]>map[x][y]) dfs2(num,x-1,y,1);
if(x+1<=n && front!=1 && map[x+1][y]>map[x][y]) dfs2(num,x+1,y,2);
if(y-1>=1 && front!=4 && map[x][y-1]>map[x][y]) dfs2(num,x,y-1,3);
if(y+1<=m && front!=3 && map[x][y+1]>map[x][y]) dfs2(num,x,y+1,4);
}int main( )
{
int i,j,bfans=0,dp[501];scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
scanf("%d",&map[i][j]);
bools[i][j]=0;
}//
bfs( );
for(i=1;i<=m;i++)
if(bools[n][i]==0) bfans++;if(bfans!=0) {printf("0\n%d",bfans);goto endl;}
//
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
bools[i][j]=0;for(i=1;i<=m;i++)
dfs1(i,n,i,0);//
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
bools[i][j]=0;for(i=m;i>=1;i--)
dfs2(i,n,i,0);//
for(i=1;i<=m;i++)
dp[i]=1000008;dp[0]=0;
dp[1]=1;for(i=2;i<=m;i++)
{
for(j=1;j<=m;j++)
{
if(left[j]<=i && right[j]>=i) dp[i]=min(dp[i],dp[left[j]-1]+1);
else if(left[j]>i) break;
}
}printf("1\n%d",dp[m]);
//
endl:return 0;
} -
0
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
bool l[501][501],w[501];
int e[501][501],f[501],m,n;
class s
{
public:
int l,r;
s()
{
l=0x7fffffff;
r=0;
}
}a[501];
bool operator<(s a,s b)
{
return a.r<b.r;
}
void o(int s,int x,int y)
{
int h;
if(x==n)
{
w[y]=1;
a[s].l=min(a[s].l,y);
a[s].r=max(a[s].r,y);
}
l[x][y]=1;
h=e[x][y];
if(x<n&&e[x+1][y]<h&&!l[x+1][y])
o(s,x+1,y);
if(x>1&&e[x-1][y]<h&&!l[x-1][y])
o(s,x-1,y);
if(y<m&&e[x][y+1]<h&&!l[x][y+1])
o(s,x,y+1);
if(y>1&&e[x][y-1]<h&&!l[x][y-1])
o(s,x,y-1);
}
main()
{
int i,j,x=0,t=1;
cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
cin>>e[i][j];
for(i=1;i<=m;i++)
{
if(i>1&&e[1][i]<e[1][i-1])
continue;
if(i<m&&e[1][i]<e[1][i+1])
continue;
memset(l,0,sizeof(l));
o(i,1,i);
}
for(i=1;i<=m;i++)
if(w[i])
x++;
if(x<m)
{
cout<<"0\n"<<m-x;
return 0;
}
sort(a+1,a+1+m);
for(i=1;i<=m;i++)
f[i]=0x7fffffff/2;
for(i=1;i<=m;i++)
{
if(i<a[t].r)
continue;
while(t<=m&&i>a[t].r)
t++;
while(i==a[t].r)
f[i]=min(f[i],f[a[t++].l-1]+1);
for(j=1;j<i;j++)
f[j]=min(f[j],f[i]);
}
cout<<"1\n"<<f[m];
} -
0
const d:array[1..4,1..2]of shortint=((0,1),(0,-1),(-1,0),(1,0));
var
i,j,k,n,m,t,ans:longint;
l,r:array[1..500]of longint;
a:array[1..500,1..500]of longint;
f:array[0..501,0..501]of boolean;
procedure pre;
var i:longint;
begin
fillchar(f,sizeof(f),0);
for i:=1 to m do
begin f[0,i]:=true; f[n+1,i]:=true end;
for i:=1 to n do
begin f[i,0]:=true; f[i,m+1]:=true end
end;
PROCEDURE qs(p,q:word);
VAR
i,j,k1,k2,t:longint;
BEGIN
i:=p; j:=q;
k1:=l[(p+q)shr 1];
k2:=r[(p+q)shr 1];
REPEAT
WHILE (l[i]<k1)or(l[i]=k1)and(r[i]>k2) DO inc(i);
WHILE (l[j]>k1)or(l[j]=k1)and(r[j]<k2) DO dec(j);
IF i<=j
THEN BEGIN
t:=l[i]; l[i]:=l[j]; l[j]:=t;
t:=r[i]; r[i]:=r[j]; r[j]:=t;
inc(i); dec(j)
END;
UNTIL i>j;
IF j>p THEN qs(p,j);
IF i<q THEN qs(i,q)
END;
procedure floodfill(x,y:integer);
var
i,nx,ny:integer;
begin
f[x,y]:=true;
for i:=1 to 4 do
begin
nx:=x+d[i,1]; ny:=y+d[i,2];
if not f[nx,ny]and(a[nx,ny]<a[x,y])
then floodfill(nx,ny)
end
end;
begin
readln(n,m); pre;
for i:=1 to n do
for j:=1 to m do read(a[i,j]);
if n>1 then
begin
for i:=1 to m do
if not f[1,i] then floodfill(1,i);
for i:=1 to m do
if not f[n,i] then inc(k);
if k>0 then
begin writeln(0); write(k); exit end;
pre
end;
for i:=1 to m do
begin
floodfill(1,i);
for j:=1 to m+1 do
if f[n,j] then break;
if j<=m then l[i]:=j;
for j:=m downto 0 do
if f[n,j] then break;
if j>0 then r[i]:=j; pre
end;
qs(1,m); i:=1; ans:=1; j:=0;
while l[i]=0 do inc(i);
repeat
inc(j); l[j]:=l[i]; r[j]:=r[i];
while l[i]=l[j] do inc(i);
until i>m;
t:=m; m:=j; i:=1;
if r[i]<t then
repeat
j:=r[i]; n:=0;
for i:=i+1 to m do
begin
if l[i]>j+1 then break;
if r[i]>n then
begin n:=r[i]; k:=i end
end;
i:=k; j:=n; inc(ans)
until n=t;
writeln(1); write(ans)
end. -
0
NOIP2014赛前AC留念
const x:array[1..4] of integer=(-1,1,0,0);
y:array[1..4] of integer=(0,0,-1,1);var c:array[0..700,1..2] of longint;
linex,liney:array[0..500000] of longint;
h:array[0..700,0..700] of longint;
n,m,nowx,j,nowy,temp,i,ans:longint;
use:array[0..700,0..700] of boolean;
f:array[0..701] of longint;function can(a,b:longint):boolean;
begin
if h[a,b]<h[nowx,nowy] then
if (a>0) and (a<=n) and (b>0) and (b<=m) and (not use[a,b]) then
exit(true);
exit(false);
end;procedure bfs;
var opened,closed,i,j:longint;
begin
opened:=0;
closed:=m;
for i:=1 to m do
begin
linex[i]:=1;
liney[i]:=i;
use[1,i]:=true;
end;
repeat
inc(opened);
nowx:=linex[opened];
nowy:=liney[opened];
for i:=1 to 4 do
begin
if can(nowx+x[i],nowy+y[i]) then
begin
use[nowx+x[i],nowy+y[i]]:=true;
inc(closed);
linex[closed]:=nowx+x[i];
liney[closed]:=nowy+y[i];
end;
end;
until opened>=closed;
for j:=1 to m do
if not use[n,j] then inc(ans);
end;function min(a,b:longint):longint;
begin
if a<b then exit(a)
else exit(b);
end;procedure dfs(k,p:longint);
var i:longint;
begin
use[k,p]:=true;if k=n then
begin
if p>c[temp,2] then c[temp,2]:=p;
if (p<c[temp,1]) or (c[temp,1]=0) then c[temp,1]:=p;
end;for i:=1 to 4 do
begin
nowx:=k;
nowy:=p;
if can(k+x[i],p+y[i]) then
begindfs(k+x[i],p+y[i]);
end;
end;end;
begin
//assign(input,'flow.in');
//assign(output,'flow.out');
//reset(input);
//rewrite(output);
readln(n,m);
for i:=1 to n do
for j:=1 to m do read(h[i,j]);
bfs;
if ans>0 then
begin
writeln(0);
writeln(ans);
//close(input);
//close(output);
halt;
end;for i:=1 to m do
begin
temp:=i;
fillchar(use,sizeof(use),false);
dfs(1,i);
end;for i:=1 to m do
begin
f[i]:=maxlongint;
for j:=1 to m do
if c[j,2]>=i then
if c[j,1]<=i then
if f[c[j,1]-1]<>maxlongint then
f[i]:=min(f[c[j,1]-1]+1,f[i]);
end;writeln(1);
writeln(f[m]);
//close(input);
//close(output);
end. -
0
#include <cstdio>
#include <iostream>
#include <cstring>
#define INF (~0U>>4)
using namespace std;
int n,m;
int h[502][502];
int f[502];
bool arr[502];
struct Q
{
int x,y;
}q[1000006];
int ll[502][502],rr[502][502];
int ans1=0;
bool vst[502][502];
const int px[4]={0,1,0,-1},py[4]={1,0,-1,0};
bool Check(int x,int y)
{
if (x<0 || y<0) return false;
if (x>n || y>m) return false;
if (vst[x][y]) return false;
return true;
}
void Bfs(int u)
{
int l=0,r=0;
q[++r].x=1,q[r].y=u;
vst[1][u]=true;
while (l!=r)
{
++l;
l%=1000006;
Q x=q[l];
for (int i=0;i<4;i++)
if (Check(x.x+px[i],x.y+py[i]) && h[x.x][x.y]>h[x.x+px[i]][x.y+py[i]])
{
vst[x.x+px[i]][x.y+py[i]]=true;
++r,r%=1000006;
q[r].x=x.x+px[i],q[r].y=x.y+py[i];
}
}
}
void Bfs1(int u)
{
int l=0,r=0;
q[++r].x=n,q[r].y=u;
vst[n][u]=true;
ll[n][u]=u;
while (l!=r)
{
++l;
l%=1000006;
Q x=q[l];
for (int i=0;i<4;i++)
if (Check(x.x+px[i],x.y+py[i]) && h[x.x][x.y]<h[x.x+px[i]][x.y+py[i]])
{
vst[x.x+px[i]][x.y+py[i]]=true;
ll[x.x+px[i]][x.y+py[i]]=u;
++r,r%=1000006;
q[r].x=x.x+px[i],q[r].y=x.y+py[i];
}
}
}
void Bfs2(int u)
{
int l=0,r=0;
q[++r].x=n,q[r].y=u;
vst[n][u]=true;
rr[n][u]=u;
while (l!=r)
{
++l;
l%=1000006;
Q x=q[l];
for (int i=0;i<4;i++)
if (Check(x.x+px[i],x.y+py[i]) && h[x.x][x.y]<h[x.x+px[i]][x.y+py[i]])
{
vst[x.x+px[i]][x.y+py[i]]=true;
rr[x.x+px[i]][x.y+py[i]]=u;
++r,r%=1000006;
q[r].x=x.x+px[i],q[r].y=x.y+py[i];
}
}}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) scanf("%d",h[i]+j);
for (int i=1;i<=m;i++) if (!vst[1][i])Bfs(i);
int x=0;
for (int i=1;i<=m;i++)
x+=vst[n][i];
if (x!=m)
{
puts("0");
printf("%d\n",m-x);
return 0;
}
memset(vst,0,sizeof(vst));
for (int i=1;i<=m;i++)
if (!vst[n][i])Bfs1(i);
memset(vst,0,sizeof(vst));
for (int i=m;i;i--)
if (!vst[n][i])Bfs2(i);
for (int i=1;i<=m;i++)
if (ll[1][i]) f[ll[1][i]]=max(f[ll[1][i]],rr[1][i]);
int last=f[1],r=f[1];
int ans=1;
for (int i=1;i<=m && last<m;i++)
{
if (i>last) last=max(f[i],r),ans++;
r=max(r,f[i]);
}
puts("1");
printf("%d\n",ans);
return 0;
} -
0
速度还可以吧。。线段覆盖写了O(n log n)的。
编译成功测试数据 #0: Accepted, time = 0 ms, mem = 5900 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 5900 KiB, score = 10
测试数据 #2: Accepted, time = 19 ms, mem = 5904 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 5904 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 5908 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 5916 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 5916 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 5908 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 5932 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 5988 KiB, score = 10
Accepted, time = 65 ms, mem = 5988 KiB, score = 100http://hi.baidu.com/greencloud/item/939e36ce914e5726ef466562
-
0
O(n^2)算法，先dfs判断可行，然后再dfs求出每个临湖城市能覆盖的区间，最后DP求解，三步均为n^2。对于pascal来说还算是漂亮的时间：
编译成功
测试数据 #0: Accepted, time = 0 ms, mem = 6144 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 6148 KiB, score = 10
测试数据 #2: Accepted, time = 62 ms, mem = 6144 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 6152 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 6148 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 6144 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 6148 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 6144 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 6148 KiB, score = 10
测试数据 #9: Accepted, time = 93 ms, mem = 6160 KiB, score = 10
Accepted, time = 215 ms, mem = 6160 KiB, score = 100uses math;
type
rec=record
x,y:longint;
end;
var
n,m,i,j,top,ans:longint;
ok:array[0..501,0..501]of boolean;
a:array[0..501,0..501]of longint;
ll,rr:array[0..501,0..501]of longint;
st:array[0..250000]of rec;
f:Array[0..501]of longint;procedure check(x,y,i,j:longint);
begin
if (i<1)or(i>n)or(j<1)or(j>m) then exit;
if a[x,y]<=a[i,j] then exit;
if ok[i,j] then exit;
inc(top); ok[i,j]:=true;
st[top].x:=i; st[top].y:=j;
end;
procedure dfs(x,y:longint);
begin
st[1].x:=x; st[1].y:=y; top:=1; ok[x,y]:=true;
while top>0 do
begin
x:=st[top].x; y:=st[top].y; dec(top);
check(x,y,x,y-1); check(x,y,x,y+1);
check(x,y,x-1,y); check(x,y,x+1,y);
end;
end;function check2(x,y,i,j:longint):boolean;
begin
if (i<1)or(i>n)or(j<1)or(j>m) then exit(false);
if a[x,y]<=a[i,j] then exit(false);
exit(true);
end;
procedure dfs2(x,y:longint);
begin
if ok[x,y] then exit;
ok[x,y]:=true;
if check2(x,y,x,y-1) then begin
dfs2(x,y-1);
ll[x,y]:=min(ll[x,y],ll[x,y-1]);
rr[x,y]:=max(rr[x,y],rr[x,y-1]);
end;
if check2(x,y,x,y+1) then begin
dfs2(x,y+1);
ll[x,y]:=min(ll[x,y],ll[x,y+1]);
rr[x,y]:=max(rr[x,y],rr[x,y+1]);
end;
if check2(x,y,x-1,y) then begin
dfs2(x-1,y);
ll[x,y]:=min(ll[x,y],ll[x-1,y]);
rr[x,y]:=max(rr[x,y],rr[x-1,y]);
end;
if check2(x,y,x+1,y) then begin
dfs2(x+1,y);
ll[x,y]:=min(ll[x,y],ll[x+1,y]);
rr[x,y]:=max(rr[x,y],rr[x+1,y]);
end;
end;begin
readln(n,m);
for i:=1 to n do
for j:=1 to m do
read(a[i,j]);
fillchar(ok,sizeof(ok),false);
for j:=1 to m do
if not ok[1,j] then dfs(1,j);
ans:=0;
for j:=1 to m do
if not ok[n,j] then inc(ans);
if ans>0 then begin writeln(0); writeln(ans); halt; end;
fillchar(ll,sizeof(ll),127);
fillchar(rr,sizeof(rr),0);
for i:=1 to m do begin ll[n,i]:=i; rr[n,i]:=i; end;
fillchar(ok,sizeof(ok),false);
for i:=1 to m do
if not ok[1,i] then dfs2(1,i);
fillchar(f,sizeof(f),127);
f[0]:=0;
for i:=1 to m do
for j:=ll[1,i]-1 to rr[1,i]-1 do
f[rr[1,i]]:=min(f[rr[1,i]],f[j]+1);
writeln(1);
writeln(f[m]);
end.就是代码略长……
ATHENS_
LV 9
@ 2017-10-13 23:11:19
