$\href{https://blog.csdn.net/eveee1123}{\sf\color{magenta}{My}\;\color{blue}{CS}\color{red}{DN}}$

2836

t = int(input())

def LIS(arr, n):
f = [1] * n
for i in range(1, n):
for j in range(i):
if arr[i] > arr[j]: f[i] = max(f[i], f[j] + 1)
return max(f)
while t:
t -= 1
n = int(input())
num = list(map(int, input().split()))
ans = LIS(num, n)
ans = max(ans, LIS(num[::-1], n))
print(ans)


n = int(input())

rec = []
for i in range(n):
l, r = map(int, input().split())
rec.append((l, r))

rec.sort(key = lambda x: x[1])

cnt = 1
now = rec[0][1]
for i in rec:
l, r = i[0], i[1]
if l > now:
cnt += 1
now = r
print(cnt)


n = int(input())

rec = []
for i in range(n):
l, r = map(int, input().split())
rec.append((l, r))

rec.sort(key = lambda x: x[1])

cnt = 1
now = rec[0][1]
for i in rec:
l, r = i[0], i[1]
if l <= now <= r: continue
else:
cnt += 1
now = r
print(cnt)


1个月前

## 树状数组

维护序列前缀和

复杂度 O（logN）

小心不要用到下标[0]

C = [0] * (n + 1)
def lowbit(x):
return x & (-x)

while x <= n:
C[x] += i
x += lowbit(x)
def query(x):
ans = 0
while x:
ans += C[x]
x -= lowbit(x)
return ans


## 线段树

维护区间和

class Node():
l = 0
r = 0
su = 0 #sum
def __init__(self, l = 0, r = 0, su = 0):
self.l = l
self.r = r
self.su = su

def pushup(u):
global t
t[u].su = t[u << 1].su + t[u << 1 | 1].su
def build(u, l, r):
global t
if l == r:
t[u] = Node(l, r, num[r - 1])
return
else:
t[u] = Node(l, r)
mid = l + r >> 1
build(u << 1, l, mid)
build(u << 1 | 1, mid + 1, r)
pushup(u)
def query(u, l, r):
if t[u].l >= l and t[u].r <= r: return t[u].su
mid = t[u].l + t[u]. r >> 1
ans = 0
if l <= mid: ans = query(u << 1, l, r)
if r > mid: ans += query(u << 1 | 1, l, r)
return ans
def modify(u, x, v):
if t[u].l == t[u].r:
t[u].su +=v
return
mid = t[u].l + t[u].r >> 1
if x <= mid: modify(u << 1, x, v)
else: modify(u << 1 | 1, x, v)
pushup(u)


## KMP

next数组表示模版串中以i结尾的后缀子串和前缀最大匹配长度

def KMP():
global s, p
s = ' ' + s
p = ' ' + p
ne = [0] * (n + 2)
#求next
j = 0
for i in range(2, n + 1):
while j and p[i] != p[j + 1]: j = ne[j]
if p[i] == p[j + 1]: j += 1
ne[i] = j
#匹配
j = 0
for i in range(1, m + 1):
while j and  s[i] != p[j + 1]: j = ne[j]
if s[i] == p[j + 1]: j += 1
if j == n:
print(i - n, end = ' ')
j = ne[j]


1个月前

## 平面图欧拉公式

$V - E + F = 2$

### 堆优化版本dijkstra

import heapq
INF = 0x3f3f3f3f
N = 1000000

e = [0] * N
idx = 0
ne = [0] * N
w = [0] * N
h = [-1] * N
n, m = map(int, input().split())

global e, w, ne ,h, idx
e[idx] = b
w[idx] = c
ne[idx] = h[a]
h[a]= idx
idx += 1

while m:
m -= 1
a, b, c = map(int, input().split())

def dijkstra():
st = [False] * N
dist = [INF] * N
dist[1] = 0
hp = []
heapq.heappush(hp, (0, 1))

while len(hp):
t = heapq.heappop(hp)
cur = t[1]; dis = t[0]

if st[cur]: continue
st[cur] = True

i = h[cur]
while ~i:
j = e[i]
if dist[j] > dist[cur] + w[i]:
dist[j] = dist[cur] + w[i]
heapq.heappush(hp, (dist[j], j))
i = ne[i]

return -1 if dist[n] == INF else dist[n]

print(dijkstra())


### Dijkstra

n , m = map(int , input().split())
N = n + 1000
g = [[0x3f3f3f3f]*N for i in range(N)]
while m:
m -= 1
x , y , z = map(int , input().split())
g[x][y] = z
for  i in range(n):
g[i][i] = 0
def dijkstra():
st = [False] * N
dist = [0x3f3f3f3f] * N
dist[1] = 0
for i in range(n-1):
t = -1
for j in range(1,n+1):
if not st[j] and (t == -1 or dist[j] < dist[t]): t = j
for j in range(1,n+1):
dist[j] = min(dist[j] , dist[t] + g[t][j])

st[t] = True
return -1 if dist[n] == 0x3f3f3f3f else dist[n]

print(dijkstra())


## Bellman_ford

两层循环，复杂度O(nm)

最外层循环意味着当前最短路包含几条边

'''

'''
import copy
class edge(): # a, b, w分别表示起点和终点以及权值
a = 0
b = 0
w = 0
def __init__(self, a, b, w):
self.a = a
self.b = b
self.w = w

n, m, k = map(int, input().split())
g = [None] * m

for i in range(m):
a, b, w = map(int, input().split())
g[i] = edge(a, b, w)

def bellman_ford():
dis = [0x3f3f3f3f3f] * (n + 1)
dis[1] = 0
for i in range(k):
backup = copy.deepcopy(dis)#backup是dis列表的拷贝，防止下面那层循环在更新dis数组时用到本层循环中刚更新过的dis
for j in range(m):
dis[g[j].b] = min(dis[g[j].b], backup[g[j].a] + g[j].w)
return dis[n]

ans = bellman_ford()

if ans > 0x3f3f3f3f: print('impossible')
else: print(ans)


## SPFA

from collections import deque
def spfa():
dist = [0x3f3f3f3f] * (n + 1)
v = [0] * (n + 1)
q = deque()
q.append(1)
dist[1] = 0
while len(q):
pos = q.popleft()
v[pos] = 0
while ~i:
j = e[i]
if dist[j] > dist[pos] + w[i]:
dist[j] = dist[pos] + w[i]
if not v[j]: q.append(j); v[j] = 1
i = ne[i]
return 'impossible' if dist[n] == 0x3f3f3f3f else dist[n]



## Kruskal

'''

'''
'''
e 用来存储边
n 点数
m 边数
ans 最小生成树代价
cnt 选取得总边数
'''
n, m = map(int, input().split())

class edge():
a = 0
b = 0
w = 0
def __init__(self, a = 0, b = 0, c = 0):
self.a = a
self.b = b
self.w = c

e = [edge() for i in range(m)]
fa = [i for i in range(n + 1)]
for i in range(m):
a, b, c = map(int, input().split())
e[i].a = a
e[i].b = b
e[i].w = c

e.sort(key = lambda x: x.w)

def find(x):
if x == fa[x]:
return fa[x]
else:
fa[x] = find(fa[x])
return fa[x]
ans = 0
cnt = 0
for i in e:
x = i.a
y = i.b
x = find(x)
y = find(y)
if x != y:
fa[x] = y
ans += i.w
cnt += 1
if cnt < n - 1:
print('impossible')
else:
print(ans)


1个月前

## Lucas 组合数取模

b存在乘法逆元的充要条件是b与模数m互质

def exgcd(a, b): #扩展欧几里得
if b == 0:
x = 1
y = 0
return x, y
x1, y1 = exgcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return x, y
'''

a ^ p % p = 1

b的逆元为 b ^ (p - 2)
b存在乘法逆元的充要条件是b与模数m互质
'''
def quick_mod(a, b, p): #快速幂
# return a^b%p
ans = 1
a %= p
while b:
if b & 1:
ans = ans * a % p
b -= 1
b >>= 1
a = a * a % p
return ans
def Inv(b, p): #求逆元
x, y = exgcd(b, p)
return (x + p) % p
def C(n, m, p):
if m > n: return 0
a = 1; b = 1
while m:
a = a * n % p
n -= 1
b = b * m % p
m -= 1
return a * Inv(b, p) % p
def Lucas(n, m, p):
if m == 0:
return 1
return C(n % p, m % p, p) * Lucas(n // p, m // p, p) % p



## 素数判定

def judge(x):
if x < 2: return False
sqx = int(math.sqrt(x)) + 1
for i in range(2, sqx):
if x % i == 0: return False
return True


## 质因数分解

def prime_fac(x):
p = []
c = []
for i in range(2, int(sqrt(x)) + 1):
if x % i == 0:
p.append(i)
cnt = 0
while x % i == 0:
x //= i
cnt += 1
if cnt: c.append(cnt)
if x > 1:
p.append(x)
c.append(1)
return p, c


## 最大公约数

python自带gcd函数哦

import math
print(math.gcd(4, 6))


## 快速幂

def quick_mod(a, b, p):
'''
return a ^ b mod p
'''
ans = 1
while b:
if b & 1: ans *= a
a = a * a % p
b >>= 1
return ans % p

pow(a, b, c)
#这个是内置函数，直接就是快速幂，比我上面手写那个要快一些


## 扩展欧几里得

通解：

$a’ = a // gcd(a, b)$

$b’ = b // gcd(a, b)$

$x = x’ + k * b’$

$y = y’ - k * a’$

最小正整数解

$x = x’ mod b’$

def ex_gcd(a, b):
'''
return ax + by = gcd(a, b)
'''
if b == 0:
x = 1
y = 0
return x, y
x1, y1 = ex_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return x, y


## 质数筛

#线性筛
'''
if i % primes[j] == 0: break

break的原因是此时pj是i的最小质因子，那么下一个pj*i筛的合数的最小质因子一定不是pj
'''
cnt = 0 #cnt表示质数总个数
for i in range(2, n+1):
if not vis[i]: #vis这个列表用来标记一个数是否被筛选过
cnt += 1
primes[cnt] = i #primes列表用来记录每一个质数
for j in range(1, cnt+1):
if primes[j] > n//i: break # 原因请见最上方注释
vis[primes[j] * i] = 1
if i % primes[j] == 0: break



## 质因数分解

'''

'''
import math
def get_prime_fac(x):
sqr_x = int(math.sqrt(x))+ 1
for i in range(2, sqr_x):
cnt = 0
if x % i == 0:
while x % i == 0: x //= i; cnt +=1
print(i, cnt) #i是当前质因数，cnt是指数
if x != 1:
print(x, 1) #x表示质因数，1表示指数是1
print() # 输出一个回车，无实际意义


1个月前
n = int(input())
nums = list(map(int, input().split()))
nums.append(-0x3f3f)
now = -1
cnt = 0
for i in range(n):
if nums[i] <= nums[i + 1] and now == -1:
now = nums[i]
if nums[i] <= nums[i + 1] and now != -1:
continue
if nums[i] > nums[i + 1] and now != -1:
cnt += nums[i] - now
now = -1

print(cnt)



1个月前
n = int(input())
N = 2 * n + 100
idx = 0
e = [0] * N
nx = [-1] * N
w = [-1] * N
global idx
e[idx] = b
w[idx] = c
idx += 1

for i in range(n - 1):
a, b, c = map(int, input().split())

mxdeep = -1
node = -1
def dfs(x, fa, deep):
global mxdeep, node
if deep > mxdeep:
mxdeep = deep
node = x
while ~i:
j = e[i]
if j == fa: i = nx[i]; continue
dfs(j, x, deep + w[i])
i = nx[i]
return

dfs(1, 1, 0)
dfs(node, node, 0)
print((11 + 10 + mxdeep) * mxdeep // 2)


1个月前
from collections import deque
n = int(input())

g = [[] for i in range(n)]
vis = [[0] * n for i in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
tmp = input()
for j in tmp:
g[i].append(j)

def bfs(i, j):
total = 0
warn = 0
q = deque()
q.append((i, j))
vis[i][j] = True
while q:
x, y = q.popleft()
total += 1
sea = False
for d in range(4):
nx, ny = x + dx[d], y + dy[d]
if nx < 0 or ny < 0 or nx >= n or ny >= n: continue
if vis[nx][ny]: continue
if g[nx][ny] == '#': q.append((nx, ny)); vis[nx][ny] = True
if g[nx][ny] == '.': sea = True
if sea: warn += 1
return warn == total

cnt = 0
for i in range(n):
for j in range(n):
if g[i][j] == '#' and not vis[i][j]:
if bfs(i, j): cnt += 1
print(cnt)