Codeforces Round 863 (Div 3)总结
文章目录
- A
- B
- C
- F
文章首发于我的个人博客：欢迎大佬们来逛逛
A
题目描述：在一个数字序列中的任意位置插入一个给定的数字，最后要使得这个整数序列所表示的值尽可能大。
很容易想出来，如果我们给定的数字是 5，并且序列的为 12345，则5一定插入到开头位置；如果序列为 65123，则5一定插入到第二个位置；如果为98765，则5一定插入到最后。
因此寻找第一个 a[i]<b 的位置即为插入的值。
B
两个点在传送带上移动，求得两个点相隔几个传送带。
可以发现，每个在一条传送带上的物品一定会随着传送带移动，并且经过左上角的点，同时这个点的坐标可以通过以下公式来维护：
m i n ( x , y , n + 1 − x , n + 1 − y ) min(x,y,n+1-x,n+1-y) min(x,y,n+1−x,n+1−y)
例如：
- n=2,(2,2)：min(2,2,1,1) = 1
- n=4,(1,4)：min(1,4,4,1) = 1
- (3,3)：min(3,3,2,2) = 2
因此求出左上角的两个位置后，取这两个点的差的绝对值即可。
C
重塑序列，一个序列 b 可以表示为 b[i]=max(a[i],a[i+1])，则告诉你这个 b 序列，让你反推出原始序列最有可能的值。
假设原始序列为 a，则：
- a[0] = b[0]
- a[1] = min(b[i],b[i-2])
- a[n-1] = b[n-2]
反过来表示即可
F
如果一个数字序列不包含任何的4，例如：0，1，2，3，5，6，7，8，9 …. 13，15 … 23，25 … 那么表示出第 x 个数字在这种情况下对应的数字是几？
数字的十进制用九进制表示：
0，1，2，3，4，5，6，7，8；
10，11，12，13，14，15，16，17，18 …
如果我们把存在4的数字之后（包括这位数字）的所有数字+1，则会变成这种：
0，1，2，5，6，7，8，9；
11，12，13，15，16，17，18，19 …
因此这就符合我们的题意。
因此我们就可以把给定的 x 转换为九进制，然后把每一位的值通过映射转换即可。