A

模拟

检查字母按字典序升序，出现次数是否是一个公差为1的数列

void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    map<char,int>mp;
    for(char c:s){
        mp[c]++;
    }
    bool ok=1;
    int pre=-1;
    for(auto &[k,v]:mp){
        if(v!=pre+1&&pre!=-1){
            ok=0;
        }
        pre=v;
    }
    if(ok)cout<<"YES\n";
    else cout<<"NO\n";
}

B

枚举

检查是否存在一个，是合数

枚举，试除法检查是否为合数即可

void solve(){
    int n;
    cin>>n;
     
    rep(i,1,n-1){
        int t=n^i;
        rep(j,2,sqrt(t)){
            if(t%2==0){
                cout<<i<<'\n';
                return;
            }
        }
    }
    cout<<-1<<'\n';
}

C

构造 数论

构造一个排列，相邻元素的的和，是个偶数

一个很有用的性质是，恒成立，所以如果排列长度为奇数，直接，和就是偶数了

如果长度为偶数，按这个构造和是奇数，那么交换任意一对相邻元素就是偶数了

void solve(){
    int n;
    cin>>n;
    if(n==2)cout<<-1<<'\n';
    else{
        if(n%2){
            rep(i,1,n){
                cout<<i<<' ';
            }
            cout<<'\n';
        }
        else{
            rep(i,1,n-2){
                cout<<i<<' ';
            }
            cout<<n<<' '<<n-1<<'\n';
        }
    }
}

D

倍增 贪心

每次可以选择一个子序列，复制每个元素接在对应元素后面，也就是这样

问把输入序列变成目标序列的最少操作次数

先看能否变成目标序列。我们把每一个相同字符组成的子区间看成一段，用这一段的字母和长度表示，初始和目标序列的每一段，字母必须都相同，且初始长度不超过目标长度，才能通过操作变成目标序列

把两个序列按这个思路进行压缩，得到两个二元组序列，就能判断了

接下来看最少操作次数。对于两个序列相互对应的一段，想变成一样的，实际上就是把初始长度，每次可以加上不超过，问最少几次可以变成，显然最优的是一直倍增，直到下一次倍增就超过了，那么最后这次不倍增，而是加上，操作次数就是

每次可以操作一个子序列，那么我们可以同步操作多个段，瓶颈在于需要次数最多的那个段，对每一段的操作次数取即可

void solve(){
    int n,m;
    cin>>n>>m;
    vi a(n+1),b(m+1);
    rep(i,1,n)cin>>a[i];
    rep(i,1,m)cin>>b[i];
     
    int len=0;
    vvi c,d;
    rep(i,1,n){
        if(i!=1&&a[i]!=a[i-1]){
            c.push_back({a[i-1],len});
            len=1;
        }
        else{
            len++;
        }
    }
    c.push_back({a[n],len});
    len=0;
    rep(i,1,m){
        if(i!=1&&b[i]!=b[i-1]){
            d.push_back({b[i-1],len});
            len=1;
        }
        else{
            len++;
        }
    }
    d.push_back({b[m],len});
    len=0;  
     

    if(c.size()!=d.size()){
        cout<<-1<<'\n';
        return;
    }
     
    n=c.size();
     
    int ans=0;
    rep(i,0,n-1){
        if(c[i][0]!=d[i][0]||c[i][1]>d[i][1]){
            cout<<-1<<'\n';
            return;
        }
        ans=max(ans,(int)ceil(log2(1.0*d[i][1]/c[i][1])));
    }
    cout<<ans<<'\n';
}

E

数论乱搞

对每个元素，找到一个不能整除它的另一个元素，输出下标

整除一个重要的性质是，，那么，也就是如果能整除，肯定不超过被除数的一半，反之，一定大于被除数的一半的一定不能整除。

然后这个问题其实原始序列的顺序不重要，是一个从集合里选数的过程，只要记录每个数原始下标即可。所以考虑排序，可能会得到一些很好的性质。

排序后就可以发现，可能整除的一定在前面，并且实际上从往前枚举就可以，很快就会出现不能整除的。

这是对的是因为：

如果枚举到一个，根据前面的结论就直接找到答案了。

如果，且能整除，那么这些需要指数速度减小，因为能整除的是很稀疏的，不能整除的是很稠密的，如果不是指数级减小，而是这样减小，很快就会遇到一个不能整除的，就结束了。而以指数级减小，只会有项就变成了，就结束了，那么就无解。所以要么很快的减小，一直找不到，然后无解，要么减小的很慢，然后很快就找到一个解，都不会往前枚举太多位。

