选O(max(n,m))
选第二个，shell附带选项和参数两者shell命令都可以带
不会
编程题1：小红的字符生成
题目描述
小红每次可以把一个字符编程两个字母表中比它小一位的字符，例如可以把'b'变成两个'a'，可以把'z'变成两个'y'。
小红希望最终可以生成x个'a'，你能帮小红求出初始的字符串吗？请你输出最短的合法字符串，有多解时输出任意即可。
输入描述
一个正整数x，代表最终'a'的数量
1<=x<=1000
输出描述
一个字符串，代表小红操作前的字符串。如果有多个合法解，输出任意一个合法字符串即可。但需要保证输出的是最短字符串。
示例1
输入
5
输出
ca
说明
'ca'->'bba'->'aaaaa'
输出ac也是可以的
x = int(input())
word = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'g', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
word_cont = []
word_num = len(word)
num = 1
for _ in range(len(word)):
word_cont.append(num)
num *= 2
# print(word_cont)
res = []
while x>0:
idx = None
for i in range(word_num-1, -1, -1):
if x>=word_cont[i]:
idx = i
break
res.append(word[idx])
x -= word_cont[idx]
print(''.join(res))
编程题2：树上节点
题目描述
给定一课根为1号节点的树，每个节点初始的权值为1.现在每次可以选择一个节点，使得其子树所有节点的权值加1，请问最少多少次操作可以使得每个节点的权值等于它的编号？
输入描述
第一行输入一个正整数n，代表树上的节点数量。
接下来的n-1行，每行输入两个正整数u和v，代表u号节点和v号节点有一条边相连。
2<=x<=100000
1<=u,v<=n
输出描述
一个整数，代表最小的操作次数
示例1
输入
3
1 2
1 3
输出
3
说明
第1次选择编号为2的子树。
第2次选择编号为3的子树。
第3次选择编号为3的子树。
说明：有两个坑，一是需要考虑输入的边是双向的，使用一个数组去标记是否访问过；二是需要考虑父节点的编号大于子节点，这样永远无法实现题目的情况，没有答案，输出-1。
# 第一种写法，自己建树，就是写起来比较麻烦
class TreeNode:
def __init__(self, order, num=1):
self.order = order
self.num = num
self.childs = []
n = int(input())
d = {}
for _ in range(n-1):
u, v = map(lambda x: int(x), input().split())
if u in d:
u_node = d[u]
else:
u_node = TreeNode(u, 1)
if v in d:
v_node = d[v]
else:
v_node = TreeNode(v, 1)
u_node.childs.append(v_node)
v_node.childs.append(u_node)
d[u] = u_node
d[v] = v_node
vis = [True]+[False]*n
def dfs(node: TreeNode, num: int):
global count
vis[node.order] = True
cnt = 0
add_num = 0
add_num += node.order - num - node.num
cnt += add_num
if add_num<0:
return -1
if len(node.childs)==0:
return 0
for ch in node.childs:
if not vis[ch.order]:
ch_cnt = dfs(ch, num+add_num)
if ch_cnt<0:
return -1
cnt += ch_cnt
return cnt
root = d[1]
print(dfs(root, 0))
# 简化版，使用列表模拟树
n = int(input())
nodes = [[] for _ in range(n+1)]
for _ in range(n-1):
u, v = map(lambda x: int(x), input().split())
nodes[u].append(v)
nodes[v].append(u)
vis = [True]+[False]*n
def dfs(order, num: int):
vis[order] = True
cnt = 0
add_num = 0
add_num += order-num-1
cnt += add_num
if add_num<0:
return -1
for ch_order in nodes[order]:
if not vis[ch_order]:
ch_cnt = dfs(ch_order, num+add_num)
if ch_cnt<0:
return -1
cnt += ch_cnt
return cnt
print(dfs(1, 0))
编程题3：小红的好串
题目描述
小红定义一个字符串是好串，当且仅当只有一个字符串出现的次数为奇数，其它字母均为偶数。
小红拿到了一个字符串，她想知道该字符串有多少子串是好串？
子串的定义：一个字符串取一段连续的区间得到的字符串。例如“arcaea”的子串，有“arc”、“ca”等，但“ara”则不是它的子串。
输入描述
一个长度不超过200000的、仅由小写字母组成的字符串。
输出描述
好子串的数量。
示例1
输入
ababa
输出
9
说明
所有长度为1、3、5个子串均为好子串。共有9个好子串。
leetcode简单变形题：1915 https://leetcode.cn/problems/number-of-wonderful-substrings/
# 不会：前缀异或和
from collections import defaultdict
data = input()
freq = defaultdict(int)
freq[0] = 1
ans = 0
mask = 0
for ch in data: # 遍历所有的字符
idx = ord(ch)-ord('a') # 计算字符索引
mask ^= (1<<idx) # 计算到当前字符所有字符的掩码
for i in range(26): # 总共26位
mask_pre = mask^(1<<i) # 计算某一位出现次数为奇数，其它为出现次数为偶数的数量
ans += freq[mask_pre] # 获取变位后数量
freq[mask] += 1
print(ans)
