NOIp 2011 提高組 廣東成績 & 無責任統計新增1＝

广东提高组
广东提高组新增一等統計

TOUHOU II problem 4 伊吹萃香 (suika) 分层图 / 拆点 最短路

题意Overview：

1. 有向图，黑点白点

2.每经过一个时刻颜色翻转

3.从黑点走向白点减去ABS(W[U] – W[V])，从白点走向黑点，加上ABS(W[U] – W[V])

4.停留在黑点，减去S[U]；停留在白点，没变化

5. 保证有解

题解Solution：

上年做的一份模拟题，有小朋友问，于是重写了一下。

“给定一张有向图，通过一条边时间为1，代价为边权，奇偶时刻边权不同，可以停留于某一点，代价s[i]。求从节点1到节点N的最小代价。”

其实就是把点拆成偶点和奇点（那么颜色也是不同的），令$1, 2, \dots, N$为偶时刻，$N + 1, N + 2, \dots, 2 \times N$为奇时刻。然后对于原图一条边<U, V>，连<U, V + N>和<U + N, V>，分别代表“偶时刻从U走到V”和“奇时刻从U走到V”。再对每个点连<U, U + N>和<U + N, U>，分别代表“偶时刻停留在U”和“奇时刻停留在U”。

然后求最短路。

代码Code：

const
 MaxN = 10010;
 MaxM = 30000 * 4 + MaxN + 10;
 inf = maxlongint shr 1;

var
 a, w, s, vect, q, dist: array[0..MaxN] of longint;
 visit: array[0..MaxN] of boolean;
 edge: array[0..MaxM] of record dest, next, cost: longint; end;
 n, m, cnt: longint;

procedure add(a, b, c: longint);
 begin
  inc(cnt);
  with edge[cnt] do
   begin
    dest:= b;
    cost:= c;
    next:= vect[a];
    vect[a]:= cnt;
   end;
 end;
function max(a, b: longint): longint;
 begin
  if a > b then exit(a) else exit(b);
 end;

function min(a, b: longint): longint;
 begin
  if a < b then exit(a) else exit(b);
 end;

function spfa(st: longint): longint;
 var
  i, u, head, tail: longint;
 begin
  for i:= 1 to n * 2 do
   dist[i]:= inf;
  dist[st]:= 0;
  visit[st]:= true;
  head:= 0;
  tail:= 1;
  q[1]:= st;
  while head <> tail do
   begin
    head:= head mod MaxN + 1;
    u:= q[head];
    i:= vect[u];
    while i <> 0 do
     with edge[i] do
      begin
       if dist[dest] > cost + dist[u] then
        begin
         dist[dest]:= cost + dist[u];
         if not visit[dest] then
          begin
           visit[dest]:= true;
           tail:= tail mod MaxN + 1;
           q[tail]:= dest;
          end;
        end;
       i:= next;
      end;
    visit[u]:= false;
   end;
  exit(min(dist[n], dist[N + N]));
 end;

var
 u, v, ww, w1, w2, i, j: longint;

 begin
  assign(input, 'suika.in'); reset(input);
  assign(output, 'suika.out'); rewrite(output);
  readln(n, m);
  for i:= 1 to n do
   read(a[i]);
  for i:= 1 to n do
   read(w[i]);
  for i:= 1 to n do
   read(s[i]);

  for i:= 1 to n do
   if a[i] = 1 then
    begin
     add(i, i + n, s[i]);
     add(i + n, i, 0);
    end else
    begin
     add(i, i + n, 0);
     add(i + n, i, s[i]);
    end;
  for i:= 1 to m do
   begin
    read(u, v, ww);
    if a[u] <> a[v] then
     begin
      if a[u] = 1 then
       begin
        w1:= ww + abs(w[u] - w[v]);
        w2:= max(0, ww - abs(w[u] - w[v]));
       end else
       begin
        w2:= ww + abs(w[u] - w[v]);
        w1:= max(0, ww - abs(w[u] - w[v]));
       end;
     end else
     begin
      w1:= ww;
      w2:= ww;
     end;
    add(u, v + n, w1);
    add(u + n, v, w2);
   end;
  writeln(spfa(1));
  close(input);
  close(output);
 end.

[HDU 1291] Closing Ceremony of Sunny Cup 杨式图表 钩子公式

题意Overview：
给$N(\le 20)$，用$1$到$N^2$的數字來填$N \times N$的矩陣。對於矩陣上格子$(i, j)$的數值$a(i, j)$，必須滿足$a(i, j) < a(i - 1, j)$且$a(i, j) < a(i, j - 1)$。问方案数。

题解Solution：
钩子公式秒杀之，各种神奇>_<。
对于$N$个格子的方案数。等于$N!$除以（每个格子上方和左方的格子数目＋1）的积。

[Ulm Local 2007][PKU/POJ 3364 & 3365]Black and White Painting & Cylinder 数学

题意Overview：
3364：给定一个$N \times M$的棋盘和右下角的格子颜色，问包含了多少个$8 \times 8$且右下角为白色的棋盘。
3365：一张$W \times H$的纸，求能够做成的最大容积的圆筒（一个圆 ＋ 一个侧面）。

