@[TOC]([CF复盘] Codeforces Round 863 (Div. 3) 20230404 )
一、本周周赛总结
-
做到E，但DE都TLE，很难受。
-
A 贪心。
-
B 坐标运算。
-
C 贪心构造。
-
D 分治DFS。
-
E 九进制模拟。
二、 A. Insert Digit
链接: A. Insert Digit
1. 题目描述
2. 思路分析
贪心，从左找到第一个小于d的数字，插到它前边。
3. 代码实现
# Problem: A. Insert Digit
# Contest: Codeforces - Codeforces Round 863 (Div. 3)
# URL: https://codeforces.com/contest/1811/problem/A
# Memory Limit: 256 MB
# Time Limit: 2000 ms
import sys
RI = lambda: map(int, sys.stdin.buffer.readline().split())
RS = lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST = lambda: list(RI())
DEBUG = lambda *x: sys.stderr.write(f'{str(x)}\n')
MOD = 10 ** 9 + 7
PROBLEM = """https://codeforces.com/contest/1811/problem/A
输入t(<=1e4)表示t组数据，每组数据：
输入数字n<=2e5和d(0<=d<=9)，然后输入一个n位的数字x。
你可以把d插入到x的任意位置，包括首尾。使得到的数尽可能大。
"""
"""贪心，从左找到第一个小于d的数字，插到它前边"""
# ms
def solve():
n, d = RI()
a, = RS()
a = list(a)
for i, c in enumerate(a):
if d > int(c):
a.insert(i, str(d))
break
else:
a.append(str(d))
print(*a, sep='')
if __name__ == '__main__':
t, = RI()
for _ in range(t):
solve()
三、B. Conveyor Belts
链接: B. Conveyor Belts
1. 题目描述
2. 思路分析
其实就是计算两个传送带的距离，设计一下传送带编号即可：越靠近外边编号越小，那么尝试x到上下边界最小值和y到上下边界最小值就是传送带编号
3. 代码实现
PROBLEM = """https://codeforces.com/contest/1811/problem/B
输入t(<=2e5)表示t组数据，每组数据：
输入n(偶数且<=1e9),x1,x2,y1,y2 (均<=n)。
其中n表示一个边长n的正放心栅格，栅格是由n//2个旋转运行的传送带组成。
你可以花费1点能量跳到相邻传送带，问从x1y1到x2y2最少花费几能量。
"""
"""其实就是计算两个传送带的距离，设计一下传送带编号即可：越靠近外边编号越小，那么尝试x到上下边界最小值和y到上下边界最小值就是传送带编号"""
# ms
def solve():
n, x1, y1, x2, y2 = RI()
d1 = min(x1, n - x1 + 1, y1, n - y1 + 1)
d2 = min(x2, n - x2 + 1, y2, n - y2 + 1)
print(abs(d1 - d2))
if __name__ == '__main__':
t, = RI()
for _ in range(t):
solve()
四、C. Restore the Array
链接: C. Restore the Array
1. 题目描述
2. 思路分析
- 最左边的位置显然是最不受影响的，让a[0]=b[0]，那么a[1]就可以是0~b[0]之间任意数，我们希望它空出来不要影响后一个数b[1]，因此填0最佳。
- 对于b[i]如果前边的a[i]已经填了一个b[i]则他可以不填，取前边的数；如果前边没填数据，且b[i]比前边那个数小，则可以填到a[i]上；否则为了不影响前边只能填到后边的位置。
3. 代码实现
PROBLEM = """https://codeforces.com/contest/1811/problem/C
输入t(<=1e4)表示t组数据，每组数据：
输入n(<=2e5)和长为n-1的数组b(bi<=1e9)。
构造一个长为n的数组a，使对于所有i<n-1,max(a[i],a[i+1])=b[i]
你可以输出任意一个合法答案。
"""
"""贪心构造
最左边的位置显然是最不受影响的，让a[0]=b[0]，那么a[1]就可以是0~b[0]之间任意数，我们希望它空出来不要影响后一个数b[1]，因此填0最佳。
对于b[i]如果前边的a[i]已经填了一个b[i]则他可以不填，取前边的数；如果前边没填数据，且b[i]比前边那个数小，则可以填到a[i]上；否则为了不影响前边只能填到后边的位置。
"""
# ms
def solve():
n, = RI()
b = RILST()
a = [0] * n
a[0] = b[0]
for i in range(1, n - 1):
if b[i] <= b[i - 1] and a[i] == 0:
a[i] = b[i]
elif a[i] == b[i]:
pass
else:
a[i + 1] = b[i]
print(*a)
# c = []
# for i in range(n-1):
# c.append(max(a[i],a[i+1]))
# print(b == c)
if __name__ == '__main__':
t, = RI()
for _ in range(t):
solve()
五、D. Umka and a Long Flight
链接: D. Umka and a Long Flight
1. 题目描述
2. 思路分析
- 直接dfs分治，注意加记忆化过不了。
- 显然n=1是能过的，看case1。
- 剩余情况画一下图，尝试把矩形的长边按照宽的位置切一刀，那么可以选左边或者右边切出来；这样会变成一个正方形和一个更小的n-1号fib矩形；
- 目标位置必须在矩形上才可以。否则返回false。
- 注意t<=2e5,因此组内需要保证复杂度<=500,加记忆可能导致内存问题，巨卡。不加记忆化由于n一直-1，因此最多是44。
3. 代码实现
PROBLEM = """https://codeforces.com/contest/1811/problem/D
定义斐波那契数列为fib=[1,1,2,3...]，定义第n个fib矩形的高是fib[n],宽fib[n+1]的长方形。
输入t(<=2e5)表示t组数据，每组数据：
输入n(<=44), x, y (为第n个fib矩形内的合法坐标点)，
你需要判断能否把矩形切分成恰好n+1个正方形方格，且同时满足3个条件：
1. (x,y)位置必须单独切分成1X1的小方格。
2. 至少有一对方块的边长相同。
3. 每个方格的边长都是斐波那契数。
"""
"""
直接dfs分治，注意加记忆化过不了。
显然n=1是能过的，看case1。
剩余情况画一下图，尝试把矩形的长边按照宽的位置切一刀，那么可以选左边或者右边切出来；这样会变成一个正方形和一个更小的n-1号fib矩形；
目标位置必须在矩形上才可以。否则返回false。
注意t<=2e5,因此组内需要保证复杂度<=500,加记忆可能导致内存问题，巨卡。不加记忆化由于n一直-1，因此最多是44。
当然可以写while写法，直接迭代n,x,y。
"""
fib = [1, 1]
for _ in range(44):
fib.append(fib[-1] + fib[-2])
# 1309 ms
def solve():
n, x, y = RI()
# @lru_cache
def f(n, x, y):
if n == 1:
return True
h, w = fib[n], fib[n + 1]
x = min(x, h - x + 1)
if y > h:
return f(n - 1, y - h, x)
if y <= w - h:
return f(n - 1, y, x)
return False
ans = f(n, x, y)
# f.cache_clear()
if ans:
return 'YES'
else:
return 'NO'
if __name__ == '__main__':
t, = RI()
ans = []
for _ in range(t):
ans.append(solve())
# f.cache_clear()
print(*ans, sep='\n')
六、E. Living Sequence
链接: E. Living Sequence
1. 题目描述
2. 思路分析
本来我写了个数位DP+二分。但是过不了，我以为和D是一样的卡记忆化，其实不是。
- 由于t=1e4,数位dp状态数是位数1422，转移要10，再加一个log可能是50，组内复杂度就是2e5，肯定是过不了的。
- 考虑9进制：把所有数字都去掉4的话，那么其实每位只有9个选项，而且大小顺序是不变的。从1开始数的话，找出这个9进制的k即可，然后把每一位换成对应的数字。
- 直接用连除拆解每一位。
3. 代码实现
PROBLEM = """https://codeforces.com/contest/1811/problem/E
输入t(t<=1e4)代表t组数据，每组数据：
输入k。
从1开始向后的自然数中，去除所有带4的数字，问第k个数字是几（注意k从1开始计数）
"""
"""本来我写了个数位DP+二分。但是过不了，我以为和D是一样的卡记忆化，其实不是。
由于t=1e4,数位dp状态数是位数14*2*2，转移要10，再加一个log可能是50，组内复杂度就是2e5，肯定是过不了的。
---
考虑9进制：把所有数字都去掉4的话，那么其实每位只有9个选项，而且大小顺序是不变的。从1开始数的话，找出这个9进制的k即可，然后把每一位换成对应的数字。
直接用连除拆解每一位。
"""
def my_bisect_left(a, x, lo=None, hi=None, key=None):
"""
由于3.10才能用key参数，因此自己实现一个。
:param a: 需要二分的数据
:param x: 查找的值
:param lo: 左边界
:param hi: 右边界(闭区间)
:param key: 数组a中的值会依次执行key方法，
:return: 第一个大于等于x的下标位置
"""
if not lo:
lo = 0
if not hi:
hi = len(a) - 1
else:
hi = min(hi, len(a) - 1)
size = hi - lo + 1
if not key:
key = lambda _x: _x
while size:
half = size >> 1
mid = lo + half
if key(a[mid]) < x:
lo = mid + 1
size = size - half - 1
else:
size = half
return lo
# tle ms
def solve1():
# n, = RI()
k, = RI()
def ok(x):
s = str(x)
n = len(s)
# mp = {}
@lru_cache
def f(i, is_limit, is_num):
if i == n:
return int(is_num)
# if (i, is_limit, is_num) in mp:
# return mp[i, is_limit, is_num]
ans = 0
if not is_num:
ans += f(i + 1, False, False)
up = int(s[i]) if is_limit else 9
down = 0 if is_num else 1
for j in range(down, up + 1):
if j != 4:
ans += f(i + 1, is_limit and j == up, True)
# mp[i, is_limit, is_num] = ans
return ans
ans = f(0, True, False)
# f.cache_clear()
return ans
print(my_bisect_left(range(10 ** 15), k, key=ok))
# 9进制 140 ms
def solve():
# n, = RI()
k, = RI()
s = '012356789'
ans = []
while k:
ans.append(s[k % 9])
k //= 9
print(*ans[::-1], sep='')
if __name__ == '__main__':
t, = RI()
for _ in range(t):
solve()
![[Java Web]Session | 一文详细介绍会话跟踪技术中的Session](https://img-blog.csdnimg.cn/32feed7cf8c14e8c9f6038739c91568e.png)
