其實這隻是一次改題的經過而已….
Problem1：分割(divide)
小N想要模拟出小T家後面的山水景觀，于是他找了個N*M的凹槽，某些地方放入了石塊作為山，然後在剩下的部分灌入水。比較湊巧的是剩下的部分正好形成了 1個連通塊。
小A向小N提議在某些地方放入石塊使得水被分成超過1個的連通塊，小N覺得主意不錯，于是準備去外面再去找些石塊，因為石塊比較難找，是以小N想知道最少還需要多少個石塊才能實作。如果怎麼樣都不能分成超過1個的連通塊的話就輸出-1。水是4連通的.
5 5
#####
#. . .#
#####
#. . .#
#####
100%資料N,M<=50
思路：
其實這道題表面上看起來好像很難，其實是一道比較簡單的題。首先分析樣例，多畫幾次圖會發現其實分成聯通塊的地方是一個角落或者是隻有一格水，兩邊是石頭，這兩種情況，而且答案隻能是-1，1,2。是以我們可以做幾次dfs去求聯通，最後再特判答案為2的情況。
Problem2：小A的作業(city)
小A的老師給小A布置了這樣一份作業：某個城市x是“重要”的，當且僅當存在兩個點a，b(a<>x,b<>x)，當x不能通過時，a->b的最短路徑的值改變了，現在告訴你N 個城市和M條連接配接城市之間的路徑，求出哪些點是重要的。小A忙着去找小N是以沒空做作業。請幫助小A算出哪些城市是重要的。如果不存在就輸出"No important cities."給出的是一個無向圖。
60%資料中N<=100 100%資料中N<=200,M<=N*N,0<=c<=10000
思路：
其實這道題的本質是問你從a點到b點的最短路有沒有多條路，這樣就可以直接Floyd或者是dijkstra+堆優化。d[j]>d[i]+e[i,j] 則記錄下j的必經點中為i，若d[i]+e[i,j]=d[j]，則說明有多個路徑到j,再記錄一下即可。本題沒有什麼特别的技巧。
附代碼
var
a,v,g:array[..,..] of longint;p:boolean;
i,n,m,x,y,z,tot,j:longint;
dis:array[..] of longint;
bz,w:array[..] of boolean;
h:array[..,..] of longint;
procedure swap(x,y:longint);
begin h[]:=h[x];h[x]:=h[y];h[y]:=h[];end;
procedure delete;
var i,j:longint;
begin
h[]:=h[tot];dec(tot);
i:=;j:=;
while j<=tot do begin
if (j<tot)and(h[j,]>h[j+,]) then inc(j);
if h[j,]<h[i,] then begin
swap(i,j);
i:=j;j:=j*;
end else break;
end;
end;
procedure insert(x,y:longint);
var i,j:longint;
begin
inc(tot);h[tot,]:=x;h[tot,]:=y;
i:=tot;j:=tot div ;
while j> do begin
if h[i,]<h[j,] then begin
swap(i,j);
i:=j;j:=j div ;
end else break;
end;
end;
procedure dijkstra(x:longint);
var i,now:longint;
begin
fillchar(bz,sizeof(bz),false);
fillchar(dis,sizeof(dis),$f);
tot:=;insert(x,);dis[x]:=;
while true do begin
while (tot>)and(bz[h[,]]) do
delete;
if tot= then break;
now:=h[,];
bz[now]:=true;
for i:= to a[now,] do
if dis[a[now,i]]>dis[now]+v[now,a[now,i]] then begin
dis[a[now,i]]:=dis[now]+v[now,a[now,i]];
insert(a[now,i],dis[a[now,i]]);g[x,a[now,i]]:=now;end
else if dis[a[now,i]]=dis[now]+v[now,a[now,i]] then g[x,a[now,i]]:=;
end;
end;
begin
assign(input,'city.in');reset(input);
assign(output,'city.out');rewrite(output);
readln(n,m);
for i:= to m do begin
read(x,y,z);
if x=y then continue;
if (v[x,y]=) then begin
inc(a[x,]);a[x,a[x,]]:=y;
inc(a[y,]);a[y,a[y,]]:=x;
v[x,y]:=z;v[y,x]:=z;
end else if (v[x,y]>z) then begin
v[x,y]:=z;v[y,x]:=z;
end;
end;
for i:= to n do begin
dijkstra(i);
for j:= to n do
if g[i,j]<> then if (g[i,j]<>i)and(g[i,j]<>j) then w[g[i,j]]:=true;
end;
for i:= to n do if w[i] then begin write(i,' ');p:=true;end;
if not p then writeln('No important cities.');
close(input);close(output);
end.
另外Floyd：
for u:= to n do
for i:= to n do
if (f[u,i]<>max) then
for j:= to n do
if (i<>j)and(f[u,j]<>max) then
begin
if f[u,i]+f[u,j]<f[i,j] then
begin
f[i,j]:=f[u,i]+f[u,j];f[j,i]:=f[i,j];
use[i,j]:=u;use[j,i]:=u;
end else
if f[u,i]+f[u,j]=f[i,j] then
use[i,j]:=;
end;
但是還是要注意dijkstra的堆打法，易錯。
再還有spfa+lll+slf優化：
fillchar(dis,sizeof(dis),$f);
l:=;t[1]:=n+;t[2]:=n++n+;r:=;dis[n+1]:=;dis[n+1+n+2]:=;cont:=;su:=;
while l<>r do begin
l:=l mod mo+;
while dis[t[l]]>su div cont do begin
r:=r mod mo+;t[r]:=t[l];l:=l mod mo+;
end;
no:=t[l];
p:=last[no];
dec(cont);dec(su,dis[t[l]]);
while p<>0 do begin
if (dis[no]+v[p]<dis[bi[p]])or(dis[bi[p]]=dis[]) then begin
dis[bi[p]]:=dis[no]+v[p];
if not bz[bi[p]] then begin
bz[bi[p]]:=true;inc(cont);su:=su+dis[bi[p]];
if dis[bi[p]]<dis[t[l mod mo+1]] then begin
t[l]:=bi[p];l:=(l+mo-)mod mo+;
end else begin
r:=r mod mo+;t[r]:=bi[p];
end;
end;
end;
p:=next[p];
end;
bz[no]:=false;
end;
Problem3：連續段的期望(nine)
小N最近學習了位運算，她發現2個數xor之後數的大小可能變大也可能變小，and之後都不會變大，or之後不會變小。于是她想算出以下的期望值，現在有 N個數排成一排，如果她随意選擇一對l,r并将下标在l和r中間(包括l,r)的數(xor,and,or)之後期望得到的值是多少呢？取出每一對l,r 的機率都是相等的。
2
4 5
2.750 4.250 4.750
每一組l,r取的機率都是相同的,xor=(4+1+1+5)/4=2.750 其他同理（正反即可如(l,r)和(r,l)）
思路：
見到位運算，就把它們轉成二進制來看，然後你會發現隻用一位位來做（每次可以加i個序列，及當做到第j位第i個數時，那麼可以和前面的1~i組合，一共有i個），做32次，每次處理每一位的and，xor，or的和即可。
or處理：因為隻要有一個數的一位為1，那麼從它前面的任意包括他自己k到i or出來的結果都是1，那麼答案就可以加2^j*2了。在算的過程中求出最近的1所在的第k個數的第j位，答案就是k*2^j*2。（乘2是因為可以反過來）
其他的類似。
代碼：
for k:= to do begin orp:=;orn:=;ao:=;ad:=;ax1:=;ax0:=;ax:=;
for i:= to n do begin
if a[i,k]= then orp:=i;
if a[i,k]= then orn:=i;
if orp<> then ao:=ao+orp;
if (a[i,k]=) then ad:=ad+i-orn;
if a[i,k]= then begin t:=ax0;ax0:=ax1;ax1:=t+;end else ax0:=ax0+;
ax:=ax+ax1;
if a[i,k]= then begin dec(ao);dec(ad);dec(ax);end;
end;
bo:=bo+ao*mi*;bd:=bd+ad*mi*;bx:=bx+ax*mi*;mi:=mi*;
end;
writeln(bx/(n*n)::,' ',bd/(n*n)::,' ',bo/(n*n)::);
總結：
總而言之，這次做的模拟賽，其實收獲很大
1.雖然是當練習，但是反映了我的思維不夠靈活，如第二題的轉換。
2.且當題目看起來比較難時，要多找找例子，說不定就是一道水題。
3.位運算要多往轉成二進制後和and，or，xor自身的特點去做。
![常用的排序算法的空間複雜度和時間複雜度[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)