计算机系菜鸟一个..  初次开独立博客,请多多指教!


第一题 梦幻布丁(程序文件名:pudding.exe)100分,运行时限:1s

    一天,小徐的好友邀请他去吃布丁,于是小徐高高兴兴地来到好友家。哇!这么多五彩缤纷的布丁!好友说:“在我们开吃前先玩会儿游戏吧。”于是他将布丁摆成一行,接着说:“我可以把某种颜色的布丁全部变成另一种颜色,我还会在某些时刻问你当前一共有多少段颜色。例如:颜色分别为1、2、2、1的四个布丁一共有3段颜色。”

    【输入格式】(input.txt)

    从文件input.txt中读入数据,文件第一行包含两个整数n和m,分别表示布丁的个数和好友操作的次数,n和m之间用空格隔开,第二行包含用空格隔开的n个整数A1、A2、…、An,其中Ai(1≤i≤n)表示第i个布丁的颜色。从第三行起的m行,依次描述m个操作,若第一个数是1,则表示好友要改变颜色,这时空格后依次接两个用空格隔开的整数x和y(x可能等于y),表示执行该操作后所有颜色为x的布丁被变成颜色y。若第一个数是2,则表示好友要询问目前有多少段颜色,这时应该输出一个整数回答。输入的数据保证0<n,m<100001;0<Ai,x,y<1000000。

    【输出格式】(output.txt)

    输出文件output.txt的行数为m次操作中的第二类操作(即:询问目前有多少段颜色)的数目,针对每次询问,对应行依次输出当时有多少段颜色。

    【输入输出样例】

     input.txt               output.txt

     4 3                    3

     1 2 2 1                 1

     2

     1 2 1

     2

第二题:通往城堡之路(程序文件名:road.exe)100分,运行时限:2s

    听说公主被关押在城堡里,彭大侠下定决心:不管一路上有多少坎坷,不管城堡中的看守有多少厉害,不管救了公主之后公主会不会再被抓走,不管公主是否漂亮、是否会钟情于自己,他将义无反顾地朝着城堡前进。

    可是,通往城堡的路上出现了一些情况。抽象地说,假象地图在二维平面的第一象限。在每个横轴的x位置上有一个高为hx的支撑点,如果彭大侠没有跳到支撑点上,那么他就会掉下去,牺牲在路途。开始时彭大侠在起点(1,h1)处,而城堡的入口在(n,hn)处。彭大侠每次可以从支撑点(x,hx)跳到支撑点(x+1,hx+1)。但是彭大侠每次的跳跃能量只有d,也就是说,每次跳跃必须满足条件|hx+1-hn|≤d。换句话说,如果两个相邻支撑点的纵向落差大于d,那么彭大侠就无法跳跃了!幸运的是,彭大侠还有一个杀手锏。在起点处,他可以花一个金币,把某个支撑点升高1个单位,或者降低1个单位。但是,起点处和城堡入口处的支撑点高度不能改变,并且一旦离开起点彭大侠就无法使用该杀手锏。

    彭大侠被告知100个金币可兑换一单位生命。于是他希望通过少花金币来保存更多单位的生命。他终于找到了你这位热心的高手,请你帮他规划一下以便耗费尽量少的金币来到达城堡。

    【输入格式】(input.txt)

    从文件input.txt中读入数据,文件第一行包含一个整数m(m≤5),表示问题求解次数。接下来的2m行依次表示每次求解的输入数据块。每个输入数据块占2行,其中第一行包含两个整数n和d,分别表示从起点到城堡入口处必须经过的支撑点数和每次跳跃允许的最大纵向落差,n和d之间用空格隔开,输入数据保证2≤n≤5000,0≤d≤109;第二行包含用空格隔开的n个非负整数h1、h2、…、hn,其中hi(1≤i≤n)表示第i个支撑点的高度,特别地,h1表示彭大侠出发时所在支撑点的高度,hn表示城堡入口所在支撑点的高度,输入数据保证对所有1≤i≤n有0≤hi≤109

    【输出格式】(output.txt)

    输出文件output.txt有m行,第I(1≤I≤m)行表示第I次求解时彭大侠到达城堡必须耗费的最少金币数量。若无论怎样使用杀手锏他都无法到达城堡,则输出impossible。输入数据保证答案在int64范围之内。

    【输入输出样例】

     input.txt                  output.txt

     3                        6

     10 2                      impossible

     4 5 10 6 6 9 4 7 9 8          4

     3 1

     6 4 0

     4 2

     3 0 6 3

    【样例说明】

     对样例中的第一个输入数据块,d=2,把第三个支撑点降低3个单位,把第六个支撑点降低1个单位,把第七个支撑点升高2个单位,原序列变成:4 5 7 6 6 8 6 7 9 8,这时任意相邻支撑点的纵向落差没有超过2,彭大侠可以到达城堡!

     对样例中的第二个输入数据块,d=1,这时不管怎样调节第二个支撑点的高度,都无法使任意相邻支撑点的纵向落差不超过1。

     对样例中的第三个输入数据块,d=2,这时,把第二个支撑点升高1个单位,把第三个支撑点降低3个单位就满足条件了。

    【数据规模】

     20%     n≤100

     40%     n≤1000

     100%    n≤5000

 

