NOIP2010提高组 解题报告

少说多做～！

1.机器翻译

略微思索即可得到O(n)算法，略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

var n,m,i,x,head,ans,tail:longint;
    q:array[1..1000]of longint;
    b:array[1..1000]of boolean;
begin
  fillchar(b,sizeof(b),0);
  readln(m,n);
  head:=0;tail:=0;
  ans:=0;
  for i:=1 to n do begin
    read(x);
    if not b[x] then begin
      if tail-head=m then begin
        inc(head);
        b[q[head]]:=false;
      end;
      inc(tail);
      q[tail]:=x;
      b[x]:=true;
      inc(ans);
    end;
  end;
  writeln(ans);
end.

2.乌龟棋

四维动规，用f[k1,k2,k3,k4]表示用了k1张走1格的卡、k2张走2格的卡……那么，此时的位置tmp=1+k1+2k2+3k3+4*k4。走到f[k1,k2,k3,k4]有四种选择：用一张走1格的卡；用一张走2格的卡…… 由于题目规定了用完所有的卡正好走到最后一格，所以答案就是f[b[1],b[2],b[3],b[4]]（b[i]为走i格的卡片的总数）

1
2
3
4
5
6
7
8
9
10
11
12
13

{$inline on}
var i,j,tmp,k1,k2,k3,k4,n,m:longint;
    a:array[0..350]of longint;
    b:array[1..4]of longint;
    f:array[0..40,0..40,0..40,0..40]of longint;
