【Test】[1011][数论+记忆化搜索+枚举(Heap优化)+SPFA]

【闲话】

成绩：

第一题(Count):AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

第二题(Length):AAATTTTTTT

第三题(Station):AAAAAAAAAAAAAAAAAAAA

第四题(Party):AAAAAAAAAA

第三题的满分是骗的，O(n2)过了全点，真正的解法应该是O(nlogn)的。

第二题确实没写过类似的题。

【题目】

数数(Count)

【问题描述】

给定n，m，k都是小于等于10001的正整数，输出给定的n个数中，其m次幂能被k整除的数的个数。

【输入格式】

有两行组成，第一行是三个整数n，m，k

第二行是n个正整数 都不超过10001

【输出格式】

输出满足条件的数的个数

【样例输入】count.in

3 2 50

9 10 11

【样例输出】count.out

1

【解析】

两种解法。

1.快速模取幂，效率O(nlogm)。不阐述…

2.分解质因数，效率O(n*25)。看程序吧…

最长链

【问题描述】

给定一棵有N个节点的树，求每个节点到其他节点的最大距离

【输入格式】

输入第一行是一个自然数 N (N<=10000), 接下来 (N-1) 行描述：

第i行包含两个自然数 , 表示编号为i的节点连接到的节点编号和这条网线的长度..距离总长不会超过10^9. 每行中的两个数字用空格隔开.

【输出格式】

输出包含N行. 第i行表示对于离编号为i的节点最远的节点与该节点的距离Si（1<=i<=N).

【样例输入】length.in

3

1 1

1 2

【样例输出】length.out

2

3

3

【数据范围】

30% N<=100

100%N<=10000

【解析】

应用树形动归(记忆花搜索)的方法。

传送门：_______。

水站

【问题描述】

已知有一个N 层的水站 :

Wi表示未操作之前第i层的已有水量；

Li 表示第i个水站能够维持或者储存的水的重量；

Pi 表示在第i层进行减压放水操作所需的费用.

被压减放水层所储存的所有水都将流向下一层.

如果第 i层的水量比Li大,则这一层也会（自动）减压(不需要任何费用).

现在想要使最后一层减压(第N级) ，求最少的花费.

这个任务现在交给了你。

【输入格式】

每个输入的第一行包含一个自然数N (1<=N<=15000).

接下来N行每行包含 3 个数 Wi, Li, Pi (0<=Wi,Li,Pi<=15000).

【输出格式】

第一行输出所需的最小费用

第二行若干个整数，从小到大输出必须减压的层的编号。

【样例输入】station.in

3

1000 1000 1

0 1000 2

2 10 100

【样例输出】station.out

3

1 2

Hint:给第一层和第二层减压

【数据范围】

30% N<=5000

100%N<=15000

【题意分析】

令Si=W1+W2+…+Wi（特别的S0=0）。

不妨设恐怖分子炸毁的第高层是第p层（第一层是最高层，第N层是最底层）。

因为恐怖分子的目标是毁灭第N层，所以水必须从第p层一直泻下去。如果存在一个i，满足Wp+Wp+1+…+Wi-1+Wi<=Li，也就是说前面几层的水全部泄下来也无法把第i层自动冲毁，那么就必须要使用***把它炸开了。

所以恐怖分子需要炸毁的层的集合就是Bomb[p]={p}∪{i |i>p Si-Sp-1<=Li}

令Qi=Si-Li，那么：

Bomb[p]={p}∪{i |i>p Qi<=Sp-1}

我们枚举p，然后看哪些层需要炸毁。这样就得到了一个O(n2)的算法。

【设计算法】

n<=15000，O(n2)的算法效率太低。

注意到Sp是随着p的增加而递增的，观察两个集合：

Bomb[p]={p}∪{i |i>p Qi<=Sp-1}

Bomb[p-1]={p-1}∪{i |i>p-1 Qi<=Sp-2}

因为Sp-2<=Sp-1，所以{i |i>p-1 Qi<=Sp-2}Bomb[p]。

也就是说，Bomb[p-1]是在Bomb[p]的基础上，通过以下操作得到的：

1．删除所有的i∈Bomb[p]，Qi>Sp-2。

2．添加p-1。