第三题:有趣的数列(程序文件名:sequence.exe)100分,运行时限:1s

    我们称一个长度为2n的数列是有趣的,当且仅当该数列满足以下三个条件:

    (1)它是从1到2n共2n个整数的一个排列{ai};

    (2)所有的奇数项满足a1<a3<…<a2n-1,所有的偶数项满足a2<a4<…<a2n

    (3)任意相邻的两项a2i-1与a2i(1≤i≤n)满足奇数项小于偶数项,即:a2i-1<a2i

    现在的任务是:对于给定的n,请求出有多少个不同的长度为2n的有趣的数列。因为最后的答案可能很大,所以只要求输出答案 mod P的值。

    【输入格式】(input.txt)

    从文件input.txt中读入数据,输入文件只包含用空格隔开的两个整数n和P。输入数据保证,50%的数据满足n≤1000,100%的数据满足n≤1000000且P≤1000000000。

    【输出格式】(output.txt)

    输出文件output.txt中仅含一个整数,表示不同的长度为2n的有趣的数列个数mod P的值。

    【输入输出样例】

    input.txt               output.txt

    3 10                    5

    【输入输出样例说明】

    对应的5个有趣的数列分别为(1,2,3,4,5,6),(1,2,3,5,4,6),(1,3,2,4,5,6),(1,3,2,5,4,6),(1,4,2,5,3,6)。

第四题:最小圈(程序文件名:cycle.exe)100分,运行时限:1s

考虑带权的有向图G=(V,E)以及w:E→R,每条边e=(i,j)(i≠j,i∈V,j∈V)的权值定义为wi,j,令n=|V|。c=(c1,c2,…,ck)(ci∈V)是G中的一个圈当且仅当(ci,ci+1)(1≤i<k)和(ck,c1)都在E中,这时称k为圈c的长度同时令ck+1=c1,并定义圈c=(c1,c2,…,ck)的平均值为μ(c)=4e5c84a5x6dddc5861fec&690 ,即c上所有边的权值的平均值。令μ*(c)=Min{μ(c)},为G中所有圈c的平均值的最小值。现在的目标是:在给定了一个图G=(V,E)以及w:E→R之后,请求出G中所有圈c的平均值的最小值μ*(c)=Min{μ(c)}。

    【输入模式】(input.txt)

从文件input.txt中读取数据,文件中第一行包含两个整数n和m,并用一个空格隔开,其中n=|V|,m=|E|分别表示图中有n个点和m条边。接下来m行,每行包含用空格隔开的三个数i、j和wi,j,表示有一条边(i,j)且该边的权值为wi,j。输入数据保证图G=(V,E)连通,存在圈且有一个点能到达其他所有的点。

【输出格式】(output.txt)

    输出文件output.txt中仅含一个实数μ*(c)=Min{μ(c)},要求输出到小数点后8位。

【输入输出样例】

input.txt           output.txt        input.txt            output.txt

4 5               3.66666667       2 2               -3.00000000

1 2 5                              1 2 -2.9

2 3 5                              2 1 -3.1

3 1 5

2 4 3

4 1 3

【输入输出样例说明】

样例1中共有2个圈(1,2,3)和(1,2,4)。其中第一个圈的平均值为5,第二个圈的平均值为11/3。样例2中存在一个负圈。

【数据规模】

20%的数据:n≤100,m≤1000;

20%的数据:n≤1000,m≤5000;

50%的数据:n≤3000,m≤10000;

100%的数据:|wi,j|≤107