红字是为了醒目

你用的什么浏览器0 0

你应该是排序超时了

排序，我没有排序啊，但是有一段是n2，就是输入一个名字，寻找它的过程。
难道是快排+2分？？？？？？？

你都n^2了还不TLE……
这不一看就是个 Trie 么…………………………

好吧，会不会超空间呢

………………怎么会超空间………………
N*MAXL 在 MAXL=20 时怎么可能 MLE ………………

邻接表。。=。=前向星也可以。。

邻接表开多少呢

差不多就行了

type
 he=record
  s:string;p:longint;t:longint;
  g:array[1..5000]of longint;
 end;
var
  a:array[1..50000]of he;
  s,s1:string;
  c,d,e,f,i,j,n:longint;
function min(a,b:longint):longint;
begin
 if a>b then exit(b);exit(a);
end;
function ye(x:longint):boolean;
begin
 for i:=1 to a[x].p do if a[x].g[i]=1 then exit(false);exit(true);
end;
function xe(x,y:longint):boolean;
begin
 for i:=1 to a[x].p do if a[x].g[i]=y then exit(false);exit(true);
end;
function bfs(x:longint):longint;
begin
 //if ye(x) then exit(10000000);
 if x=1 then exit(0);
 for i:=1 to a[x].p do a[x].t:=min(a[x].t,a[a[x].g[i]].t+1);
 exit(a[x].t);
end;
procedure qsort(l,r:longint);
var
 i,j,x:longint;mid,y:string;
begin
 i:=l;j:=r;mid:=a[(l+r)shr 1].s;
 repeat
  while a[i].s<mid do inc(i);
  while a[j].s>mid do dec(j);
  if i<=j then begin x:=a[i].t;a[i].t:=a[j].t;a[j].t:=x;
   y:=a[i].s;a[i].s:=a[j].s;a[j].s:=y;inc(i);dec(j);end;
 until i>j;
 if i<r then qsort(i,r);
 if l<j then qsort(l,j);
end;
begin
 assign(input,'a.txt');reset(input);assign(output,'a1.txt');rewrite(output);
 readln(n);for i:=1 to 50000 do a[i].t:=10000000;a[1].t:=0;
 for j:=1 to n do begin
  d:=0;e:=0;f:=0;
  readln(s);s1:=copy(s,1,pos(' ',s)-1);
  for i:=1 to c do if a[i].s=s1 then begin d:=i;break;end;
  if d=0 then begin inc(c);a[c].s:=s1;d:=c;end;
  delete(s,1,pos(' ',s));
  s1:=copy(s,1,pos(' ',s)-1);
  for i:=1 to c do if a[i].s=s1 then begin e:=i;break;end;
  if e=0 then begin inc(c);a[c].s:=s1;e:=c;end;
  delete(s,1,pos(' ',s));
  s1:=s; for i:=1 to c do if a[i].s=s1 then begin f:=i;break;end;
  if f=0 then begin inc(c);a[c].s:=s1;f:=c;end;
  if xe(f,d) then begin inc(a[f].p);a[f].g[a[f].p]:=d;end;
  if xe(f,e) then begin inc(a[f].p);a[f].g[a[f].p]:=e;end;
  if xe(d,f) then begin inc(a[d].p);a[d].g[a[d].p]:=f;end;
  if xe(d,e) then begin inc(a[d].p);a[d].g[a[d].p]:=e;end;
  if xe(e,f) then begin inc(a[e].p);a[e].g[a[e].p]:=f;end;
  if xe(e,d) then begin inc(a[e].p);a[e].g[a[e].p]:=d;end;
 end;
 qsort(1,c);
 for i:=1 to c do a[i].t:=bfs(i);
 for i:=1 to c do if a[i].t=10000000 then writeln(a[i].s,' undefined',a[i].g[1])
  else writeln(a[i].s,' ',a[i].t);
  for i:=1 to c do begin for j:=1 to a[i].p do write(a[i].g[j],' ');writeln;end;
end.
end.

这是我写的n个程序之一，这样行不行呢
ps。只看记录类型定义

不太清楚你的程序,我的用50000*1000..spfa(最后两个点re了。。)（我的打了将近400行。两层hash+最短路。结果hash函数问题没ac（数据完全就是瞄准了我hash的弊端出的啊）。。你们字符串是怎么处理的？）。。话说你的头像是怎么换过来的（用户设置里找了半天没看见改的地方。=。=）

有个gravater，但是我的电脑打不开，于是哪儿填了别人的邮箱

为何要写spfa这样的东西? 你不认为只要直接bfs就可以了么?

我试图用树一样的东西，建立fa数组，但是可能不满足最优（类似贪心）；
bfs怎么做呢
ps。样例不科学，我第一遍做，过了样例，结果爆0 QAQ

用bfs求最短路径你不会?

所有边都是单位边, 你用bfs当然是线性的. 何必要用spfa?

好吧，有问题我在回复

说的有道理=。=.......我只是看着朋友用spfa一遍就ac了很郁闷而已orz.........呜哇想不出hash函数来啊TT.........

那bfs不是要开一个map数组吗，map数组开多么大

bfs的话=。=我觉得用邻接表也可以啊。。所以还是我上面那个范围应该可以了吧。。我觉得=。=

等等。。spfa用单源的话。。那么不就是bfs嘛？！。。就是说啊，单源spfa就是从bfs中演变过来的啊(而且我用来拓展节点的队列以及程序模板和bfs一摸一样=。=)。。╮(╯▽╰)╭脑子又卡了不好意思=。=

bfs怎么弄一层一层的，我是优先广度，其次深度，dfs的写法不行

