写在前面：
用倍增优化的动态规划算法求解问题时，一般分为两部分，第一部分是预处理，用阶段成倍增长的DP，计算出若干与2的整数次幂相关的代表状态。第二部分是拼凑，基于二进制拆分思想，用上一部分得到的代表状态组合成最终答案。

一、P1081 开车旅行：
题目描述
小 A 和小 B 决定利用假期外出旅行，他们将想去的城市从 1到 N 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 i的海拔高度为Hi，城市 i和城市 j之间的距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值，即d[i,j]=|Hi - Hj|

旅行过程中，小 A和小 B 轮流开车，第一天小 A 开车，之后每天轮换一次。他们计划选择一个城市 S 作为起点，一直向东行驶，并且最多行驶 X 公里就结束旅行。小 A 和小 B的驾驶风格不同，小 B总是沿着前进方向选择一个最近的城市作为目的地，而小 A总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 X 公里，他们就会结束旅行。

在启程之前，小 A想知道两个问题：

对于一个给定的 X=X0，从哪一个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小（如果小 B 的行驶路程为 0，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 A 开车行驶的路程总数与小 B行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
对任意给定的 X=Xi 和出发城市 Si，小 A 开车行驶的路程总数以及小 B行驶的路程总数。
输入格式
第一行包含一个整数 N，表示城市的数目。

第二行有 N个整数，每两个整数之间用一个空格隔开，依次表示城市 1 到城市 N的海拔高度，即 H1,H2,…,Hn，且每个 Hi都是不同的。
第三行包含一个整数 X0。
第四行为一个整数 M，表示给定 M组 Si和 Xi。

接下来的 M 行，每行包含 2 个整数 Si和 Xi，表示从城市 Si出发，最多行驶 Xi 公里。

输出格式
输出共 M+1 行。

第一行包含一个整数 S0 ，表示对于给定的 X0，从编号为 S0的城市出发，小 A开车行驶的路程总数与小 B 行驶的路程总数的比值最小。

接下来的 M行，每行包含 2 个整数，之间用一个空格隔开，依次表示在给定的 Si和Xi 下小 A 行驶的里程总数和小 B 行驶的里程总数。

输入输出样例
输入 #1 复制
4
2 3 1 4
3
4
1 3
2 3
3 3
4 3
输出 #1 复制
1
1 1
2 0
0 0
0 0
输入 #2 复制
10
4 5 6 1 2 3 7 8 9 10
7
10
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7
输出 #2 复制
2
3 2
2 4
2 1
2 4
5 1
5 1
2 1
2 0
0 0
0 0

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int maxn=100100;
// 0 A
// 1 B
int f[maxn][20][2],nt[maxn][2],h[maxn];
ll da[maxn][20][2],db[maxn][20][2];
ll la,lb,maxa,maxb;
int n,m,x0,xi,si,ans,t;

struct node
{
    int id,hi;
    node(){}
    node(int a,int b)
    {
        id=a,hi=b;
    }
    friend bool operator <(const node &a,const node &b)
    {
        return a.hi<b.hi;
    }
};

struct nn
{
    int id;
    int dis;
    int hi;
    nn(){}
    nn(int a,int b,int c)
    {
        id=a,dis=b,hi=c;
    }
    friend bool operator <(const nn &a,const nn &b)
    {
        if(a.dis!=b.dis) return a.dis<b.dis;
        else return a.hi<b.hi;
    }
}_nt[10];

set<node>se;
set<node>::iterator it,lit,rit;


void get_dis(int si,int xi)
{
    la=lb=0;
    for(int i=t;i>=0;i--)
    {
        if(f[si][i][0]&&da[si][i][0]+db[si][i][0]<=xi)
        {
            xi-=da[si][i][0]+db[si][i][0];
            la+=da[si][i][0],lb+=db[si][i][0];
            si=f[si][i][0];
        }
    }
}



