《计算概论(B)》(闫宏飞)期末考试参考代码(2017 ~ 2019)

  • 2019-11-28 12:00
  • 2020-01-03 23:02

前言

两年前的我怎么也不会想到我竟然会在大三的时候还在为《计算概论》这门课而头疼。我当年大一的时候上的计概课是马思伟老师主讲的,程序语言是C。然而我现在在看的是化院开设的计概,主讲老师是闫宏飞,程序语言是Python。当然,我自己有一些Python编程的基础,而且计概B讲道理不会特别难,所以我就打开了新世界的大门。

总而言之因为种种原因,我做完了化院开设的《计算概论(B)》(主讲:闫宏飞)的期末考试题。虽然也有别人的作业作为参考,但是我觉得他写得不太详细,因此我自己随手写了一份参考代码出来,也算是造福人民大众了。当然,我的水平肯定不及大佬,让大家见笑了。

本文提供的所有代码均以在课程网站(OpenJudge)上进行过测试,大部分是能通过Accepted)的,有些题实在通不过Wrong Answer)的我也放出来了,不怕丢脸,希望大家一起来讨论。

因为我个人不太喜欢在代码里面写注释,因此所有的说明都放在“思路”一段中。

对了,如果你看的是pdf版本,那么你复制粘贴代码会很困难(因为有行号而且没有缩进)。建议你自己写一遍,或者扫描第一页的二维码前往网页版。另外,pdf版本和网页版都是有书签的,方便对题目进行定位。

祝大家期末考试顺利!

来自一条大三的老咸鱼

目录

2017级期末考试 2018级期末考试
题目ID 标题 页码 题目ID 标题 页码
A字符串连接位置 A找魔数
B充实的寒假生活 B24点
C股票 C2050年成绩计算
D改卷子 D军备竞赛
E上机考试 E图像的均值滤波
F北大杯台球比赛 F统计套利策略
2019级期末考试
题目ID 标题 页码
A这一天星期几
B提取实体
C图的拉普拉斯矩阵
D二维矩阵上的卷积运算
E买学区房
F因材施教

2017级期末考试

A. 字符串连接位置

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号16527
  • 提交次数:539
  • 尝试人数:152
  • 通过人数:121
  • 通过率:80%笔者注:正文所述“提交次数”“尝试人数”“通过人数”“通过率”均为考试数据。参考代码中的“时间”“内存”均为运行在OpenJudge上得出的数据。

描述

给定两个字符串A和B,如果A的某一后缀恰好和B的某一前缀相同,则定义字符串A可以连接到B。

例如,字符串xxxxxabc可以连接到字符串abc********,因为

xxxxxabc
     abc********

输入

输入为两行,分别为字符串A和B。

输入保证A和B是可连接的。

输出

字符串连接的位置,从0开始计数。

如果存在多个可连接位置,则输出值最大的位置。

样例输入1

xxxxxabc
abc********

样例输出1

5

样例输入2

a
abcd

样例输出2

0

思路

这道题需要求出A的后缀与B的前缀相同的最小长度。笔者注:由于输出值最大,而输出值 = A的长度 - 相同前后缀长度,因此需要满足相同前后缀最小。

最简单的实现方法就是遍历,依次比较两字符串长为1个、2个、3个……字符的前后缀是否相等,一旦相等即停止循环(得到最小长度)。而通过利用Python的切片特性可以很快获取字符串的前缀、后缀。

如果需要得到最大长度,可反向循环。

参考代码

  • 时间:297 ms
  • 内存:3244 kB
a, b = input(), input();
n = 0;
for i in range(1, min(len(a), len(b)) + 1):
    if a[-i:] == b[:i]:
        n = i;
        break;
print(len(a) - n);

B. 充实的寒假生活

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号16528
  • 提交次数:228
  • 尝试人数:81
  • 通过人数:31
  • 通过率:38%

描述

寒假马上就要到了,龙傲天同学获得了从第0天开始到第60天结束为期61天超长寒假,他想要尽可能丰富自己的寒假生活。

现提供若干个活动的起止时间,请计算龙同学这个寒假至多可以参加多少个活动?注意所参加的活动不能有任何时间上的重叠,在第x天结束的活动和在第x天开始的活动不可同时选择。

输入

第一行为整数n,代表接下来输入的活动个数(n < 10000)。

紧接着的n行,每一行都有两个整数,第一个整数代表活动的开始时间,第二个整数代表结束时间。

输出

输出至多参加的活动个数。

样例输入

5
0 0
1 1
2 2
3 3
4 4

样例输出

5

思路

此题可直接用模拟法求解。先设置变量数组days用于表明第i天是否有空,然后按顺序比较活动开始时间到结束时间内是否有空,如有空则可安排活动,否则不可安排活动。

由于要尽可能多地参加活动,因此应对全部活动按持续时间排序,先安排持续时间短的活动。可以证明这种安排方式是最优解。

参考代码

  • 时间:962 ms
  • 内存:4532 kB
n = int(input());
l = [];
for i in range(n):
    l.append([int(i) for i in input().split()]);
k = 0;
days = [True for i in range(61)];
l.sort(key = (lambda x:x[1] - x[0]));
for i in l:
    if all(days[i[0]: i[1] + 1]):
        k += 1;
        days[i[0]: i[1] + 1] = [False for i in range(i[0], i[1] + 1)];
print(k);

C. 股票

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号16529
  • 提交次数:306
  • 尝试人数:107
  • 通过人数:42
  • 通过率:39%

描述

假设小明一开始有100块钱,给出每天的股票价格,小明可以在这些天内先后进行一次买操作和一次卖操作,或者什么也不干。 问小明最后最多可以得到多少钱?

注意

  1. 一定要先买后卖。
  2. 股票最后一定要卖掉。
  3. 数据量较大,如果简单枚举(买入价,卖出价)会超时。

提示n天内只能买进一次,卖出一次。并且可以买非整数股。

输入

第一行为天数n(1 ≤ n ≤ 100000)。

接下来一行有n个数pi,为每天的股票价格,pi > 0。

输出

最后小明可以得到最多的钱数(小数点后保留两位)。

样例输入1

5
0.1 0.8 20 0.5 0.01

样例输出1

20000.00

样例输入2

6
599 600 301 599 300 301

样例输出2

199.00

样例输入3

5
5 4 3 2 1

样例输出3

100.00

样例输入4

5
5 4 3 21 1

样例输出4

700.00

思路

很容易想到,此题的基本思路是求出在i < j的条件下,pj / pi的最大值。

最简单的想法就是直接遍历i < j的所有值,求出所有pj / pi,然后求最大值。但此方法复杂度为O(n2),在数据量较大时会超时(我已经试过了)。

网上冲浪之后发现了简化解法,仅需一层遍历。基本想法是先设置变量mi用于存放股价的较小值,rate用于存放卖出价与买入价的最大比率。对于每天的股价,如果其大于等于较小值mi,则该天买入后无论哪天卖出,其比率一定小于等于最大比率rate,因此无需计算直接跳过;如果其小于较小值mi,则先判断该天之后的最大股价与该天股价的比值r是否大于之前的最大比率rate,若是则将mirate替换为该天的值,若否则不进行操作。最后将最大比率rate乘以初始值100元即可。此方法复杂度应为O(n)。

参考代码

  • 时间:2191 ms笔者注:是的,运行时间超过了1000 ms,但还是通过了。
  • 内存:20332 kB
n = int(input());
l = [float(i) for i in input().split()];
mi = l[0];
rate = 1.0;
for i in range(n):
    if l[i] < mi or i == 0:
        r = max(l[i + 1: n]) / l[i];
        if r > rate:
            rate = r;
            mi = l[i];
print("{0:.2f}".format(rate * 100));

D. 改卷子

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号16530
  • 提交次数:299
  • 尝试人数:118
  • 通过人数:86
  • 通过率:73%

描述

闫老师希望将所有学生的卷子按姓名分成两摞,交给两位助教批改。假设每位考生姓名由大写字母组成。

你想出来一个好办法:你给出一个字符串,然后让闫老师将每位同学姓名的每个字母依次与该字符串比较。为了使这个过程更简单,你认为这个字符串应该尽可能的短。

现在有n位学生,请你找出这样一个字符串S,使得学生姓名小于或等于S的有一半,而另一半学生姓名大于S。如果有多个字符串满足最短长度,那么就取字母排序最小的那个字符串。

输入

每组数据以n开始,代表n个学生。(n ≥ 2且n ≤ 1000且n为偶数)。

接下来n行为学生姓名。每个名字都由大写字母组成,长度小于30个字母。

输出

针对每组数据,一行输出一个符合条件的最短字符串(大写字母)。

样例输入1

2
LARHONDA
LARSEN

样例输出1

LARI

样例输入2

4
SAM
FRED
JOE
MARGARET

样例输出2

K

样例输入3

2
A
C

样例输出3

A

样例输入4

2
AYZZ
AZ

样例输出4

AYZZ

思路

这题我是看了别人的代码才发现了自己的错误……丢脸……

显然此题需要先对名字排序,然后选取最中间的两个字符A、B进行比较笔者注:此处比较方法是字典序比较。其基本思路与字典的单词排序顺序类似,即先比较两字符串第一个字符,若相同则比较下一个字符。若出现不同,则字符较小者靠前。例如:ABC < ABD。若某字符串先结束,则较短者靠前。例如:ABC < ABCD。。基本思路如下:

首先先将A、B的最长相同前缀提取出来,这部分对最终的结果无影响。