题解Soluion：
3364：就直接算一下$(N – 7) \times (M – 7)$中有多少个白色格子就可以了。
3365：-_- 分类讨论一下各种裁剪方法，然后可以算出最值⋯⋯我不知道为什么一直因为精度问题WAWAWAWAWAWA⋯⋯

代码Code：

var
 n, m, c: longint;

procedure solve;
 begin
  if c = 1 then writeln(((n - 6) shr 1) * ((m - 6) shr 1) + ((n - 7) shr 1) * ((m - 7) shr 1))
           else writeln(((n - 7) shr 1) * ((m - 6) shr 1) + ((n - 6) shr 1) * ((m - 7) shr 1));
 end;

 begin
  read(n, m, c);
  while n <> 0 do
   begin
    solve;
    read(n, m, c);
   end;
 end.

[Ulm Local 2007][PKU/POJ 3370] Halloween Sweets 鸽巢原理 同余

题意Overview：
从$N$个数$a_i$中选出若干个数，使它们的和能被$C$整除。$1 \le C < N \le 10^5$。

题解Solution：
知道关键点也就很简单。首先令$S_k ＝ \sum\limits_{i = 1}^k a_i$。
由于$C < N$，由鸽巢原理可知，必然存在$i, j~(i \neq j)$，使得$S_i \equiv S_j \pmod{c}$。
这里方便地令$i < j$，那么$i + 1, i + 2, \dots, j - 1, j$就是一组可行解了。

代码Code：

const
 MaxN = 100001;
var
 a, r: array[0..MaxN] of longint;
 f: array[0..MaxN] of boolean;
 c, n: longint;

procedure solve;
 var
  ans, i, j, k: longint;
 begin
  fillchar(f, sizeof(f), 0);
  f[0]:= true;
  for i:= 1 to n do
   read(a[i]);
  k:= 0;
  for i:= 1 to n do
   begin
    k:= (k + a[i]) mod c;
    if f[k] then
     begin
      for j:= r[k] + 1 to i – 1 do
       write(j, ‘ ‘);
      writeln(i);
      exit;
     end else
     begin
      f[k]:= true;
      r[k]:= i;
     end;
   end;
 end;

 begin
  read(c, n);
  while n <> 0 do
   begin
    solve;
    read(c, n);
   end;
 end.

[Ulm Local 1997][PKU/POJ 2253]Frogger floyd or dij + 二分答案

題意Overview：
求$1 -> 2$的一條可行路徑，使得所經過的路的最大值最小。

題解Solution：
你妹啊，我怕TLE寫了個dij ＋ heap ＋ 二分，結果本地怎麼測都過，交上去怎麼都WA。
寫了個floyd卡著過了。你妹啊。

水題就不貼了。

[Ulm Local 1997][PKU/POJ 2250] Compromise 最长公共子串 DP

题意Overview：
看标题。

题解Solution：
$f[i, j]$表示$A$串前$i$个与$B$串前$j$个最长公共子串的长度。
若$a[i] \neq b[j]$，则$f[i, j] = \text{max}\{f[i - 1, j], f[i, j - 1]\}$;
若$a[i] = b[j]$，则 $f[i, j] = \text{max}\{f[i - 1, j], f[i, j - 1], f[i - 1, j - 1] + 1\}$

再用$prev[]$来记录上一个匹配的$i$和$j$。

这种恶心猥琐无聊输出题居然1A了好高新。><

代码Code：

type
 aa = array[0..101] of string;
var
 n, m: longint;
 prev: array[1..2, 0..101, 0..101] of longint;
 f: array[0..101, 0..101] of longint;
 ans, a, b: aa;

function init(var tot: longint): aa;
 var
  a: aa;
  ps: longint;
  st: string;
 begin
  readln(st);
  fillchar(a, sizeof(a), 0);
  tot:= 1;
  while st <> ‘#’ do
   begin
    while st <> ” do
     begin
      inc(tot);
      ps:= pos(‘ ‘, st);
      if ps = 0 then
       begin
	a[tot]:= st;
        st:= ”;
       end else
       begin
        a[tot]:= copy(st, 1, ps – 1);
	delete(st, 1, ps);
       end;
     end;
    readln(st);
   end;
  exit(a);
 end;

procedure deal(i, j, c, d: longint);
 begin
  if a[c] = b[d] then
   begin
    prev[1, i, j]:= c;
    prev[2, i, j]:= d;
   end else
   begin
    prev[1, i, j]:= prev[1, c, d];
    prev[2, i, j]:= prev[2, c, d];
   end;
 end;

