2017 FDU-ICPC 程序设计校赛现场赛解题报告

作者:root     创建时间:2017年12月11日 15:12     最后更新:2017年12月11日 15:21

A - Lucky Number

题目大意:

给一个正整数 n,求不超过 n 的数码和最大的正整数,输出该数码和。

简要题解:

最大数码和有两种情况:

1、n 本身的数码和

2、设 n 是 a 位数,最高位为 w,则 (w-1)+9(a-1) 也是一种可能的情况

时间复杂度:O(T logn)

标程:http://paste.ubuntu.com/26162057/


B - Jumping

题目大意:

给定一个 n*m 的矩形地图和一个跳跃步数 s,每次可以从一个格子 (x,y) 跳到 (x+s,y),(x-s,y),(x,y+s),(x,y-s) 这四个格子(如果没有出界)。现在可以选择一个格子作为起点,问有多少个初始起点可以使得能到达的不同格子的数量最大。

简要题解:

首先 (1,1) 肯定是可选起点之一。

考虑 (1,1) 能跳到的格子数,即 ceil(n/s)*ceil(m/s),ceil()表示向上取整。

再考虑有多少个满足条件的,不在同一个连通分支的起点:((n-1)%s+1)*((m-1)%s+1)。

所以最后答案是:((n-1)%s+1)*((m-1)%s+1)*ceil(n/s)*ceil(m/s)。注意要用 long long。

时间复杂度:O(T)。

标程:http://paste.ubuntu.com/26162062/


C - Good Number

题目大意:

给一个正整数 s,要找到最小的正整数 n,使得可以在 1~n 这 n 个整数前添加“+”号或“-”号后,式子的值恰好等于s。

简要题解:

如果一个 n 满足可以在 1~n 这 n 个整数前添加“+”号或“-”号后,式子的值恰好为 s,则需要满足:

1、1+2+...+n >= s,即 n(n-1) >= 2s

2、n(n-1) 与 s 同奇偶

所以就只要令 ans 初始为 sqrt(2s),然后每次判断当前 ans 是否合法,如果合法则输出答案,否则令 ans++ 之后继续判断。可以保证这样寻找答案的次数是常数级别的。

时间复杂度:O(T)。

标程:http://paste.ubuntu.com/26162064/


D - Kamui

题目大意:

给一个 1~n 的排列 A,再给定一个长为 n 的 W 数组。现有一个初始排列 P,即 Pi=i,每次可以排列中的两个元素 x,y 进行交换,交换的代价是 W_x+W_y,问把 P 进行若干次交换操作后变成 A 的最小总代价。

简要题解:

我们可以找出若干个置换环。对于每个置换环 [a1,a2,...,am],有两种还原方式:

1、在环中选择一个 W 值最小的元素 u,然后让该元素沿着环依次交换,总代价为 W_u * (m-2)+W_a1+W_a2+...+W_am;

2、在环外选一个 W 值最小的元素 v,先将其与环内 W 值最小元素 u 交换,使 v 加进环内,然后再沿着环依次交换,总代价为 W_v*(m+1)+W_u+W_a1+W_a2+...+W_am。

每个置换环都单独考虑,并取总代价最小的方式进行还原即可。

时间复杂度:O(Tn)。

标程:http://paste.ubuntu.com/26162065/


E - Palindromic Cut

题目大意:

给一个字符串 s,现在要用这个串中出现的所有字符来凑出若干长度相同的回文串。输出使串的数量最少的一种方案。

简要题解:

首先统计一下有多少种出现次数为奇数的字母,记种数为 cnt,那么串的个数肯定不少于 cnt,因为一个回文串里最多只有一种字母能出现奇数次。

对于所有字母都出现了偶数次的情况,我们进行特判。

此后我们令最后回文串的数量为 x,只有当 x >= cnt, x 是 s 的约数,并且 s/x 为奇数时,这个 x 才是可行的。所以就让 x 从 cnt 开始枚举,直到满足条件为止。

