「Nescafé XXVI」杯HE两校联赛(Day2)

A.小猫爬山

        宿敌啊，真面目是USACO Fence Rails (fence8)。我Training就是卡在这题目上了，居然没认出来，一开始还想到纪念品分组，高兴太早了。卡时+剪枝得64分。

        显然车越多越容易装上猫，有单调性所以可以二分。

View Code 
 1 program catclimb;
 2 uses math;
 3 var w,n,timer:Qword;
 4     A,C:array[1..18] of Qword;
 5     i,l,r,mid:longint;
 6 function  DFS(k:byte):boolean;
 7           var i:longint;
 8           begin
 9           if k>n then exit(true);DFS:=false;
10           for i:=1 to min(k,mid) do
11             if A[i]+C[k]<=w
12               then begin
13                    inc(A[i],C[k]);
14                    if DFS(k+1)then exit(true);
15                    dec(A[i],C[k]);
16                    end;
17           end;
18 begin
19 readln(n,w);l:=0;r:=n;
20 for i:=1 to n do read(c[i]);
21 while l<r-1 do begin
22   fillchar(A,sizeof(A),0);
23   mid:=(l+r)>>1;
24   if dfs(1)
25     then r:=mid
26     else l:=mid;
27   end;
28 writeln(r);
29 end.

B.Freda的传呼机

       这题目太猥琐了，A类很显然，B、C就不会了。以为B类可以通过两次删边解决，结果还是WA30。。。只有40分

View Code 
program communicate;
uses math;
const Filename='communicate';
      maxn=10000;
      maxm=12000;
var x,y,t,n,m,s,i,tot,sum,forbidden:longint;
    w,v,next:array[0..maxn*2+100] of longint;
    right,p:array[0..maxm*2+100] of longint;
    q,head,list,dis,father,ancester:array[1..maxn+10] of longint;
    vis:array[1..maxn] of boolean;
    a,b,ans:array[1..maxm] of longint;
procedure build(x,y,t:longint);
          begin
          inc(tot);
          v[tot]:=y;w[tot]:=t;
          next[tot]:=head[x];
          head[x]:=tot;
          end;
procedure add(x,y:longint);
          begin
          inc(sum);P[sum]:=y;
          right[sum]:=list[x];
          list[x]:=sum;
          end;
function  find(x:longint):longint;
          begin
          if father[x]=x then exit(x);
          find:=find(father[x]);
          father[x]:=find;
          end;
procedure union(x,y:longint);
          begin father[find(y)]:=find(x);end;
procedure Tarjan(u:longint);
          var i,temp:longint;
          begin
          father[u]:=u;ancester[find(u)]:=u;
          vis[u]:=true;i:=head[u];
          while i<>0 do begin
            if(not vis[v[i]])and
              (i>>1<>forbidden)
              then begin
                   Tarjan(v[i]);
                   union(u,v[i]);
                   ancester[find(u)]:=u;
                   end;
            i:=next[i];end;
          i:=list[u];
          while i<>0 do begin
            if vis[p[i]]
              then begin
                   temp:=dis[A[i>>1]]+dis[B[i>>1]]-
                         dis[ancester[find(p[i])]]<<1;
                   ans[i>>1]:=min(ans[i>>1],temp);
                   end;
            i:=right[i];end;
          end;
procedure APro(forb:longint);
          var i,h,t:longint;
          begin
          fillchar(vis,sizeof(vis),false);
          h:=0;t:=1;Q[1]:=1;forbidden:=forb;
          dis[1]:=0;vis[1]:=true;
          while h<t do begin
            inc(h);i:=head[Q[h]];
            while i<>0 do begin
              if not vis[v[i]]
                then begin
                     vis[v[i]]:=true;
                     dis[v[i]]:=dis[Q[h]]+w[i];
                     inc(t);Q[t]:=v[i];
                     end;
              i:=next[i];end;end;
          fillchar(vis,sizeof(vis),false);Tarjan(1);
          end;
procedure BPro;
          var i,h,t,c1,c2:longint;
          begin
          h:=0;t:=1;Q[1]:=1;c1:=0;
          dis[1]:=0;vis[1]:=true;
          while(h<t)and(c1=0)do begin
            inc(h);i:=head[Q[h]];
            while i<>0 do begin
              if not vis[v[i]]
                then begin
                     vis[v[i]]:=true;
                     dis[v[i]]:=dis[Q[h]]+w[i];
                     father[v[i]]:=i>>1;
                     inc(t);Q[t]:=v[i];
                     end
                else if v[i]<>father[Q[h]]
                       then begin
                            c1:=i>>1;
                            c2:=father[v[i]];
                            end;
              i:=next[i];end;
            end;
          APro(c1);APro(c2);
          end;
procedure SPFA(s:longint);
          var h,t:longint;
          begin
          filldword(dis,sizeof(dis)>>2,maxlongint);
          fillchar(vis,sizeof(vis),false);
          h:=0;t:=1;Q[1]:=s;vis[s]:=true;dis[s]:=0;
          while h<>t do begin
            inc(h);if h>n then h:=0;
            i:=head[Q[h]];
            while i<>0 do begin
              if dis[Q[h]]+w[i]<dis[v[i]]
                then begin
                     dis[v[i]]:=dis[Q[h]]+w[i];
                     if not vis[v[i]]
                       then begin
                            inc(t);if t>n then t:=0;
                            Q[t]:=v[i];vis[v[i]]:=true;
                            end;end;
              i:=next[i];end;
            vis[Q[h]]:=false;end;
          end;
procedure SONGFEN;
          var u,i:longint;
          begin
          for u:=1 to n do
            if list[u]<>0 then begin
              SPFA(u);i:=list[u];
              while i<>0 do begin
                ans[i>>1]:=dis[P[i]];
                i:=right[i];end;end;
          end;
begin
readln(n,m,s);
tot:=1;sum:=1;
for i:=1 to m do begin
  read(x,y,t);
  build(x,y,t);
  build(y,x,t);
  end;
for i:=1 to s do begin
  read(A[i],B[i]);
  ans[i]:=maxlongint;
  add(A[i],B[i]);
  add(B[i],A[i]);
  end;
if m<n then APro(-1);
if m=n then BPro;
if m>n then SONGFEN;
for i:=1 to s do writeln(ans[i]);
end.

A.Freda的队列

        亮点在于队列顶多存N个元素，还有就是各种细节不要错了。

Code


Rainbow的信号

      考虑期望的可加性，把P拆成32个P做即可。拆完以后就是0/1的了，然后求方案数，再除个N^2即为答案。and和or的求法类似去年NOIp Hotel(?)。xor乱搞，记录从当前位置向左经过了奇数和偶数个1的位置数。

WA40是因为Q爆maxlongint，日。

Code

94分 62名

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/lijianlin1995/p/2734220.html