唯一的问题是可能出现并且前面出现多次，导致枚举多次。这其实也很好解决，我们排序后去重。。把每个值当成一个桶，它的所有出现下标都放进这个桶里，每次一块处理答案

void solve(){
    int n;
    cin>>n;
    vi a;
    map<int,vi>mp;
    rep(i,1,n){
        int x;
        cin>>x;
        a.push_back(x);
        mp[x].push_back(i);
    }
     
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());
     
    vi ans(n+1);
    rep(i,0,a.size()-1){
        if(i==0){
            for(int pos:mp[a[i]]){
                ans[pos]=-1;
            }
        }
        else{
            int j;
            for(j=i-1;j>=0;j--){
                if(a[j]*2>a[i]){
                    for(int pos:mp[a[i]]){
                        ans[pos]=mp[a[j]][0];
                    }
                    break;
                }
                else{
                    if(a[i]%a[j]){
                        for(int pos:mp[a[i]]){
                            ans[pos]=mp[a[j]][0];
                        }
                        break;
                    }
                }
            }
            if(j==-1){
                for(int pos:mp[a[i]]){
                    ans[pos]=-1;
                }
            }
        }
    }
     
    rep(i,1,n){
        cout<<ans[i]<<' ';
    }
    cout<<'\n';
}

F

计数dp 斐波那契 求补集

从里选个数，问他们中至少存在三个数，能组成三角形的概率？

古典概型，先转化成方案数/总方案数

至少存在很多时候很难做，可以考虑转化成全集-补集，也就是总方案数-不存在的方案数。也就是有很多情况，但是就一种情况，往往更好做。

问题转化成选出来个数，不存在三个数能组成三角形，也就是对于所有三个元素的组合，都有

但这个所有三元素，还是不好dp+y<=z$的，一定是相邻的三个元素，如果所有长度为三的子数组都满足了，其它三元组一定也满足。

所以转化成在里选一个长为的子序列，满足所有长度为三的子区间，都有

这就是一个经典子序列了，状态里记录选中的子序列的最后两个元素下标，就能转移时判断是否满足条件了。

然后还有长度为的宇约束，状态里还需要记录子序列长度，这看起来状态数就了，但本题的复杂度应该最多允许？

注意到根据这个条件，实际上合法的子序列的增长比斐波那契数列还快，所以子序列最多项，更长的是不可能的。所以长度这个维度大概开就行，的询问，选中的所有子序列都是不合法的，一定不满足，也就是一定有，对于原问题，也就是方案数等于总方案数，概率为1

对于的询问，我们开始时预处理表示长度为，值域为的方案数，也就是先让记录长度为，最后一个元素为的方案数，然后再对于每个做前缀和。回答时查询

，转移时，外层枚举长度，内层枚举新增元素，和已选中的最后一个元素，此时可以确定已选中的倒数第二个元素的范围了，一定有，且，故。可以从转移过来。这是个区间，考虑前缀和优化，记录最后一个元素为，倒数第二个元素下标在范围内的方案数之和

int sum[N][N],ans[N][N];
void pre(){
	vvi dp(N,vi(N)),ndp(N,vi(N));
	int n=1500;
	rep(i,1,n){
		rep(j,1,i-1){
			dp[i][j]=1;
		}
	}
	rep(i,3,17){
		rep(j,1,n){
			rep(k,1,j-1){
				sum[j][k]=(sum[j][k-1]+dp[j][k])%M2;
			}
		}
		
		
		rep(j,1,n){
			rep(k,1,j-1){
				int p=min(k-1,j-k);
				ndp[j][k]=sum[k][p];
			}
		}
		
		swap(dp,ndp);
		rep(j,1,n){
			ans[i][j]=ans[i][j-1];
			rep(k,1,j-1){
				ans[i][j]+=dp[j][k];
				ans[i][j]%=M2;
			}
		}
	}
}
void solve(){
	int n,m;
	cin>>n>>m;
	
	if(m<=2)cout<<0<<'\n';
	else if(m>17)cout<<1<<'\n';
	else{
//		cout<<ans[m][n]<<' ';
		int res=ans[m][n]*inv(C(n,m),M2)%M2;
		res=(1-res+M2)%M2;
		cout<<res<<'\n';
	}
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int test=1;	
	pre();
    cin>>test;

    while(test--){	
    	solve();	
    }
}