针对这两种操作，我们可以使用大根堆(Heap)。从大到小枚举p，对于每一个p，执行：

Step1. 如果堆的根i满足Qi >Sp-2，那么删除根；否则转Step3。

Step2. 转Step1。

Step3. 添加p-1。

每层至多进堆一次、出堆一次，所以总的时间复杂度是O(nlogn)。对于n<=15000的范围完全能够胜任了。

聚会

【问题描述】

小S想要从某地出发去同学k的家中参加一个party，但要有去有回。他想让所用的时间尽量的短。但他又想知道从不同的点出发，来回的最短时间中最长的时间是多少，

这个任务就交给了你。

【输入格式】

第一行三个正整数n,m,k(n是节点个数，m是有向边的条数，k是参加聚会的地点编号)( 1 ≤ N ≤ 1000 ,1 ≤ M ≤ 100,000)

第二行..m+1行每行3个整数x，y，w 代表从x到y需要花w的时间(1 ≤w≤ 100)

【输出格式】

输出从不同的节点出发的最短时间中最长的时间。

【样例输入】party.in

4 8 2

1 2 4

1 3 2

1 4 7

2 1 1

2 3 5

3 1 2

3 4 4

4 2 3

【样例输出】party.out

10

【解析】

对每一个点两遍SPFA，注意返回值如果为$7F则为不连通，此时不能更新ans。

【Code】

第一题：

1: Program Count(input,output);

2: const List:array[1..168]of longint=

3: (

4: 2,3,5,7,11,13,17,19,23,29,

5: 31,37,41,43,47,53,59,61,67,71,

6: 73,79,83,89,97,101,103,107,109,113,

7: 127,131,137,139,149,151,157,163,167,173,

8: 179,181,191,193,197,199,211,223,227,229,

9: 233,239,241,251,257,263,269,271,277,281,

10: 283,293,307,311,313,317,331,337,347,349,

11: 353,359,367,373,379,383,389,397,401,409,

12: 419,421,431,433,439,443,449,457,461,463,

13: 467,479,487,491,499,503,509,521,523,541,

14: 547,557,563,569,571,577,587,593,599,601,

15: 607,613,617,619,631,641,643,647,653,659,

16: 661,673,677,683,691,701,709,719,727,733,

17: 739,743,751,757,761,769,773,787,797,809,

18: 811,821,823,827,829,839,853,857,859,863,

19: 877,881,883,887,907,911,919,929,937,941,

20: 947,953,967,971,977,983,991,997

21: );

22: var Std,Test:array[1..168]of longint;

23: n,m,k,a,ans,tmp,i,j:longint;

24: Flag:boolean;

25: begin

26:assign(input,'count.in');reset(input);

27:assign(output,'count.out');rewrite(output);

28:readln(n,m,k);ans:=0;Fillchar(Std,sizeof(Std),0);

29:for i:=1 to 168 do

30: if k mod List[i]=0 then

31: begin

32: tmp:=0;

33: while k mod List[i]=0 do

34: begin

35:inc(tmp);

36:k:=k div List[i];

37: end;

38: Std[i]:=tmp;

39: end;

40:for i:=1 to n do

41: begin

42: read(a);Flag:=true;Fillchar(Test,sizeof(Test),0);

43: for j:=1 to 168 do

44: begin

45: if a mod List[j]=0 then Test[j]:=m;

46: if Test[j]<Std[j] then begin Flag:=false;break;end;

47: end;

48: if flag then inc(ans);

49: end;

50:writeln(ans);

51:close(input);

52:close(output);

53: end.

54:

第二题：

1: Program length(input,output);

2: type

3: edge=record

4:x,w,next:longint;

5: end;

6: var

7: e,e2:array[0..200000]of edge;

8: k,k2:array[0..10000]of longint;

9: fa:array[0..10000]of longint;

10: w:array[0..10000]of longint;

11: tot,tot2,i,j,n,x,y:longint;

12: v:array[0..10000]of boolean;

13: f:array[0..10000,0..2]of longint;

14: function max(a,b:longint):longint;

15: begin

16:if (a>b) then exit(a) else exit(b);

17: end;

18: procedure add2(a,b,c:longint);

19: begin

20:inc(tot2);

