小红的整数自增 
x=list(map(int,input().split()))
x.sort()
res=(x[2]-x[0])+(x[2]-x[1])
print(res)
略


小红的01串取反 
n=int(input())
s=[int(i) for i in input()]
t=[int(i) for i in input()]
res=[]
for i in range(n-1):
    if s[i]!=t[i]:
        s[i]^=1
        s[i+1]^=1
        res.append([i+1,i+2])
if s[-1]!=t[-1]:
    print(-1)
else:
    print(len(res))
    for i,j in res:
        print(i,j)
从左往右依次检查即可，遇到不同的就翻转连续的两个，最后检查末尾是否相同


小红的乘2除2 
n=int(input())
a=list(map(int,input().split()))

tot=0
for i in range(1,n):
    tot+=abs(a[i]-a[i-1])

z=0
for i in range(n):
    if a[i]%2!=0:
        b=a[i]-1
        da=db=0
        if i>0:
            da+=abs(a[i]-a[i-1])
            db+=abs(b-a[i-1])
        if i<n-1:
            da+=abs(a[i]-a[i+1])
            db+=abs(b-a[i+1])
        z=max(z,da-db)

def cal(a):
    ans=0
    for i in range(n-1):
        d=nd=0
        if i>0:
            d+=abs(a[i]-a[i-1])
            nd+=abs(a[i]//2-a[i-1])
        d+=abs(a[i]-a[i+1])
        nd+=abs(a[i]//2-a[i+1]*2)
        if i+1<n-1:
            d+=abs(a[i+1]-a[i+2])
            nd+=abs(a[i+1]*2-a[i+2])
        if d>nd:
            ans=max(ans,d-nd)
    l=[0]*n
    r=[0]*n
    for i in range(1,n):
        l[i]=l[i-1]
        d=nd=0
        if i-1>0:
            d+=abs(a[i-1]-a[i-2])
            nd+=abs(a[i-1]//2-a[i-2])
        d+=abs(a[i-1]-a[i])
        nd+=abs(a[i-1]//2-a[i])
        l[i]=max(l[i],d-nd)
    for i in range(n-2,-1,-1):
        r[i]=r[i+1]
        d=nd=0
        if i+1<n-1:
            d+=abs(a[i+1]-a[i+2])
            nd+=abs(a[i+1]*2-a[i+2])
        d+=abs(a[i+1]-a[i])
        nd+=abs(a[i+1]*2-a[i])
        r[i]=max(r[i],d-nd)
    for i in range(n):
        ans=max(ans,l[i]+r[i])
    return ans

x=cal(a)
y=cal(a[::-1])

print(tot-max(x,y,z))
由于两种操作必须都恰好进行一次，所以一共有两种情况
要么是对同一个数 整除2 乘2
这个只需要模拟一下，记录一个最大减少量即可
特别的，偶数 整除2 乘2 是不变的，所以可以跳过

要么是一个数字 整除2 ，另一个不同的数乘2
我们可以默认 是左侧的一个数 整除2，右侧的一个数 乘2
另一种镜像的 右侧的一个数 整除2，左侧的一个数 乘2，我们直接翻转数组，再调用刚刚的代码再跑一次

一个数整除2 ，一个数乘2 又要分为两种情况
一种是 i和i+1  ，另一种是i和j  (j-i>1)
对于i和i+1的情况，直接遍历一次即可
对于不相邻的两个i和j，我们可以使用前后缀分解来做
定义l[i]表示i左侧的数字使用 整除2 后的最大减少量
定义r[i]表示i右侧的数字使用 乘2 后的最大减少量

小红的伪回文子串 
from collections import Counter,defaultdict,deque

arr=input()
n=len(arr)

res=0
for L in range(1,n+1):
    res+=(n-L+1)*(L//2)

d=defaultdict(deque)
for i,a in enumerate(arr):
    d[a].append(i)

for a in list(d.keys()):
    while len(d[a])>1:
        l=d[a][0]+1
        r=n-d[a][-1]
        if l<r:
            d[a].popleft()
            res-=l*len(d[a])
        else:
            d[a].pop()
            res-=r*len(d[a])
        
print(res)
先考虑数组所有数字都不相等的情况
那么长度为1的子数组有n个，长度为2的子数组有n-1个....长度为n的数组有1个
长度为L的所有数都互不相同的子数组需要修改L//2次才能回文，遍历所有长度即可求得
再考虑一些数字会重复，有一对下标(i,j)数字重复，能构成的子串长度上限来自 1到i的距离 和 j到n的距离 取最小值 也就是 min(i-1,n-j)
我们把相同数字放一起，使用双端队列，看左侧的元素离1近还是右侧的元素离n近，谁近就弹出谁，贡献就是 最小距离*剩余相同元素个数

完全原题
E - Make it Palindrome (atcoder.jp)


小红的迷宫行走 
from heapq import  heapify,heappop,heappush
inf=1<<60

class PrimeTable:
    def __init__(self, n=int((10**9)**0.5)+3) -> None:
        self.n = n
        self.primes = []
        self.min_div = [0] * (n+1)
        self.min_div[1] = 1
 
        mu = [0] * (n+1)
        phi = [0] * (n+1)
        mu[1] = 1
        phi[1] = 1
 
        for i in range(2, n+1):
            if not self.min_div[i]:
                self.primes.append(i)
                self.min_div[i] = i
                mu[i] = -1
                phi[i] = i-1
            for p in self.primes:
                if i * p > n: break
                self.min_div[i*p] = p
                if i % p == 0:
                    phi[i*p] = phi[i] * p
                    break
                else:
                    mu[i*p] = -mu[i]
                    phi[i*p] = phi[i] * (p - 1)

    def is_prime(self, x:int):
        if x < 2: return False
        if x <= self.n: return self.min_div[x] == x
        for p in self.primes:
            if p * p > x: break
            if x % p == 0: return False
        return True

    def prime_factorization(self, x:int):
        for p in self.primes:
            if p * p > x: break
            if x <= self.n: break
            if x % p == 0:
                cnt = 0
                while x % p == 0: cnt += 1; x //= p
                yield p, cnt
        while (1 < x and x <= self.n):
            p, cnt = self.min_div[x], 0
            while x % p == 0: cnt += 1; x //= p
            yield p, cnt
        if x >= self.n and x > 1:
            yield x, 1

    def get_factors(self, x:int):
        factors = [1]
        for p, b in self.prime_factorization(x):
            n = len(factors)
            for j in range(1, b+1):
                for d in factors[:n]:
                    factors.append(d * (p ** j))
        return factors

m,n=list(map(int,input().split()))
    
pt=PrimeTable(10**5+1)

has={x:i+m*n for i,x in enumerate(pt.primes)}

a=[list(map(int,input().split())) for _ in range(m)]

g=[[] for _ in range(m*n+len(has))]

for i in range(m):
    for j in range(n):
        if i<m-1:
            g[i*n+j].append(((i+1)*n+j,1))
        if j<n-1:
            g[i*n+j].append((i*n+(j+1),1))
        for p,c in pt.prime_factorization(a[i][j]):
            g[i*n+j].append((has[p],1))
            g[has[p]].append((i*n+j,0))

def dijkstra(g, start):
    dist = [inf] * len(g)
    dist[start] = 0
    h = [(0, start)]
    while h:
        d, x = heappop(h)
        if d > dist[x]:
            continue
        for y, wt in g[x]:
            new_d = dist[x] + wt
            if new_d < dist[y]:
                dist[y] = new_d
                heappush(h, (new_d, y))
    return dist
            
dij=dijkstra(g,0)
print(dij[m*n-1])
两个点如果不互质，两点连一条1权边
给定的n*m=500*500=2e5，暴力连边肯定爆了，这个时候需要虚拟节点优化建图
不互质的本质其实就是至少有一个相同质因子
我们只需要对每一个质因子都开一个虚拟节点
每个点向自己所有的质因子连一条1权边，然后反过来连一条0权边
这样所有点移动到图中任意一个不互质的点都只需要1边权的代价了
然后建个图跑dij就可以了
其实只有0和1边权的图是可以跑01bfs的，复杂度更优

一道同样是用质因子做虚拟节点的题