AcWing 80场杯赛

Q1 4803. 满足的数 [Easy] 题解

Q2 4804. 构造矩阵 [Medium] 题解

Q3 4805. 加减乘 [Hard] 题解

Q1

4803. 满足的数 - AcWing题库

思路

额，模拟

代码

n = int(input())
a = list(map(int,input().split()))
s = sum(a)
ans = 0
for i in range(1, 6):
    if (s+i)%(n+1) != 1: ans += 1
print(ans)

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

Q2

4804. 构造矩阵 - AcWing题库

思路

题目理解很容易，但写起来怪怪的😅😅。

1. 有0就必须行列全为0，这个规则很硬性。所以得先处理，把所有必须为0的先改成0.
2. 再遍历改完的数组，如果为1，则把行列标记为”有1存在“。
3. 最后遍历原数组，如果为1，看其所属行列有没有”1存在的标记“。如果没有，返回NO。
4. 输出答案。

代码

n, m = list(map(int,input().split()))
g = [list(map(int,input().split())) for i in range(n)]
f = [[ii for ii in g[i]] for i in range(n)]
zx = set()
zy = set()
ox = set()
oy = set()
for i in range(n):
    for j in range(m):
        if g[i][j] == 0:
            zx.add(i)
            zy.add(j)
for i in range(n):
    for j in range(m):
        if i in zx or j in zy: f[i][j] = 0
for i in range(n):
    for j in range(m):
        if f[i][j] == 1:
            ox.add(i)
            oy.add(j)
for i in range(n):
    for j in range(m):
        if g[i][j] == 1:
            if not i in ox and not j in oy:
                print("NO")
                exit()
print("YES")
for i in range(n):
    for j in range(m):
        print(f[i][j], end=' ')
    print()

复杂度分析

• 时间复杂度：O(nm)
• 空间复杂度：O(nm)

Q3

4805. 加减乘 - AcWing题库

思路

DP

代码

import java.util.*;import java.io.*;

public class Main {
    static String ss, io[];
    static int test, N = 100010, M = 1000000007;
    static void solve() throws Exception{
        int n = ni(); 
        long x = ni(), y = ni();
        long[] dp = new long[2*n+1];
        Arrays.fill(dp, (long)1e18);
        dp[0] = 0;
        for (int i = 0;i <= n;i++){
            dp[i] = min(dp[i], min(dp[i-1]+x, dp[i+1]+x));
            dp[i*2] = min(dp[i*2], dp[i]+y);
        }
        out.println(dp[n]);
    }
    public static void main(String[] args) throws Exception {
        test = 1;
        // test = ni(in.readLine());
        while (test-- > 0){
            solve();
        }out.flush();
    }
    static int ni() throws IOException{input.nextToken();return (int) input.nval;}
    static long nl() throws IOException{input.nextToken();return (long) input.nval;}
    static int ni(String x) {return Integer.parseInt(x);}
    static long nl(String x) {return Long.parseLong(x);}
    static int max(int a, int b) {return a > b ? a : b;}
    static long max(long a, long b) {return a > b ? a : b;}
    static int min(int a, int b) {return a < b ? a : b;}
    static long min(long a, long b) {return a < b ? a : b;}
    static int lg2(long a) {return (int)Math.ceil((Math.log(a)/Math.log(2)));}
    static int abs(int a) {return a > 0?a:-a;}
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer input = new StreamTokenizer(in);
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
}  

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)