T1

双休在家的凯凯真的是太无聊了，他准备和他家的猫玩一个游戏。
凯凯随手写下一串01数列，定义这串数列的子串和为所有长度为2的子串的和。比如数列=010001，有如下长度为2的子串：
01 （前导0， =1）
10
00 （前导0，=0）
00 （前导0，=0）
01 （前导0，=1）
所以和为1+10+0+0+1 = 12

如果要只是算子串和的话，那对喵喵来说实在是太简单了，所以凯凯准备加大难度。
喵喵有k次机会可以交换数列里的相邻两个数（可以不用完这k次机会），使得交换完之后子串和最小。
这下喵喵不会做了，你可以帮帮它么？

输入为先输入一个t，代表t组。然后分别是n、k，字符串。
input:
3
4 0
1010
7 1
0010100
5 2
00110

output:
21
22
12

分析字符串中每一个1，只有3种情况：

• 出现在字符串首部，贡献为10
• 出现在字符串中央，贡献为11
• 出现在字符串末尾，贡献为01

那么只需要考虑能不能把1换到头尾就好了。

for _ in range(int(input())):
    n,k=list(map(int,input().split()))
    s=input()
    n1=s.count('1')
    if n1==0:
        print(0)
        continue

    ans=n1*11
    ri=s.rindex('1')
    rneed=(n-1-ri)
    if k>=rneed:
        k-=rneed
        ans-=10

        # 后面交换成功了
        if n1==1:
            print(1)
            continue
        else:
            lneed=s.index('1')
            if k>=lneed:
                ans-=1
            print(ans)
    else:
        lneed=s.index('1')
        if k>=lneed:
            ans-=1
        print(ans)

T2

第一行输入两个整数n和m，表示迷宫的长和宽。
接下来n行，每行m 个字符， 用于描述迷宫构造，每个字符可能为以下几种：
.表示空地， 玩家在空地时可以选择往 [上，下，左，右] 中的某个方向移动一格
U，D，L，R 分别表示朝向[上，下，左，右] 的传送带，站在传送带上的人会被强制移动到其指向的下一个位置
如果下一个位置还是传送带，会被继续传下去
如果传送带指向迷宫外，玩家会撞在墙上，昏过去，游戏结束，无法再到达出口
O表示迷宫出口

请你找到有多少点按照规则行走不能到达终点。

n<1e5，m<1e5，n*m<1e5
input:
5 5
.....
.RRD.
.U.DR
.ULL.
....O

output:
10

思路来自于一个银牌佬，反向思考，把传送带视为一个单向板。从终点反向遍历，假设你处于一个空地上，你左侧的点只有为R的时候才可以从你这个位置到达R那个位置，然后查找地图上所有O的数量。n*m-count(O)即可。

之前写的深搜思路有问题，已删除。

from collections import deque

n,m=list(map(int,input().split()))
g=[list(input()) for _ in range(n)]
ex,ey=-1,-1
for i in range(n):
    for j in range(m):
        if g[i][j]=='O':
            ex,ey=i,j
            break
    if ex!=-1:break
q=deque([(ex,ey)])
while q:
    x,y=q.popleft()

    # up
    if x-1>=0 and g[x-1][y] in 'D.':
        q.append((x-1,y))
        g[x-1][y]='O'

    # down
    if x+1<n and g[x+1][y] in 'U.':
        q.append((x+1,y))
        g[x+1][y]='O'


    # left
    if y-1>=0 and g[x][y-1] in 'R.':
        q.append((x,y-1))
        g[x][y-1]='O'


    # right
    if y+1<m and g[x][y+1] in 'L.':
        q.append((x,y+1))
        g[x][y+1]='O'

onum=sum(line.count('O') for line in g)
print(n*m-onum)

T3

在广告平台中，为了给广告主一定的自由性和效率，允许广告主在创造标题的时候以通配符的方式进行创意提交。线上服务的时候，会根据用户的搜索词触发的bidword对创意中的通配符（通配符是用成对{}括起来的字符串）进行替换（用0个或者多个字符替换通配符），用来提升广告投放体验。例如：{末日血战}，上线送SSR英雄，三天集鲚无敌阵容！”，会被替换成“帝国时代下载上线送SSR英雄，三天集齐无敌阵容！”。给定一个含有通配符的创意和一句标题，判断这句标题是否从该创意替换生成的。

输入一个n，有n个标题。第一行是带有通配符的创意，下面n行是所有标题。对于每一行标题，如果可以用通配符匹配，输出True否则输出False。

input:
4
ad{XYZ}cdc{Y}f{x}e
adcdcefdfeffe
adcdcefdfeff
dcdcefdfeffe
adcdcfe

output:
True
False
False
True

普通回溯，注意记录每一个通配符的对应字符串。不是自己的场，没时间写了。

T4

小明和小红在玩摇骰子游戏，每个骰子有固定的面数k（2<=k<=8）,每一面对应的点数分别为1,2,.…,k。
小明有n（1<=n<=20）个骰子，对于骰子i（1<=i<=n），它的面数为a_i(2<=a_i<=8),摇到每一面的概率都是1/a_i。
小红有m（1<=m<=20）个骰子，对于骰子j（1<=j<=m），它的面数为bj(2<=bj<=8),摇到每一面的概率都是1/bj。
小明和小红分别摇各自拥有的全部骰子，然后把骰子朝上那一面的点数相加，最后比较谁的点数和最大，大的获胜，相同平手，小的获败。小明和小红只摇一把，平手不会继续重摇，小明想知道他获胜的概率，你能帮帮他吗？

输入n、m。然后输入n个骰子和m个骰子
输出获胜概率，保留小数点后3位

input:
1 3
8
2 3 4

output:
0.255

对于小明，维护一个数组A：A[i]代表小明获得i点的方案数。小红同理。那么假设小明获到i点，需要小红获取到1~i-1点才可以让小明获胜，利用维护的上面这个数组来计算获胜的方案数和总方案数。

如何计算这个数组？考虑还没有扔骰子的情况，那么只有一种方案，那就是什么都不扔，只能得到数字0，且方案数为1。那么开始扔第一个骰子，假设这个骰子有k个面，根据第一种方案，使用这个骰子可以获得1~k点，且每一种都是1种方案。
在扔第二个骰子的时候，假设这个骰子点数有k个面，在扔一个骰子的方案数的基础上。假设扔一个骰子可以获得i分，那么可以通过这个i分获取到：i+1、i+2、...、i+k分。以此类推。具体可以在代码中看。

本题代码没有过100%，只过了85%，如果大佬看出问题希望在评论区留言指正，感激不尽

n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
b=list(map(int,input().split()))

ac=sum(a)
fa=[0]*(ac+1)
fa[0]=1
for i in a:
    ga=[0]*(ac+1)
    for j in range(ac+1):
        if not fa[j]:continue
        for k in range(1,i+1):
            ga[j+k]+=fa[j]
    fa=ga


bc=sum(b)
fb=[0]*(bc+1)
fb[0]=1
for i in b:
    gb=[0]*(bc+1)
    for j in range(bc+1):
        if not fb[j]:continue
        for k in range(1,i+1):
            gb[j+k]+=fb[j]
    fb=gb

can=0
j=0
cj=0
for i in range(ac+1):
    while j<i and j<=bc:
        cj+=fb[j]
        j+=1
    can+=fa[i]*cj
tot=sum(fa)*sum(fb)

print(round(can/tot,3))