不是自己的场，所以不太认真，有问题的话大家可以随时私聊我。

T1

小红拿到了两个正整数a和b，她每次操作可以选择其中个正整数，删除个数位。例如，对于"1243"而言，进行一次操作可以生成"124"、"123"、 "143"或"243"。
小红希望最终a是b的倍数或者b是a的倍数。她想知道自己最少的操作次数是多少？
输入2个数a b，其中a,b<=1e9
输出最少的操作次数。

input:
1234 99

output:
2

思路：
1e9以内的数长度在10位以内，考虑某一个数字进行操作可以生成的所有的子项，顶多生成2^10=1024个。那么遍历两个数字可以生成的子集，总组合数不会超过1e6。

from collections import defaultdict

a,b=input().split()
inf=float('inf')
def getmap(s):
    n=len(s)
    mp=defaultdict(lambda:inf)
    for i in range(1,1<<n):
        price=0
        cnt=0
        for j in range(n):
            if (i&(1<<j))==0:
                price+=1
            else:
                cnt=cnt*10+int(s[j])
        mp[cnt]=min(mp[cnt],price)
    return mp


amap=getmap(a)
bmap=getmap(b)
ans=inf
for i,v1 in amap.items():
    for j,v2 in bmap.items():
        if i%j==0 or j%i==0:
            ans=min(ans,v1+v2)
print(ans if ans != inf else -1)

T2

嘤嘤觉得长城很美 ，特别是它的锯齿， 非常的优雅！
现在有一个数组，嘤嘤想把这个数组变成"长城"，即对于"长城"中每 一个元 素左右两边的元素相等，并且与它不相等。例如[2，1，2，1，2，1，2），（1，9，1，9}是长城，{2，1，3，2，4，1，4，4，4，4）则不是长城。
你每次可以将一个元素加一，请问最少需要几次操作？

输入n和n个正整数。其中n<=2e5，ai<=1e9。

input:
6
1 1 4 5 1 4

output:
11

不难看出，最终序列中，奇数下标的所有数字都相同，偶数下标的数字也相同。
因为只能进行+1操作，那么数字只能上升到对应位置的最大值，统计最大值就好了。注意处理一下最大值相同的状况。

n=int(input())
a=list(map(int,input().split()))
mv=[0,0]
for i,v in enumerate(a):
    mv[i&1]=max(mv[i&1],v)
ans=0
for i,v in enumerate(a):
    ans+=mv[i&1]-v
if mv[0]==mv[1]:
    ans+=n//2
print(ans)

T3

小红拿到了一个仅由r'、'e'、'd'组成的字符串， 她定义一个字符'e'为"好e"当 且仅当这个'e'字符既和r相邻也和'd'相邻。 例如"reeder"只有一个"好e"，前 两个'e'都不是"好e"，只有第三个'e'是"好e"。
小红每次可以修改一个字符（可以将任意字符修改）为任意字符，即三种类型的字符可以相互修改） ，她希望最终"好e"的数量尽可能多。小红想知道，自己最少要修改多少次？
输入一个只有red三中字符的字符串，长度<2e5。
输出最小修改次数

input:
derrd

output:
1

这题太麻烦了不想写了……说下思路。

首先考虑奇数：目标字符串必然是redered 或者dereder。e的出现位置必然是奇数下标，偶数下标的值只有2种组成情况，看这2个组成的字符串和目标字符串的diff即可。

偶数比较麻烦。首先考虑偶数情况下的2种极端情况（我先将非e的字符写成x，以便统一）：

1. xexex*
2. *xexex

为什么这两种特殊？因为里面有个，这个出现什么都可以，不用处理，相当于删了个字符用奇数的方案来处理。

然后考虑不能删除字符的情况。考虑到一个分割点，将字符串分割成：xex | xexex这种形态。为什么是这种形态呢？首先可以看到两侧的出现次数都是奇数，奇数的情况下组合序列必然唯一。
可以分割成多少种这种形态呢？可以枚举分割点，我们只需要使用一个前缀和和后缀和来维护前面的代价：
设定数组pre，pre[i]代表将[0..i]处理成形态为xexex的最小代价。
设定数组suf，suf[i]代表将[i..n)处理成形态为xexex的最小代价，注意这里是后缀，从后往前。

那么枚举所有的分割点（分割点前必然是偶数），ans=min(ans, pre[i]+suf[i+1])
注意我将原题中的字符转化为了x，x可能为r可能为d，所以一种xexexex其实是对应两种形态，注意处理。

因为不是自己的笔试……不想写了，太难了。

T4

小红拿到了一个数组 a1....an，她想知道有多少组（i, j, k）为"v三元组"：第一个数和第三个数相等。且第一个数大于第二个数。
用数学语言描述：
1<=i<j<k<=n 且 ai==ak 且 ai>aj
输入n<1e5， ai<=1e9。

input:
6
3 1 3 4 3 4

output:
3

思路：
先考虑暴力：计算某一个位置的贡献，遍历所有它左侧左右比它大的数的出现次数，乘以所有它右侧比它大的数的出现次数。比如：2221222，1左侧有3个2，右侧有3个2，贡献将为9。
转化问题：对于一个位置，求一个数左侧和右侧出现相同的数字的组合。那么利用前缀和的思想，只需要看某个数字左侧有多少数字比它大，右侧有多少数字比它大，维护其出现次数的乘积就可以了。
假设当前遍历到了i位置，设定数组l，l[x]代表在[0..i)之中，x的出现次数。设定数组r，r[x]代表(i..n-1]中x的出现次数。那么再利用一个树状数组维护相同数字的乘积即可。

实现技巧：因为ai<=1e9，树状数组没法直接跑，要离散化
实现技巧：可以数字排倒序然后离散化，将问题转化为求比某数字小的组合。

n=int(input())
a=list(map(int,input().split()))
s=sorted(set(a),reverse=True)
mp={v:i for i,v in enumerate(s,start=1)}
a=[mp[i] for i in a]
maxv=100010
tree=[0]*maxv
l=[0]*100010
r=[0]*100010

def add(i,x):
    while i<maxv:
        tree[i]+=x
        i+=i&-i

def get(i):
    ans=0
    while i:
        ans+=tree[i]
        i-=i&-i
    return ans

for i in a:r[i]+=1

ans=0

for i in a:
    ans+=get(i-1)
    add(i,-l[i]*r[i])
    l[i]+=1
    r[i]-=1
    add(i,l[i]*r[i])
print(ans)