21:e2[tot2].x:=b;

22:e2[tot2].w:=c;

23:e2[tot2].next:=k2[a];

24:k2[a]:=tot2;

25: end;

26: procedure add(a,b,c:longint);

27: begin

28:inc(tot);

29:e[tot].x:=b;

30:e[tot].w:=c;

31:e[tot].next:=k[a];

32:k[a]:=tot;

33: end;

34: procedure build(x:longint);

35: var

36:t:longint;

37: begin

38:v[x]:=true;

39:t:=k2[x];

40:while (t<>0) do

41: begin

42: if (not v[e2[t].x]) then

43: begin

44: fa[e2[t].x]:=x;

45: w[e2[t].x]:=e2[t].w;

46: add(x,e2[t].x,e2[t].w);

47: build(e2[t].x);

48: end;

49: t:=e2[t].next;

50: end;

51: end;

52: procedure dp_down(x:longint);

53: var

54:t:longint;

55: begin

56:t:=k[x];

57:while (t<>0) do

58: begin

59: dp_down(e[t].x);

60: if (f[e[t].x][1]+e[t].w>f[x][1]) then

61: begin

62: f[x][2]:=f[x][1];

63: f[x][1]:=f[e[t].x][1]+e[t].w;

64: end

65: else

66: if (f[e[t].x][1]+e[t].w>f[x][2]) then

67: begin

68: f[x][2]:=f[e[t].x][1]+e[t].w;

69: end;

70: t:=e[t].next;

71: end;

72: end;

73: procedure dp_up(x:longint);

74: var

75:t:longint;

76: begin

77:if (fa[x]<>0) then

78: begin

79: if (f[fa[x]][1]=f[x][1]+w[x]) then

80: f[x][0]:=max(f[fa[x]][2],f[fa[x]][0])+w[x]

81: else f[x][0]:=max(f[fa[x]][1],f[fa[x]][0])+w[x];

82: end;

83:t:=k[x];

84:while (t<>0) do

85: begin

86: dp_up(e[t].x);

87: t:=e[t].next;

88: end;

89: end;

90: begin

91: assign(input,'length.in');reset(input);

92: assign(output,'length.out');rewrite(output);

93: readln(n);

94: for i:=2 to n do

95:begin

96: readln(x,y);

97: add2(i,x,y);

98: add2(x,i,y);

99:end;

100: build(1);

101: dp_down(1);

102: dp_up(1);

103: for i:=1 to n do

104:begin

105: writeln(max(f[i][0],f[i][1]));

106:end;

107: close(input);

108: close(output);

109: end.

第三题：

1: Program Station(input,output);

2: var sum,now,most,cost:array[1..15000]of longint;

3: n,i,ansmoney,ans,money,j:longint;

4: begin

5:assign(input,'Station.in');reset(input);

6:assign(output,'Station.out');rewrite(output);

7:readln(n);

8:for i:=1 to n do

9: begin

10: readln(now[i],most[i],cost[i]);

11: sum[i]:=sum[i-1]+now[i];

12: end;

13:ansmoney:=19940805;

14:for i:=1 to n do

15: begin

16: Money:=cost[i];

17: for j:=i+1 to n do

18: begin

19: if(sum[j]-sum[i-1]<=most[j])then inc(money,cost[j]);

20: if money>ansmoney then break;

21: end;

22: if money<ansmoney then

23: begin

24: ansmoney:=money;

25: ans:=i;

26: end;

27: end;

28:writeln(ansmoney);write(ans,' ');

29:for i:=ans+1 to n do

30: if(sum[i]-sum[ans-1]<=most[i])then

31: write(i,' ');

32:close(input);

33:close(output);

34: end.

这个Code是O(n^2)的，但是她出人意料的Ac了。

1: program dsqwwe;

2: type

3:tt=record

4:x,y:longint;

5:end;

6: var

7:a:array[1..30005] of tt;

8:p,l,w,sum:array[0..30005] of longint;

9:done:boolean;

10:i,n,tot,cost,min,k:longint;

11: procedure up(i:longint);

12: var

13:t:tt;

14: begin

15:done:=false;

16:if i=1 then exit;

17:repeat

18: if a[i].x>a[i div 2].x then

19: begin

