盛日辉的博客
0%

发表于 更新于 分类于 
1
2
3
4
5
FileInput = False

if FileInput:
    sys.stdin = open('flower.in', 'r')
    sys.stdout = open('flower.out', 'w')

发表于 更新于 分类于

分组背包

问题：每一组当中的物品只能选一个。

方法：在0/1背包的基础上，在每一组中遍历所有物品。

题目

方法

方法一：转换为0/1问题

将每一个物品都看作是一种物品。

阅读全文 »

发表于 更新于 分类于

题目

https://www.lanqiao.cn/problems/1505/learning/

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# 03-剪邮票-1
from collections import deque

mp = [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14]
vis = [False] * 13
a = [0] * 5  # 选出来的5个数


def bfs():
    global a
    cnt = [0] * 5
    q = deque()
    q.append(a[0])
    cnt[0] = 1
    while q:
        x = q.popleft()
        for i, y in enumerate(a):
            if abs(x - y) in [1, 5] and cnt[i] == 0:
                q.append(y)
                cnt[i] = 1
        if sum(cnt) == 5:
            return True
    else:
        return False


def dfs(s):
    global ans, vis
    if s == 6:
        if bfs():
            # print(a)
            ans += 1
    else:
        for i in range(12):
            if not vis[i]:
                vis[i] = True
                a[s - 1] = mp[i]
                dfs(s + 1)
                vis[i] = False


ans = 0

