T1

#include<bits/stdc++.h>
using namespace std;
const long long N=1e5+10;
long long T,n,m,k,d1[N],d2[N],c,cd,cdn,cdnl1,l,nl,dnl,cdnl2;
/*
d1[i]表示字符串a以第i个结尾的m个中有几个CDNL,d2[i]则表示b以i开头的...
c cd cdn cdnl1 分别表示a以c cd cdn cdnl1结尾的m个中最多有几个CNDL
l nl dnl cdnl2同理
-1表示不存在这种结尾/开头  注意0表示以这个结尾最多0个CDNL，而非没有这个结尾，所以会出现过不了样例的情况（数据太水了）
*/
string a,b;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--) {
        cin>>n>>m>>k>>a>>b;
        c=0,cd=0,cdn=0,cdnl1=0,l=0,nl=0,dnl=0,cdnl2=0;
        memset(d1,0,sizeof(d1));
        memset(d2,0,sizeof(d2));
        for(int i=4; i<=n; i++) {
            d1[i]=d1[i-1];
            if(a.substr(i-4,4)=="CDNL") {
                d1[i]++;
            }
            if(m<i) {
                if(a.substr(i-m-1,4)=="CDNL") {
                    d1[i]--;
                }
            }
            if(a[i-1]=='C') {
                c=max(c,d1[i]);
            }
            if(i>=2 && a.substr(i-2,2)=="CD") {
                cd=max(cd,d1[i]);
            }
            if(i>=3 && a.substr(i-3,3)=="CDN") {
                cdn=max(cdn,d1[i]);
            }
            if(i>=4 && a.substr(i-4,4)=="CDNL") {
                cdnl1=max(cdnl1,d1[i]);
            }
            //cout<<i<<' '<<d1[i]<<'\n';//c
        }
        for(int i=n-4+1; i>=1; i--) {
            d2[i]=d2[i+1];
            if(b.substr(i-1,4)=="CDNL") {
                d2[i]++;
            }
            if(i+k-1<n) {
                if(b.substr(i+k-4,4)=="CDNL") {
                    d2[i]--;
                }
            }
            if(b[i-1]=='L') {
                l=max(l,d2[i]);
            }
            if(i+1<=n && b.substr(i-1,2)=="NL") {
                nl=max(nl,d2[i]);
            }
            if(i+2<=n && b.substr(i-1,3)=="DNL") {
                dnl=max(dnl,d2[i]);
            }
            if(i+3<=n && b.substr(i-1,4)=="CDNL") {
                cdnl2=max(cdnl2,d2[i]);
            }
            //cout<<i<<' '<<d2[i]<<'\n';//c
        }
        //cout<<"c cd cdn cdnl1 l nl dnl cdnl2:"<<c<<' '<<cd<<' '<<cdn<<' '<<cdnl1<<' '<<l<<' '<<nl<<' '<<dnl<<' '<<cdnl2<<'\n';//c
        cout<<max({c+dnl+1-(!(c&&dnl)),cd+nl+1-(!(cd&&nl)),cdn+l+1-(!(cdn&&l)),cdnl1+cdnl2})<<'\n';
    }
    return 0;
}
/*
cdnlcdnl
*/

T2

/*
T2纯属分类讨论
1.不在同一直线上
    1.紧贴着：显然是1
    2.否则：显然是2，因为两条路劲只能堵一条
2.在同一直线上 显然会堵在直线上
    1.紧贴：显然是1
    2.两种走法为2：
        1.直行一段，再直接斜着到达终点 显然会直行两点距离再斜走
        2.斜走一段，拐弯斜走一段 显然会斜行两点距离/2再拐弯 需满足两点距离%2==0
        /\
       /  \
      s    t
      两种走法需满足横向有足够空间让你斜行
    3.不满足则3步
*/
#include<bits/stdc++.h>
using namespace std;
long long T,n,m,sx,sy,tx,ty,l,r,a,s,t,k;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>m>>sx>>sy>>tx>>ty;
        if(sx!=tx && sy!=ty){
            if(abs(sx-tx)==1 && abs(sy-ty)==1){
                cout<<1<<'\n';
            }else{
                cout<<2<<'\n';
            }
        }else if(sx==tx && sy==ty){
            cout<<0<<'\n';
        }else{
            //将两种情况化为一种
            if(sx==tx){
                l=1;
                r=n;
                a=sx;
                s=sy;
                t=ty;
            }else{
                l=1;
                r=m;
                a=sy;
                s=sx;
                t=tx;
            }
            //k表示侧面能够斜行的宽度
            k=max(a-l,r-a);
            if(abs(t-s)==1){
                cout<<1<<'\n';
                continue;
            }
            if(abs(t-s)%2==0){  //显然能斜行两步就不会选择直行
                if(abs(t-s)/2<=k){
                    cout<<2<<'\n';
                }else{
                    cout<<3<<'\n';
                }
            }else{
                if(abs(t-s)<=k){
                    cout<<2<<'\n';
                }else{
                    cout<<3<<'\n';
                }
            }
        }
    }
    return 0;
}

T3

/*
二分答案
对于一个答案mid，进行贪心
1.最大化利用h
对于每一个ai，填上floor( (mid-a[i])/h )块h
这样可以保证所有h不会被浪费
当然h不够用了就别用了
2.对于剩余的
    1.在前面就用完了h
        剩余的只能用1来补，全部加起来check即可
    2.前面未用完h
        显然，bi(剩余的)<h
        从大到小排列，较大的kk（前面用过后剩余的h的数量）个用h填补，剩余的加起来用1填补，check
    剩余的需要用1填补的<=m则可行
*/
#include<bits/stdc++.h>
using namespace std;
const long long N=1e5+10;
long long n,m,k,h,a[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k>>h;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
    }
    long long l=1,r=1e18,ans=0;
    while(l<=r) {
        long long mid=l+(r-l)/2,mm=m,kk=k,sumb=0;
        long long b[N];
        for(int i=1; i<=n; i++) {
            if(a[i]>=mid){
                b[i]=0;
                continue;
            }
            long long a1=min(kk,(mid-a[i])/h);
            kk-=a1;
            b[i]=mid-a[i]-a1*h;
        }
        sort(b+1,b+1+n);
        bool flag=1;
        for(int i=1;i<=n-kk;i++){
            sumb+=b[i];
            if(sumb>mm){
                flag=0;//这里注意要实时判断是否超出，不然会溢出，不要问我怎么知道的
            }
        }
        if(flag){
            l=mid+1;
            ans=mid;
        }else{
            r=mid-1;
        }
        
    }
    cout<<ans<<'\n';
    return 0;
}

T4

我不会，给点思路吧： 每一步操作实际上是把 $a_i$ 变成了 $a_{a_i}$ 与我们平时见到的不同，他这里的 $a_i$ 是会变化的 令 $aj_i$ 为第 $j$ 次变化后 $a_i$ 的值则 a3_i=a2_{a2_i}=a1_{a1_{a1_{a1_i}}}=a0_{a0_{a0_{a0_{a0_{a0_{a0_{a0_i}}}}}}}

即 $m$ 次操作相当于走了 $2^m-1$ 步 我也只能想到这儿了