感觉生活从来没有像现在这样混乱过.

不知道自己为什么会变成今天的自己,究竟是怎么一步一步走过来的呢?已经找不到从前的脚印,那些在时间轴上可能只是不远的距离,却已经被遗留在人生的后方.

却又似乎在变老中传出唏嘘,不能停止怀念,怀念从前.那一个个晚上的辗转反侧,可以是小时候没有实现的梦想；可以是今天没有完成的作业；可以是一句没有说完的话；可以是一句别人给我的冷嘲与斥责；还可以是一种来自内心的愁,一种强赋的愁,那是一种明亮的愁,照亮了整个天空.

曾经一次次地告诉自己,不要想太多；曾经一次次地欺骗自己,不要想太多；曾经一次次地责备自己,不要想太多--事情总会变好的,不是么?

不,不是的,我从来就没有从这些幻想的悲哀中获得任何同情,从来就没有在你们的心中留下一点位置,从来就没有在哪里留下一点痕迹；
是,是的,我从来就是成为茶余饭后的笑话,从来就是注定被遗忘在角落里,从来就是被漠视,被宅化.

我不知道自己是不是为了再次博得你的同情而萌生这样的想法.

感觉从来没有像现在这样混乱过.

不知道有没有走错,这是一条少有人走的路.这是一条得不到你们的理解,够不着大家的理想的路.
但我偏偏知道,这是一条不归路,难道这世间真还有回退?还有撤消?还有那个倒带人生?

梦想从来就没有像现在这样单薄过.

披星戴月的日子,没有一丝喝彩,没有一点问候；战战兢兢的生活,不许有丝毫闪失,不许有一点差池.
在这些孤独而重复枯燥的日子里,我就想有个人来找我,问声:"你还好吗?"
我会像复读机般迫不及待地告诉你:
我还好,我很好!
我会迫不及待地告诉你:
我最近有很多事情想和你分享!
我会迫不及待地告诉你:
我最近有很多话想和你说!
我会迫不及待地告诉你:
我有很多好笑的笑话,你要听么?
我还会迫不及待地告诉你:
你也想告诉我什么有趣的么?
......
我却好像复读机般被遗忘在角落里,等待你按下按钮.

That's just life?
你看,人生是不是从来就没有像现在这样迷茫过?

或许他日回头,会告诉自己,也许当时年纪小.
或许他日回头,会告诉自己,这真是你的人生.
或许他日会有人告诉你,是的,这就是你的人生.

他日是何日?还能以怎样的姿态走过去?
没有任何人曾经告诉你,这就是你的路.
是你自己选的,是你自己走的,是你自己承担的,是你自己忍受的,是你自己知道的--
你过去的人生从来没有像这样迷茫过,你的路从来就没有像现在这样泥泞过.

闭上眼睛,在等待,等待下一份愁情涌上来,好歹装出孤独浪子的样子,从今以后走向自己的路.
当别人问起这个曾经的自己时,也好能告诉他:
那只是为赋新词强作愁.

一句话题解:
1 crack: 多关键字快排
2 contact: MST
3 charge: 树形动态规划,泛化物品
4 switch: 搜索题(穷举题)

1 crack
典型初赛第一题,当时比赛没有认真做,果然只拿10分样例分

其实就是多关键字快排,字典序的综合应用了
[cc lang="pascal"]const
table:array['a'..'z'] of longint=(4,2,5,6,1,4,5,6,7,2,3,4,8,9,3,1,2,6,8,9,2,6,3,2,5,7);
maxn=50000;
type
node=record
value:longint;
w:string;
end;
var
w:array[1..maxn] of node;
n,m:longint;

procedure convert(var value:longint;s:string);
var
i:longint;
begin
value:=0;
for i:=1 to length(s) do
inc(value,table[s[i]]);
end;

procedure Init;
var
i:longint;
begin
readln(n,m);

for i:=1 to n do
begin
readln(w[i].w);
convert(w[i].value,w[i].w);
end;
end;

function isMin(a,b:string):boolean;
var
i:longint;
begin
if length(a)length(b)
then exit(false);

