牛客周赛 Round 130（ABCDEF）
A.红美铃的访客登记
链接：A-红美铃的访客登记_牛客周赛 Round 130
题目详情：
红美铃需要将记录访客数量的字符串（可能包含前导零，如 “009”）整理为标准正整数格式，即去掉所有无意义的前导零。
给定一个表示正整数的数字字符串 s，请输出去掉前导零后的结果。
输入描述：
一行输入一个仅由数字字符组成的字符串 s（1≤length(s)≤100），保证 s 代表的数值是正整数（1≤value(s)≤10^9）。
输出描述：
输出去掉前导零后的整数形式。
代码：
x=int(input())
print(x)B.爱丽丝的魔力零件分类
题目详情：
在 n×n 的网格中，有 4 个由*表示的魔力方块（其余为.），这些方块连接成T 型或L 型（可能经过旋转 / 翻转），需判断其类型：
-
T 型：3 个方块排成直线，第 4 个方块连接在中间方块的侧面；
-
L 型：3 个方块排成直线，第 4 个方块连接在其中一个末端方块的侧面。
输入描述：
-
第一行输入整数 T (1≤T≤100)，代表测试数据组数；
-
每组数据：
-
第一行输入整数 n (4≤n≤20)，表示网格大小；
-
接下来 n 行，每行输入一个长度为 n 的字符串（仅含
.和*），表示网格的一行；
-
-
保证网格中恰好有 4 个
*，且它们四连通（上下左右相邻），是合法的 T 型或 L 型。
输出描述：
对于每组数据，输出一行：
-
若为 T 型，输出
T； -
若为 L 型，输出
L。
代码：
def demo():
n=int(input())
aList=[]
for i in range(n):
line=list(input())
if "*" not in line:
continue
else:
aList.append(line)
bList=[(1,0),(-1,0),(0,1),(0,-1)]
len1=len(aList)
for i in range(len1):
for j in range(n):
if aList[i][j]=="*":
cList=[]
if i-1>=0:
cList.append(aList[i-1][j])
if j-1>=0:
cList.append(aList[i][j-1])
if i+1=3:
return "T"
return "L"
t=int(input())
while t:
t-=1
print(demo()) C.博丽大结界的稳定轴心
题目详情：
博丽灵梦需要维护一个由 n 个灵力节点和 n−1 条通道构成的树状结界。她需要从 n 个节点中挑选一个作为轴心（根节点），要求当树以该节点为根时，成为一棵标准的二叉树。
请你统计出所有合法的轴心节点数量。
【名词解释】
二叉树：满足以下条件的树：
-
可以是空集；若不为空，则由一个根节点以及两棵互不相交的左子树和右子树组成。
-
每个节点要么没有父节点（根节点），要么被 1 个父节点连接（子节点）。
-
每个节点连接的子节点数量要么为 0（叶子节点），要么不超过 2，且每个子节点都有明确的 “左” 或 “右” 属性。
输入描述：
-
第一行输入整数 n (1≤n≤10^5)，表示节点数量。
-
接下来 n−1 行，每行输入两个整数 ui 和 vi (1≤ui,vi≤n; ui!=vi)，表示节点 ui 和 vi 之间有一条通道。
-
保证输入的边构成一棵树。
输出描述：
输出一个整数，表示可以作为合法轴心的节点数量。
代码：
def demo():
n=int(input())
aList=[list(int(x) for x in input().split()) for _ in range(n-1)]
aDict={}
for i in range(n-1):
aDict[aList[i][0]]=aDict.get(aList[i][0],0)+1
aDict[aList[i][1]]=aDict.get(aList[i][1],0)+1
num3=0
for v in aDict.values():
if v==3:
num3+=1
elif v>=4:
return 0
return n-num3
print(demo())D.魔法人偶的十进制校准
题目详情：
爱丽丝需要构造一个最简真分数 yx，满足：
- 1≤x
- x 与 y 互质（最大公约数为 1）
- 该分数的小数展开式中，小数点后第 a 位的数字恰好为 b
请你给出一组符合条件的整数 x 和 y。
输入描述:
-
第一行输入整数 T (1≤T≤100)，代表测试数据组数；
-
每组数据输入两个整数 a 和 b (1≤a≤10^9, 0≤b≤9)，分别表示目标小数位的位置和该位应具备的数字。
输出描述:
对于每组数据，输出一行两个整数 x 和 y，表示找到的分子和分母。
代码：
def demo():
a,b=map(int,input().split())
if b==0:
if a==1:
print(1,100)
else:
print(1,10)
elif b==9:
if a%2==1:
print(10,11)
else:
print(1,11)
else:
if b==3:
print(1,3)
elif b==6:
print(2,3)
else:
print(b,9)
t=int(input())
while t:
t-=1
demo()E.爱丽丝的人偶圆舞曲
题目详情：
爱丽丝有一排人偶，每个人偶的衣服颜色用小写字母 a 到 z 表示，对应数值 0 到 25。
一个颜色序列被称为和谐的，当且仅当存在一个全局统一的步长 d (0≤d≤25)，使得序列中任意相邻两个人偶的颜色数值之差在模 26 意义下恰好为 d 或 −d。
你的任务是计算通过修改最少数量的人偶衣服颜色，使整个序列达到和谐状态所需的最小修改次数。
输入描述:
一行输入一个仅由小写英文字母组成的字符串 s (1≤length(s)≤10^5)，代表初始的人偶颜色序列。
输出描述:
输出一个整数，表示将序列变为和谐状态所需修改的最少字符数量。
代码：
def demo():
aList=[ord(x)-97 for x in input().strip()]
n=len(aList)
ans=10**9+7
for d in range(14):
dp=[1]*26
dp[aList[0]]=0
for i in range(1,n):
new_dp=[0]*26
cur=aList[i]
for j in range(26):
num=0 if cur==j else 1
new_dp[j]=min(dp[(j-d+26)%26],dp[(j+d)%26])+num
dp=new_dp
ans=min(ans,min(dp))
print(ans)
demo()F.红魔馆的微瑕序位
题目详情：
帕秋莉的魔导书现在是一个随机排列 a1,a2,…,an，定义 “混乱度” 为：S=∑i=1n∣ai−i∣当混乱度 S 恰好等于 2 时，图书馆的魔力最为稳定。
你每次可以交换任意两本书的位置，需要计算最少需要多少次交换，才能使混乱度 S=2。
输入描述：
-
第一行输入整数 T (1≤T≤2×10^5)，代表测试数据组数；
-
每组数据：
-
第一行输入整数 n (2≤n≤2×10^5)，表示魔导书的数量；
-
第二行输入 n 个两两不同的整数 a1,a2,…,an (1≤ai≤n)，表示当前的排列；
-
-
单个测试文件中所有 n 之和不超过 2×10^5。
输出描述：
对于每组数据，输出一行整数，表示使混乱度恰好为 2 所需的最少交换次数。
代码：
def demo():
n=int(input())
aList=[0]+[int(x) for x in input().split()]
id=[0]*(n+1)
cnt=0# 环的数量
for i in range(1,n+1):
if id[i]==0:
cnt+=1
cur=i
while id[cur]==0:
id[cur]=cnt# id记录为当前的环号
cur=aList[cur]
f=1
for i in range(1,n):
if id[i]==id[i+1]:
f=-1
break
print(n-cnt+f)
t=int(input())
while t:
t-=1
demo()