20: t:=a[i]; a[i]:=a[i div 2]; a[i div 2]:=t;

21: end

22: else done:=true;

23: i:=i div 2;

24:until (i=1) or done;

25: end;

26: procedure down(i:longint);

27:var

28: t:tt;

29:begin

30: done:=false;

31: if i*2>tot then exit;

32: repeat

33: i:=i*2;

34: if (i+1<=tot) and (a[i+1].x>a[i].x) then inc(i);

35: if a[i div 2].x<a[i].x then

36:begin

37: t:=a[i div 2]; a[i div 2]:=a[i]; a[i]:=t;

38:end

39: else done:=true;

40: until (2*i>tot) or done;

41:end;

42: procedure delete;

43:begin

44: cost:=cost-a[1].y;

45: a[1].x:=-1000000000;

46: down(1);

47:end;

48: begin

49:assign(input,'station.in');reset(input);

50:assign(output,'station.out');rewrite(output);

51:readln(n);

52:for i:=1 to n do

53:begin

54: readln(w[i],l[i],p[i]);

55: sum[i]:=sum[i-1]+w[i];

56:end;

57:tot:=1;

58:a[1].x:=sum[n]-l[n];

59:a[1].y:=p[n];

60:if w[n]>l[n] then a[1].y:=0;

61:cost:=a[1].y;

62:min:=cost;

63:for i:=n-1 downto 1 do

64:begin

65: while (a[1].x>sum[i-1]) do delete;

66: inc(tot);

67: a[tot].x:=sum[i]-l[i];

68: a[tot].y:=p[i];

69: if w[i]>l[i] then begin

70: a[tot].y:=0;

71: end

72: else cost:=cost+p[i];

73: up(tot);

74: if cost<min then

75:begin

76: min:=cost;

77: k:=i;

78:end;

79:end;

80:writeln(min);

81:write(k,' ');

82:for i:=k+1 to n do

83:if sum[i]-sum[k-1]<=l[i] then

84: write(i,' ');

85:close(input);

86:close(output);

87: end.

88:

兆哥的，Ac标准程序

第四题：

1: Program Party(input,output);

2: type point=^node;

3: node=record

4:data,weight:longint;

5:next:point;

6: end;

7: var que:array[1..10000]of longint;

8: map:array[1..10000]of point;

9: vis:array[1..10000]of boolean;

10: dist:array[1..10000]of longint;

11: head,tail,quehead,n,m,k,ans,d,i,x,y,c:longint;

12: p,edge:point;

13: Function SPFA(st,ed:longint):longint;

14:begin

15: fillchar(que,sizeof(que),0);

16: fillchar(vis,sizeof(vis),false);

17: fillchar(dist,sizeof(dist),$7F);

18: dist[st]:=0;head:=0;tail:=1;que[tail]:=st;

19: while head<tail do

20: begin

21: inc(head);

22: quehead:=que[head];vis[quehead]:=false;edge:=map[quehead];

23: while edge<>nil do

24: begin

25:if dist[quehead]+edge^.weight<dist[edge^.data] then

26: begin

27: dist[edge^.data]:=dist[quehead]+edge^.weight;

28: if not(vis[edge^.data]) then

29: begin

30: inc(tail);

31: que[tail]:=edge^.data;

32: vis[edge^.data]:=true;

33: end;

34: end;

35:edge:=edge^.next;

36: end;

37: end;

38: exit(dist[ed]);

39:end;

40: begin

41:assign(input,'Party.in');reset(input);

42:assign(output,'Party.out');rewrite(output);

43:readln(n,m,k);

44:for i:=1 to m do

45: begin

46: readln(x,y,c);

47: new(p);p^.data:=y;p^.weight:=c;p^.next:=map[x];map[x]:=p;

48: end;

49:ans:=-19940805;

50:for i:=1 to n do

51: begin

52: d:=SPFA(i,k)+SPFA(k,i);

53: if(d>ans)and(d<19940805)then ans:=d;

54: end;

55:writeln(ans);

56:close(input);

57:close(output);

58: end.

如果觉得《【Test】[1011][数论+记忆化搜索+枚举(Heap优化)+SPFA]》对你有帮助，请点赞、收藏，并留下你的观点哦！