for i:=1 to length(a) do
if a[i]b[i]
then exit(false);
exit(false);
end;

procedure qsort(l,r:longint);
var
i,j:longint;
k,t:node;
begin
i:=l;j:=r;k:=w[(i+j) shr 1];
repeat
while (w[i].valuek.value)or((w[j].value=k.value)and(isMin(k.w,w[j].w))) do dec(j);
if ij;
if il then qsort(l,j);
end;

procedure Outit;
var
i:longint;
begin
for i:=n downto n-m+1 do
writeln(w[i].w,' ',w[i].value);
end;

begin
assign(input,'crack.in');reset(input);
assign(output,'crack.out');rewrite(output);
Init;
qsort(1,n);
Outit;
close(input);close(output);
end.
[/cc]

2 contact
当时比赛的时候还没有看过图论的知识,果然不会做

其实就是kruskal或者prim,但我用了比较麻烦的方法将邻接矩阵转为边集数组,再来kruskal,显然代码就爆长了.
值得注意的是,并查集要将父亲合并,当初在这里卡了很久......

[cc lang="pascal"]const
maxn=1000;
type
node=record
u,v,cost:longint;
end;
var
g:array[1..maxn,1..maxn] of longint;
edge,op:array[1..maxn*maxn*2] of node;
father:array[1..maxn] of longint;
m,n,ans,edgeCount,open:longint;

function find(x:longint):longint;
begin
if father[x]x
then father[x]:=find(father[x]);
exit(father[x]);
end;

procedure union(u,v:longint);
begin
father[u]:=v;
end;

procedure Init;
var
i,j,u,v,legal:longint;
begin
readln(n);inc(n);
for i:=1 to n do
begin
for j:=1 to n do
read(g[i,j]);
readln;
end;
for i:=1 to n do
g[i,i]:=1 shr 30;

for i:=1 to n do father[i]:=i;
readln(m);legal:=0;
for i:=1 to m do
begin
readln(u,v);
g[u,v]:=0;
g[v,u]:=0;
if find(v)find(u) then
begin
inc(legal);
union(find(v),find(u));
end;
end;
edgeCount:=0;m:=legal;
for i:=1 to n do
for j:=i to n do
if ij then
begin
inc(edgeCount);
edge[edgeCount].u:=i;
edge[edgeCount].v:=j;
edge[edgeCount].cost:=g[i,j];
end;
end;

procedure qsort(l,r:longint);
var
i,j,k:longint;
t:node;
begin
i:=l;j:=r;k:=edge[(i+j) shr 1].cost;
repeat
while edge[i].costk do dec(j);
if ij;
if il then qsort(l,j);
end;

procedure relax(u,v:longint);
begin
inc(open);
op[open].u:=u;
op[open].v:=v;
end;

procedure kruskal;
var
i,count:longint;
begin
ans:=0;count:=0;open:=0;
qsort(1,edgeCount);

for i:=1 to edgeCount do
begin
if count=n-1-m then break;
if find(edge[i].u)find(edge[i].v) then
begin
inc(count);inc(ans,edge[i].cost);
union(find(edge[i].u),find(edge[i].v));
relax(edge[i].u,edge[i].v);
end;
end;
end;

procedure Outit;
var
i:longint;
begin
writeln(ans);
for i:=1 to open do
writeln(op[i].u,' ',op[i].v);
end;

begin
assign(input,'contact.in');reset(input);
assign(output,'contact.out');rewrite(output);
Init;
kruskal;
Outit;
reset(input);reset(output);
end.[/cc]

3 charge
个人觉得最难的一道题,树形DP一直都不太懂

这道题就是选课变形(出题人如此说),是一棵前优先树(从别人那里看回来的,就是选儿子必选父亲),我们可以在每次DFS儿子之前将父亲的值强行加入到儿子身上,然后再选择取或不取就是了
[cc lang="pascal"]const
trutle=40000000;
maxn=10000;maxc=500;
var
ch:array[0..maxn,0..maxC*2] of longint;
f:array[0..maxn,0..maxc] of longint;
weight:array[1..maxn] of longint;
n,C,ans,i:longint;

