头像

233


访客:3236

离线:21小时前


活动打卡代码 AcWing 154. 滑动窗口

233
1天前
def solve():
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    window_min, window_max = [], []

    sliding_min = []
    sliding_max = []

    for i in range(k):
        while window_max and nums[i] >= nums[window_max[-1]]:
            window_max.pop()
        window_max.append(i)

        while window_min and nums[i] <= nums[window_min[-1]]:
            window_min.pop()
        window_min.append(i)
    sliding_min.append(nums[window_min[0]])
    sliding_max.append(nums[window_max[0]])

    for i in range(k, len(nums)):
        while window_max and nums[i] >= nums[window_max[-1]]:
            window_max.pop()
        while window_max and i - window_max[0] >= k:
            del window_max[0]
        window_max.append(i)
        sliding_max.append(nums[window_max[0]])

        while window_min and nums[i] <= nums[window_min[-1]]:
            window_min.pop()
        while window_min and i - window_min[0] >= k:
            del window_min[0]
        window_min.append(i)
        sliding_min.append(nums[window_min[0]])

    print(*sliding_min)
    print(*sliding_max)


if __name__ == '__main__':
    solve()




233
1天前
class MinStack(object):

    def __init__(self):
        self.st = []
        self.min_st = []

    def push(self, x):
        self.st.append(x)
        if not self.min_st or self.min_st[-1] >= x:
            self.min_st.append(x)

    def pop(self):
        if self.st and self.st.pop() == self.min_st[-1]:
            self.min_st.pop()
        return -1

    def top(self):
        if not self.st:
            return -1
        return self.st[-1]

    def getMin(self):
        if not self.min_st:
            return -1
        return self.min_st[-1]




233
1天前
def solve(ls: list) -> int:
    st, area = [], 0
    for i in range(len(ls)):
        while st and ls[i] < ls[st[-1]]:
            top = st.pop()
            area = max(area, ls[top] * (i - st[-1] - 1))
        st.append(i)
    return area


if __name__ == '__main__':
    res = []
    while True:
        ls = list(map(int, input().split()))
        if not ls[0]:
            break
        else:
            res.append(solve([0] + ls[1:] + [0]))
    for r in res:
        print(r)



活动打卡代码 AcWing 103. 电影

233
2天前
from collections import Counter


def solve():
    n = int(input())

    m_ap = Counter(map(int, input().split()))

    m = int(input())

    ls = [(i + 1, m_ap[val[0]], m_ap[val[1]]) for i, val in
          enumerate(zip(map(int, input().split()), map(int, input().split())))]

    ls.sort(key=lambda x: (x[1], x[2]), reverse=True)

    return ls[0][0]


if __name__ == '__main__':
    print(solve())


活动打卡代码 AcWing 104. 货仓选址

233
2天前
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; ++i) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);

        int mid = arr[n >> 1];
        int res = 0;
        for (int num : arr) {
            res += Math.abs(mid - num);
        }
        System.out.println(res);
    }
}



233
2天前
def solve():
    n = int(input())
    tmp = []
    def dfs(k,state):
        if k == n:
            print(*tmp)
        else:
            for i in range(1,n + 1):
                if not state >> i & 1:
                    tmp.append(i)
                    dfs(k + 1,state | 1 << i)
                    tmp.pop()
    dfs(0,0)
if __name__ == '__main__':
    solve()



233
3天前
def solve():
    n, m = map(int, input().split())
    res = []

    def dfs(s, k, state):
        if s > n and k != m:
            return None
        if k == m:
            res.append([i for i in range(1, n + 1) if state >> i & 1])
        else:
            dfs(s + 1, k + 1, state | 1 << s)
            dfs(s + 1, k, state)

    dfs(1, 0, 0)
    for r in res:
        print(*r)

if __name__ == '__main__':
    solve()



233
3天前
def solve():
    n,res = int(input()),[]
    def dfs(s,n,state):
        if s > n:
            res.append([i for i in range(32) if state >> i & 1])
        else:
            dfs(s + 1,n,state | 1 << s)
            dfs(s + 1, n, state)
    dfs(1,n,0)
    for r in res:
        print(*r)
if __name__ == '__main__':
    solve()


活动打卡代码 AcWing 91. 最短Hamilton路径

233
3天前
'''
dp[i][j]
i 记录哪些点被使用过了,j 表示当前停在 j 位置上
'''
def solve():
    n = int(input())
    weight = []
    for i in range(n):
        weight.append(list(map(int,input().split())))
    dp = [[0x3f3f3f3f] * n for i in range(1 << n)]
    dp[1][0] = 0

    for i in range(1 << n):
        for j in range(n):
            #如果当前停留在 j 位置上
            if i >> j & 1:
                for k in range(n):
                    #枚举当前点从何处转过来的.
                    if (i - (1 << j)) >> k & 1:
                        dp[i][j] = min(dp[i][j],dp[i - (1 << j)][k] + weight[k][j])
    return dp[-1][-1]

if __name__ == '__main__':
    print(solve())


活动打卡代码 AcWing 90. 64位整数乘法

233
3天前
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong(), b = sc.nextLong(), p = sc.nextLong();
        System.out.println(powMod(a, b, p));
    }

    public static long powMod(long a, long b, long p) {
        long res = 0;
        while (b != 0) {
            if ((b & 1) != 0) {
                res = (res + a) % p;
            }
            b >>= 1;
            a = (a * 2) % p;
        }
        return res % p;
    }
}