西工大ACM校赛题解

   由于本人英语水平有限，所以此次ACM校赛7道题目均为中文题面。以下是简要题解，供大家赛后参考。题目均为原创，测试数据大部分随机生成，个别组为人工设置用于卡一些边界的处理。每道题目在本人写了标程测试后都分别找了华电的雷神，上海大学的邝斌，安徽大学的程文章以及西电的石国勋等人验过。在我的程序和他们的程序跑的结果一样的情况下，将所处理数据定为最终的测试数据。标准程序和现场测试数据都已发到西工大ACM群中，可自行下载。

 

                         A 武士

有一个m*n的矩阵，每个位置都有一个武力超强的武士，而你也已经山中修炼了30年。现在你要挑战这些武士。挑战的规则和顺序是这样的：第一个和最后一个你要挑战的分别是位于左上角和右上角的武士，而每挑战完一个你可以选择相邻的右边、上边或下边的武士继续挑战，但是挑战过的就不能再选择了。刚开始你的血值是0，每打完一个武士，你的血值的变化等于相应位置上的整数（正数代表增血，负数代表掉血）。当然，你不会因为血值小于0而死掉。为了到最后得到更大的血值，你该如何根据规则来选择挑战的武士呢？

 

输入：输入有多组测试数据（不超过100组）。每组数据的第一行输入两个正整数m，n（m<=100,n<=100）。接下来的m行，每行n个整数，分别代表挑战相应位置武士你的血值的变化，每个整数都大于等于-100且小于等于100。

输出：每组测试数据输出一行，输出一个整数，代表根据最优的打法，你打完右上角那个武士时能获得的最大的血值。

 

 

输入样例：

3 4
1 -1 1 0
2 -2 4 2
3 5 1 -90

2 2

1 1 

1 1

 

输出样例：

18

4

 

解法：

