其实这只是一次改题的经过而已….
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=)