NOIP 2009 解题报告

A 潜伏者

      没什么好说的。

B Hankson的趣味题

      用数论的知识抽象出一下题目给的条件。此题不超时的重要优化：在根号N的时间内枚举N的全部因子。然后判定是否满足两个条件即可。

program hankson;
const FileName='hankson';
var n:longint;
function  GCD(a,b:longint):longint;
          var r:longint;
          begin
          repeat
            r:=a mod b;
            a:=b;b:=r;
          until r=0;
          exit(a);
          end;
function  solve:longint;
          var sqrtm,a0,a1,b0,b1,n1,n2,m,x,ans:longint;
          begin ans:=0;
          readln(a0,a1,b0,b1);
          n1:=a0 div a1;
          n2:=b1 div b0;
          m :=b1 div a1;
          if(b1<>m*a1)then exit(0);
          sqrtm:=trunc(sqrt(m));
          if sqrtm*sqrtm=m
            then begin
                  if(GCD(sqrtm,n1)=1)and
                    (GCD(sqrtm,n2)=1)
                     then inc(ans);
                  dec(sqrtm);
                  end;
          for x:=1 to sqrtm do
            if(m  mod  x=0)
              then begin
                   if(GCD(x,n1)=1)and
                     (GCD(m div x,n2)=1)
                      then inc(ans);
                   if(GCD(x,n2)=1)and
                     (GCD(m div x,n1)=1)
                      then inc(ans);
                   end;
          exit(ans);
          end;
begin
readln(N);
while N>0 do begin
  writeln(solve);
  dec(n);end;
end.

C 最优贸易

      练练tarjan。注意缩点完成之后belong[1]不一定能到达所有点，belong[n]不一定由所有点可达。所以DP的时候顺便求一下某个点能不能到N，然后用从1可达的点更新答案。

program zuiyoumaoyi;
uses math;
const FileName='zymy';maxn=100000;maxm=500000;
var   v,next:array[0..maxm*4] of longint;
      low,s,head,new,dfn,f,g,belong,w:array[0..maxn] of longint;
      sell,Ins:array[0..maxn] of boolean;
      x,y,z,n,m,ans,cnt,index,tot,top,u,i:longint;
procedure build(var head:array of longint;a,b:longint);
          begin
          inc(tot);
          v[tot]:=b;
          next[tot]:=head[a];
          head[a]:=tot;
          end;
procedure Tarjan(u:longint);
          var i,j:longint;
          begin
          inc(Index);inc(top);
          s[top]:=u;InS[u]:=true;
          DFN[u]:=Index;
          LOW[u]:=Index;
          i:=head[u];
          while i<>0 do begin
            if DFN[v[i]]=0
              then begin
                   Tarjan(v[i]);
                   LOW[u]:=min(LOW[v[i]],LOW[u]);
                   end
              else if InS[v[i]]
                     then LOW[u]:=min(DFN[v[i]],LOW[u]);
            i:=next[i];end;
          if LOW[u]=DFN[u] then
            begin
            inc(cnt);
            f[cnt]:=-maxlongint;
            g[cnt]:=maxlongint;
            repeat
              j:=s[top];dec(top);
              belong[j]:=cnt;InS[j]:=false;
              f[cnt]:=max(w[j],f[cnt]);
              g[cnt]:=min(w[j],g[cnt]);
            until j=u;
            end;
          end;
procedure DP(u:longint);
          var i:longint;
          begin
          InS[u]:=true;i:=new[u];
          while i<>0 do begin
            if not InS[v[i]]
              then DP(v[i]);
            if sell[v[i]]
              then f[u]:=max(f[u],f[v[i]]);
            sell[u]:=sell[u] or sell[v[i]];
            i:=next[i];end;
          end;
procedure DFS(u:longint);
          var i:longint;
          begin
          InS[u]:=true;i:=new[u];
          while i<>0 do begin
            if not InS[v[i]]
              then DFS(v[i]);
            i:=next[i];end;
          if sell[u] then
              ans:=max(f[u]-g[u],ans);
          end;
begin
readln(n,m);
for i:=1 to n do read(w[i]);
for i:=1 to m do begin
  readln(x,y,z);
  build(head,x,y);
  if z=2 then build(head,y,x);
  end;
for i:=1 to n do
  if DFN[i]=0
    then tarjan(i);
