深圳网站建设招聘,中国建设信息网站,wordpress强大吗,城乡建设厅官方网站办事大厅[acwing周赛复盘] 第 91 场周赛20230218 一、本周周赛总结二、 4861. 构造数列1. 题目描述2. 思路分析3. 代码实现三、4862. 浇花1. 题目描述2. 思路分析3. 代码实现四、4863. 构造新矩阵1. 题目描述2. 思路分析3. 代码实现六、参考链接一、本周周赛总结
这周挺难的。T1 贪心分…
[acwing周赛复盘] 第 91 场周赛20230218 一、本周周赛总结二、 4861. 构造数列1. 题目描述2. 思路分析3. 代码实现三、4862. 浇花1. 题目描述2. 思路分析3. 代码实现四、4863. 构造新矩阵1. 题目描述2. 思路分析3. 代码实现六、参考链接一、本周周赛总结
这周挺难的。T1 贪心分解数位。T2 差分 / 排序模拟。T3 二分思维。 二、 4861. 构造数列
链接: 4861. 构造数列
1. 题目描述 2. 思路分析
想了半天
其实就是贪心的处理每一位拆出来即可。
3. 代码实现
# Problem: 构造数列
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4864/
# Memory Limit: 256 MB
# Time Limit: 1000 msimport sys
import bisect
import random
import io, os
from bisect import *
from collections import *
from contextlib import redirect_stdout
from itertools import *
from array import *
from functools import lru_cache
from types import GeneratorType
from heapq import *
from math import sqrt, gcd, inf
if sys.version 3.8: # ACW没有combfrom math import combRI 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)# ms
def solve():n, RI()ans []base 1for i,v in enumerate(str(n)[::-1]):if v ! 0:ans.append(int(v)*base)base * 10print(len(ans))print(*ans)if __name__ __main__:t, RI()for _ in range(t):solve()三、4862. 浇花
链接: 4862. 浇花
1. 题目描述 2. 思路分析
方法1排序模拟由于数据是有序的而且不允许重复因此直接判断开始时间和上个元素的结束时间是否相邻即可。数量就最后暴力。 方法2差分出题人的本意是让差分做其实更好。预处理差分数组后遍历还原数组应该每个值都是1,否则就返回失败。
3. 代码实现
# Problem: 浇花
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4865/
# Memory Limit: 256 MB
# Time Limit: 1000 msimport sys
import bisect
import random
import io, os
from bisect import *
from collections import *
from contextlib import redirect_stdout
from itertools import *
from array import *
from functools import lru_cache
from types import GeneratorType
from heapq import *
from math import sqrt, gcd, infif sys.version 3.8: # ACW没有combfrom math import combRI 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)# 差分 ms
def solve():n, m RI()a [0] * (n 2)for _ in range(m):x, y RI()a[x] 1a[y 1] - 1s 0for i in range(1,n1):s a[i]if s ! 1:return print(i,s)print(OK)# ms
def solve1():n, m RI()a []for _ in range(m):a.append(RILST())a.sort()i 0ans -1for x, y in a:if x i:ans xbreakif x i 1:ans i 1breaki yelse:if i n:ans i 1if ans -1:print(OK)else:s sum(x ans y for x, y in a)print(ans, s)if __name__ __main__:solve()四、4863. 构造新矩阵
链接: 4863. 构造新矩阵
1. 题目描述 2. 思路分析
二分答案但是judge函数需要一定思维。考试时首交提交了个比较长的代码复杂度看起来过不了其实能过哈哈已注释。 简单的方法 判断每列都有满足L的数字同时存在一行有至少两个L的数字。这是因为只要每列(共n列)都有满足的数字则起码可以选出n行来满足需求。那么只要存在某行拥有2个L的数就可以少取一行变成n-1行。其它情况则不满足。 然后二分即可由于L越大越不可能满足因此是单调递减的。
3. 代码实现
# Problem: 构造新矩阵
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4866/
# Memory Limit: 256 MB
# Time Limit: 1000 msimport sys
import bisect
import random
import io, os
from bisect import *
from collections import *
from contextlib import redirect_stdout
from itertools import *
from array import *
from functools import lru_cache
from types import GeneratorType
from heapq import *
from math import sqrt, gcd, infif sys.version 3.8: # ACW没有combfrom math import combRI 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 7def my_bisect_left(a, x, loNone, hiNone, keyNone):由于3.10才能用key参数因此自己实现一个。:param a: 需要二分的数据:param x: 查找的值:param lo: 左边界:param hi: 右边界(闭区间):param key: 数组a中的值会依次执行key方法:return: 第一个大于等于x的下标位置if not lo:lo 0if not hi:hi len(a) - 1else:hi min(hi, len(a) - 1)size hi - lo 1if not key:key lambda _x: _xwhile size:half size 1mid lo halfif key(a[mid]) x:lo mid 1size size - half - 1else:size halfreturn lo# 5148 ms
def solve():RS()m, n RI()g []for _ in range(m):g.append(RILST())# 首先判断若每列都有满足x的数则起码可以选不超过n行出来满足条件。# 这是只要存在一行有用2个x得数就可以少选一行即n-1行。# 否则就不行def ok(x):if all(max(col) x for col in zip(*g)) and any(sum(v x for v in row) 2 for row in g):return Falsereturn Trueprint(my_bisect_left(range(10 ** 10), True, keyok) - 1)# 4887 ms
def solve1():RS()m, n RI()g []for _ in range(m):g.append(RILST())# 相当于给m个[1,0,1,0]布条重叠放其中1是不透明的。# 问最少几根布条叠在一起可以全部不透明。# 或者说给m个n位的二进制数问最少几个数或到一起可以全1。# 贪心考虑优先选1最多的那个数。# 选了的1从剩余数字每个中删掉对剩余数字依然有1的数字重新按照1数量排序。# 直到选完了或者数字没有了。这时如果没选完就失败。# 用set来储存每个数字1的位置按len排序。每次排序复杂度log(m)# 这里的复杂度看似很高但其实每位上的1最多从每个数中删去1次复杂度是m*n的。def ok(x):p []for row in g:s {i for i, v in enumerate(row) if v x}if s:p.append(s)if not p:return Truep.sort(keylen)c 0t set(range(n))while t and p:c 1if c n - 1:return Trues p.pop()if not s:breakt - sq []for v in p:v - sif v:q.append(v)p qp.sort(keylen)if t:return Truereturn Falseprint(my_bisect_left(range(10 ** 10), True, keyok) - 1)if __name__ __main__:t, RI()for _ in range(t):solve()六、参考链接
无