dfs(1)
print(ans // 120)

发表于 更新于 分类于

题目

https://www.lanqiao.cn/problems/178/learning/

DFS

会栈溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 05-全球变暖1
import sys

sys.setrecursionlimit(600000)


def dfs(i, j):
    global flag, vis, mp, Dir
    if mp[i + 1][j] == "#" and mp[i - 1][j] == "#" and \
            mp[i][j + 1] == "#" and mp[i][j - 1] == "#":
        flag = True
        # return
    for di, dj in Dir:
        ni, nj = i + di, j + dj
        # if ni < 0 or nj < 0 or ni >= n or nj >= n or vis[ni][nj]:
        #     continue
        # 因为最外面一圈都是海
        if not vis[ni][nj] and mp[ni][nj] == "#":
            vis[ni][nj] = True
            dfs(ni, nj)
            # vis[ni][nj] = False


ans = 0
n = int(input())
mp = []
vis = [[False] * n for _ in range(n)]
Dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for _ in range(n):
    mp.append(list(input()))
for x in range(n):
    for y in range(n):
        if mp[x][y] == "." or vis[x][y]:
            continue
        # print(x,y)
        flag = False
        vis[x][y] = True
        dfs(x, y)
        if not flag:
            ans += 1
print(ans)

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
# 02-全球变暖-1
from collections import deque


def bfs(i, j):
    global flag
    q = deque()
    q.append((i, j))
    vis[i][j] = True
    while q:
        x, y = q.popleft()
        if mp[x + 1][y] == "#" and mp[x - 1][y] == "#" and \
                mp[x][y + 1] == "#" and mp[x][y - 1] == "#":
            flag = True
        for dx, dy in Dir:
            nx, ny = x + dx, y + dy
            if not vis[nx][ny] and mp[nx][ny] == "#":
                vis[nx][ny] = True
                q.append((nx, ny))


ans = 0
n = int(input())
mp = []
vis = [[False] * n for _ in range(n)]
Dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for _ in range(n):
    mp.append(list(input()))
for x in range(n):
    for y in range(n):
        if mp[x][y] == "." or vis[x][y]:
            continue
        # print(x,y)
        flag = False
        vis[x][y] = True
        bfs(x, y)
        if not flag:
            ans += 1
print(ans)
"""
输入

7
.......
.##....
.##....
....##.
..####.
...###.
.......
copy
输出

1

10
 .......... .......... ...#...... .......... ....#.##.. ....#.##.. .#..####.. .#........ .##....... ..........
"""

"""
20
....................
....................
....................
....................
....#...............
....########........
....##########......
....###############.
.....##############.
.....##############.
.....##############.
......#############.
......#############.
......#############.
.......############.
.......############.
........###########.
.........##########.
..........#########.
....................

"""

发表于 更新于 分类于

题目

https://www.lanqiao.cn/problems/602/learning/

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 01-迷宫2019-2
import sys
from queue import Queue

# 加围墙
mp = []
mp.append([1] * 52)
for _ in range(30):
    mp.append([1] + list(map(int, input())) + [1])
mp.append([1] * 52)
mp[1][1] = 1
path = [["."] * 52 for _ in range(32)]
k = ("D", "L", "R", "U")
dir = ((1, 0), (0, -1), (0, 1), (-1, 0))


def print_path(x, y):
    if x == 1 and y == 1:
        return
    if path[x][y] == "U":
        print_path(x + 1, y)
    if path[x][y] == "D":
        print_path(x - 1, y)
    if path[x][y] == "L":
        print_path(x, y + 1)
    if path[x][y] == "R":
        print_path(x, y - 1)
    print(path[x][y], end="")


q = Queue()
q.put((1, 1))
mp[1][1] = 1
while q:
    x, y = q.get()
    for i in range(4):
        dx, dy = dir[i]
        nx, ny = x + dx, y + dy
        if mp[nx][ny] == 1:
            continue
        mp[nx][ny] = 1
        path[nx][ny] = k[i]
        if nx == 30 and ny == 50:
            print_path(30, 50)
            sys.exit(0)
        q.put((nx, ny))

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 01-迷宫2019-1
from queue import Queue

mp = []
n, m = 30, 50
for _ in range(n):
    mp.append(input())

vis = [list(map(int, i)) for i in mp]
k = ("D", "L", "R", "U")
dir = ((1, 0), (0, -1), (0, 1), (-1, 0))
q = Queue()
q.put((0, 0, ""))
vis[0][0] = 1
while q:
    x, y, p = q.get()
    # print(x, y, p)
    if x == n - 1 and y == m - 1:
        print(p)
        break
    for i in range(4):
        dx, dy = dir[i]
        nx, ny = x + dx, y + dy
        # print(i, x, y, dx, dy, nx, ny)
        if nx < 0 or ny < 0 or nx >= n or ny >= m or vis[nx][ny] == 1:
            continue
        p_t = p + k[i]
        vis[nx][ny] = 1
        q.put((nx, ny, p_t))
        # print(nx, ny, p)

发表于 更新于 分类于

题目

https://www.lanqiao.cn/problems/226/learning/

思路

这其实是一道排序题，要让B从小到大排，A从大到小牌。

但是为什么呢？

让我来数学证明一下~

首先，规定一下符号。

和别的地方说的一样，容易说明，连续的增加A或B，顺序是不影响最后的结果的。假设连续增加A，那么$A_n=\log_2{(A_0+a_1+a_2+…)}$，改变顺序不影响$A_n$的值。所以只需要讨论A和B的增加量交替出现的时候如何选择了。

阅读全文 »

发表于 更新于 分类于

题目

https://www.lanqiao.cn/problems/196/learning/

思路

  1. 所有操作都是在数组内进行的，整个数组的和不变；
  2. 每次操作的三个数的和不变，因此考虑到用前缀和。
  3. 一次更新后，s[i-1]变为原来的s[i],s[i]变为原来的s[i-1],s[i+1]不变；
  4. 因此“一次加减操作”转变为“前两个前缀和的交换”。
  5. 两端的武士不向外传递灵能，但他们的灵能值也会改变，而s[n]是所有的和，不变。因此，s[0]=0，s[1]到s[n-1]可以交换到任意位置。
  6. 要求的东西就变成了求max{|s[i]-s[i-1|}尽量小。
  7. 先考虑简单情况，s[]都是正的，将他排序，相邻差最大的就是结果，因为如果不排序，相邻相减会大；
  8. https://blog.csdn.net/xuxiaobo1234/article/details/108095193
  9. 最后一步，我只能理解成：小于s[0]大于min部分的值要排列起来，使得相邻两数的差最大值最小化，从图像上想象就是，s[0]固定住，s[1]到s[p]（假设是这样的下标）升序排序，但都小于s[0]，然后隔一个的将数拆开成两部分，一部分降序地排列在s[0]后面，然后另一部分更在后面，这样能“使得相邻两数的差最大值最小化”。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 灵能传输

T = int(input())
for _ in range(T):
    n = int(input())
    arr = list(map(int, input().split()))
    # 计算前缀和
    s = [0] * (n + 1)
    for i, x in enumerate(arr):
        s[i + 1] = s[i] + x
    s0, sn = s[0], s[-1]
    if s0 > sn:
        s0, sn = sn, s0
    # print(s)
    s.sort()
    s0_idx = s.index(s0)
    sn_idx = s.index(sn)
    # print(s)
    # print(s0_idx)
    # print(sn_idx)
    res_sum = s.copy()
    L, R = 0, n
    vis = [True] * (n + 1)
    for i in range(s0_idx, -1, -2):
        res_sum[L] = s[i]
        L += 1
        vis[i] = False
    for i in range(sn_idx, n + 1, 2):
        res_sum[R] = s[i]
        R -= 1
        vis[i] = False
    for i in range(n + 1):
        if vis[i]:
            res_sum[L] = s[i]
            L += 1

    res = 0
    for i in range(1, len(res_sum)):
        res = max(res, abs(res_sum[i] - res_sum[i - 1]))

    print(res)

发表于 更新于 分类于

扫地机器人

题目：https://www.lanqiao.cn/problems/199/learning/

  • 每个机器人“负责”的区域（包括他自己的）*2=他的时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
# n, k = map(int, input().split())
# # n, k = 10, 3
# arr = [False] * (n + 1)
#
# for i in range(k):
#     arr[int(input())] = True
#
#
# # for i in [5, 2, 10]:
# #     arr[i] = True
#
#
# def check(d):
#     i = 1
#     while i <= n:
#         # print(d, i, i + d, arr[i:i + d])
#         if not any(arr[i:i + d]):
#             return False
#         i += d
#     return True
#
#
# l, r = 1, n
# while l < r:
#     mid = (l + r) // 2
#     print(l, r, mid)
#     if check(mid):
#         r = mid
#     else:
#         l = mid + 1
# print((l - 1) * 2)


n, k = map(int, input().split())
a = [0]
for i in range(k):
    a.append(int(input()))
a.sort()

print(a)


def check(d):
    len = 0  # 覆盖长度，从最左端开始一直到最右端
    for i in range(1, k + 1):
        if len + d >= a[i]:  # 当前覆盖长度加上d之后，是否包括了a[i]
            if len > a[i]:  # 当前覆盖长度是否已经包括了a[i]
                # 如果当前覆盖长度已经包括了，说明a[i]之前的机器人已经负责了到len这块的区域
                # 那a[i]就可以负责len往后再加d的部分
                len = a[i] + d - 1  # 减1是因为还要算上自己
            else:
                # 如果当前覆盖长度没有包括a[i]，那就让a[i]负责[len+1,len+d]
                len += d
        else:
            return False
    return len >= n


l, r = 1, n
mid = 0
while l < r:
    mid = (l + r) // 2
    print(l, r, mid)
    if check(mid):
        r = mid
    else:
        l = mid + 1
print((l - 1) * 2)