T1
用set很方便，不用像c++ incude一坨
T4
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
|
# 读取输入：N为坐标范围，M为块数
N, M = map(int, input().split())
block = list()
# 初始化白块最低位置为无穷大
wy = 0x3f3f3f3f
flag = True
# 读取每个块的信息
for i in range(M):
x,y,c = input().split()
x = int(x)
y = int(y)
block.append((x,y,c))
# 按x坐标排序
block.sort()
# 检查每个块
for i in block:
if i[2] == 'W': # 如果是白块
wy = min(i[1], wy) # 更新白块最低位置
else: # 如果是黑块
if i[1] >= wy: # 检查是否有白块在左上方
flag = False
break
print("Yes" if flag else "No")
|
T5
竟然是暴力，$O(\tbinom{n}{k} *k)$然后应该会爆，简单的优化一下，根据二项式性质$\tbinom{n}{k}=\tbinom{n}{n-k}$所以优化成$O(\tbinom{n}{k} * min(k, n-k)$，关键在于这个$min(k, n-k)$其实是很小的的，但是我不会证。
然后不光k和n-k这块，既然反选了，你就好好想想奥比如原来四选一，是ABCD然后我选ABC相当于0^A^B^C，又知道0^A = A A^A=0所以说和(A^B^C^D)^D是等价的，那就把所有的数都xor了，然后再反选。
还有就是python的递归真不是闹着玩的，这栈太小了，记得改一下。
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
|
import sys
sys.setrecursionlimit(3 * 10**5)
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
def func(xor, idx, c):
global ans
if c == 0:
ans = max(ans, xor)
return
if idx == N:
return
# 选当前idx
func(xor ^ A[idx], idx + 1, c - 1)
# 不选当前idx
func(xor, idx + 1, c)
if K <= N - K:
func(0, 0, K)
else:
all_xor = 0
for i in range(N):
all_xor ^= A[i]
func(all_xor, 0, N - K)
print(ans)
|
题解还说了，调库！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
import itertools
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
if K <= N - K:
for a in itertools.combinations(A, K):
xor = 0
for i in a:
xor ^= i
ans = max(ans, xor)
else:
all_xor = 0
for i in range(N):
all_xor ^= A[i]
for a in itertools.combinations(A, N - K):
xor = all_xor
for i in a:
xor ^= i
ans = max(ans, xor)
print(ans)
|