PDF《2018 年西安电⼦科技⼤学程序设计竞赛⾮官 ⽅题解》

2018 年西安电?科技?学程序设计竞赛?官 ?题解 xry111 April 15,

2018 约定 数组下标从

0 开始.

Problem A No More A+B Problem 难度

1 关键字 组合数学 题解 引?正整数 x 作为松弛变量,将不等式约束化为等式约束: A + B + x = C +

1 (1) 我们就要求

3 个正整数的和是 C +

1 的?案数,即将 C +

1 个相同的球分为

3 部分.考虑把球排成?条线,根据植树问题知道球之间有 C 个位置.在2个位 置插?隔板即可分为

3 部分,?案数就是?项式系数 ( C

2 ) = C(C ? 1)

2 (2) 时间复杂度 O(1). Problem B Chrystal ?王 难度

1 关键字 最?公约数, Euclid 算法 题解 很显然答案就是 a 和b的最?公约数,? Euclid 算法求出来即可.不知 道暴?枚举能不能过. 时间复杂度 Euclid 算法的时间复杂度为 O(log a).

1 Problem C Middle Problem 难度

2 关键字 ?分查找,前缀和 题解 ?先可以看出小于中位数的数(前?n/2? 小的数)都没?.?分答案 x, 判断能否把中位数提?到x.要把中位数提?到x,就要把中位数和?它?且小 于x的数都增加到 x.把a预先排序,?分查找到第?个?于等于 x 的数 at, 要增加的数就是 k ∈ [?n/2?, t) 中的所有数,有t??n/2? 个.增加它们到 x 需 要的糖果数量就是 t?1 ∑ k=?n/2? (x ? ak) = (t ? ?n/2?)x ? t?1 ∑ k=?n/2? ak = (t ? ?n/2?)x ? (St ? S?n/2?) (3) S 是预先计算的前缀和: Si = i?1 ∑ k=0 ak = Si?1 + ai?1 (4) 时间复杂度 排序时间复杂度为 O(n log n), 求前缀和 S 时间复杂度为 O(n), ? 分答案次数的上界为 log(m+max ai), ?分查找 at 的时间复杂度为 O(log n), 总计O((n + log(m + max ai)) log n). Problem D XXX 的最初之兽 难度

2 关键字 找规律 题解 打表找规律知道,x >

100 时答案就是 x ? 10,否则是 91. 时间复杂度 O(1). Problem E 汀?师数?国 难度

3 关键字 动态规划

2 题解 令f(i, j) 表?得到 i 个小杰,j 个小国需要的最少操作数,能够写出状态 转移?程f(i, j) = min { f(i, j ? i) +

1 j > i f(k, j/2) +

1 j = 2i, k = 1, 2, 3, ・ ・ ・ (5) 注意到 f(i, j) 只依赖于 j < j1 的f(i1, j1),满??后效性,可以?动态规划解 决.直接按上式写时间复杂度是三次的,维护?下最小值 g(j) = min i f(i, j) (6) 即可将时间复杂度减小到?次. 时间复杂度 O(n2 ). Problem F XXX 与第九兽 难度

3 关键字 矩阵乘法,快速幂 OEIS A005251 题解 令fi 表??度为 i,最后?个是妖精的队列数(我们认为空队列的最后? 个是妖精,即f0 = 1) ,gi 表??度为 i ,最后?个是兽的队列数.由于任何队 列后?都可以加?个妖精,有fi = fi?1 + gi?1 (7) 由于任何最后?个是妖精的队列后?可以加

2 个或以上的兽,有gi = fi?2 + fi?3 f1 (8) 令S为g的前缀和: Si = ∑ k