如果此时A无剩余字符或仅剩余1个字符,由于必有A < B,则A本身即是满足条件的最短字符串,返回A即可。例如:A & AB,返回A;AA & AB,返回AA。

设A剩余字符为α,B剩余字符为β。若β1 - α1 > 1(α1表示α的第1个字符的ASCII码,后同),则只需返回最长前缀后接(α1 + 1)即可。此时由于α1不可能为Z,因此无需考虑超出范围。例如:AB & C,返回B。

β1 - α1 == 1且B有大于等于2个剩余字符,此时同样返回前缀后接(α1 + 1)。同样,α1不可能为Z。例如:AB & BA,返回B。笔者注:我第一次做这道题的时候就是没有考虑到这种情况,然后Debug好久都没发现……

β1 - α1 == 1,此时α1可能为Z。需要按位置顺序依次检查字符是否为Z,并在第一个不为Z的字符上+1(如果此字符为结尾字符,则直接返回该字符)。例如:AZAA & B,返回AZB;AZA & B,返回AZA。

参考代码

  • 时间:875 ms
  • 内存:3616 kB
def main(n, nameList):
    nameList.sort();
    a, b = nameList[n // 2 - 1], nameList[n // 2];
    i = 0;
    while i < min(len(a), len(b)):
        if a[:i + 1] != b[:i + 1]:
            break;
        i += 1;
    if len(a) <= i + 1:
        return a;
    elif (ord(b[i]) - ord(a[i]) > 1) or len(b) > i + 1:
        return a[:i] + chr(ord(a[i]) + 1);
    else:
        for i in range(i + 1, len(a) - 1):
            if a[i] != 'Z':
                return a[:i] + chr(ord(a[i]) + 1);
        return a;

n = int(input());
nameList = [];
for i in range(n):
    nameList.append(input());
print(main(n, nameList));

E. 上机考试

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号16531
  • 提交次数:165
  • 尝试人数:47
  • 通过人数:12
  • 通过率:26%

描述

一个班的同学在m行 × n列的机房考试,给出学生的座位分布和每个人的做题情况,统计做题情况与周围(上下左右)任一同学相同的学生人数。

另外,由于考试的优秀率不能超过40%,请统计这个班的优秀人数(可能为0,相同分数的同学必须要么全是优秀,要么全不是优秀)。

提示m × n行做题情况可能为空。因为如果所有学生做题过程中,一直没有提交,则空。笔者注:我个人没有看懂这句话的含义,在编写程序时也没有考虑这种情况,提交之后也通过了。

输入

第一行为两个整数,mn

接下来m行每行n个整数,代表对应学生的编号,编号各不相同,范围由0到m × n - 1。

接下来m × n行,顺序给出编号由0到n - 1的同学的做题情况,1代表做对,0代表做错。

输出

两个整数,以空格分隔;分别代表“与周围任一同学做题情况相同的学生人数”和“班级优秀的人数”。

样例输入1

2 5
0 1 2 3 4
5 6 7 8 9
1 1 1
1 0 1
0 0 0
0 0 1
0 0 0
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

样例输出1

6 0

解释

编号为0 5 6 7 8 9的同学做题情况与周围同学相同,因此第一个整数是6。

全对的同学人数已经超过了40%,因此优秀的人数为0。

样例输入2

1 3
1 0 2
0 1 0 0
0 0 0 0
0 0 0 0

样例输出2

0 1

解释:并不存在与相邻同学做题情况相同的同学,并且做对一题的同学比例小于40%,因此有一人优秀。

样例输入3

2
A
C

样例输出3

A

样例输入4

2
AYZZ
AZ

样例输出4

AYZZ

思路

这题思路倒是不难,用模拟法求解就可以。通过率低可能是因为考试写不完了。“做题相同人数”和“优秀人数”分别求解。

先看“优秀人数”。先设置变量字典scores用于存放各成绩的人数,count用于存放优秀人数,maxCount用于存放最大优秀人数。先遍历所有学生,求出总成绩,然后存放入scores对应的值中。然后对成绩倒序排序后遍历,如果某成绩的人数加上已有优秀人数大于最大优秀人数,则结束遍历。

再看“做题相同人数”。我一直认为会有简化算法,但是想了半天还是用了遍历思想。先设置列表same用于存放某编号学生是否与周围人做题相同,然后用两个二重循环,一个用于横向两两比较,另一个用于竖向两两比较。若比较结果为两人相同,则将same对应的值设为True。最后对sameTrue的数目进行计数即可。

参考代码

  • 时间:749 ms
  • 内存:3480 kB
m, n = (int(i) for i in input().split());
ids = [];
for i in range(m):
    ids.append([int(i) for i in input().split()]);
results = [None for i in range(m * n)];
scores = {};
for i in range(m * n):
    results[i] = [int(i) for i in input().split()];
    s = sum(results[i]);
    if s in scores:
        scores[s] += 1;
    else:
        scores[s] = 1;
count = 0;
maxCount = m * n * 0.4;
for i in sorted(scores.keys(), reverse = True):
    if (count + scores[i]) > maxCount:
        break;
    else:
        count += scores[i];
same = [False for i in range(m * n)];
for i in range(m):
    for j in range(n - 1):
        if (results[ids[i][j]] == results[ids[i][j + 1]]):
            same[ids[i][j]] = True;
            same[ids[i][j + 1]] = True;
for i in range(m - 1):
    for j in range(n):
        if (results[ids[i][j]] == results[ids[i + 1][j]]):
            same[ids[i][j]] = True;
            same[ids[i + 1][j]] = True;
print(same.count(True), count);

F. 北大杯台球比赛

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号16532
  • 提交次数:81
  • 尝试人数:23
  • 通过人数:11
  • 通过率:48%

描述

北大杯台球比赛进入白热化的黑八大战环节,台球桌尺寸为16 × 5笔者注:原文如此。此说法似乎不妥,坐标编号为(0 ~ 16, 0 ~ 5),尺寸应为17 × 6。,以台球桌左上角建立坐标系如下图所示:

0——1——2——3——4——5——6——7——8——...——16——   x轴
|  |  |  |  |  |  |  |  |       |
1——.——.——.——.——.——.——.——.——...——.
|  |  |  |  |  |  |  |  |       |
2——.——.——.——.——.——.——.——.——...——.
|  |  |  |  |  |  |  |  |       |
3——.——.——.——.——.——.——.——.——...——.
|  |  |  |  |  |  |  |  |       |
4——.——.——.——.——.——.——.——.——...——.
|  |  |  |  |  |  |  |  |       |
5——.——.——.——.——.——.——.——.——...——.
|

y轴

其中(0, 0)、(8, 0)、(16, 0)、(0, 5)、(8, 5)、(16, 5)是台球桌上的六个入袋口,台球只有运动到这六个网格顶点时才能进球。

现在已知台球桌上仅剩下一个白色母球和一个黑球,并且知道他们的x, y坐标(均为整数)。击球时只能击打白色母球,且击球方向只有左上(-1, -1)、左下(-1, 1)、右上(1, -1)、右下(1, 1)四种方向。

击球后白色母球会沿击球方向运动,若碰到球桌壁则会发生反弹,若碰到黑球则会发生完全弹性碰撞导致动能完全传递(即白球静止,黑球获得白球的速度继续运动)。球向以上4个方向移动一次就会消耗一单位能量。请计算最后的胜负情况。

输入

输入为四行。

第一行为白色母球的坐标。

第二行为黑球的坐标。

第三行为击球方向。

第四行为击球力度,即施加给白球的初始动能是多少单位。

输入保证两球的坐标落在球桌内,不会在球壁上,且不重复,保证击球方向为上述四方向之一,保证击球能量 ≥ 0。

输出

输出为一行。

假如白球入库输出-1,黑球入库则输出1,无球入库则输出0。

样例输入1

1 1
2 2
-1 -1
10

样例输出1

-1

样例输入2

2 2
1 1
-1 -1
10

样例输出2

1

样例输入3

2 2
1 1
-1 -1
0

样例输出3

0

思路

这题我的第一想法是找出运动轨迹然后直接计算,但是考虑到这是道考试题,大概也没时间做花里胡哨的东西,所以还是直接模拟法求解吧。

为了简化代码,我把“无球”定义为0,“白球”定义为1,“黑球”定义为2。先设置变量数组pos用于存放白球和黑球的位置,direc用于存放正在运动的球的运动方向,force用于存放球的剩余能量,now用于存放正在运动的球,map用于存放地图各点的状态,holes用于存放所有球洞的位置。开始时先将map中白球和黑球的点分别设置为12(代表这两点上有白球和黑球),其他位置为0(代表这些点上没有球)。

在保证能量force > 0的情况下循环:先计算正在运动的球的位置newPos = pos[now] + direc笔者注:此处为简化写法,实际上应对xy坐标分别相加。。先判断特殊情况:

  • 若新位置在洞中,则直接输出掉入洞中的球(白球输出-1,黑球输出1),结束程序。
  • 若新位置上有球,则将正在运动的球改为新位置上的球,由于完全弹性碰撞没有能量损失,因此force不变,继续循环。
  • 若新位置为桌壁,则改变运动方向(与左右壁碰撞改变x方向,与上下壁碰撞改变y方向)。

判断特殊情况后,将map上一个位置的数值设为0,将现在的位置pos[now]设为新位置newPos,将map新位置的数值设为正在运动的球now。然后将能量force- 1,继续循环。

如果循环结束时没有返回值(即没有球入洞),则返回0

参考代码

  • 时间:403 ms
  • 内存:3396 kB
def main():
    pos = [None, [int(i) for i in input().split()], [int(i) for i in input().split()]];
    direc = [int(i) for i in input().split()];
    force = int(input());
    now = 1;
    map = [[0 for i in range(6)] for j in range(17)];
    holes = [(0, 0), (8, 0), (16, 0), (0, 5), (8, 5), (16, 5)];

    map[pos[1][0]][pos[1][1]] = 1;
    map[pos[2][0]][pos[2][1]] = 2;
    while force:
        newPos = (pos[now][0] + direc[0], pos[now][1] + direc[1]);
        if newPos in holes:
            return -1 if now == 1 else 1;
        elif map[newPos[0]][newPos[1]] != 0:
            now = map[newPos[0]][newPos[1]];
            continue;
        elif newPos[0] in (0, 16):
            direc[0] = -direc[0];
        elif newPos[1] in (0, 5):
            direc[1] = -direc[1];
        map[pos[now][0]][pos[now][1]] = 0;
        pos[now] = newPos;
        map[pos[now][0]][pos[now][1]] = now;
        force -= 1;
    return 0;

print(main());

2018级期末考试

A. 找魔数

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号18224
  • 提交次数:490
  • 尝试人数:133
  • 通过人数:105
  • 通过率:79%

描述

一个数如果能表示为两个完全平方数的和(两个正整数的平方和,如:22 + 42 = 20,12 + 42 = 17),则称为魔数。要求你在一堆数字中找出魔数,并且分别以二进制、八进制、十六进制输出这个数字。

输入

第一行1个整数,代表m个数字(1 ≤ m ≤ 100)。

接下来1行,为m个整数,xi(1 ≤ xi ≤ 1000)。

输出

每个魔数1行,以空格间隔输出该魔数的二进制、八进制、十六进制。

(注:如果出现abcdef等字母,都按小写输出)。

样例输入

4
3 9 20 17

样例输出

0b10100 0o24 0x14
0b10001 0o21 0x11

思路

“魔数”其实就是两个完全平方数的和,由于1 ≤ xi ≤ 1000,因此最暴力的方法实际上就是把1 ~ 1000以内的所有“魔数”求出来,然后从输入的数字里面把“魔数”挑选出来,再进行后续输出操作。而输出二进制、八进制、十六进制则直接调用Python内置函数bin()oct()hex()即可。

至于求魔数的方法,可以单独写一段Python代码求,也可以直接用Excel求。由于312 = 961,322 = 1024,所以只需要求出1 ~ 31的平方并两两加和,去重后得到列表data

Python代码见下:

magicNumbers = [];
for i in range(1, 32):
    for j in range(i, 32):
        magicNumbers.append(i * i + j * j);
magicNumbers = sorted(list(set(magicNumbers)));
print(magicNumbers);

Excel求法见。图中A列和1行是1 ~ 31的数列,B列和2行是其平方,C3 ~ AG33单元格是平方和。然后复制C3 ~ AG33单元格中的内容直接粘贴到Python中作为长字符串(用'''包含),然后用split方法分隔成单独的数字即可。

用Excel求“魔数”

暴力法简单粗暴好想,但是在数据量大的时候会消耗大量内存,同时在查表的时候也会消耗大量时间。另一种思想是对于给定的数,直接判断该数是否为“魔数”。数学上或许可以证明了两个完全平方数的和的性质,但是考试时间紧,数学证明不太现实。因此这里同样给出遍历判断的Python代码:

from math import sqrt

magicNumbers = {};
def isMagicNumber(x):
    global magicNumbers;
    if x in magicNumbers:
        return magicNumbers[x];
    else:
        maxRoot = int(sqrt(x));
        for i in range(1, maxRoot + 1):
            for j in range(i, maxRoot + 1):
                if x == i * i + j * j:
                    magicNumbers[x] = True;
                    return True;
        magicNumbers[x] = False;
        return False;

上述代码中利用了“缓存”的思想,即维护一个字典magicNumbers,如果一个数x已被判断过,则直接输出magicNumbers[x]。否则,求出x的平方根的下取整值maxRoot,进行二重循环(1 ~maxRoot, i~maxRoot),判断x是否等于两数平方和。若是则保存magicNumbers[x] = True并返回True;若循环结束仍未返回True则保存magicNumbers[x] = False并返回False

下述参考代码中直接使用了暴力法,直接将计算好的“魔数”保存为数组data减少运算量。在判断某数是否为“魔数”时,利用了Python内置的filter()函数和lambda表达式的写法。

如果想用判断法,可参考第C题的写法。

参考代码

  • 时间:709 ms
  • 内存:3604 kB
data = [2, 5, 8, 10, 13, 17, 18, 20, 25, 26, 29, 32, 34, 37, 40, 41, 45, 50, 52, 53, 58, 61, 65, 68, 72, 73, 74, 80, 82, 85, 89, 90, 97, 98, 100, 101, 104, 106, 109, 113, 116, 117, 122, 125, 128, 130, 136, 137, 145, 146, 148, 149, 153, 157, 160, 162, 164, 169, 170, 173, 178, 180, 181, 185, 193, 194, 197, 200, 202, 205, 208, 212, 218, 221, 225, 226, 229, 232, 233, 234, 241, 242, 244, 245, 250, 257, 260, 261, 265, 269, 272, 274, 277, 281, 288, 289, 290, 292, 293, 296, 298, 305, 306, 313, 314, 317, 320, 325, 328, 333, 337, 338, 340, 346, 349, 353, 356, 360, 362, 365, 369, 370, 373, 377, 386, 388, 389, 392, 394, 397, 400, 401, 404, 405, 409, 410, 416, 421, 424, 425, 433, 436, 442, 445, 449, 450, 452, 457, 458, 461, 464, 466, 468, 477, 481, 482, 485, 488, 490, 493, 500, 505, 509, 512, 514, 520, 521, 522, 530, 533, 538, 541, 544, 545, 548, 549, 554, 557, 562, 565, 569, 577, 578, 580, 584, 585, 586, 592, 593, 596, 601, 605, 610, 612, 613, 617, 625, 626, 628, 629, 634, 637, 640, 641, 648, 650, 653, 656, 657, 661, 666, 673, 674, 676, 677, 680, 685, 689, 692, 697, 698, 701, 706, 709, 712, 720, 722, 724, 725, 730, 733, 738, 740, 745, 746, 754, 757, 761, 765, 769, 772, 773, 776, 778, 785, 788, 793, 794, 797, 800, 801, 802, 808, 809, 810, 818, 820, 821, 829, 832, 833, 841, 842, 845, 848, 850, 853, 857, 865, 866, 872, 873, 877, 881, 882, 884, 890, 898, 900, 901, 904, 905, 909, 914, 916, 922, 925, 928, 929, 932, 936, 937, 941, 949, 953, 954, 962, 964, 965, 968, 970, 976, 977, 980, 981, 985, 986, 997, 1000]
n = int(input());
numbers = [int(i) for i in input().split()];
magicNumbers = filter(lambda x: x in data, numbers);
for i in magicNumbers:
    print(" ".join([bin(i), oct(i), hex(i)]));

B. 24点

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号18223
  • 提交次数:254
  • 尝试人数:139
  • 通过人数:123
  • 通过率:88%

描述

给定4个整数,判断是否能只用加减运算(即在4个数中间插入3个+或-符号,可以调换数字顺序),使得运算结果为24。

输入

第一行1个整数,代表m组数据(1 ≤ m ≤ 100)

接下来m行,每行为4个整数,xi(1 ≤ xi ≤ 10100),注意整数可能很大。

输出

m行,每行为YES或者NO,代表是否能凑成24点。

对于如下输入,6 + 6 + 6 + 6 = 24,25 - 3 + 1 + 1 = 24,100000000000000000000000 - 100000000000000000000000 - 100000000000000000000000 + 100000000000000000000024 = 24。

样例输入

4
6 6 6 6
3 25 1 1
100000000000000000000000 100000000000000000000000 100000000000000000000000 100000000000000000000024
2 3 4 5

样例输出

YES
YES
YES
NO

思路

虽然题目中有说“可以调换数字顺序”,但是因为题目限定了加减运算,因此只需要考虑四个数前面的符号是“+”还是“-”即可。如果遍历的话,理论上要运算24 = 16次,但是考虑到形如“++++”和“----”的两组符号得到的结果互为相反数(即如果“++++”得到24,则“----”得到-24),因此只需要运算8次,比较运算结果是否等于24或-24即可。

参考代码中利用了Python内置的map()函数简化代码量,也可以用for循环代替,且for循环可以在得到24或-24后立刻跳出循环,理论上可以节省时间。

参考代码

  • 时间:750 ms
  • 内存:3516 kB
matrix = ((1, 1, 1, 1),
          (1, 1, 1, -1),
          (1, 1, -1, 1),
          (1, 1, -1, -1),
          (1, -1, 1, 1),
          (1, -1, 1, -1),
          (1, -1, -1, 1),
          (1, -1, -1, -1));
n = int(input());
for i in range(n):
    numbers = [int(i) for i in input().split()];
    def calc(a):
        return numbers[0] * a[0] + numbers[1] * a[1] + numbers[2] * a[2] + numbers[3] * a[3];
    results = list(map(calc, matrix));
    print("YES" if (24 in results or -24 in results) else "NO");

C. 2050年成绩计算

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号18176
  • 提交次数:442
  • 尝试人数:112
  • 通过人数:40
  • 通过率:36%

描述

随着人工智能技术和基因编辑技术的普及,2050年的学生成绩计算与目前2018年的规则很不一样。课程成绩要求是t-prime,才是有效成绩,否则按照零分计算。

现在需要统计每位学生在一个学期中,所有有效成绩课程的平均分,需要你的帮忙。

(素数是指除了1和它本身以外,不能被任何整数整除的数。类似地,如果整数t恰好有且仅有三个不同的正除数笔者注:原文如此。个人认为应该称其为“因数”。,我们将称为它为t-prime。)

输入

第一行为两个整数,m个学生(1 ≤ m ≤ 2000),n门课(1 ≤ n ≤ 100,每个学生选课数可以不一样)。

接下来m行,每行代表学生选课获得成绩。成绩由空格分隔,成绩是整数xi(1 ≤ xi ≤ 108)。

输出

m行,每行对应一位学生有效成绩课程的平均分(小数点后保留两位)。如果该生所有选课有效成绩是零分,则输出0

对如下样例,第一个学生所有成绩都不是t-prime,因此输出0,注意这里不保留两位小数。

第二位学生只有4分是有效分数,故输出4 / 3 = 1.33。

第三位学生只有两门课有成绩,4和25均为t-prime,因此输出平均值14.50。

样例输入

3 3
100 120 2
3 4 5
4 25

样例输出

0
1.33
14.50

思路

t-prime看似复杂,其实很好理解。除了1之外的数至少都有1和它本身作为因数,而t-prime有且仅有3个因数,因此第3个因数应为其平方根,且该平方根为质数。因此判断一个数是否为t-prime,只需判断该数是否为完全平方数,以及该数的平方根是否为质数。

参考第A题,很容易想到两种解法,即暴力法和判断法。暴力法的思想是求出1 ~ 108范围内的所有t-prime,进而想到求出1 ~ 104范围内的所有质数。而质数的计算方法较简单,只需计算该数是否能被2 ~ 该数平方根的范围内的整数整除即可。参考代码如下:

from math import sqrt

prime = [True for i in range(10000)];
prime[0:1] = [False, False];
for i in range(1, 10000):
    for j in range(2, int(sqrt(i)) + 1):
        if i % j == 0:
            prime[i] = False;
            break;
primes = [];
for i in range(1, 10000):
    if prime[i]:
        primes.append(i);
tPrimes = [i * i for i in primes];
print(tPrimes);

输出如下:

[4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2809, 3481, 3721, 4489, 5041, 5329, 6241, 6889, 7921, 9409, 10201, 10609, 11449, 11881, 12769, 16129, 17161, 18769, 19321, 22201, 22801, 24649, 26569, 27889, 29929, 32041, 32761, 36481, 37249, 38809, 39601, 44521, 49729, 51529, 52441, 54289, 57121, 58081, 63001, 66049, 69169, 72361, 73441, 76729, 78961, 80089, 85849, 94249, 96721, 97969, 100489, 109561, 113569, 120409, 121801, 124609, 128881, 134689, 139129, 143641, 146689, 151321, 157609, 160801, 167281, 175561, 177241, 185761, 187489, 192721, 196249, 201601, 208849, 212521, 214369, 218089, 229441, 237169, 241081, 249001, 253009, 259081, 271441, 273529, 292681, 299209, 310249, 316969, 323761, 326041, 332929, 344569, 351649, 358801, 361201, 368449, 375769, 380689, 383161, 398161, 410881, 413449, 418609, 426409, 434281, 436921, 452929, 458329, 466489, 477481, 491401, 502681, 516961, 528529, 537289, 546121, 552049, 564001, 573049, 579121, 591361, 597529, 619369, 635209, 654481, 657721, 674041, 677329, 683929, 687241, 703921, 727609, 734449, 737881, 744769, 769129, 776161, 779689, 786769, 822649, 829921, 844561, 863041, 877969, 885481, 896809, 908209, 935089, 942841, 954529, 966289, 982081, 994009, 1018081, 1026169, 1038361, 1042441, 1062961, 1067089, 1079521, 1100401, 1104601, 1125721, 1129969, 1142761, 1181569, 1190281, 1194649, 1203409, 1216609, 1229881, 1247689, 1261129, 1274641, 1324801, 1329409, 1352569, 1371241, 1394761, 1408969, 1423249, 1442401, 1471369, 1481089, 1495729, 1510441, 1515361, 1530169, 1560001, 1585081, 1630729, 1635841, 1646089, 1661521, 1666681, 1682209, 1692601, 1697809, 1708249, 1739761, 1745041, 1760929, 1852321, 1868689, 1885129, 1907161, 1957201, 1985281, 2024929, 2036329, 2042041, 2053489, 2070721, 2093809, 2105401, 2111209, 2128681, 2163841, 2193361, 2199289, 2211169, 2217121, 2229049, 2247001, 2283121, 2319529, 2343961, 2380849, 2399401, 2411809, 2430481, 2455489, 2468041, 2493241, 2505889, 2550409, 2563201, 2582449, 2588881, 2601769, 2621161, 2627641, 2647129, 2679769, 2745649, 2765569, 2778889, 2785561, 2866249, 2879809, 2886601, 2920681, 2961841, 2968729, 3003289, 3031081, 3052009, 3073009, 3094081, 3157729, 3179089, 3193369, 3200521, 3243601, 3279721, 3323329, 3352561, 3411409, 3463321, 3485689, 3500641, 3508129, 3523129, 3530641, 3568321, 3613801, 3636649, 3659569, 3728761, 3736489, 3798601, 3806401, 3892729, 3916441, 3948169, 3972049, 3988009, 3996001, 4012009, 4044121, 4068289, 4108729, 4116841, 4157521, 4214809, 4255969, 4280761, 4330561, 4338889, 4355569, 4363921, 4405801, 4456321, 4464769, 4532641, 4541161, 4566769, 4583881, 4592449, 4635409, 4669921, 4748041, 4853209, 4870849, 4897369, 4932841, 5004169, 5013121, 5031049, 5067001, 5139289, 5148361, 5166529, 5202961, 5230369, 5257849, 5276209, 5331481, 5340721, 5442889, 5470921, 5480281, 5508409, 5527201, 5555449, 5621641, 5650129, 5669161, 5678689, 5707321, 5726449, 5755201, 5812921, 5841889, 5870929, 5938969, 5958481, 5987809, 6046681, 6086089, 6115729, 6135529, 6265009, 6355441, 6405961, 6446521, 6466849, 6497401, 6507601, 6538249, 6651241, 6713281, 6723649, 6806881, 6848689, 6869641, 6932689, 7006609, 7059649, 7070281, 7091569, 7134241, 7166329, 7198489, 7219969, 7230721, 7252249, 7284601, 7327849, 7349521, 7360369, 7392961, 7447441, 7458361, 7513081, 7557001, 7579009, 7656289, 7711729, 7778521, 7789681, 7823209, 7845601, 7856809, 7946761, 8025889, 8048569, 8082649, 8128201, 8162449, 8185321, 8288641, 8334769, 8392609, 8427409, 8462281, 8508889, 8567329, 8637721, 8720209, 8743849, 8779369, 8814961, 8826841, 8994001, 9006001, 9066121, 9114361, 9138529, 9223369, 9247681, 9296401, 9369721, 9406489, 9480241, 9504889, 9541921, 9665881, 9728161, 9740641, 9840769, 10004569, 10029889, 10042561, 10118761, 10156969, 10182481, 10259209, 10297681, 10349089, 10374841, 10426441, 10569001, 10582009, 10608049, 10621081, 10699441, 10883401, 10896601, 10936249, 10975969, 11015761, 11042329, 11082241, 11095561, 11175649, 11202409, 11282881, 11296321, 11363641, 11377129, 11485321, 11498881, 11607649, 11648569, 11785489, 11895601, 11950849, 11978521, 11992369, 12020089, 12033961, 12187081, 12243001, 12327121, 12369289, 12439729, 12453841, 12482089, 12524521, 12538681, 12581209, 12652249, 12666481, 12752041, 12823561, 12837889, 12909649, 13010449, 13053769, 13082689, 13126129, 13184161, 13227769, 13271449, 13388281, 13476241, 13490929, 13520329, 13623481, 13667809, 13697401, 13756681, 13830961, 13890529, 13935289, 13980121, 14145121, 14190289, 14205361, 14280841, 14386849, 14417209, 14462809, 14600041, 14615329, 14691889, 14799409, 14830201, 14845609, 14922769, 15031129, 15062161, 15124321, 15264649, 15295921, 15342889, 15358561, 15389929, 15437041, 15452761, 15547249, 15578809, 15737089, 15912121, 16008001, 16024009, 16056049, 16104169, 16152361, 16168441, 16216729, 16394401, 16410601, 16459249, 16589329, 16638241, 16736281, 16752649, 16801801, 16900321, 17032129, 17048641, 17081689, 17131321, 17247409, 17280649, 17297281, 17447329, 17648401, 17732521, 17783089, 17799961, 17884441, 17901361, 17986081, 18003049, 18088009, 18139081, 18156121, 18241441, 18258529, 18344089, 18395521, 18464209, 18722929, 18809569, 18826921, 18913801, 18983449, 19035769, 19123129, 19280881, 19333609, 19439281, 19545241, 19562929, 19722481, 19775809, 19811401, 19864849, 19918369, 20079361, 20097289, 20187049, 20313049, 20367169, 20403289, 20421361, 20457529, 20675209, 20693401, 20802721, 20857489, 21003889, 21077281, 21132409, 21187609, 21353641, 21501769, 21520321, 21557449, 21613201, 21631801, 21687649, 21743569, 21836929, 21893041, 22005481, 22118209, 22287841, 22306729, 22363441, 22401289, 22572001, 22648081, 22877089, 22915369, 22934521, 22972849, 23030401, 23049601, 23164969, 23203489, 23338561, 23629321, 23726641, 23785129, 23902321, 24039409, 24098281, 24196561, 24314761, 24334489, 24373969, 24433249, 24512401, 24571849, 24671089, 24690961, 24730729, 24870169, 24930049, 24990001, 25030009, 25090081, 25110121, 25210441, 25230529, 25391521, 25512601, 25593481, 25775929, 25816561, 25877569, 25999801, 26020201, 26081449, 26142769, 26204161, 26491609, 26553409, 26697889, 26739241, 26822041, 26925721, 27008809, 27133681, 27321529, 27363361, 27384289, 27426169, 27678121, 27804529, 27867841, 27888961, 28058209, 28121809, 28185481, 28334329, 28440889, 28590409, 28633201, 28955161, 29019769, 29084449, 29149201, 29235649, 29300569, 29343889, 29365561, 29495761, 29560969, 29604481, 29626249, 29691601, 29931841, 29997529, 30019441, 30063289, 30261001, 30283009, 30327049, 30459361, 30481441, 30547729, 30591961, 30880249, 30946969, 31013761, 31058329, 31147561, 31259281, 31618129, 31798321, 31820881, 31888609, 31933801, 31956409, 32001649, 32024281, 32137561, 32296489, 32364721, 32410249, 32501401, 32615521, 32684089, 32913169, 32959081, 32982049, 33051001, 33396841, 33443089, 33535681, 33651601, 33721249, 33790969, 33884041, 33953929, 34093921, 34140649, 34210801, 34234201, 34304449, 34351321, 34421689, 34445161, 34562641, 34586161, 34774609, 34845409, 35081929, 35129329, 35271721, 35438209, 35772361, 35844169, 36084049, 36132121, 36348841, 36445369, 36517849, 36566209, 36638809, 36808489, 36881329, 36954241, 37075921, 37100281, 37222201, 37368769, 37466641, 37589161, 37613689, 37736449, 37834801, 37982569, 38105929, 38402809, 38427601, 38477209, 38576521, 38651089, 38700841, 38800441, 39025009, 39150049, 39225169, 39300361, 39325441, 39400729, 39526369, 39677401, 39702601, 39828721, 39904489, 39980329, 40056241, 40157569, 40233649, 40360609, 40436881, 40462321, 40538689, 40615129, 40691641, 40819321, 40921609, 41229241, 41306329, 41589601, 41615401, 41847961, 41899729, 42003361, 42133081, 42523441, 42627841, 42863209, 42915601, 42941809, 43072969, 43151761, 43178041, 43256929, 43309561, 43546801, 43652449, 43811161, 44049769, 44262409, 44342281, 44368921, 44528929, 44609041, 44742721, 44769481, 44903401, 44930209, 45010681, 45144961, 45333289, 45387169, 45711121, 45738169, 45954841, 45981961, 46117681, 46144849, 46280809, 46553329, 46607929, 46635241, 46689889, 46799281, 47018449, 47100769, 47183161, 47210641, 47375689, 47596201, 47706649, 47761921, 47844889, 48260809, 48288601, 48427681, 48455521, 48539089, 48594841, 48678529, 48762289, 48874081, 48958009, 49014001, 49182169, 49266361, 49378729, 49547521, 49603849, 49801249, 49970761, 50112241, 50452609, 50537881, 50708641, 50794129, 50822641, 51136801, 51251281, 51509329, 51652969, 51739249, 51940849, 51998521, 52027369, 52113961, 52258441, 52374169, 52461049, 52519009, 52606009, 53042089, 53246209, 53392249, 53421481, 53597041, 53743561, 53772889, 54007801, 54037201, 54302161, 54656449, 54922921, 55011889, 55249489, 55517401, 55606849, 55636681, 55905529, 55965361, 56055169, 56085121, 56235001, 56355049, 56505289, 56595529, 56685841, 56806369, 56866681, 56957209, 56987401, 57138481, 57168721, 57350329, 57410929, 57501889, 57592921, 57623281, 57805609, 57866449, 58079641, 58354321, 58415449, 58507201, 58813561, 58874929, 58997761, 59089969, 59151481, 59274601, 59336209, 59552089, 59644729, 59706529, 59923081, 60109009, 60171049, 60202081, 60668521, 60730849, 61105489, 61199329, 61293241, 61481281, 61669609, 61889689, 61984129, 62047129, 62078641, 62141689, 62425801, 62520649, 62710561, 62837329, 62932489, 62995969, 63186601, 63218401, 63409369, 63888049, 64144081, 64176121, 64272289, 64625521, 64850809, 64947481, 65108761, 65302561, 65399569, 65431921, 65496649, 65626201, 65788321, 65885689, 65983129, 66373609, 66601921, 66699889, 66765241, 66896041, 67092481, 67387681, 67551961, 67584841, 67749361, 67782289, 67848169, 67947049, 68277169, 68376361, 68442529, 68674369, 68740681, 68773849, 68840209, 69072721, 69172489, 69372241, 69772609, 69939769, 70040161, 70174129, 70341769, 70375321, 70879561, 70946929, 71048041, 71081761, 71284249, 71351809, 71588521, 71690089, 72267001, 72471169, 72607441, 72709729, 72880369, 72914521, 72982849, 73324969, 73496329, 73633561, 73908409, 73942801, 74114881, 74356129, 74425129, 74459641, 74666881, 74770609, 75047569, 75151561, 75290329, 75359761, 75498721, 75568249, 75672601, 75811849, 75916369, 76020961, 76230361, 76335169, 76405081, 76510009, 76615009, 76755121, 77070841, 77141089, 77492809, 77563249, 77774761, 77810041, 77986561, 78092569, 78127921, 78304801, 78517321, 78552769, 78623689, 78978769, 79085449, 79619929, 79727041, 79798489, 79941481, 80120401, 80335369, 80442961, 80478841, 80982001, 81018001, 81126049, 81198121, 81234169, 81522841, 81739681, 81775849, 81884401, 82065481, 82210489, 82646281, 82864609, 82973881, 83302129, 83411689, 83484769, 83740801, 83850649, 83923921, 84143929, 84290761, 84400969, 84621601, 84695209, 84805681, 85026841, 85137529, 85359121, 85396081, 85692049, 86062729, 86136961, 86174089, 86359849, 86694721, 86843761, 86918329, 87179569, 87254281, 87291649, 87403801, 87815641, 87928129, 88190881, 88303609, 88416409, 88604569, 88717561, 88755241, 88943761, 88981489, 89056969, 89094721, 89510521, 89548369, 89624089, 89737729, 89851441, 90079081, 90193009, 90459121, 90649441, 90878089, 90992521, 91145209, 91221601, 91910569, 92179201, 92409769, 92525161, 92602129, 92717641, 92756161, 92987449, 93103201, 93334921, 93644329, 93683041, 93876721, 94031809, 94458961, 94497841, 94731289, 94848121, 94926049, 95043001, 95394289, 95433361, 95667961, 95785369, 95863681, 96098809, 96255721, 96373489, 96609241, 96687889, 96805921, 97042201, 97160449, 97199881, 97436641, 97673689, 97752769, 98029801, 98148649, 98465929, 98585041, 98624761, 98823481, 98982601, 99341089, 99460729]

用暴力法也可以写出相应的代码,但是经过运算后发现超时Time Limit Exceeded)。经过改动得到了判断法的代码,如下所示。

参考代码

  • 时间:750 ms
  • 内存:3516 kB
from math import sqrt

tPrimes = {};
def isTPrime(x):
    global tPrimes;
    if x in tPrimes:
        return tPrimes[x];
    else:
        if int(int(sqrt(x)) ** 2) == x:
            root = int(sqrt(x));
            for i in range(2, int(sqrt(root) + 1)):
                if root % i == 0:
                    tPrimes[x] = False;
                    return False;
            tPrimes[x] = True;
            return True;

m, n = (int(i) for i in input().split());
for i in range(m):
    scores = [int(i) for i in input().split()];
    tPrimeScores = list(filter(isTPrime, scores));
    if len(tPrimeScores):
        print("%.2f" % (sum(tPrimeScores) / len(scores)));
    else:
        print(0);

D. 军备竞赛

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号18211
  • 提交次数:138
  • 尝试人数:68
  • 通过人数:50
  • 通过率:74%

描述

鸣人是木叶村的村长,最近在跟敌国进行军备竞赛,他手边有n份武器设计图,每张设计图有制作成(大于等于零)本且最多使用一次,可以选择花钱制作或是以同样的价钱卖给敌国,同时任意时刻敌国的武器不能比我国更多,鸣人的目标是在不负债的前提下武器种类比敌国越多越好。

输入

第一行为起始整数经费p,并且p ≥ 0。且要求任何时刻p不能小于0。

第二行为n个整数,以空格分隔,并且每个整数 ≥ 0。代表每张设计图的制作成本,同时也是卖价,最多用一次(无法又制作又卖)。

输出

一个整数,代表武器种类最多比敌国多多少。

样例输入1

10
20 30 40

样例输出1

0

解释:10元不足以制作20元的武器,所以为0,也不能先卖50元的笔者注:原文如此。,不能让敌国武器比木叶多。

样例输入2

10
15 5

样例输出2

1

解释:10元可以制作5元的武器,木叶的武器比对手多一件。

样例输入3

40
20 80 60 40

样例输出3

2

解释:先制作20元的武器,再贩卖80元的武器,这时经费为100,再制作40、60的武器,木叶的武器比对手多二件。

思路

此题思路其实比较简单,把最便宜的留给自己,把最贵的买给敌人。设置变量数组fee存放所有武器的费用,然后对费用排序。先将所有经费用于制作最便宜的武器,并将制作过的武器费用从fee中移除。然后,如果有2件以上的武器剩余,且敌人武器数比自己少,则将贵的卖给敌人,用得到的钱继续制作武器。如果不能卖掉武器,则结束判断,输出比敌国多的武器。

参考代码

  • 时间:778 ms
  • 内存:3348 kB
p = int(input())
fee = [int(i) for i in input().split()];
fee.sort();
self, enemy = 0, 0;
while True:
    while fee and p >= fee[0]:
        p -= fee[0];
        fee.pop(0);
        self += 1;
    if len(fee) > 1 and enemy < self:
        p += fee[-1];
        fee.pop(-1);
        enemy += 1;
        continue;
    else:
        break;
print(self - enemy);

E. 图像的均值滤波

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号18188
  • 提交次数:155
  • 尝试人数:103
  • 通过人数:92
  • 通过率:89%

描述

背景知识:

  1. 像素是指由图像的小方格组成的,这些小方块都有一个明确的位置和被分配的色彩数值,小方格颜色和位置就决定该图像所呈现出来的样子,对于灰度图而言,每个小方格即存放一个数值,即为像素值。
  2. 数字图像在计算机中通常以二维数组(矩阵)的形式存放,其中每个像素值,即为该数组的值。
  3. 图像的均值滤波操作指在图像上对目标像素给一个模板,该模板包括了其周围的临近像素以及自身,在这里我们考虑以目标像素为中心的8个像素,这时我们用模板中的全体像素的平均值来代替原来目标像素值,得到的结果即为图像均值滤波后的结果。

题目要求:实现图像的均值滤波。

给定一张输入图像,得到其均值滤波后的结果,得到的均值结果若是浮点数则向下取整。比如一个像素点均值为2.5,则结果为2。

边界点的像素只考虑在图像内部的。比如左上角的点邻居只有3个,分别是右边、下边、和右下。

输入

首先为mn两个正整数,表示图像有mn列。

接下来的m行每行有n个正整数代表输入图像的像素。

输出

mn列的二维数组,即经过均值滤波后的结果。

样例输入1

3 3
2 3 2
3 2 1
1 1 1

样例输出1

2 2 2
2 1 1
1 1 1

解释

考虑图像每个像素:

对于下标为(0,0)点,输入像素值为2,输出计算为(2 + 3 + 3 + 2) / 4 = 2.5 -> 2。

对于下标为(0,1)点,输入像素值为3,输出计算为(2 + 3 + 2 + 3 + 2 + 1) / 6 = 2.17 -> 2。

对于下标为(1,1)点,输入像素值为2, 输出计算为(2 + 3 + 2 + 3 + 2 + 1 + 1 + 1 + 1) / 9 = 1.78 -> 1。

对于下标为(2,2)点,输入像素值为1,输出计算为(2 + 1 + 1 + 1) / 4 = 1.25 -> 1。

样例输入2

3 4
2 3 2 4
3 2 1 1
1 1 1 1

样例输出2

2 2 2 2
2 1 1 1
1 1 1 1

思路

此题思路也比较简单,直接把每个点周围的点拉进来算一遍就行了。但是考虑到边界点的处理比较麻烦,因此定义了两个函数:

safeCall函数用于判断给定的(x, y)值是否在边界范围内,若在范围内则返回对应值,若不在范围内则返回None

safeAverage函数用于剔除所有None后求平均值。

参考代码

  • 时间:650 ms
  • 内存:3436 kB
def safeCall(matrix, x, y):
    if x >= 0 and x < len(matrix) and y >= 0 and y < len(matrix[0]):
        return matrix[x][y];
    else:
        return None;

def safeAverage(lst):
    lst = list(filter(lambda x: x != None, lst));
    return sum(lst) // len(lst);

matrix = ((-1, -1), (-1, 0), (-1, 1),
          (0, -1), (0, 0), (0, 1),
          (1, -1), (1, 0), (1, 1))

m, n = (int(i) for i in input().split());
oldMatrix = [];
for i in range(m):
    oldMatrix.append([int(i) for i in input().split()]);
newMatrix = [[0 for i in range(n)] for i in range(m)];
for i in range(m):
    for j in range(n):
        lst = [safeCall(oldMatrix, i + k[0], j + k[1]) for k in matrix];
        newMatrix[i][j] = str(safeAverage(lst));

print("\n".join([" ".join(j) for j in newMatrix]));

F. 统计套利策略

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号18177
  • 提交次数:46
  • 尝试人数:13
  • 通过人数:1
  • 通过率:8%

描述

Mike最近在课上学习了统计套利交易的简单思想,他想自己编写程序来对市场上的品种(股票、期货、外汇)进行交易。在众多资产中,他打算选取只两个品种来配对交易(选定之后就无法更改)。试帮他找出选取哪两个品种可以获得最大的利润,且计算该利润。

Mike的策略:

  1. 选定两种资产后,每一个交易日,他会计算之前所有日期两者价格的平均差值(下面提示中的第一个公式),作为他对两者价差的“合理估计”。
  2. 计算之前所有日期两者价差序列的标准差(下面提示中的第二个公式)作为对风险的“合理估计”。
  3. 在新的每一天,如果选定两个品种的价差偏离历史平均一个标准差,Mike预期会发生均值回归。故会相应在两个品种分别持有1单位做空(即卖出,估计之后要跌)和做多(即买入,估计之后要涨)的仓位(方向为假设发生均值回归会盈利的方向),偏离历史平均两个标准差则持有2单位,以此类推。

Mike在第四天才开始交易,以前三天的平均值和标准差作为初始值。

配对交易维基定义:Pairstrading is a market-neutral trading strategy that matches a long position witha short position in a pair of highly correlated instruments such as two stocks, exchange-traded funds (ETFs), currencies, commodities or options.

具体的例子:比如下图中当两者价格偏离过大的时候,就可以买入其中一者卖出另一者,并期待其差值回归以获利。(绿箭头代表买入,红箭头代表卖出)

“统计套利策略”题图

提示

\[\mathrm{mean}(P_{A} - P_{B}) = \cfrac {\sum\limits_{i = 1}^{n}(P_{A, i} - P_{B, i})} {n},\] \[\mathrm{std}(P_{A} - P_{B}) = \sqrt { \cfrac {\sum\limits_{i = 1}^{n}(P_{A, i} - P_{B, i} - \mathrm{mean}(P_{A} - P_{B}))^2} {n} }.\]

参考伪代码

If P_(A, N + 1) - P_(B, N + 1) > mean(P_A - P_B) + k * std(P_A - P_B)
Then
    position(A) = k
    position(B) = -k

输入

第一行输入两个正整数,分别代表总共的品种数目n,和总共的天数d

接着会输入n行,每行d个正整数,代表一个品种观测期间所有的价格数据。

输出

从第四天(含)起总收益最大的两个品种的序号(从小到大,序号从1开始,连续编号),以及最后的总收益(整数)。

(注:测试数据保证有唯一最优的套利对)

样例输入

4 8
18	14	15	17	10	11	10	14
19	15	18	18	15	11	15	16
16	18	13	10	17	13	14	17
20	12	11	16	14	17	11	15

样例输出

1 3 38

解释

样例计算过程分析:

此时选取第1和第3个资产可以取得最大利润。

资产A价格序列:18 14 15 17 10 11 10 14。

资产B价格序列:16 18 13 10 17 13 14 17。

差价定义为A - B,则意味着向上偏离历史均值,A高估,应做空,B应做多。反之亦然。

  • 第4天:
    • 历史平均差价:0.00,历史方差:2.83,今日差价:7。
    • A持有到明天单位收益 = A(Day5) - A(Day4) = -7,持有A做空手数:-2,收益:14。
    • B持到到明天单位收益 = B(Day5) - B(Day4) = 7,持有B做多手数:2,收益:14。
    • 总收益:28,累积收益:28。
  • 第5天:
    • 历史平均差价:1.75,历史方差:3.90,今日差价:-7。
    • A持有到明天单位收益 = A(Day6) - A(Day5) = 1,持有A手数:2,收益:2。
    • B持到到明天单位收益 = B(Day6) - B(Day5) = -4,持有B手数:-2,收益:8。
    • 总收益:10,累积收益:38。
  • 第6天:
    • 历史平均差价:0.00,历史方差:4.94,今日差价:-2。
    • A持有到明天单位收益 = A(Day7) - A(Day6) = -1,持有A手数:0,收益:0。
    • B持到到明天单位收益 = B(Day7) - B(Day6) = 1,持有B手数:0,收益:0。
    • 总收益:0,累积收益:38。
  • 第7天:
    • 历史平均差价:-0.33,历史方差:4.57,今日差价:-4。
    • A持有到明天单位收益 = A(Day8) - A(Day7) = 4,持有A手数:0,收益:0。
    • B持到到明天单位收益 = B(Day8) - B(Day7) = 3,持有B手数:0,收益:0。
    • 总收益:0,累积收益:38。

思路

这题我没做出来……把错误代码扔到这里大家自己看吧……

参考代码

from math import sqrt

def MEAN(A, B):
    return sum([A[i] - B[i] for i in range(len(A))]) / len(A);

def STD(A, B, mean):
    return sqrt(sum([(A[i] - B[i] - mean) ** 2 for i in range(len(A))]) / len(A));

n, d = [int(i) for i in input().split()];
prices = [];
for i in range(n):
    prices.append([int(i) for i in input().split()]);

maxProfit = [0, 0, 0];
for i in range(n):
    for j in range(i + 1, n):
        profit = 0;
        for k in range(3, d - 1):
            A, B = prices[i][:k], prices[j][:k];
            mean = MEAN(A, B);
            std = STD(A, B, mean);
            diff = prices[i][k] - prices[j][k];
            K = int((diff - mean) / std);
            profit += (prices[i][k] - prices[i][k + 1]) * K - (prices[j][k] - prices[j][k + 1]) * K;
            print(profit);
        if profit > maxProfit[2]:
            maxProfit = [i + 1, j + 1, profit];
print(" ".join([str(i) for i in maxProfit]));

2019级期末考试

A. 这一天星期几

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号19944
  • 提交次数:415
  • 尝试人数:135
  • 通过人数:118
  • 通过率:87%

描述

在日常生活中,计算某一个具体的日期是星期几,往往需要去翻阅日历。请你帮助更快地计算出每个日期在一星期是第几天。

参考:

蔡勒公式(Zellers congruence),是一种计算任何一日属一星期中哪一日的算法,由德国数学家克里斯提安·蔡勒推算出来,可以计算1582年10月15日之后的情况。

\[w = \left ( y + \left [ \cfrac {y} {4} \right ] + \left [ \cfrac {c} {4} \right ] - 2c + \left [ \cfrac {26(m + 1)} {10} \right ] + d - 1 \right ) \mod 7.\]

公式都是基于公历的置闰规则来考虑。

公式中的符号含义如下:

\(w\):星期(计算所得的数值对应的星期:0-Sunday;1-Monday;2-Tuesday;3-Wednesday;4-Thursday;5-Friday;6-Saturday)。

\(c\):年份前两位数。

\(y\):年份后两位数。

\(m\):月(\(m\)的取值范围为3至14,即在蔡勒公式中,某年的1、2月要看作上一年的13、14月来计算,比如2003年1月1日要看作2002年的13月1日来计算)。

\(d\):日。

[ ]:称作高斯符号,代表向下取整,即,取不大于原数的最大整数。

mod:同余(这里代表括号里的答案除以7后的余数)。

输入

第一行1个整数n,代表输入日期的个数。

接下来n行分别为n个以8位数字表示的日期,如20190101。

保证所有输入都在蔡勒公式的计算范围之内。

输出

n行,每行为该日期对应的weekday名称(Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday)。

样例输入

15
19850706
19710710
20041125
20141220
19841128
19760429
19931102
19951002
20161006
20151226
19790715
20080410
20091104
19910621
19891012

样例输出

Saturday
Saturday
Thursday
Saturday
Wednesday
Thursday
Tuesday
Monday
Thursday
Saturday
Sunday
Thursday
Wednesday
Friday
Thursday

思路

我觉得2019年的期末简直是在放水……

这题不太需要什么思路,直接按题目给出的公式计算即可。要注意的是如果m < 3不仅需要令m = m + 12,还要把年份- 1(另外需要考虑世纪变化),否则是无法通过的(我就是在这里卡住的)。

(补充:偶然翻知乎看到一个答案,才想起来python是有自带的日期库的……随手重新写了一段代码,见参考代码2)参考资料:Super Mario. 在信息学竞赛中,你见过哪些“这都能AC!?”的题? - Super Mario 的回答 [EB/OL]. 知乎. (2019-11-24) [2019-12-30]. https://www.zhihu.com/question/343126456/answer/881280919.

参考代码1

  • 时间:779 ms
  • 内存:3640 kB
weekName = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"];

n = int(input());
for i in range(n):
    i = input();
    c, y, m, d = (int(i[x:x + 2]) for x in range(0, 8, 2));
    if m < 3:
        m += 12;
        if y > 0:
            y -= 1;
        else:
            y = 99;
            c -= 1;
    w = (y + y // 4 + c // 4 - 2 * c + 26 * (m + 1) // 10 + d - 1) % 7;
    print(weekName[w]);

参考代码2

  • 时间:920 ms
  • 内存:4084 kB
import datetime

n = int(input());
for i in range(n):
    i = input();
    c, y, m, d = (int(i[x:x + 2]) for x in range(0, 8, 2));
    print(datetime.date(c * 100 + y, m, d).strftime("%A"));

B. 提取实体

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号19949
  • 提交次数:354
  • 尝试人数:116
  • 通过人数:74
  • 通过率:64%

描述

一个句子里面一些特殊的单词被称作实体,实体是存在于现实世界中并且可以与其他物体区分开来的物体,如“John has an apple .”这句话中,“John”和“apple”都是实体。

现在我们有很多个人工标注好实体的英文文档,每篇文档有很多个句子,每个句子中,每个实体的每单词都添加了“###”前缀,并且添加了“###”后缀,表明两个“###”之间的部分是实体或者是实体的一部分。例如:

1) 两个“###”之间是实体:

“###John### has an ###apple### ”中有两个实体,是John和apple。

2) 两个“###”之间是实体的一部分,即是,连续的几个被“###”前后包裹的单词被认为是同一个实体:

“###Shelley### ###Berkley### , a Democratic representative”中有一个实体,是Shelley Berkley。

“###Dominic### ###J.### ###Baranello### , an enduring power in Democratic Party”中有一个实体,是Dominic J. Baranello。

请你帮助统计每篇文档里有多少个实体,暂时不考虑句子间的实体有重复的情况。

输入

第一行为1个整数n,代表文档里的句子数目。

接下来n行,每行代表一个英文句子,每个句子有多少单词是未知的,词与词之间用空格分隔。

输出

1个整数,代表该篇文档里的实体数目。

样例输入1

1
###John### has an ###apple### .

样例输出1

2

解释:文档中只有一个句子,该句子中有两个实体“John”和“apple”,所以输出是2。

样例输入2

1
###Shelley### ###Berkley### , a Democratic representative of Nevada Mrs. ###Babbitt### 's daughter lives in ###Las### ###Vegas### testified about the case in July at a Congressional hearing into the recovery of art stolen during World War II .

样例输出2

3

解释:文档中仍然只有一个句子,但是现在有三个实体,“Shelley Berkley”,“Babitt”和“Las Vegas”。

思路

看到这个题我第一反应是正则表达式匹配……但是考虑到正则表达式需要一定的基础,因此我换了一种简单的思路。

由于原题中提到“连续的几个被‘###’前后包裹的单词被认为是同一个实体”,因此可以直接把所有“### ###”删掉,然后计算所有“###”的数目再除以2即可。

参考代码

  • 时间:694 ms
  • 内存:3800 kB
n = int(input());
text = "\n".join([input() for i in range(n)]);
print(len(text.replace("### ###", "").split("###")) // 2);

C. 图的拉普拉斯矩阵

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号19943笔者注:此链接无法打开,似乎是老师没有公开此题作为练习题。
  • 提交次数:165
  • 尝试人数:110
  • 通过人数:94
  • 通过率:85%

描述

在图论中,度数矩阵是一个对角矩阵 ,其中包含的信息为的每一个顶点的度数,也就是说,每个顶点相邻的边数。邻接矩阵是图的一种常用存储方式。如果一个图一共有编号为0, 1, 2, , n - 1的n个节点,那么邻接矩阵A的大小为n × n,对其中任一元素Aij,如果节点ij直接有边,那么Aij = 1;否则Aij = 0。

将度数矩阵与邻接矩阵逐位相减,可以求得图的拉普拉斯矩阵。具体可见下图示意。

\[L := D - A,\]

“提取实体”题图

现给出一个图中的所有边的信息,需要你输出该图的拉普拉斯矩阵。

输入

第一行2个整数,代表该图的顶点数n和边数m

接下m行,每行为空格分隔的2个整数ab,代表顶点a和顶点b之间有一条无向边相连,ab均为大小范围在0到n - 1之间的整数。输入保证每条无向边仅出现一次(如1 2和2 1是同一条边,并不会在数据中同时出现)。

输出

n行,每行为以空格分隔的n个整数,代表该图的拉普拉斯矩阵。

样例输入

4 5
2 1
1 3
2 3
0 1
0 2

样例输出

2 -1 -1 0
-1 3 -1 -1
-1 -1 3 -1
0 -1 -1 2

思路

这道题并没有开放练习,因此我也不知道我做得对不对,讲一下思路。

先设置两个空矩阵DA,矩阵元素均设置为0;然后依次读取各条边,把D中对应的数+ 1、A中对应的数设为1。最后直接输出两个矩阵的差即可。

参考代码

  • 时间:??? ms
  • 内存:???? kB
n, m = [int(i) for i in input().split()];
D, A = ([[0 for i in range(n)] for j in range(n)] for k in range(2));
for i in range(m):
    x, y = [int(i) for i in input().split()];
    D[x][x] += 1;
    D[y][y] += 1;
    A[x][y] = 1;
    A[y][x] = 1;

print("\n".join([" ".join([str(D[j][i] - A[j][i]) for i in range(n)]) for j in range(n)]));

D. 二维矩阵上的卷积运算

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号19942
  • 提交次数:134
  • 尝试人数:82
  • 通过人数:73
  • 通过率:89%

描述

二维矩阵上的卷积,是卷积神经网络中经常需要进行的一种运算。该运算在输入的二维矩阵上滑动不同的卷积核,并在每一个滑动的位置上将卷积核与输入图像对应位置的元素进行相乘并逐个求和的运算。下图很好地说明了运算的结果矩阵的每一个位置是如何计算得来的。本题中在行列方向的滑动均以1为步长进行,且输入输出均为整数。

如对第1行第1列,12 = 3 × 0 + 3 × 1 + 2 × 2 + 0 × 2 + 0 × 2 + 1 × 0 + 3 × 0 + 1 × 1 + 2 × 2。

“二维矩阵上的卷积运算”题图

输入

第一行4个整数,分别代表二维矩阵的行数和列数mn以及卷积核的行数和列数pq(1 ≤ pm,1 ≤ qn)。

接下来m行,每行为空格分隔的n个整数,代表二维数组中每行的数据。

接下来p行,每行为空格分隔的q个整数,代表卷积核中每行的数据。

输出

易知,p × q的卷积核在m × n的矩阵上以1为步长滑动,横向一共有m + 1 - p个位置,纵向一共有n + 1 - q个位置。

因此输出共m + 1 - p行,每行为以空格分隔的n + 1 - q个整数,代表卷积运算后的结果。

样例输入1

5 5 3 3
3 3 2 1 0
0 0 1 3 1
3 1 2 2 3
2 0 0 2 2
2 0 0 0 1
0 1 2
2 2 0
0 1 2

样例输出1

12 12 17
10 17 19
9 6 14

样例输入2

5 4 4 4
10 -8 6 9
7 -9 1 0
1 -9 2 -5
-3 6 -1 2
-10 -2 -1 -2
-9 -1 -6 10
3 -2 -5 9
-10 -3 -10 7
3 -2 -7 0 

样例输出2

-46
-77

思路

先设置两个矩阵ab分别存放二维数组和卷积核,然后依次遍历m + 1 - p行和n + 1 - q列上的数字,对于每个位置上的数字也要遍历二维数组和卷积核对应位置的乘积和,然后输出。

参考代码

  • 时间:761 ms
  • 内存:3640 kB
m, n, p, q = (int(i) for i in input().split());
a = [[int(i) for i in input().split()] for j in range(m)];
b = [[int(i) for i in input().split()] for j in range(p)];

result = [[0 for i in range(n + 1 - q)] for j in range(m + 1 - p)];
for i in range(m + 1 - p):
    for j in range(n + 1 - q):
        c = sum(sum([a[x + i][y + j] * b[x][y] for y in range(q)]) for x in range(p));
        print(c, end = " " if j < n - q else "\n");

E. 买学区房

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号19963
  • 提交次数:145
  • 尝试人数:71
  • 通过人数:50
  • 通过率:70%

描述

小明同学的家长为了让小明同学接受更好的教育,最近在考虑买某重点中学附近的房子,已知他们买房子要考虑两个因素:房子离学校的距离,以及房子的价格。现在他们有一系列备选的房子,已知这些房子距离学校的x方向距离和y方向距离,以及每栋房子的价格。小明的家长认为,只有同时满足了以下两个条件的房子H买了才是不亏的:

1. 小明的家长比较精打细算,所以房子的性价比大于所用备选房子性价比的中位数(定义见下图)笔者注:原文如此。此处的图片有误导,本题在验证时选取的中位数计算方法应该按照“提示”中所述,选取中间两数平均数。

2. 小明的家长想攒钱,所以房子的价格小于所有备选房子价格的中位数。

“买学区房”题图

注:性价比 = 房子和学校之间的交通距离 / 房子的价格。

(由于该城市的街道布局接近方格状,且从学校到房子无法穿墙而过,房子H去学校的交通距离定义为,房子H距离学校的x方向距离和y方向距离的和)。

现在需要你来帮小明的家长判断,一系列备选房子里,值得买的房子有多少栋。

提示: 求中位数,要先进行数据的排序(从小到大),然后计算中位数的序号,分数据为奇数与偶数两种来求。排序时,相同的数字不能省略。

如果总数个数是奇数的话,按从小到大的顺序,取中间的那个数。

如果总数个数是偶数的话,按从小到大的顺序,取中间那两个数的平均数。

输入

第1行为1个整数,n,代表备选房子的数目。

第2行为n个房子离学校的xy距离对,如“(x, y)”,距离均为整数。

第3行为n个整数,代表每个房子的价格。

输出

一个整数,代表n个房子中值得买的房子数目。

样例输入1

5
(100,200) (50,50) (100,300) (150,50) (50,50)
100 300 200 400 500

样例输出1

2

说明:共有5个房子备选,离学校的交通距离分别是100 + 200 = 300,50 + 50 = 100,100 + 300 = 400,150 + 50 = 200,50 + 50 = 100。这些房子的性价比依次为300 / 100 = 3, 100 / 300 = 1 / 3, 400 / 200 = 2, 200 / 400 = 0.5, 100 / 500 = 0.2,中位数是0.5,满足第1个条件的只有第1个和第3个房子。这些房子的价格中位数是300,因此满足第2个条件的只有第1个和第3个房子。所以同时满足两个条件的有第1个和第3个房子,输出2。

样例输入2

3
(10,90) (20,180) (30,270)
100 200 300

样例输出2

0

说明:共有三个房子备选,离学校的交通距离分别是10 + 90 = 100,20 + 180 = 200,30 + 270 = 300。这些房子性价比依次为100 / 100 = 1,200 / 200 = 1,300 / 300 = 1,中位数是1,没有房子满足第1个条件,因此不用考虑第二个条件,输出一定是0。

思路

首先先定义求中位数函数getMedian。这里使用了偷懒的办法,先将列表排序,然后直接返回最中间两个数的平均值,无论列表长度是奇数还是偶数(因为即使列表长度是奇数,中位数也是中间两数之平均值)。

然后就是常规操作了,先输入距离(这里距离求算有些麻烦)和价格,然后求性价比,再筛选出所有性价比高于中位数和价格低于中位数的房子,最后计数并输出。

参考代码

  • 时间:810 ms
  • 内存:4188 kB
def getMedian(l):
    l = sorted(l);
    return (l[len(l) // 2] + l[(len(l) - 1) // 2]) / 2;

n = int(input());
distance = [sum([int(j) for j in i[1:-1].split(",")]) for i in input().split()];
price = [int(i) for i in input().split()];
ratio = [distance[i] / price[i] for i in range(n)];

ratioM = getMedian(ratio);
priceM = getMedian(price);
count = [(True if (ratio[i] > ratioM and price[i] < priceM) else False) for i in range(n)];

print(count.count(True));

F. 因材施教

  • 总时间限制:1000 ms
  • 内存限制:65536 kB
  • 全局题号19948
  • 提交次数:47
  • 尝试人数:37
  • 通过人数:26
  • 通过率:70%

描述

有一所魔法高校招入一批学生,为了贯彻因材施教的理念,学校打算根据他们的魔法等级进行分班教育。在确定班级数目的情况下,班级内学生的差异要尽可能的小,也就是各个班级内学生的魔法等级要尽可能的接近。

例如:现在有n = 7位学生,他们的魔法等级分别为r = [2, 7, 9, 9, 16, 28, 45],我们要将他们分配到m = 3个班级,如果按照([2, 7], [9, 9], [16, 28, 45])的方式分班,则他们的总体差异为d = (7 - 2) + (9 - 9) + (45 - 16) = 34。

输入

第一行为两个整数:学生人数n和班级数目m,1 ≤ mn ≤ 105

第二行为n个整数:每位学生的魔法等级ri,1 ≤ ri ≤ 109

输出

一个整数:学生的最小总体差异d

样例输入1

7 3
2 7 9 9 16 28 45

样例输出1

14

说明:最小总体差异的分班方式为([2, 7, 9, 9, 16], [28], [45])。

样例输入2

15 9
90 73 116 47 400 212 401 244 13 372 248 56 194 482 177

样例输出2

65

说明:最小总体差异的分班方式为([13], [47, 56, 73, 90], [116], [177, 194], [212], [244, 248], [372], [400, 401], [482])。

思路

这个题乍一看没看懂,再一看看懂了但是没思路,想了一会觉得可以模拟分班方式,最后算了一下发现不用这么麻烦。

先讲原理:由于总体差异是每个班级中最高级和最低级的级别之差的总和,因此应使每个班级的差尽可能小。注意到,如果某班级仅有一个人,那么该班级的差异为0。因此应该把那些和别人相差较大的人单独分班,转换成程序语言就是:先把所有能力值排序,然后计算相邻两项之差。这时注意到n位学生分到m个班级中会产生n - m个差异,因此把相邻两项之差再次排序,选取前n - m个加和即为所求。

由于本题仅需要求出最小总体差异,因此到这一步就可以结束了。如果要求相应的分班方式,也可采用同一思想。

另外,本题的标题标注了“greedy”,意为“贪心算法”。但我个人觉得我使用的方法并没有用到贪心算法。

参考代码

  • 时间:3777 ms
  • 内存:26796 kB
m, n = [int(i) for i in input().split()];
score = sorted([int(i) for i in input().split()]);
print(sum(sorted([score[i] - score[i - 1] for i in range(1, m)])[:m - n]));

后记

老子曾经说过,一篇文章有前言就应该有后记。

这篇资料是我为了一个女孩写的。遗憾的是,我并没有能够打动她,于是我选择切断了和她的联系。即便如此,我还是把这篇资料完成了。

因为写的时候我是按照“入门级资料”的思想编写的,因此我把题目要求都放了上来,看上去显得比较完备。但是这也导致整篇资料非常冗长。不过我觉得应该不会有人把它一页一页打印下来吧……既然是电子化阅读,多一点也无所谓了,反正也占不了多少空间。

今年的北京至今已经下了两场大雪。什么时候才能有人陪我一起看雪呢?或许这个问题只有上天才知道答案吧。

那么,有缘再见。

张祥伟

2019年12月28日于燕园