[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()
六、參考連結
- 無