跟spfa一样。。每次用邻接表找出当前节点连接的节点进行松弛。。然后加入队列中并且将队列的头指针不断向前知道头指针>尾指针。。。（其实就是bfs了吧。。我个人认为）

敢问liyinghaowei, 广度优先搜索 与 BFS 有什么区别?

我是用dfs的写法，写了bfs。我知道错误了，以前都用dfs没想到写法不同

这套题是不是就考了宽搜

本人太弱了，刚刚学会bfs

while he<=ti do
begin
for i:=1 to a[he].p do if a[a[he].g[i]].l then begin
a[a[he].g[i]].l:=false;inc(ti);b[ti]:=a[he].g[i];
a[a[he].g[i]].t:=a[he].t+1;end;
inc(he);
end; 这一段哪儿错了
ps。初始化已做好，a。t意思是答案，a。g是和他一起比赛的人。a。l是访问标识he队首ti队尾

d[q2[k]]:=0;q[1]:=q2[k];shou:=0;wei:=1;pan[k]:=true;
while shou<wei do
begin
inc(shou);t:=q[shou];
for k:=1 to ling[t,0] do
if (not pan[ling[t,k]])and(d[t]+1<d[ling[t,k]]) then
begin d[ling[t,k]]:=d[t]+1;inc(wei);q[wei]:=ling[t,k];pan[ling[t,k]]:=true;end;
end;
这是我的spfa。。=。=d是最短距离，shou是队首指针，wei是队尾指针,pan是判断节点是否松弛过，ling是临界表,q是队列。。=。=好吧写得很丑吐槽轻点我怕疼。。

好吧，我50分，因为字符串操作花的时间太长
怎么办

凉拌。

第四题是水题呀...解答我丢那一题的题解里面了...NOIP普及组难度的题目.
第三题是好题, 动态规划. =_= 大概你考虑状态 f[i][j] := 前i个人坐下后, 有j个"团体", 然后自己闹补后面的, 详细情况等我有空了再写题解.

orz...第四题真“良心”noip普及组难度... 这个状态数量真心有点大...
第三题的题解我看了，但是疑惑仍然还有，题解里是这样说的：

如果i , j确定了，且依次每一个团体是哪些人也知道了（旋转意义下的顺序，也就是说"A"+"BC"+"DE"与"BC"+"DE"+"A"被看作是相同的顺序）那么，满足给定i , j 和给定团体 的方案总数，是可以通过 i , j 算出来，这里我们需要的只是组合数学的方法。

f[i][j]确实可以说是确定了i,j，但是“依次每一个团体是哪些人”似乎并不能根据i,j确定吧..
0010200和0010020这两种都是两个人，两个团体，但接下去的转移却不是一样的..

小岛大神能不能详细说明一下这个问题？

第四题7百万的有向图,BFS一次怎么也不可能超时的, 一点也不大. >_<

第三题,你所提到的0010200和0010020都被看作是状态<2,2>因为都是2个人, 当前是2个团体, 你可以思考这样一个问题:"给定N个座位围一圈, K个人坐上去了, 它们是按照顺序的, [也就是第一个人的右边是第二个人(有可能存在些许间隔), 第二个人右边是第三个人, ... , 第K个人右边是第一个人] 形成了G个团体的方案, 是多少?" 这个答案只与N, K, G有关. 那么类似的, 我给定任何一个K个人的全排列 (记为t1...tk) 并要求它们按照这个全排列的顺序去座位 (允许相邻两个人中间有间隙, 且桌子是圆形的), 满足的答案个数总是一样的. 所以我们可以不要考虑最后的间距是多少, 也不用管每一个人坐在哪里, 只要最终的排列确定下来了, 总方案就确定了. 那么到底有多少可行的最终的排列呢?(实际上是有多少可行的圆排列?) 就需要递推算出来.

唔..似乎明白了..谢小岛大神啦orz..

我不能公开全部数据, 但是我可以每题挑2个数据给你.=_=

http://pan.baidu.com/s/1gdFxC35

多谢了！O(∩_∩)O~

怎么给你?

http://pan.baidu.com/s/1gdFxC35

比赛用统一评测器 Jtwd2, 所以不予重测.

比赛是统一使用的jtwd2评测的。

非比赛递交会自动分配评测机，可能不是同一台。

T1可以转成有根树DFS吗，感觉似乎可以，比赛的时候还在上晚修真是坑的1B。确定难度小于NOIP提高组？

首先确定小于提高组………………（T3不一定…………
然后 T1 为毛要转有根树…………直接在图上 BFS 不一样么…………
（其实这套题神犇 1.5h- 就可以 AK 啦>.<
可惜我是脑残。

我感觉去年前两天前两题都比这个简单，我感觉T3还是有思路的，跟题解差不多，T4丝毫思路都没有

T4是小学题, 你说写错还情有可原, 你说没思路那noip还怎么考?

正在评测中，评测完毕后在比赛页会有的。

可以查看了

有么有标程？

当然有标程, 但是并不会公开. 其实也没有公开的必要.

T1 T4都是普及组的题, T2也差不多, 要是没有T3这就是一套小学题了, 你还想要如何简单? 4道a+b可否?

orz

是的。

好的谢谢

512MB

请问所有的题都是吗？

所有题 都是 512 MB

哦 我造了 谢

那两个题目呀, 一个是 树型动态规划, 只要维护5组状态 : "车进车出" "车进人出" "人进人出" "车进不出" "人进不出" 就可以了. 还有一个题目呀是基础数据结构题, 嘛..你可以去学习下Splay之类的.

Orz! 明天好想来卖个萌呢QAQ