NOIP2009提高组 解题报告

少说多做- -||

1.潜伏者

简单的字符替换，需要注意的是，‘A’..’Z’需要建立一一对应的关系，而不是映射的关系（因为这点错了1个数据，可见数据弱爆了）。

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

var i:longint;
    c:char;
    code,conv:array['A'..'Z']of char;
    e,d,s:string[100];
begin
  fillchar(code,sizeof(code),' ');
  fillchar(conv,sizeof(conv),' ');
  readln(e);
  readln(d);
  for i:=1 to length(e) do
    if ((code[e[i]]=' ')or(code[e[i]]=d[i]))and((conv[d[i]]=' ')or(conv[d[i]]=e[i])) then begin
      code[e[i]]:=d[i];
      conv[d[i]]:=e[i];
    end else begin
      writeln('Failed');
      close(input);close(output);
      halt;
    end;
  for c:='A' to 'Z' do if code[c]=' ' then begin
    writeln('Failed');
    close(Input);close(output);
    halt;
  end;
  readln(s);
  for i:=1 to length(s) do write(code[s[i]]);
end.

2.Hankson的趣味题

其实这题朴素做法也可以过，甚至比普及组相对应的那题更简单。朴素做法如下： 题目求方程组：gcd(a0,x)=a1 && lcm(b0,x)=b1 由于lcm(a,b)=ab/gcd(a,b)，所以方程组化为： gcd(a0,x)=a1 && gcd(b0,x)b1=b1*x 并且题目已知b1，x必定小于b1，并且b1能够整除x。因此可以考虑枚举x，枚举范围就是1..sqrt(b1)，之所以只枚举到sqrt(b1)，是因为另一半必定为b1 div x，这样可以减少很多没必要的浪费。

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

{$inline on}
var a0,a1,b0,b1,x,tmp,T,ans:longint;
function gcd(a,b:longint):longint;
  var r:longint;
  begin
    if a<b then begin r:=a;a:=b;b:=r; end;
    r:=a mod b;
    while r<>0 do begin
      a:=b;b:=r;r:=a mod b;
    end;
    exit(b);
  end;
begin
  readln(T);
  while T>0 do begin
    dec(t);
    ans:=0;
    readln(a0,a1,b0,b1);
    for x:=1 to trunc(sqrt(b1)) do if b1 mod x=0 then begin
      if (gcd(a0,x)=a1)and(gcd(b0,x)*b1=b0*x) then inc(ans);
      tmp:=b1 div x;
      if (tmp<>x)and(gcd(a0,tmp)=a1)and(gcd(b0,tmp)*b1=b0*tmp) then inc(ans);
    end;
    writeln(ans);
  end;
end.

3.最优贸易

此题可以两遍SPFA解决。第一遍SPFA，求出从1出发，达到i点的最便宜收购价Min[i]。然后把边倒置，第二遍SPFA，求出从n出发，到达i点的最贵售价Max[i]。然后枚举最大的Max[i]-Min[i]（也就是路径1->i->n）。 
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

/*
 * RQNOJ 520
 * abcdabcd987
 * @20110823
 */
#include <iostream>
#include <cstring>
#include <ios>
using namespace std;
const int MAXN=100000;
const int MAXM=500000;
int n,m,top,Min[MAXN+1],Max[MAXN+1],road[MAXM][3],q[MAXN*10],value[MAXN+1];
bool s[MAXN+1];
struct heap { int v,next; } g[MAXN+2*MAXM+1];