最后我们就只要构造出 x 个回文串就可以了。这个首先把出现次数为奇数的字母都选一个出来作为回文串的中心,不够的话就随便再选一些字母作为中心点(这里可以重复选),并保证选完之后所有字母就都是偶数个,此后就把字母两个两个地套在串的外面,这样就构造出了 x 个长度相同的回文串。

时间复杂度:O(T|s|)。

标程:http://paste.ubuntu.com/26162067/


F - Lucky Permutation

题目大意:

给两个正整数n,k,要找到一个 1~n 的排列,使得所有长度为 k 的子段的数字和都是合数。如果有解则输出任意一组,否则输出”-1”(不含引号)。

简要题解:

当 k = 1:显然无解(1就不是合数)

当 k = 2:

   n <= 4 时无解(必然有相邻两数和为奇数,而这个奇数 <= 7,不可能是合数)

   n >= 5 时,可构造排列:1,3,...,2k+1,5,4,2,6,...,2m

当 k >= 3:1,2,3,...,n 就是一个合法解,大家可以想一想为什么

时间复杂度:O(Tn)。

标程:http://paste.ubuntu.com/26162068/


G - Ndb

题目大意:

给定 n,L,R,问有多少个大小为 n 的数的集合 S,满足:

1、S 中所有数都在 [L,R] 区间内。

2、把 S 中的数从大到小排列之后构成的数列是一个等比数列。

简要题解:

如果 n=1,那么答案是 R-L+1。

如果 n=2,那么答案是 (R-L+1)(R-L)/2。

如果 n>=30,那么答案是 0。

特判掉上面的情况后,首先可以令 lim = pow(R,1/(n-1)),然后枚举不超过 lim 的整数对 (u,v)(1<=u<v<=lim,gcd(u,v)=1),那么 u^(n-1),u^(n-2)v,...,uv^(n-2),v^(n-1) 就是一个长为 n 的单位等比数列。然后我们可以再把这个单位等比数列上的所有数都乘以一个常数 k,得到的数列还是等比数列。此时我们可以求出可行的 k 的取值范围。最后把所有的数对 (u,v) 的可行的 k 的数量累加起来就是答案了。

时间复杂度:O(TR)。

标程:http://paste.ubuntu.com/26162070/


H - Station

题目大意:

在二维平面直角坐标系上有n条直线航线的信息 Li: Aix+Biy=Ci。已知这 n 条航线两两互不平行且均与 X 轴和 Y 轴相交。记这 n 条航线相交所产生的 n(n-1)/2 个交点为P1,P2,...,Pn(n-1)/2 ,为了更好地管理这些航线,现要求在二维平面坐标上选择一个位置 Q,使得 d(Q,P1)+d(Q,P2)+...+d(Q,Pn(n-1)/2) 最小。其中 d(A,B) = |xA-xB|+|yA-yB|。如有多个满足条件的位置,输出 x 坐标最小的,若有多个 x 坐标最小的位置,输出其中 y 坐标最小的位置。

简要题解:

Q 点的 X 坐标和 Y 坐标可以分开处理,那么我们现在考虑求 Q 点的 X 坐标。首先可以得到:只有当 Q 点的 X 坐标是 n(n-1)/2 个交点的 X 坐标中位数或处在中位数区域时,才是一个满足条件的坐标。

基于以上结论,我们可以对这个 X 坐标进行二分,关键在于如何求解有多少个交点的 X 坐标在当前二分的 X 坐标之前。考虑以下做法:先令 x=-1e9 或者其他足够小的值,并把所有直线按在 x=-1e9 时的 Y 坐标排序,记为顺序 A,再令 x 为当前二分的坐标,然后再把所有直线按照此时的 Y 坐标排序,若坐标相同,则令在 A 顺序中靠后的直线在新的顺序中靠前,得到顺序 B。那么两个 B 关于 A 的逆序对个数就是 X 坐标在当前二分坐标之前的交点个数。因为每产生一个逆序对就对应着一个新出现的交点。逆序对个数可以用树状数组或者是归并排序来求解。

这样我们就可以通过二分答案来找到 Q 点的 X 坐标了,Y 坐标也是一样的求法。

设坐标范围为 w,则时间复杂度:O(Tn logn logw)。

标程:http://paste.ubuntu.com/26162072/