procedure Init;
var
i,father:longint;
begin
readln(n,C);
fillchar(ch,sizeof(ch),0);

for i:=1 to n do
begin
readln(father,weight[i]);
inc(ch[father,0]);
ch[father,ch[father,0]]:=i;
end;

fillchar(f,sizeof(f),0);
end;

function whoMax(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;

procedure dfs(k,C:longint);
var
i,j,child:longint;
begin
if C<=0 then exit;
for i:=1 to ch[k,0] do
begin
child:=ch[k,i];
for j:=0 to C do
f[child,j]:=f[k,j]+weight[child];
dfs(child,C-1);
for j:=1 to C do
f[k,j]:=whoMax(f[k,j],f[child,j-1]);
end;
end;

begin
assign(input,'charge.in' ;reset(input);
assign(output,'charge.out' ;rewrite(output);
Init;
f[0,1]:=trutle;
dfs(0,C);

ans:=-(1 shl 30);
for i:=0 to C do
ans:=whoMax(f[0,i],ans);
writeln(ans);
close(input);close(output);
end.[/cc]

4 switch
我坦诚地说,我是照着标程打的,没想到穷举打表都能那么优雅

因为每种操作就做两次,所以就直接从$0660出发,枚举,然后记录下当前操作步骤,最后打表输出就可以了
通过这道题学到了不少新搜索技巧

这题就不贴代码了,代码插件太垃圾了

感谢这次贴吧提供了一个那么好的长自信的比赛...希望复赛的题目和这个相当难度吧

距离2010NOIP初赛还有28天
距离2010NOIP复赛还有63天

顺带说说blog.cd,实在是不怎么好用,yo2你快点回来吧......

grid

Problem 2 : grid
连接格点

问题描述
有一个M行N列的点阵，相邻两点可以相连。一条纵向的连线花费一个单位，一条横向的连线花费两个单位。某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。

输入数据
第一行输入两个正整数m和n。
以下若干行每行四个正整数x1,y1,x2,y2，表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1-x2|+|y1-y2|=1。

输出数据
输出使得连通所有点还需要的最小花费。

输入样例
2 2
1 1 2 1

输出样例
3

时间限制
各测试点1秒

内存限制
你的程序将被分配32MB的运行空间

数据规模
m,n<=1000

[cc lang="pascal"]const
maxn=1000;
type
node=record
x,y:longint;
end;
var
g:array[1..maxn,1..maxn] of node;
m,n:longint;

function find(x,y:longint):node;
begin
if (g[x,y].xx) or (g[x,y].yy)
then g[x,y]:=find(g[x,y].x,g[x,y].y);
exit(g[x,y]);
end;

procedure Init;
var
x1,y1,x2,y2,i,j:longint;
t:node;
begin
readln(m,n);

for i:=1 to m do
for j:=1 to n do
begin
t.x:=i;
t.y:=j;
g[i,j]:=t;
end;

repeat
readln(x1,y1,x2,y2);
g[find(x1,y1).x,find(x1,y1).y]:=find(x2,y2);
until eof;
end;

function equal(a,b:node):boolean;
begin
exit((a.x=b.x)and(a.y=b.y));
end;

procedure kruskal;
var
i,j,ans:longint;
begin
ans:=0;
for j:=1 to n do
for i:=1 to m-1 do
if not equal(find(i,j),find(i+1,j)) then
begin
g[g[i,j].x,g[i,j].y]:=g[i+1,j];
inc(ans);
end;

for i:=1 to m do
for j:=1 to n-1 do
if not equal(find(i,j),find(i,j+1)) then
begin
g[g[i,j].x,g[i,j].y]:=g[i,j+1];
inc(ans,2);
end;

writeln(ans);
end;

begin
assign(input,'grid.in');reset(input);
assign(output,'grid.out');rewrite(output);
Init;
kruskal;
close(input);close(output);
end.
[/cc]

一句话题解:老k变形,并查集原来还可以这样用的.

leader2

Problem 1 : leader2
谁是组长2

问题描述
八中信息组需要选一个组长。信息组一共有n个人，分别用1到n编号，其中m个人参与了投票。得票数过半（票数大于m div 2）的人将被选为组长。
输入数据将告知这m个人分别将票投给了谁，请统计出谁将担任八中信息组的组长。

输入数据
第一行两个数n和m。
第二行有m个数，这些数都是不超过n的正整数，表明这m个人的选择。

输出数据
输出将被选为组长的人。如果没有人的票数过半，请输出-1。

输入样例
7 4
7 7 2 7

输出样例
7

时间限制
各测试点1秒

内存限制
你的程序将被分配32MB的运行空间

数据规模
1<=n<=maxlongint
1<=m<=1 000 000

[cc lang="pascal"]const
maxn=1000000;
var
count:array[1..maxn] of longint;
n,m,ans:longint;

procedure Init;
var
i:longint;
begin
readln(n,m);
for i:=1 to m do
read(count[i]);
end;

procedure swap(var a,b:longint);
var
tmp:longint;
begin
tmp:=a;a:=b;b:=tmp;
end;

function find(l,r,k:longint):longint;
var
i,j,mid:longint;
begin
if l=r then exit(count[l]);
i:=l;j:=r;mid:=count[(i+j) shr 1];
repeat
while count[i]mid do dec(j);
if ij;
if (l<=j)and(k<=j) then exit(find(l,j,k));
if (i=i) then exit(find(i,r,k));
end;

function isLegal(a:longint):boolean;
var
i,c:longint;
begin
c:=0;
for i:=1 to m do
if count[i]=a then inc(c);
if c>m shr 1
then exit(true)
else exit(false);
end;

begin
assign(input,'leader2.in');reset(input);
assign(output,'leader2.out');rewrite(output);
Init;
ans:=find(1,m,m shr 1);
if isLegal(ans)
then writeln(ans)
else writeln(-1);
close(input);close(output);
end.
[/cc]

一句话题解:查找第K大元素(快速选择)

最近还是要补补图论,不然到时出道像最优贸易的出来就糟糕了

老k:

[cc lang="pascal"]const
maxn=100;
type
node=record
u,v,w:longint;
end;
var
g:array[1..maxn*maxn] of node;
f:array[1..maxn] of longint;
n,m:longint;

procedure Init;
var
i:longint;
begin
readln(n,m);

for i:=1 to m do
readln(g[i].u,g[i].v,g[i].w);

for i:=1 to n do
f[i]:=i;
end;

procedure qsort(l,r:longint);
var
i,j,k:longint;
t:node;
begin
i:=l;j:=r;
k:=g[(i+j) shr 1].w;
repeat
while g[i].wk do dec(j);
if ij;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;

procedure union(u,v:longint);
begin
f[u]:=v;
end;

function find(x:longint):longint;
begin
if xf[x] then f[x]:=find(f[x]);
exit(f[x]);
end;

procedure kruskal;
var
ans,i,count:longint;
begin
qsort(1,m);

count:=0;ans:=0;
for i:=1 to m do
begin
if count=n-1 then break;
if find(g[i].u)find(g[i].v) then
begin
inc(ans,g[i].w);
union(find(g[i].u),find(g[i].v));
inc(count);
end;
end;

writeln(ans);
end;

begin
[/cc]

Dijkstra:
[cc lang="pascal"]const
maxn=100;
var
g:array[1..maxn,1..maxn] of longint;
fa:array[1..maxn] of longint;
n,sp:longint;

procedure Init;
var
i,j:longint;
begin
readln(n);

for i:=1 to n do
begin
for j:=1 to n do
begin
read(g[i,j]);
if g[i,j]=0 then g[i,j]:=1 shl 30;
end;
readln;
end;
readln(sp);
end;

procedure findFa(a:longint);
begin
if fa[a]a
then findFa(fa[a]);
if asp then write('->',a);
end;

procedure dij;
var
d:array[1..maxn] of longint;
v:array[1..maxn] of boolean;
min,i,j,tmp:longint;
begin
fillchar(v,sizeof(v),false);
for i:=1 to n do
if i=sp
then d[i]:=0
else d[i]:=1 shl 30;
fa[sp]:=sp;

for i:=1 to n do
begin
min:=1 shl 30;
for j:=1 to n do
if (v[j]=false)and(d[j]d[tmp]+g[tmp,j] then
begin
d[j]:=d[tmp]+g[tmp,j];
fa[j]:=tmp;
end;
end;

for i:=1 to n do
begin
write(d[i],' ');
write(sp);
findFa(i);
writeln;
end;
end;

begin
Init;
dij;
end.
[/cc]
用邻接矩阵实现的,当然用邻接表的效率会更高,但是为了简单易懂,还是先写这个吧.

话说dij果然是不能用在复权图里,
6
0 2 3 0 1 0
2 0 0 7 0 0
3 0 0 3 1 0
0 7 3 0 -1 1
1 0 1 -1 0 7
0 0 0 1 7 0
1

立马给我死翘翘了:

0 1
2 1->2
2 1段错误

话说还要用堆(优先队列什么的就浮云了)来优化,杯具了

嗯,还要补SPFA...

距离2010NOIP初赛还有34天
距离2010NOIP复赛还有69天

题目均来自M67大牛的第二次基础代码考试

1.typewrt
[cc lang="pascal"]const
maxn=maxint;
type
bnum=record
count:longint;
d:array[1..maxn] of integer;
end;
var
ans,nine,temp:bnum;
n,i:longint;

procedure Init;
begin
readln(n);
fillchar(ans,sizeof(ans),0);
fillchar(nine,sizeof(nine),0);
ans.count:=1;
ans.d[ans.count]:=1;
nine.count:=1;
nine.d[nine.count]:=1;
end;

function whoMax(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;

procedure ZeroJustify(var c:bnum);
begin
while (c.count>1)and(c.d[c.count]=0) do dec(c.count);
end;

procedure Plus(a,b:bnum;var c:bnum);
var
i,len,carry:longint;
begin
c.count:=0;carry:=0;
len:=whoMax(a.count,b.count);
fillchar(c,sizeof(c),0);
for i:=1 to len do
begin
inc(c.d[i],a.d[i]+b.d[i]+carry);
carry:=c.d[i] div 10;
c.d[i]:=c.d[i] mod 10;
end;
while carry>0 do
begin
inc(len);
c.d[len]:=carry mod 10;
carry:=carry div 10;
end;
c.count:=len;
ZeroJustify(c);
end;

procedure Multlipy(a:bnum;b:longint;var c:bnum);
var
i,len,carry:longint;
begin
len:=a.count;carry:=0;
c.count:=0;
fillchar(c,sizeof(c),0);
for i:=1 to len do
begin
c.d[i]:=a.d[i]*b+carry;
carry:=c.d[i] div 10;
c.d[i]:=c.d[i] mod 10;
end;
while carry>0 do
begin
inc(len);
c.d[len]:=carry mod 10;
carry:=carry div 10;
end;
c.count:=len;
ZeroJustify(c);
end;

procedure readNum(var a:bnum);
var
num:string;
i:integer;
begin
a.count:=0;
readln(num);
for i:=1 to length(num) do
a.d[length(num)-i+1]:=ord(num[i])-ord('0');
a.count:=length(num);
ZeroJustify(a);
end;

procedure printNum(a:bnum);
var
i:longint;
begin
for i:=a.count downto 1 do write(a.d[i]);
writeln;
end;

procedure MoveNum(var c:bnum);
var
i:longint;
begin
for i:=c.count downto 1 do
c.d[i+1]:=c.d[i];
c.d[1]:=0;
inc(c.count);
end;

begin
assign(input,'typewrt.in');reset(input);
assign(output,'typewrt.out');rewrite(output);
Init;
for i:=2 to n do
begin
MoveNum(ans);
Multlipy(nine,9,temp);
nine:=temp;
Plus(ans,nine,temp);
ans:=temp;
end;
printNum(ans);
close(input);close(output);
end.
[/cc]

小小练习了高精度...

2.flu
[cc lang="pascal"]const
maxn=100000;
type
pointer=^node1;
node1=record
value:longint;
next:pointer;
end;
node2=record
step,node:longint;
end;
var
g:array[1..maxn] of pointer;
queue:array[1..maxn] of node2;
hash:array[1..maxn] of boolean;
n,m,sp,front,tail:longint;

procedure Insert(u,v:longint);
var
temp:pointer;
begin
new(temp);
temp^.value:=v;
temp^.next:=g[u];
g[u]:=temp;
end;

procedure Init;
var
i,u,v:longint;
begin
readln(n,m);

for i:=1 to m do
begin
readln(u,v);
Insert(u,v);
Insert(v,u);
end;
readln(sp);
end;

procedure BFS;
var
temp:pointer;
begin
front:=1;tail:=1;
queue[front].node:=sp;
queue[front].step:=1;
fillchar(hash,sizeof(hash),false);
hash[sp]:=true;

while front<=tail do
begin
temp:=g[queue[front].node];
while tempnil do
begin
if not hash[temp^.value] then
begin
hash[temp^.value]:=true;
inc(tail);
queue[tail].node:=temp^.value;
queue[tail].step:=queue[front].step+1;
end;
temp:=temp^.next;
end;
inc(front);
end;

writeln(queue[tail].step);
end;

begin
assign(input,'flu.in');reset(input);
assign(output,'flu.out');rewrite(output);
Init;
BFS;
close(input);close(output);
end.
[/cc]
用了邻接表的BFS

感叹还是有很多东西要补啊......

话说机房机器太渣了...居然连标程都过不了......

距离2010NOIP初赛还有36天
距离2010NOIP复赛还有71天

题目描述

"简单"的BFS+回溯计算题...可是怎么也过不了第七和第十个点...

[cc lang="pascal"]const
maxn=102;
dx:array[1..4] of integer=(1,-1,0,0);
dy:array[1..4] of integer=(0,0,1,-1);
type
node=record
x,y,c:longint;
end;
var
map:array[-1..maxn,-1..maxn] of -1..1;
count:array[-1..maxn,-1..maxn] of integer;
m,n,k,ans:longint;
sp,ep:node;

procedure Init;
var
i,tx,ty:longint;
begin
readln(n,m,k);
fillchar(map,sizeof(map),0);
for i:=1 to k do
begin
readln(tx,ty);
map[tx,ty]:=-1;
end;
sp.c:=0;
readln(sp.x,sp.y);readln(ep.x,ep.y);
end;

function isLss(a,b:longint):boolean;
begin
if a<=b then exit(true) else exit(false);
end;

procedure BFS;
var
i,front,tail:longint;
queue:array[1..maxn*maxn] of node;
t:node;
flag:boolean;
begin
queue[1]:=sp;front:=1;tail:=1;
flag:=true;
while (front<=tail)and(flag) do
begin
t:=queue[front];
if (t.x=ep.x)and(t.y=ep.y) then
begin
writeln(t.c);
flag:=false;
break;
end;
for i:=1 to 4 do
if (isLss(dx[i]+t.x,n))and(isLss(1,dx[i]+t.x))and(isLss(dy[i]+t.y,m))and(isLss(1,dy[i]+t.y))and(map[t.x+dx[i],t.y+dy[i]]-1) then
begin
inc(tail);
queue[tail].x:=dx[i]+t.x;queue[tail].y:=dy[i]+t.y;
queue[tail].c:=t.c+1;
count[t.x+dx[i],t.y+dy[i]]:=t.c+1;
end;
inc(front);
map[t.x,t.y]:=-1;
count[t.x,t.y]:=t.c;
end;

if flag then
begin
write('No Solution!');
halt;
end;
end;

procedure DFS(tx,ty:longint);
var
i:integer;
begin
if (tx=sp.x)and(ty=sp.y) then
begin
inc(ans);
exit;
end;
for i:=1 to 4 do
if (count[tx+dx[i],ty+dy[i]]=count[tx,ty]-1) then
DFS(tx+dx[i],ty+dy[i]);
end;

begin
Init;
BFS;
ans:=0;
DFS(ep.x,ep.y);
writeln(ans);
end.
[/cc]
最近还是先把DP放放...复习一下一些基本的先...

距离2010NOIP初赛还有39天
距离2010NOIP复赛还有74天

悲催...