DP或者记忆化搜索。每个点会有两个状态。Dp[i][j][0]表示向右或向下走的最大值，Dp[i][j][1]表示向右或向上的最大值。根据题意得到的转移方程是：Dp[i][j][0]=num[i][j]+max(Dp[i+1][j][0],max(Dp[i][j+1][1],Dp[i][j+1][0]);

Dp[i][j][1]=num[i][j]+max(Dp[i+1][j][1],max(Dp[i][j+1][1],Dp[i][j+1][0]);

  

 

 

                      B蚂蚁的相遇

   有这么n只蚂蚁，它们生活在一维空间的国度，我们抽象其为x坐标轴。初始时第i只蚂蚁相对于原点的坐标位置为Ci。时间t从0开始，第i个蚂蚁的速度与时间的关系为Ai*t+Bi。我们都知道速度是个矢量，在这里正号表示坐标轴正方向，负号则相反。我们想知道的是在T时间之前（包含T），这n只蚂蚁共有多少次两两相遇。（如果有三只蚂蚁a，b，c同一时间在同一地点相遇则计算为3次两两相遇，他们分别是ab，ac，bc的相遇。更多同时相遇则以此类推。）

 

输入：输入有多组测试数据（不超过20组），每组数据第一行有两个正整数n（n<=1000），T(T<=1000000)，接下来n行的每一行都有三个整数，分别代表第i只蚂蚁的Ai，Bi，Ci。输入保证每个位置最多有一只蚂蚁。

 

输出：对于每组测试数据，将在T时间内n只蚂蚁两两相遇的次数输出在一行。

 

输入样例：

2 10

1 2 0

-1 -2 1

 

输出样例：

 1

 

 

解法：

 每个蚂蚁的坐标与时间的关系都是二次函数(或一次)。两两相对位置关系也是二次函数。（注意要判断是否是一次的）解一元二级方程即可。方程的解大于0并小于等于T即为一次相遇。

    

                   C多维空间里的蚂蚁

    刚才那些生活在一维空间的n只蚂蚁被一股神秘的力量投进了一个m维空间。它们各自独立随机地分布在距离m维空间原点的欧氏距离小于等于1的空间内。我们想知道的是距离原点最近的那个蚂蚁到原点欧式距离的期望值。结果四舍五入到小数点后第6位即可。

 

 

   输入：输入有多测试组数据(不超过100)，每组数据占一行，有两个正整数n，m（n,m<=1000）。

 

   输出：每组在一行输出期望值。

 

   输入样例：1 1

   输出样例：0.500000

 

解法：

严格的计算需要概率论的一些知识。大概方向的就是积分暴力求解通项公式。公式是：结果=  （i from 1 to n）本人暴力积分算出了三维的结果，符合这个规律并推广到了n维空间。其中多校赛5的K题是这个题的推广，题解中给出了严格的数学推导。

 

                    D 蚂蚁来报数

n只蚂蚁从多维空间回来以后都感觉晕乎乎的，大家准备排成一排报个数。由于头晕，大家报的数有点乱，但是每个蚂蚁都仍清醒地知道自己报的数要大于等于前一个蚂蚁报的数并都遵守了这个规则。在遵守这个规则的前提下，每个蚂蚁可以从[1,m]m个正整数之内任意挑选一个来报。第一个蚂蚁就1-m任意报了。

 

 

请问，根据上述情况，n只蚂蚁共有多少种不同的合法报数序列呢。  

 

输入：输入有多测试组数据（不超过30组），每组数据占一行，有两个正整数n，m（n,m<=100000）。

 

输出：将每组测试数据结果对100000007取模输出，每组答案占一行。

 

输入样例：

2 1

1 2

 

输出样例：

1

2

 

解法：

 此题的本质是重复组合数问题，等效于从m个不同的物品中，允许重复地选取m个物体。结论是C(m-1,n+m-1)。

这道题本来给的数据是10000，后来缩小到了100，为的是让用DP的过。但是由于本人的失误，在给姜老师的文档里忘记改了，还请大家见谅。

 

 

                 E 热锅上的蚂蚁

  由于刚才报数报的太乱了，蚂蚁家族的A,B,C三位长老决定小小体罚一下这些蚂蚁。体罚的工具就是热锅。现在蚂蚁们都在一个二维的坐标空间里。A，B长老都一直静止不动，他俩的坐标分别为（x，y），（-x，y）。在以原点为圆心，A长老到原点距离为半径的圆上，C长老从A长老的位置出发，匀速绕一周又回到出发点，总用时为T。每时每刻的加热的区域是A,B,C围城的三角形区域（包括三角形的边界）。现在给出一个蚂蚁的坐标（a，b），问它总共被加热了多长时间。

 

 

 

输入：输入有多组测试数据（不超过2000组）。每组数据占一行，有5个整数x，y，T，a，b。（-10000<=x，y，a，b<=10000,0）

 

输出：每组测试数据的答案输出各一行，答案四舍五入到小数点后第4位即可。

 

输入样例：

2 3 10 1 2

3 0 10 0 1

输出样例：

 4.6042

2.9517   

 

解法：

举例一种情况如图。求时间即求出EF弧的角度即可。圆心角等于圆心角的一半，即在三角形AEF中求出角EAF即可。在三角形AEF中，我们可以直接算出来角AEB（圆心角AOB的一半）、角BEF（等于角FAB），角AFE（等于角ABE）。即利用三角形内角和等于π算出角EAF。还有一种情况就是当D在AB的另一边的时候，类似于上述解法也可推出。（注：此题数据设有trick，即当点D在线段AB上的时候，答案直接是T，当D位于圆之外的时候直接输出0）。

 

 

 

                  F  二进制数

  给你一个二进制数，将其翻转后与原二进制数相乘，并按下列所述格式将乘积也按二进制输出。

 

输入：输入有多组测试数据（不超过1000组），每组数据只有一个二进制数并且占一行，每个二进制数长度不超过30。

 

输出：每组数据按照样例格式输出一行。

 

输入样例：

  1110

101

1000

输出样例：

1110*111=1100010

101*101=11001

1000*1=1000

 

解法：全场最水一题，由于长度不超过30，所以long l ong 就可过。二进制与十进制的相互转换。注意特判输入的是0，则输出0*0=0.

 

 

 

 

               G 巨大的摩擦力

   也许很多人都玩过这个有趣的实验：将两本书逐页交叉后由于书页与书页之间产生巨大的摩擦力而很难拉开。在这里，我们忽略由于形变以及其他因素产生的摩擦力，只考虑重力产生的摩擦力。还记得静摩擦力与压力关系的公式吗：F=μN .为了简化模型，给出的数据单位已统一。每张纸重力为1，且大小为1的压力能够产生大小为1的静摩擦力。每个接触面的压力等于接触面之上所有纸张的总重力。

现在两本书可以任意方式交叉并平放。给出其中一本书的页数n,问另一本书至少要有多少页才能产生至少H的总静摩擦力。

  

 输入：输入有多组测试数据（不超过1000组），每组样例占一行包括两个正整数n,H。（n<=10000,H<=10000000）;

输出：每组测试数据输出一个整数，表示另一本书至少要多少页。

 

输入样例：

     1 2

输出样例：    

2    

 解法：

   通过画图推理很容易得出下面的结论：

即两本书为了产生最大的摩擦力，一定是页数较少的一本书B与另一本较厚书A每页交叉，并B最后一页位于A最后一页的上面。

 

 设A有a页，B有b页。也这样就得到一个公式：b*(2*a-1)。

 输入n，先判断另一本是n够不够，不够的话n*（2*x-1）>=T。x向上取整。否则 x*（2*n-1）>=T,x向上取整即可。