int main(void)
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&h[i]);
    }

    node res;
    for(int i=n;i>0;i--)
    {
        res=node(i,h[i]);
        se.insert(res);
        it=se.find(res);
        lit=rit=it;
        int cnt=0;
        if(lit!=se.begin()) lit--,_nt[++cnt]=nn(lit->id,abs(h[lit->id]-h[i]),h[lit->id]);
        if(lit!=se.begin()) lit--,_nt[++cnt]=nn(lit->id,abs(h[lit->id]-h[i]),h[lit->id]);
        if(rit++,rit!=se.end()) _nt[++cnt]=nn(rit->id,abs(h[rit->id]-h[i]),h[rit->id]);
        if(rit!=se.end()) if(rit++,rit!=se.end()) _nt[++cnt]=nn(rit->id,abs(h[rit->id]-h[i]),h[rit->id]);
        sort(_nt+1,_nt+cnt+1);

        if(cnt) nt[i][1]=_nt[1].id;
        if(cnt>=2) nt[i][0]=_nt[2].id;
    }

    for(int i=1;i<=n;i++)
    {
        if(nt[i][0]) f[i][0][0]=nt[i][0],da[i][0][0]=abs(h[nt[i][0]]-h[i]),db[i][0][0]=0;
        if(nt[i][1]) f[i][0][1]=nt[i][1],da[i][0][1]=0,db[i][0][1]=abs(h[nt[i][1]]-h[i]);
    }

    t=log2(n);
    for(int j=1;j<=t;j++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int k=0;k<=1;k++)
            {
                int cm=0;
                if(j==1) cm=k^1;
                else cm=k;

                if(f[i][j-1][k]) f[i][j][k]=f[f[i][j-1][k]][j-1][cm];
                if(f[i][j][k])
                {
                    da[i][j][k]=da[i][j-1][k]+da[f[i][j-1][k]][j-1][cm];
                    db[i][j][k]=db[i][j-1][k]+db[f[i][j-1][k]][j-1][cm];
                }
            }
        }
    }

    scanf("%d",&x0);
    maxa=1,maxb=0;
    ans=0;
    for(int i=1;i<=n;i++)
    {
        get_dis(i,x0);
        if(!lb) la=1;
        if(maxa*lb>maxb*la||maxa*lb==maxb*la&&h[i]>h[ans]) maxa=la,maxb=lb,ans=i;
    }

    printf("%d\n",ans);

    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&si,&xi);
        get_dis(si,xi);
        printf("%lld %lld\n",la,lb);
    }
    return 0;
}

二、ACWing 294. 计算重复：
定义 conn(s,n) 为 n 个字符串 s 首尾相接形成的字符串，例如：

conn(“abc”,2)=”abcabc”
称字符串 a 能由字符串 b 生成，当且仅当从字符串 b 中删除某些字符后可以得到字符串 a。

例如“abdbec”可以生成“abc”，但是“acbbe”不能生成“abc”。

给定两个字符串 s1 和 s2，以及两个整数 n1 和 n2，求一个最大的整数 m，满足conn(conn(s2,n2),m) 能由 conn(s1,n1) 生成。

输入格式
输入包含多组测试数据。

每组数据由2行组成，第一行包含s2,n2，第二行包含s1,n1。

输出格式
对于每组数据输出一行表示答案m。

数据范围
s1 和 s2 长度不超过100，n1 和 n2 不大于 106。

输入样例：
ab 2
acb 4
acb 1
acb 1
aa 1
aaa 3
baab 1
baba 11
aaaaa 1
aaa 20
输出样例：
2
1
4
7
12
这题数据好像有问题，scanf会多输出一个0，可能是最后多了一个单组的样例？

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int maxn=100100;
char str1[108],str2[108];
int n1,n2;
ll f[108][32];

void solve()
{
        int len1=strlen(str1);
        int len2=strlen(str2);
        for(int i=0;i<len1;i++)
        {
            int pos=i;
            f[i][0]=0;
            for(int j=0;j<len2;j++)
            {
                int cnt=0;
                while(str1[pos]!=str2[j])
                {
                    pos=(pos+1)%len1;
                    cnt++;
                    if(cnt>=len1)
                    {
                        printf("0\n");
                        return ;
                    }
                }
                pos=(pos+1)%len1;
                f[i][0]+=cnt+1;
            }
        }

        for(int j=1;j<=30;j++)
        {
            for(int i=0;i<len1;i++)
                f[i][j]=f[i][j-1]+f[(i+f[i][j-1])%len1][j-1];
        }

        ll maxx=0;
        for(int i=0;i<len1;i++)
        {
            ll res=i,ans=0;
            for(int j=30;j>=0;j--)
            {
                if(res+f[res%len1][j]<=len1*n1)
                {
                    res+=f[res%len1][j];
                    ans+=1<<j;
                }
            }
            maxx=max(maxx,ans);
        }
        printf("%lld\n",maxx/n2);
}

int main(void)
{

    while(cin>>str2>>n2>>str1>>n1)
    {
        solve();
    }
    return 0;
}