头像

那些花儿


访客:954

离线:1个月前


活动打卡代码 AcWing 839. 模拟堆

那些花儿
6个月前
from array import array
from sys import stdin


class Heap(object):

    def __init__(self):
        self.items = array('i', [0]) * 100000
        self.mapping = array('i', [-1]) * 100000
        self.idx = 0
        self.que = array('i')
        self.size = 0

    def siftUp(self, idx):
        if not 0 <= idx < self.size:
            return
        while True:
            fa = idx - 1 >> 1
            if fa >= 0 and self.items[self.que[idx]] < self.items[self.que[fa]]:
                self.swap(idx, fa)
                idx = fa
            else:
                break

    def siftDown(self, idx):
        if not 0 <= idx < self.size:
            return
        _min = idx
        while True:
            left = _min << 1 | 1
            right = left + 1
            if left < self.size and self.items[self.que[_min]] > self.items[self.que[left]]:
                _min = left
            if right < self.size and self.items[self.que[_min]] > self.items[self.que[right]]:
                _min = right
            if _min != idx:
                self.swap(_min, idx)
                idx = _min
            else:
                break

    def swap(self, a, b):
        self.que[a], self.que[b] = self.que[b], self.que[a]
        self.mapping[self.que[a]], self.mapping[self.que[b]] = \
            self.mapping[self.que[b]], self.mapping[self.que[a]]

    def heappop(self):
        if self.size < 1:
            return 
        self.size -= 1
        self.mapping[self.que[0]] = -1
        self.mapping[self.que[self.size]] = 0
        self.que[0] = self.que[self.size]
        self.que.pop()
        self.siftDown(0)

    def heappush(self, val):
        self.idx += 1
        self.items[self.idx] = val
        self.que.append(self.idx)
        self.mapping[self.idx] = self.size
        self.size += 1
        self.siftUp(self.size - 1)

    def peek(self):
        return self.items[self.que[0]]

    def change(self, idx, val):
        pre = self.items[idx]
        self.items[idx] = val
        if val > pre:
            self.siftDown(self.mapping[idx])
        else:
            self.siftUp(self.mapping[idx])

    def delete(self, idx):
        k = self.mapping[idx]
        if k == -1:
            return
        self.size -= 1
        self.mapping[self.que[self.size]] = k
        self.mapping[idx] = -1
        self.que[k] = self.que[self.size]
        self.que.pop()
        self.siftDown(k)
        self.siftUp(k)

def main():
    n = int(stdin.readline())
    h = Heap()
    for _ in range(n):
        op = stdin.readline().split()
        if op[0] == 'I':
            h.heappush(int(op[1]))
        elif op[0] == 'PM':
            print(h.peek())
        elif op[0] == 'DM':
            h.heappop()
        elif op[0] == 'D':
            h.delete(int(op[1]))
        else:
            h.change(int(op[1]), int(op[2]))


if __name__ == '__main__':
    main()



活动打卡代码 AcWing 838. 堆排序

那些花儿
7个月前
from array import array
from sys import stdin

def main():
    n, m = map(int, stdin.readline().split())
    que = array('I', map(int, stdin.readline().split()))

    def siftDown(idx):
        if not que:
            return
        rec = que[idx]
        n = len(que)
        while True:
            minVal, minIdx = rec, idx
            left = idx << 1 | 1
            right = left + 1
            if left < n and que[left] < minVal:
                minVal, minIdx = que[left], left
            if right < n and que[right] < minVal:
                minVal, minIdx = que[right], right
            if minIdx == idx:
                que[idx] = rec
                return
            que[idx] = minVal
            idx = minIdx

    def heapify():
        end = n - 1 >> 1
        for i in range(end, -1, -1):
            siftDown(i)

    def heappop():
        print(que[0], end=' ')
        que[0] = que[-1]
        que.pop()
        siftDown(0)

    heapify()
    for _ in range(m):
        heappop()
    print()


if __name__ == '__main__':
    main()




那些花儿
7个月前
from array import array
from sys import stdin

def main():
    n, m = map(int, stdin.readline().split())
    v = array('I', range(n+1))
    kids = array('I', [1]) * (n+1)

    def find(a):
        t = a
        while t != v[t]:
            t = v[t]
        while a != v[a]:
            a, v[a] = v[a], t
        return t

    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return 
        v[a] = b
        kids[b] += kids[a]

    for _ in range(m):
        op = stdin.readline().split()
        if op[0] == 'C':
            union(int(op[1]), int(op[2]))
        elif op[0] == 'Q1':
            if find(int(op[1])) == find(int(op[2])):
                print('Yes')
            else:
                print('No')
        else:
            print(kids[find(int(op[1]))])


if __name__ == '__main__':
    main()



活动打卡代码 AcWing 836. 合并集合

那些花儿
7个月前
from array import array
from sys import stdin


def main():
    n, m = map(int, stdin.readline().split())
    members = array('i', range(n+1))


    def find(i):
        if members[i] != i:
            members[i] = find(members[i])
        return members[i]


    def union(a, b):
        members[find(a)] = find(b)


    for _ in range(m):
        op = stdin.readline().split()
        if op[0] == 'M':
            union(int(op[1]), int(op[2]))
        else:
            if find(int(op[1])) == find(int(op[2])):
                print("Yes")
            else:
                print("No")


if __name__ == "__main__":
    main()



活动打卡代码 AcWing 143. 最大异或对

那些花儿
7个月前
from array import array
from sys import stdin


class Node(object):
    __slots__ = ("nx")

    def __init__(self):
        self.nx = [None] * 2


