文档介绍：(bestqueue; 时限:1s; 128MB)
【题目描述】
要参加复赛了,大家都在体育馆门口集合完毕,由于这次参赛的人数较多,上车前需要排一下队,所有人自愿排成两队(分别定义为A和B队列,人数大于1且两队人数随意),Ms. Zhou给每位同学一张纸,每人默默写下一个字母代表自己,比如:郑逸宁写Z,吴天舒写W等等。
A队:
字母: c m c
B队:
字母: s n m n
最佳队形为:
每个人前后可以有任意个空位,也可以没有空位;
两队在添加空位后长度必须一样,上图可以有多种方案使得A、B两队长度一致,例如:
根据每个人所写的字母,我们定义A队与B队的距离为相应位置上的字母的距离总和;
两队相应位置的距离定义为:
两个非空位的距离定义为它们的所写字母ASCII码的差的绝对值;
空位与其他任意非空位之间的距离为已知的定值K;
空位与空位的距离为0。
最佳队形为:在A、B的所有可能队形中,必定存在两个等长的队A’、B’,使得A’与B’之间的距离达到最小,这个队形就是最佳队形。
请你写一个程序,求出最佳队形时,A队与B队的距离。
【输入数据】
输入文件第一行为队列A每个人所写字母组成的字符串A;
第二行为队列B每个人所写字母组成的字符串B。(约定:A、B均由小写字母组成且长度均不超过2000)。
第三行为一个整数K(1≤K≤100),表示空位与非空位的距离。
【输出数据】
输出文件仅一行包含一个整数,表示所求得最佳队形A、B之间的距离。
【样例】
cmc 10
snmn
2
2. 数学作业(homework; 时限:1s; 128MB)
【问题描述】
数学竞赛刚刚结束,据说题目很难,不过信息学里面的数学题也不容易哦,题目描述很简单:求:方程x1+2x2+…+nxn=m的所有非负整数解(x1,x2,…,xn)的个数。例如,方程:x1+2x2+3x3+4x4+5x5=5有7组解:(5,0,0,0,0)、(3,1,0 ,0,0)、…、(0,0,0,0,1)。
运用你的数学思维加上强大的信息学能力,试试解决它吧!
【输入数据】
2个整数n,m
【输出数据】
方程非负整数解的个数ans,如果解超过10^9,只需输出ans mod 10^9。
【输入样例】
5 5
【输出样例】
7
【数据范围】
1≤n≤5000;0≤m≤5000。
3. 最美音符(song; 时限:1s; 128MB)
【问题描述】
今年的物理竞赛成绩相当好,于是高三年级部主任决定开一场庆功晚会,其中有一节为吉他专场,由你来组织。为了不使声音平淡,你希望每个曲之间都有变化。现在你已经确定了每个曲可以与上一个曲之间的音量的变化量,即每首曲开始,你可以对音量选择增加或减少一个指定的变化值。当然音量不可能为负数,也不能太高,因此必需保证每首曲音量在0和maxLevel之间(包含)。
你的任务是,根据已有的开始音量beginLevel 和每首曲之间的变化量,求出最后一首曲的最大可能音量。如果没有方案,输出-1。
【输入格式】
文件第一行有三个整数,n, beginLevel, maxLevel,分别表示曲目数,开始量,最大限制音量。
下面有n-1行整数,第i行整数表示第i首曲与第i+1首曲之间的变化量。
【输入格式】
文件只一行一个数,答案。
【样例】
样例1
样例2
4 5 10
5
3
7
5 8 20
15
2
9
10
10
-1
【数据范围】
1<=n<=60;
1<= maxLevel <=1000
0<= beginLevel <= maxLevel
4. 圆桌会议(heightround; 时限:1s; 128MB)
【问题描述】
晚会结束的第二天,学校决定请获奖的同学开一个圆桌会议。假设有N个人顺时针围在一圆桌上开会,不过他们对身高很敏感。因此决定想使得任意相邻的两人的身高差距最大值最小。
如果答案不唯一,输出字典序最小的排列,指的是身高的排列。
【输入文件】
多组测试数据。
第一行:一个整数ng, 1 <= ng <= 5. 表示有ng组测试数据。
每组测试数据格式如下:
第一行: 一个整数N, 3 <= N <= 50
第二行, 有个N整数, 第i个整数表示第i个人的身高hi, 1<=hi<=1000。按顺指针给出N个人的身高, 空格分开。
【输出文件】
字典序最小的身高序列,同时满足相邻的两人的身高差距最大值最小。
ng行,每行对应一组输入数据。
【样例】
样例
说明
heig