function max(a,b:longint):longint;inline;begin if(a0 then j:=max(j,f[k1-1,k2,k3,k4]);
    if k2>0 then j:=max(j,f[k1,k2-1,k3,k4]);
    if k3>0 then j:=max(j,f[k1,k2,k3-1,k4]);
    if k4>0 then j:=max(j,f[k1,k2,k3,k4-1]);
    f[k1,k2,k3,k4]:=j+a[tmp];
  end;
  writeln(f[b[1],b[2],b[3],b[4]]);
end.

3.关押罪犯

题目求的是最大值的最小值，可用二分答案ans。对于所有权值小于等于ans的边，都可以无视（放在同一座监狱或者两座监狱都不影响）。对于所有权值大于ans的边，必须拆到两个不同的监狱。此题转换为二分图的判定，用01染色即可解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

/*
 * RQNOJ 600
 * abcdabcd987
 * @20110824
 */
#include
#include
#include
using std::cin;
using std::cout;
const int MAXN=20000;
const int MAXM=100000;
int top,n,m,left,right,mid,color[MAXN+1];
struct link { int v,w,next; } g[MAXN+2*MAXM+1];
struct edge { int x,y,w; } a[MAXM+1];

void join(int a,int b,int w) {
  g[++top].v=b;
  g[top].w=w;
  g[top].next=g[a].next;
  g[a].next=top;
}
bool go(int u,int C) {
  color[u]=C;
  int v=g[u].next;
  while (v!=-1) {
    if (g[v].w>mid&&color[g[v].v]!=-1&&color[g[v].v]+color[u]!=1) return false;
    if (g[v].w>mid&&color[g[v].v]==-1)
      if (!go(g[v].v,1-C)) return false;
    v=g[v].next;
  }
  return true;
}
int main() {
  std::ios::sync_with_stdio(false);
  cin>>n>>m;
  for (int i=1;i  top=n;
  for (int i=1;i>a[i].x>>a[i].y>>a[i].w;
    join(a[i].x,a[i].y,a[i].w);
    join(a[i].y,a[i].x,a[i].w);
  }
  left=0,right=1000000000;
  while (right!=left) {
    mid=(left+right)>>1;
    memset(color,255,sizeof(color));
    bool can=true;
    for (int i=1;i    if (can) right=mid; else left=mid+1;
  }
  cout<}

4.引水入城

对于最后一行不能全部淹没的情况，使用深搜从点(1,i)依次往下遍历，能走到的点做标记，统计出不能走到的点的个数，复杂度O(NM+M)。对于最后一行能够全部淹没的情况，可以先预处理算出从点(x,y)出发能够淹没最后一行的哪些格子。可以证明这些格子必定是在一个连续的区间的。 证：假设从某个点(x,y)出发能够覆盖到最后一行两个不连续的区间[a,b],[ c, d ]。假设存在一条路线能够覆盖区间[b+1,c-1]，那么这两条路线必定相交于一点P（可以画个图），此时第一条线路能够在P点“拐弯”，淹没[b+1,c-1]，这与题设矛盾，故不存在这么一条线路能够淹没[b+1,c-1]。则对于全图来说，[b+1,c-1]永远无法被淹没，这于最后一行能被全部淹没矛盾。因此当最后一行能够被全部淹没时，从某点出发能够淹没到最后一行的格子，必在一个连续的区间。 有了这个条件，预处理时仅需要保存(x,y)能够淹没的最后一行的区间[left,right]即可。可以使用floodfill，对点(1,i)分别做一次floodfill，加上记忆化，预处理的复杂度可以降至O(N^2)。记忆化就是：记下每个点能够覆盖的区间[left,right]，如果(x,y)能够走到(xx,yy)，那么(x,y)能覆盖的区间一定会包含(xx,yy)的区间。 预处理后，问题转化为线段覆盖：用m条已知线段覆盖m个格子，最少需要多少条线段。可以动规解决，dp[i]表示覆盖前i个格子所需的最少线段。dp[i]=min{dp[left[j]-1]+1 (left[j]<=i<=right[j])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

{$inline on}
const xy:array[1..4,1..2]of longint=((1,0),(-1,0),(0,1),(0,-1));
type interval=record left,right:longint;end;
var i,j,count,n,m:longint;
    error:interval;
    a:array[0..501,0..501]of longint;
    color:array[1..500,1..500]of boolean;
    f:array[1..500,1..500]of interval;
    dp:array[0..500]of longint;
function min(a,b:longint):longint;inline;begin if(ab)then exit(a)else exit(b)end;
procedure swap(var a,b:longint);inline;var t:longint;begin t:=a;a:=b;b:=t;end;
function floodfill(x,y:longint):interval;
  var i:longint;
      tmp:interval;
  begin
    if (xn)or(ym) then exit(error);
    if color[x,y] then exit(f[x,y]);
    color[x,y]:=true;
    for i:=1 to 4 do if a[x,y]>a[x+xy[i,1],y+xy[i,2]] then begin
      tmp:=floodfill(x+xy[i,1],y+xy[i,2]);
      f[x,y].left:=min(f[x,y].left,tmp.left);
      f[x,y].right:=max(f[x,y].right,tmp.right);
    end;
    exit(f[x,y]);
  end;
procedure go(x,y:longint);
  begin
    if (xn)or(ym)or color[x,y] then exit;
    color[x,y]:=true;
    if a[x,y]>a[x+1,y] then go(x+1,y);
    if a[x,y]>a[x-1,y] then go(x-1,y);
    if a[x,y]>a[x,y+1] then go(x,y+1);
    if a[x,y]>a[x,y-1] then go(x,y-1);
  end;
begin
  fillchar(color,sizeof(color),0);
  fillchar(dp,sizeof(dp),63);
  readln(n,m);
  error.left:=m+1;
  error.right:=0;
  for i:=1 to n do begin
    for j:=1 to m do begin
      read(a[i,j]);
      f[i,j]:=error;
    end;
    readln;
  end;

  for i:=1 to m do go(1,i);
  count:=0;
  for i:=1 to m do if not color[n,i] then inc(count);
  if count>0 then begin
    writeln(0);
    writeln(count);
    halt;
  end;

  for i:=1 to m do begin
    f[n,i].left:=i;
    f[n,i].right:=i;
  end;
  fillchar(color,sizeof(color),0);
  for i:=1 to m do if not color[1,i] then floodfill(1,i);
  dp[0]:=0;
  for i:=1 to m do
    for j:=1 to m do
      if (f[1,j].left<=i)and(i<=f[1,j].right) then writeln(1);
  writeln(dp[m]);
end.

Comments