...
# 1.统计工龄
# 给定公司N名员工的工龄，要求按工龄增序输出每个工龄段有多少员工。
n=int(input())
lst = list(map(int,input().split()))
d = {}
for x in range(0,n):
if not lst[x] in d:
d[lst[x]] = 1
else:
d[lst[x]] = d[lst[x]] + 1
for k in sorted(d.keys()):
print(k,end=':')
print(d[k])
# 2.二分查找
# 利用二分查找找出所给出的数在数组中的下标
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d = {}
for i in range(n):
d[a[i]] = i
res = []
for i in b:
if i in d:
res.append(str(d[i]))
print(" ".join(res))
# 3.小陈的社交网络
# 小陈近期在总结自己的朋友圈，通过一定方法，他知道了某两个人是朋友关系，为了简化统计
n, m = map(int, input().split())
# 初始化并查集数组，每个人的父节点都是自己
fa = [i for i in range(n+1)]
# 查找x的根节点
def find(x):
if x != fa[x]:
fa[x] = find(fa[x])
return fa[x]
# 合并x和y所在的朋友圈
def merge(x, y):
fx, fy = find(x), find(y)
if fx != fy:
fa[fx] = fy
# 处理已知的朋友关系
for i in range(m):
a, b = map(int, input().split())
merge(a, b)
# 统计朋友圈个数，即有多少个根节点
cnt = 0
for i in range(1, n+1):
if fa[i] == i:
cnt += 1
# 输出小陈至少还需要结交的朋友数，即朋友圈个数-1
print(cnt)
# 4.二叉树的遍历！
# 我们将给出一颗二叉树，请你输出它的三种遍历，分别是先序遍历，中序遍历，后序遍历！
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right# 递归实现先序遍历
def preorderTraversal(root):
if not root:
return []
res = [root.val]
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res# 递归实现中序遍历
def inorderTraversal(root):
if not root:
return []
res = inorderTraversal(root.left)
res += [root.val]
res += inorderTraversal(root.right)
return res# 递归实现后序遍历
def postorderTraversal(root):
if not root:
return []
res = postorderTraversal(root.left)
res += postorderTraversal(root.right)
res += [root.val]
return res# 构建二叉树
def buildTree(n, nodes):
tree = {}
for i in range(1, n+1):
tree[i] = TreeNode(i)
for i in range(n):
val, left, right = nodes[i]
if left != -1:
tree[val].left = tree[left]
if right != -1:
tree[val].right = tree[right]
return tree[1]
# 主程序
if __name__ == '__main__':
n = int(input())
nodes = [list(map(int, input().split())) for _ in range(n)]
root = buildTree(n, nodes)
print(' '.join(map(str, preorderTraversal(root))))
print(' '.join(map(str, inorderTraversal(root))))
print(' '.join(map(str, postorderTraversal(root))))
# 5.图深度优先遍历
# 编写程序对给定的有向图（不一定连通）进行深度优先遍历，图中包含n个顶点
n, e = map(int, input().split())
# 构建邻接表
adj = [[] for _ in range(n)]
for i in range(e):
a, b = map(int, input().split())
adj[a].append(b)
# 深度优先遍历函数
def dfs(v, visited):
visited.add(v)
print(v, end=' ')
for u in sorted(adj[v]):
if u not in visited:
dfs(u, visited)
# 从顶点0开始进行深度优先遍历
visited = set()
dfs(0, visited)
for i in range(n):
if i not in visited:
dfs(i, visited)
# 6.旅游规划
# 有了一张自驾旅游路线图，你会知道城市间的高速公路长度
import sys
import heapq
N, M, S, D = map(int, sys.stdin.readline().split())
# 构建邻接表
graph = {}
for i in range(M):
u, v, w, f = map(int, sys.stdin.readline().split())
if u not in graph:
graph[u] = {}
if v not in graph:
graph[v] = {}
graph[u][v] = (w, f)
graph[v][u] = (w, f)
# Dijkstra算法
dist = {S: 0}
cost = {S: 0}
heap = [(0, S)]
while heap:
d, u = heapq.heappop(heap)
if u == D:
break
if u in dist and d > dist[u]:
continue
for v in graph[u]:
w, f = graph[u][v]
if v not in dist or d + w < dist[v]:
dist[v] = d + w
cost[v] = f + cost[u]
heapq.heappush(heap, (dist[v], v))
elif d + w == dist[v] and cost[u] + f < cost[v]:
cost[v] = f + cost[u]
heapq.heapreplace(heap, (dist[v], v))
print(dist[D], cost[D])
# 7.简单计算器
# 本题要求你为初学数据结构的小伙伴设计一款简单的利用堆栈执行的计算器。
n = int(input())
nums = list(map(int, input().split()))
ops = input().split()
# 定义堆栈
S1 = []
S2 = []
# 将数字和运算符依次压入堆栈
for i in range(n):
S1.append(nums[i])
if i < n - 1:
S2.append(ops[i])
# 循环执行计算
while S2:
op = S2.pop()
n2 = S1.pop()
n1 = S1.pop()
if op == '+':
S1.append(n1 + n2)
elif op == '-':
S1.append(n1 - n2)
elif op == '*':
S1.append(n1 * n2)
elif op == '/':
if n2 == 0:
print('ERROR: {}/0'.format(n1))
exit(0)
S1.append(n1 // n2)
# 输出结果
print(S1[0])
# 8.激光陷阱 1
# 小明想安全通关一个100x100网格的激光陷阱。
list1=[[1]*100 for i in range(100)]
n=int(input())
for i in range(n):
x,y=map(int,input().split())
for j in range(100):
list1[x-1][j]=list1[j][y-1]=0
count=0
for i in list1:
count+=sum(i)
print(count)
# 9.回文素数
# 小明特别喜欢素数，但是有时分不清前后，所以请你帮助小明找出给定区间内
def prime(v):
for j in range(2,int(v**0.5)+1):
if v%j==0:
return 0
return 1
A,B=map(int,input().split())
res=[]
for i in range(A,B+1):
c=str(i)
if c==c[::-1 ]and prime(i): # 先判断回文再判断素数，因为判断回文的效率比判断素数快O(1)和O(n^0.5)
res.append(i)
print(len(res))
for i in res:
print(i)
# 10.愤怒的星期一
# 长寿的小明非常不喜欢星期一，但是如果这一天恰好是小明生日的前一周
import datetime as d
n,y,r=map(int,input().split())
beg,end=d.date(n,y,r),d.date(2022,11,17)
temp,bir=d.timedelta(1),d.timedelta(6)
count=0
while beg<=end:
try: # 异常处理排除非闰年生日是2月29日这一年都没有那七天，因为当为非闰年2月29日,日期错误d.date(beg.year,y,r)会报错
if beg.isoweekday()==1 and not (d.date(beg.year,y,r)-bir)<=beg<=d.date(beg.year,y,r): # 是星期一且不属于生日前七天的区间内
count+=1
except:
count+=1
beg+=temp
print(count)
# 11.成绩排序
# 小明成绩很差，一次考试后小明想知道自己的排名是多少，请你帮小明数一数。
n,s=map(int,input().split())
res=list(map(int,input().split()))+[s]
res.sort(reverse=True)
print(res.index(s)+1)
# 12.数的操作
# 小明在玩一个游戏，对整数列表进行三种操作。
res=list(map(int,input().split()))
for i in range(int(input())):
temp=input()
if temp[0] in "LR": # 该题头部插入和尾部插入对结果都没影响
res.append(int(temp.split()[-1]))
else:
a,b,c=temp.split()
for j in range(len(res)):
res[j]=eval(f"{res[j]}{b}{c}") # eval()函数，字符串表达式的功能
print(sum(res))
# 13.多项式的加减
# 一天数学老师想为难小明，给其布置非常多的多项式加减的作业
dic=[[0]*11 for i in range(1001)] # 使用二维列表存所有未知数且不同次的系数，外层列表索引代表不同未知数（下标不同），内层列表索引代表这个未知数的不同次。
for i in range(int(input())):
a,b,c=map(int,input().split())
dic[a][c]+=b
for i in range(int(input())):
a,b,c=map(int,input().split())
dic[a][c]+=b
for index,i in enumerate(dic):
if sum(i)==0: # 如果内层列表的和为0代表这一未知数没有出现过
continue
print(index,end='')
for j,k in enumerate(i):
if k!=0:
print('',k,j,end='')
print()