for u:=1 to n do
  begin i:=head[u];
  while i<>0 do begin
    if belong[u]<>belong[v[i]]
      then build(new,belong[u],belong[v[i]]);
    i:=next[i];end;
  end;
sell[belong[n]]:=true;
fillchar(ins,sizeof(ins),false);DP(belong[1]);
fillchar(ins,sizeof(ins),false);DFS(belong[1]);
writeln(ans);
end.

D 靶形数独

       之前按照夏令营的教法A过，自己又YY了一个做法，只有65分。不改了。

       我先搜索权比较大的格子，能比较早找到最优解，然后卡时。构造常量数组来确定搜索顺序。

状态: Unaccepted

测评机：Xeost[5]

得分：65分

提交日期：2012-11-4 16:50:00

有效耗时：15829毫秒

program sudoku;
uses math;
const FileName='sudoku';timelimt=13000000;
w:array[1..9,1..9] of longint=
       ((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));
z:array[1..9,1..9] of longint=
        ((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));
ordx:array[1..81] of longint=
         (5,4,4,4,5,5,6,6,6,
          3,3,3,3,3,4,4,5,5,
          6,6,7,7,7,7,7,2,2,
          2,2,2,2,2,3,3,4,4,
          5,5,6,6,7,7,8,8,8,
          8,8,8,8,1,1,1,1,1,
          1,1,1,1,2,2,3,3,4,
          4,5,5,6,6,7,7,8,8,
          9,9,9,9,9,9,9,9,9);
ordy:array[1..81] of longint=
         (5,4,5,6,4,6,4,5,6,
          3,4,5,6,7,3,7,3,7,
          3,7,3,4,5,6,7,2,3,
          4,5,6,7,8,2,8,2,8,
          2,8,2,8,2,8,2,3,4,
          5,6,7,8,1,2,3,4,5,
          6,7,8,9,1,9,1,9,1,
          9,1,9,1,9,1,9,1,9,
          1,2,3,4,5,6,7,8,9);
var n,i,j,t,score,time,ans:longint;
    h,l,f:array[1..9] of longint;
    A:array[1..9,1..9] of longint;
    one:longint=1;Nosolution:boolean;
procedure print;
          begin
          if Nosolution
           then writeln(-1)
           else writeln(ans);
          halt;
          end;
procedure DFS(k,step,score:longint);
          var i,x,y:longint;
          begin
          inc(time);if time>timelimt then print;
          if step<1 then begin
            Nosolution:=false;
            ans:=max(ans,score);
            exit;end;
          while A[ordx[k]][ordy[k]]<>0 do inc(k);
          x:=ordx[k];y:=ordy[k];
          for i:=9 downto 1 do begin
            if (i+9*(step-1))*w[x][y]+score<=ans then exit;
            if(((h[x]>>i)and 1)=0)and
              (((l[y]>>i)and 1)=0)and
              (((f[z[x][y]]>>i)and 1)=0)
              then begin
                   h[x]:=h[x] or one<<i;
                   l[y]:=l[y] or one<<i;
                   f[z[x][y]]:=f[z[x][y]] or one<<i;
                   A[x][y]:=i;
                   DFS(k+1,step-1,score+i*w[x][y]);
                   A[x][y]:=0;
                   f[z[x][y]]:=f[z[x][y]] xor one<<i;
                   l[y]:=l[y] xor one<<i;
                   h[x]:=h[x] xor one<<i;
                   end;end;
          end;
begin
score:=0;time:=0;Nosolution:=false;
for i:=1 to 9 do begin
  for j:=1 to 9 do
    begin
    read(t);A[i][j]:=t;
    if t=0 then inc(n)
           else begin
                if((((h[i]>>t)and 1)=1)or
                   (((l[j]>>t)and 1)=1)or
              ((f[z[i][j]]>>t and 1)=1))
                  then Nosolution:=true;
                h[i]:=h[i] or one<<t;
                l[j]:=l[j] or one<<t;
                f[z[i][j]]:=f[z[i][j]] or one<<t;
                inc(score,t*w[i][j]);
                end;
    end;readln;end;
if Nosolution
  then writeln(-1)
  else begin
       Nosolution:=true;
       DFS(1,n,score);
       if Nosolution
         then writeln(-1)
         else writeln(ans);
       end;
end.