class TrieTree(object):

    def __init__(self):
        self.rt = Node()

    def insert(self, val):
        p = self.rt
        for i in range(30, -1, -1):
            cur = val >> i & 1
            if p.nx[cur] is None:
                p.nx[cur] = Node()
            p = p.nx[cur]

    def query(self, val):
        p = self.rt
        ans = 0
        for i in range(30, -1, -1):
            cur = val >> i & 1 ^ 1
            if p.nx[cur] is not None:
                ans |= (1 << i)
                p = p.nx[cur]
            else:
                p = p.nx[cur ^ 1]
        return ans


def main():
    stdin.readline()
    nums = array('I', map(int, stdin.readline().split()))
    ans = 0
    trie = TrieTree()
    for num in nums:
        trie.insert(num)
        t = trie.query(num)
        if t > ans:
            ans = t
    print(ans)


if __name__ == "__main__":
    main()



活动打卡代码 AcWing 835. Trie字符串统计

那些花儿
7个月前
from sys import stdin


class TrieNode(object):
    __slots__ = ('cnt', 'next')

    def __init__(self):
        self.cnt = 0
        self.next = {}


class TrieTree(object):
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        p = self.root
        for s in word:
            if s not in p.next:
                p.next[s] = TrieNode()
            p = p.next[s]
        p.cnt += 1

    def query(self, word):
        p = self.root
        for s in word:
            if s in p.next:
                p = p.next[s]
            else:
                print(0)
                return
        print(p.cnt)


def main():
    n = int(stdin.readline())
    t = TrieTree()
    for _ in range(n):
        op = stdin.readline().split()
        if op[0] == 'I':
            t.insert(op[1])
        else:
            t.query(op[1])


if __name__ == '__main__':
    main()



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

那些花儿
7个月前
from array import array
from collections import deque
from sys import stdin


def minQue(arr, k):
    n = len(arr)
    que = deque()
    for i in range(n):
        while que and que[0] + k <= i:
            que.popleft()
        while que and arr[que[-1]] >= arr[i]:
            que.pop()
        que.append(i)
        if i >= k - 1:
            print(arr[que[0]], end=' ')
    print()
    return None

def maxQue(arr, k):
    n = len(arr)
    que = deque()
    for i in range(n):
        while que and que[0] + k <= i:
            que.popleft()
        while que and arr[que[-1]] <= arr[i]:
            que.pop()
        que.append(i)
        if i >= k - 1:
            print(arr[que[0]], end=' ')
    print()
    return None


def main():
    n, k = map(int, stdin.readline().split())
    nums = array('i', map(int, stdin.readline().split()))
    minQue(nums, k)
    maxQue(nums, k)


if __name__ == "__main__":
    main()


活动打卡代码 AcWing 831. KMP字符串

那些花儿
7个月前
from array import array
from sys import stdin

def get_dfa(word):
    n = len(word)
    dfa = array('i', [-1]) * n
    i = 0
    j = -1
    while i < n - 1:
        if j == -1 or word[i] == word[j]:
            i += 1
            j += 1
            dfa[i] = j
        else:
            j = dfa[j]
    return dfa

def kmp(pattern, text, n, m):
    dfa = get_dfa(pattern)
    i = j = 0
    while i < m:
        if j == -1 or pattern[j] == text[i]:
            i += 1
            j += 1
        else:
            j = dfa[j]
        if j == n:
            print(i-n, end=' ')
            j = dfa[j-1] + 1

def main():
    n = int(stdin.readline())
    pattern = stdin.readline().rstrip()
    m = int(stdin.readline())
    text = stdin.readline().rstrip()
    kmp(pattern, text, n, m)
    print()


if __name__ == "__main__":
    main()




那些花儿
7个月前

题目描述

求出模板串P在模式串S中所有出现的位置的起始下标。

输入格式

第一行输入整数N,表示字符串P的长度。
第二行输入字符串P。
第三行输入整数M,表示字符串S的长度。
第四行输入字符串M。

输出格式

共一行,输出所有出现位置的起始下标(下标从0开始计数),整数之间用空格隔开。

数据范围

$1\le N\le10^4$
$1\le M\le 10^5$

代码参考

from array import array
from sys import stdin

def get_dfa(word):
    n = len(word)
    dfa = array('i', [-1]) * n
    i = 0
    j = -1
    while i < n - 1:
        if j == -1 or word[i] == word[j]:
            i += 1
            j += 1
            dfa[i] = j
        else:
            j = dfa[j]
    return dfa

def kmp(pattern, text, n, m):
    dfa = get_dfa(pattern)
    i = j = 0
    while i < m:
        if j == -1 or pattern[j] == text[i]:
            i += 1
            j += 1
        else:
            j = dfa[j]
        if j == n:
            print(i-n, end=' ')
            j = dfa[j-1] + 1

def main():
    n = int(stdin.readline())
    pattern = stdin.readline().rstrip()
    m = int(stdin.readline())
    text = stdin.readline().rstrip()
    kmp(pattern, text, n, m)
    print()


if __name__ == "__main__":
    main()



活动打卡代码 AcWing 830. 单调栈

那些花儿
7个月前
from sys import stdin
from array import array


def main():
    n = int(stdin.readline())
    arr = array('i', map(int, stdin.readline().split()))
    stack = array('i', [-1])
    for i in range(n):
        while stack[-1] >= arr[i]:
            stack.pop()
        print(stack[-1], end=' ')
        stack.append(arr[i])


if __name__ == '__main__':
    main()