A. 纪元流星雨
按照题意模拟即可。
为了便于计算,可将这个人出生的那一年设为坐标原点,计算 [0,L][0,L][0,L] 内出现多少次流星雨即可。
不难计算出在正半轴时第一次流星雨发生时间为 (E+B)%50(E+B)\% 50(E+B)%50 ,流星雨出现数量则为 (L−E)/50(L-E)/50(L−E)/50 ,并特判一下第一次流星雨是否出现即可。
时间复杂度 O(1)O(1)O(1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
B.MARCONCATENATION
按照题意模拟即可。
* 如果字符串以 o 开头,删除该 o 并在开头加上 MARCO。
* 如果字符串以 co 开头,删除 co 并在开头加上 MARCO。
* 如果字符串以 rco 开头,删除 rco 并在开头加上 MARCO。
* 如果字符串以 arco 开头,删除 arco 并在开头加上 MARCO。
* 如果字符串以 marco 开头,只需将前 5 个字母大写。
* 否则,什么也不做,保持字符串不变。
判断从 1 到 5 每个长度的前缀是否以规定子串开头,并进行修改。
时间复杂度O(1)O(1)O(1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C.TNT接力
二分找到第一个没有被打上标记的下标然后进行修改。
首先跳跃一定比走路更优,跳远可以向前走 [1,m+1][1,m + 1][1,m+1] 的任意一步,而走路只能向前走一步。
贪心的考虑,肯定是从每个点起跳的时候跳的越远越好,显然从一个点起跳时跳的远的情况肯定比跳的近的情况更优。
同时肯定要先从离起点近的点开始起跳,因为离起点近的点所跳的区域一定能被离起点远的点所到达或者经过。
简易的证明如下:
记离起点近的点所能调到的最远点为 PPP ,离原点近的点所能跳的最远点为 QQQ 。
* 如果P=QP = QP=Q,由于除起点和终点外每个点最多只能经过一次,那么二者选哪个点对答案的贡献一样。
* 如果P<QP < QP<Q,那么显然离起点近的点跳到 PPP 点,离起点远的点跳到 QQQ 点更优。如果离起点远的点跳到了PPP点,离起点近的点可能没有位置继续向前跳,此时答案一定不可能比前一种情况大。
因此我们可以得到一个贪心策略,从111到nnn开始遍历每一个起跳点,对于每一个起跳点去找到它所能到达的最远点,此时结果一定最优。
把所有能被跳的点存到一个集合里面,每次从一个点起跳的时候二分找到这个点能够跳到的最远距离,并将这个值从集合里面删去,用set 即可 log(n)\log(n)log(n) 时间完成这些操作。
具体实现见代码,时间复杂度O(nlog(n))O(n\log(n))O(nlog(n))
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
D.小丑牌
大模拟题,按照题意模拟仔细点写,没什么好说的。
注意一下如果有一个牌型符合上述多条描述,请输出符合描述的牌型中在规则中最后描述的牌型。
时间复杂度O(1)O(1)O(1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
E. VERTEX VERSE
又是一道大模拟题。
开一个三维数组,第一维表示横坐标,第二维表示纵坐标,第三位表示这个点上下左右的连线情况。
数组元素代表含义如图所示:
每次读入两个点后这两个点会连成一条线段,对这两个点分别打上标记,同时判断这条线段是否与其他线段围成了新的正方形,每次连线至多会形成两个正方形,如果新的连线与 xxx 轴平行则判断上下是否形成了新的正方形,如果新的连线与 yyy 轴平行则判断左右是否形成的新的正方形即可。
由于每次新连线所形成的正方形一定不会是之前的正方形,所以并不需要额外添加标记判断。
代码细节较多,时间复杂度 O(n)O(n)O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
F. 最优政府大楼选址-2
考察排序。
首先思考没有 ϵ\epsilonϵ 的限制,即所有的 ϵ\epsilonϵ 都为 1 的情况,此时大楼选址的坐标为 (x方向上的坐标中位数,y方向上的坐标中位数)(x方向上的坐标中位数,y方向上的坐标中位数)(x方向上的坐标中位数,y方向上的坐标中位数)
下面以求证明 xxx 方向的大楼选址坐标为例,yyy 方向的求法类似:
假设对 nnn 个居民点的xxx坐标按大小排序后为: x1,x2,x3,…,xnx_1,x_2,x_3,\dots,x_nx1 ,x2 ,x3 ,…,xn
对 x1,xnx_1,x_nx1 ,xn 两点来说,最近的点肯定在 x1,xnx_1,x_nx1 ,xn 之间 , 可以为二者之间的任意值,且跟两点的距离和为 xn−x1x_n-x_1xn −x1 ;
对 x2,xn−1x_2,x_{n-1}x2 ,xn−1 两点来说,最近的点肯定在 x2,xn−1x_2,x_{n-1}x2 ,xn−1 之间, 可以为二者之间的任意值,且跟两点的距离和为 xn−1−x2x_{n-1}-x_2xn−1 −x2 ;
⋯\cdots⋯
所以若 nnn 为奇数,则邮局的 xxx 坐标取最中间的值时最小;
所以若 nnn 为偶数,则邮局的 xxx 坐标可以取最中间两个值的之间的任意值;
注意到 ϵ\epsilonϵ 的值为整数且不超过10,因此我们可以把 ϵ\epsilonϵ 看成在这个点的大楼个数,再使用上述的方法求解。
时间复杂度O(nlog(n))O(n\log(n))O(nlog(n)),复杂度瓶颈在排序上面
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
G. 乌龟养殖场
状态压缩 dp 板子题。
注意到对于100%的数据,保证 1≤M≤101≤M≤101≤M≤10 ,因此想到采用状态压缩 dp 求解。
如果你不知道状态压缩 dp 是什么,可以点这里:状压 DP - OI Wiki。
以 f[i][j]f[i][j]f[i][j] 表示在前 iii 行中在第 jjj 个状态下的最大方案数
易得:
f[i][j]=(f[i][j]+f[i−1][k]) mod pf[i][j]=(f[i][j]+f[i−1][k])\ \text {mod}\ p \\ f[i][j]=(f[i][j]+f[i−1][k]) mod p
其中 p=1e9+7p=1\mathrm{e}9 + 7p=1e9+7,jjj 是第 iii 行的状态,kkk 是第 i−1i−1i−1 行的状态
每次转移的时候记得判断一下两行的状态是否合法,最终答案即为 f[n+1][0]−1f[n + 1][0] - 1f[n+1][0]−1,减一是因为题目要求不能全部乌龟都不放,所以要去除掉全部都不放这种状态 。
具体实现见代码,时间复杂度 O(nSm2)O(n{S_m}^2)O(nSm 2),其中 Sm{S_m}Sm 表示宽为 mmm 的合法状态数
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
H. 数据中心能耗分析
线段树板子题。
如果你不知道线段树是什么,可以点这里:线段树 - OI Wik。
注意到
(Ai+k)3=Ai3+3⋅Ai2⋅k+3⋅Ai⋅k2+k3(Ai+k)2=Ai2+2⋅Ai⋅k+k2(A_i + k)^3 = {A_i}^3 + 3 \cdot {A_i}^2 \cdot k + 3 \cdot A_i \cdot k ^ 2 + k ^ 3 \\ (A_i + k)^2 = {A_i}^2 +2 \cdot A_i \cdot k + k ^ 2 (Ai +k)3=Ai 3+3⋅Ai 2⋅k+3⋅Ai ⋅k2+k3(Ai +k)2=Ai 2+2⋅Ai ⋅k+k2
因此我们若需要维护一段序列的立方和,同时也需要维护一段序列的平方和和区间和
注意懒标记下传的时候先更新区间的立方和,再更新区间的平方和,最后更新区间和
具体实现见代码,注意 int 可能会溢出,记得开 long long,时间复杂度O(nlog(n))O(n\log(n))O(nlog(n))
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------