inline void join(int x,int y) {
  g[++top].v=y;
  g[top].next=g[x].next;
  g[x].next=top;
}
void make(int first,int second) {
  memset(g,255,sizeof(g));
  top=n;
  for (int i=1;i<=m;++i) {
    join(road[i][first],road[i][second]);
    if (road[i][2]==2) join(road[i][second],road[i][first]);
  }
}
void SPFAforMin() {
  memset(s,0,sizeof(s));
  memset(Min,0x3f,sizeof(Min));
  int head=0,tail=1;
  q[1]=1;s[1]=true;Min[1]=value[1];
  while (head<tail) {
    ++head;
    int u=q[head],v=g[q[head]].next;
    while (v!=-1) {
      if (!s[g[v].v]) {
        int tmp=Min[g[v].v];
        Min[g[v].v]=min(min(Min[u],Min[g[v].v]),value[g[v].v]);
        if (tmp!=Min[g[v].v]&&!s[g[v].v]) {
          s[g[v].v]=true;
          q[++tail]=g[v].v;
        }
      }
      v=g[v].next;
    }
    s[u]=false;
  }
}
void SPFAforMax() {
  memset(s,0,sizeof(s));
  memset(Max,0,sizeof(Max));
  int head=0,tail=1;
  q[1]=n;s[n]=true;Max[n]=value[n];
  while (head<tail) {
    ++head;
    int u=q[head],v=g[q[head]].next;
    while (v!=-1) {
      if (!s[g[v].v]) {
        int tmp=Max[g[v].v];
        Max[g[v].v]=max(max(Max[u],Max[g[v].v]),value[g[v].v]);
        if (tmp!=Max[g[v].v]&&!s[g[v].v]) {
          s[g[v].v]=true;
          q[++tail]=g[v].v;
        }
      }
      v=g[v].next;
    }
    s[u]=false;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin>>n>>m;
  for (int i=1;i<=n;++i) cin>>value[i];
  for (int i=1;i<=m;++i) cin>>road[i][0]>>road[i][1]>>road[i][2];

  make(0,1);
  SPFAforMin();
  make(1,0);
  SPFAforMax();

  int value=0;
  for (int i=1;i<=n;++i) value=max(value,Max[i]-Min[i]);
  cout<<value;
}

4.靶形数独

此题NP-Hard，所以只能搜索了。由于格子数众多，因此必须优化。 优化1：初始的时候，每个格子能填入的方案数就受到了限制。我们考虑从方案数最少的格子开始搜索，这样可以使无法成功构造数独的状态数大大降低了。我们每次填入(i,j)，都需要更新每行、每列、每小九宫格能填的数。每一次搜索，都需要从方格中找出状态数最少的格子(x,y)，代价是O(n2)，考虑到n=9且整题的复杂度为O(n2!)，所以还是可以忽略的。 优化2：对于每行、每列、每九宫格，都要保存0..9是否可用。若用布尔数组保存，浪费空间、转移也比较慢，可以考虑用二进制压缩，一个word就可以存下来。更新的时候通过and 和 or操作就可实现快速置0/1。 有几个二进制技巧，写在程序中： count1(x)：统计x的二进制位中有几个1——详见Matrix67大牛博客 搜索中，ps表示的是该行中1..9是否能填，其中二进制位是1的表示能填。p=ps and -ps可以取出ps最右边的一个1。 
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

{$inline on}
const ALL=$1ff;
      SQUARE:array[1..9,1..9]of integer=((1,1,1,2,2,2,3,3,3),(1,1,1,2,2,2,3,3,3),(1,1,1,2,2,2,3,3,3),(4,4,4,5,5,5,6,6,6),(4,4,4,5,5,5,6,6,6),(4,4,4,5,5,5,6,6,6),(7,7,7,8,8,8,9,9,9),(7,7,7,8,8,8,9,9,9),(7,7,7,8,8,8,9,9,9));
      POINT:array[1..9,1..9]of integer=((6,6,6,6,6,6,6,6,6),
                                        (6,7,7,7,7,7,7,7,6),
                                        (6,7,8,8,8,8,8,7,6),
                                        (6,7,8,9,9,9,8,7,6),
                                        (6,7,8,9,10,9,8,7,6),
                                        (6,7,8,9,9,9,8,7,6),
                                        (6,7,8,8,8,8,8,7,6),
                                        (6,7,7,7,7,7,7,7,6),
                                        (6,6,6,6,6,6,6,6,6));
var i,j,rest:longword;
    ans:longint;
    r,c,s:array[1..9]of longword;
    a:array[1..9,1..9]of longword;
function count1(x:longword):longword;inline;
  begin
    x := (x and $55555555) + ((x shr 1) and $55555555);
    x := (x and $33333333) + ((x shr 2) and $33333333);
    x := (x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F);
    x := (x and $00FF00FF) + ((x shr 8) and $00FF00FF);
    x := (x and $0000FFFF) + ((x shr 16) and $0000FFFF);
    exit(x);
  end;
procedure getmin(var minx,miny:longword);inline;
  var tmp,i,j,min:longword;
  begin
    min:=maxlongint;
    for i:=1 to 9 do
      for j:=1 to 9 do if a[i,j]=0 then begin
        tmp:=r[i] or c[j] or s[SQUARE[i,j]];
        tmp:=count1(ALL xor tmp);
        if tmp<min then begin
          min:=tmp;
          minx:=i;
          miny:=j;
        end;
      end;
  end;
function log2(x:longword):longword;inline;
  var i:longword;
  begin
    for i:=1 to 9 do if x=1 shl (i-1) then exit(i);
  end;
procedure go(step:longword);
  var ps,p,x,y:longword;
      br,bc,bs:array[1..9]of longword;
  begin
    if step=rest then begin
      p:=0;
      for x:=1 to 9 do
        for y:=1 to 9 do inc(p,a[x,y]*POINT[x,y]);
      if p>ans then ans:=p;
      exit;
    end;
    getmin(x,y);
    ps:=ALL xor (r[x] or c[y] or s[SQUARE[x,y]]);
    while ps<>0 do begin
      br:=r;bc:=c;bs:=s;
      p:=ps and -ps;
      ps:=ps-p;
      a[x,y]:=log2(p);
      r[x]:=r[x] or p;
      c[y]:=c[y] or p;
      s[SQUARE[x,y]]:=s[SQUARE[x,y]] or p;
      go(step+1);
      a[x,y]:=0;
      r:=br;c:=bc;s:=bs;
    end;
  end;
begin
  assign(input,'sudoku.in');reset(input);
  assign(output,'sudoku.out');rewrite(output);

  rest:=82;
  ans:=-1;
  for i:=1 to 9 do
    for j:=1 to 9 do begin
      read(a[i,j]);
      if a[i,j]<>0 then begin
        r[i]:=r[i] or (1 shl (a[i,j]-1));
        c[j]:=c[j] or (1 shl (a[i,j]-1));
        s[SQUARE[i,j]]:=s[SQUARE[i,j]] or (1 shl (a[i,j]-1));
        dec(rest);
      end;
    end;
  go(1);
  writeln(ans);

  close(input);close(output);
end.

另外有个很高端的做法：Dancing Links。下次有空研究下

Comments