procedure solve;
 var
  ii, jj, i, j, tot: longint;
 begin
  fillchar(f, sizeof(f), 0);
  for i:= 1 to n do
   if a[i] = b[1] then
    f[i, 1]:= 1;
  for i:= 1 to m do
   if a[1] = b[i] then
    f[1, i]:= 1;
  for i:= 2 to n do
   for j:= 2 to m do
    begin
     f[i, j]:= f[i - 1, j];
     deal(i, j, i – 1, j);
     if f[i, j - 1] > f[i, j] then
      begin
       deal(i, j, i, j – 1);
       f[i, j]:= f[i, j - 1];
      end;
     if (a[i] = b[j]) and (f[i - 1, j - 1] + 1 > f[i, j]) then
      begin
       f[i, j]:= f[i - 1, j - 1] + 1;
       deal(i, j, i – 1, j – 1);
      end;
    end;
  i:= n; j:= m;
  tot:= f[i, j];
  repeat
   if a[i] = b[j] then
    begin
     ans[tot]:= a[i];
     dec(tot);
    end;
   ii:= prev[1, i, j];
   jj:= prev[2, i, j];
   i:= ii;
   j:= jj;
  until (i = 0) or (j = 0) or (tot = 0);
  tot:= f[n, m];
  for i:= 1 to tot – 1 do
   write(ans[i], ‘ ‘);
  writeln(ans[tot]);
 end;

 begin
  while not seekeof do
   begin
    if n <> 0 then
     writeln;
    a:= init(n);
    b:= init(m);
    solve;
   end;
 end.

[Ulm Local 1997][PKU/POJ 2248] Addition Chains 搜索 ＋ 最优性剪枝

题意Overview：
给定$N$，求一合法数列$S$，使得$M = |S|$最小，且满足：

1. $S_1 = 1$
2. $S_m = N$
3. $S_1 < S_2 < \cdots < S_{m – 1} < S_m$
4. 对于$S_k(1 < k \le N)$，存在$i, j$使得$S_i + S_j = S_k$，可以有$i = j$

题解Solution：

可以证明，最优解一定会满足$S_i = S_{i – 1} + S_{j}$，其中$1 < i \le M,1 \le j \le i$。

对于$i = M$，这个结论一定成立，因为如果$S_i$不能由$S_{i - 1}$和数列中另外一个数字组成，那么最优解中肯定不含$S_{i - 1}$，也就是说相当于$S_{i - 1}$在这个数列中“什么作用都没起到”。

对于$i < M$，不严谨地想象一下也是可以发现这是对的。

代码Code：

var
 f: array[0..101, 0..101] of longint;
 n: longint;

procedure dfs(u: longint);
 var
  i, j, t: longint;
 begin
  for i:= f[u, 0] downto 1 do // 这里倒着组合数比较容易搜出一个较优解，从而减少迭代次数
   begin
    t:= u + f[u, i];
    if (t < 101) and (f[t, 0] >= f[u, 0] + 1) then
     begin
      f[t, 0]:= f[u, 0] + 1;
      for j:= 1 to f[u, 0] do
       f[t, j]:= f[u, j];
      f[t, f[t, 0]]:= t;
      dfs(t);
     end;
   end;
 end;

procedure solve;
 var
  i: longint;
 begin
  for i:= 1 to f[n, 0] - 1 do
   write(f[n, i], ' ');
  writeln(f[n, f[n, 0]]);
 end;

var
 i: longint;

 begin
  read(n);
  visit[1]:= true;
  for i:= 2 to 100 do
   f[i, 0]:= maxlongint;
  f[1, 0]:= 1;
  f[1, 1]:= 1;
  dfs(1);
  while n <> 0 do
   begin
    solve;
    read(n);
   end;
 end.

windows 通過本地網絡訪問Mac OS的共享文件夾

下載幾GB的電影還是要回到win下開小鳥才爽，於是就琢磨了一下兩台機互相訪問的方法。

找到系統偏好設置 －> 共享


先把文件共享選上，然後再開啓SMB(Windows)共享就可以了


我把所有人的權限都改到最高（讀和寫），於是在win下winkey ＋ r然後敲\\192.168.1.118，回車就可以自由傳送文件啦～

[PKU/POJ 2242][Ulm Local 1996] The Circumference of the Circle 求三角形外接圆周长

题意Overview：
抬头看标题 ＝ ＝

题解Solution：
三角形外接圆半径公式：

$r = \frac{ a \times b \times c}{4 S_{\triangle}} $

一个简单的证明：

面积公式：$S = \frac{1}{2} ab \cdot \sin{C}$

正弦公式：$\frac{c}{\sin{C}} = 2r$

整理得：$r = \frac{a b c}{4 S_{\triangle}}$

然后再利用海伦公式算面积：

$S_{\triangle} = \sqrt{p(a – p)(b – p)(c – p)},~p = \frac{a + b + c}{2}$

const
 Pi = 3.141592653589793;

procedure solve;
 var
  x1, x2, x3, y1, y2, y3, a, b, c, p, S: double;
 begin
  read(x1, y1, x2, y2, x3, y3);
  a:= sqrt(sqr(x1 - x2) + sqr(y1 - y2));
  b:= sqrt(sqr(x1 - x3) + sqr(y1 - y3));
  c:= sqrt(sqr(x3 - x2) + sqr(y3 - y2));
  p:= (a + b + c) / 2;
  S:= sqrt(p * (p - a) * (p - b) * (p - c));
  writeln((2 * Pi * (a * b * c) / (4 * S)): 0: 2);
 end;

 begin
  while not seekeof do
   solve;
 end.