[acwing周赛复盘] 第 60 场周赛20230204补
-
- 一、本周周赛总结
- 二、4803. 满足的数
-
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 三、4804. 构造矩阵
-
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 四、4805. 加减乘
-
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 六、参考链接
一、本周周赛总结
- 晚上去吃牛蛙了，回来补题。
- T1 模拟。
- T2 矩阵模拟。
- T3 DP。
二、4803. 满足的数
链接: 4803. 满足的数
1. 题目描述
2. 思路分析
- 枚举即可。
3. 代码实现
# Problem: 满足的数
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4806/
# Memory Limit: 256 MB
# Time Limit: 1000 ms
import 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没有comb
from math import comb
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
# ms
def solve():
n, = RI()
a = RILST()
s = sum(a)
ans = 0
for x in range(1, 6):
if (s + x) % (n + 1) != 1:
ans += 1
print(ans)
if __name__ == '__main__':
solve()
三、4804. 构造矩阵
链接: 4804. 构造矩阵
1. 题目描述
2. 思路分析
- 这种题一般是分别讨论行列。
- 记录一下都哪些行和列必须为0，构造出来这样的矩阵，其余位置都记1就是答案。
- 构造过程：初始化一个全1矩阵，然后枚举记录的行列，置1。复杂度n*m。
- 注意记录完后，需要在遍历一次矩阵的1，查看这个数对应的行列是否都是0。另外如果行=m/列=n，则全得是0，不能有1。
3. 代码实现
# Problem: 构造矩阵
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4807/
# Memory Limit: 256 MB
# Time Limit: 1000 ms
import 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没有comb
from math import comb
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
# ms
def solve():
m, n = RI()
b = []
row, col = set(), set()
for i in range(m):
b.append(RILST())
for j, v in enumerate(b[-1]):
if v == 0:
row.add(i)
col.add(j)
for i, r in enumerate(b):
for j, v in enumerate(r):
if v:
if i in row and j in col:
return print('NO')
if len(row) == m or len(col) == n:
return print('NO')
a = [[1]*n for _ in range(m)]
for i in row:
a[i] = [0]*n
for j in col:
for i in range(m):
a[i][j] = 0
print('YES')
for r in a:
print(*r)
if __name__ == '__main__':
solve()
四、4805. 加减乘
链接: 4805. 加减乘
1. 题目描述
2. 思路分析
DP.
- f[i]要么从i-1转移,代价x。
- 如果是偶数，可以从一半转移，即从f[i] = f[i//2] + y。
- 如果是奇数，可以从后一个数i+1转移，i+1从(i+1)//2转移，即f[i] = f[(i+1)//2)+x+y。
- 为什么偶数不从后一个转移呢？
- 如果从后边来，实际是从i+2来，即f[i] = f[(i+2)//2]+2x+y = f[i//2+1]+2x+y。
- 那我不如直接从一半来，即f[i] = f[i//2]+y。
3. 代码实现
# Problem: 加减乘
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4808/
# Memory Limit: 256 MB
# Time Limit: 1000 ms
import 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没有comb
from math import comb
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
# ms
def solve():
n, x, y = RI()
h = [(0, 0)]
f = [0] * (n + 1)
for i in range(1, n + 1):
f[i] = f[i - 1] + x
if i & 1 == 0:
f[i] = min(f[i], f[i // 2] + y)
else:
f[i] = min(f[i], f[(i + 1) // 2] + x + y)
print(f[-1])
if __name__ == '__main__':
solve()
六、参考链接
- 无