我们先求有多少个不同的数，记为cnt，然后分情况进行处理。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#define llong long long
#define For(i,a,n) for(register int i=a;i<=n;i++)
#define RF(i,a,n) for(register int i=a;i>=n;i--)
#pragma GCC optimize(2)
using namespace std;
const llong inf = 1e15+5;
const int maxn = 10005;
llong t, n, cnt;
llong arr[maxn];
llong num[10];
int main(){
ios::sync_with_stdio(false);
cin>>t;
while(t--){
cnt = 0;
cin>>n;
For(i,1,n){
cin>>arr[i];
if(i==1) num[++cnt] = arr[i];
else{
For(j,1,cnt){
if(num[j]==arr[i])
break;
if(j==cnt){
num[++cnt] = arr[i];
break;
}
}
}
}
if(cnt>3){
cout<<"NO"<<endl;
continue;
}
if(cnt<3){
cout<<"YES"<<endl;
continue;
}
int t1 = abs(num[2]-num[1]);
int t2 = abs(num[3]-num[2]);
int t3 = abs(num[1]-num[3]);
if(t1==t2 || t1==t3 || t2==t3)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
这题用了尺取的方法，在从左到右遍历的时候记录一个b数组来表示 l~r 中是否存在这个字母，然后记录一个cnt表示已存在多少不同的字母。
尺取的过程注意 l 和 r 的处理，不要先++再处理 像我一样
首先 r 一直向右遍历，遇到没访问过的字母或者问号就 进行一番处理 ，然后继续向右遍历，遇到访问过的字母则开始处理左边界 l ，l 向右遍历到与 r 当前所处的字母相同的字母（也要进行一番处理），然后停止 l，开始 r （套娃
直到cnt=26就可以停止了，最后输出时候，如果是 ？ 则从头到尾遍历b数组并输出第一个未访问的就是字典序了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#define llong long long
#define For(i,a,n) for(register llong i=a;i<=n;i++)
#define RF(i,a,n) for(register int i=a;i>=n;i--)
#pragma GCC optimize(2)
using namespace std;
const int maxn = 100005;
string str;
int b[30];
llong cnt, bg, flag;
int main(){
ios::sync_with_stdio(false);
cin>>str;
llong len = str.length();
llong l = 0, r = 0;
while(r!=len){
if(str[r] == '?'){
cnt++; r++;
}
else{
int i = str[r++] - 'A';
if(!b[i]){
b[i] = 1;
cnt++;
}
else{
int j = str[l++]-'A';
while(j!=i){
if(str[l-1]!='?')
b[j] = 0;
cnt--;
j = str[l++]-'A';
}
}
}
if(cnt==26){
bg = r-26;
flag = 1;
break;
}
}
if(!flag){
cout<<-1<<endl;
return 0;
}
For(i,bg,bg+25){
if(str[i]=='?'){
For(j,0,25){
if(!b[j]){
b[j] = 1;
cout<<char(j+'A');
break;
}
}
}
else
cout<<str[i];
}
cout<<endl;
return 0;
}
这题一看就不是暴力能解决的事情。
而这题每一块的长度可以说是一个等差数列（或者说多个
1~9相差1
10~99相差2
……
所以可以想到用前缀和的方法，可以预处理全部前缀和（数组存） 真的在想peach，1e18的数据让人绝望。
但是，前缀和的思想还是没错的，我们可以求出 x 所在块之前的所有块数的长度之和，以及x所在块数的长度。这样我们就可以确定 x 的位置。
因为数据范围1e18，所以需要二分确定 x 属于哪一块，以及 x 属于哪个数（例如属于10，则x可能有1或0）。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#define llong long long
#define For(i,a,n) for(register llong i=a;i<=n;i++)
#define RF(i,a,n) for(register llong i=a;i>=n;i--)
using namespace std;
const int maxn = 100005;
llong q, n, p1, p2;
llong ans[50];
llong get_sum(llong x, int flag)
{//flag = 1: 表示求x所在块的前n块的长度（前缀和）
//flag = 0: 表示求x所在块的长度
llong i=1, j=1, ans=0;
for(; 10*j<=x; i++,j*=10){
if(flag)
ans+=i*((1+9*j)*9*j/2)+i*j*9*(x-j*10+1);
else
ans+=i*9*j;
}
return flag?(ans+i*(x-j+2)*(x-j+1)/2):(ans+i*(x-j+1));
}
void solve(llong x)
{
memset(ans,0,sizeof(ans));
int tot = 0, p1 = 0, p2 = 0;
//二分求x属于哪一块
llong l=0, r=1e9;
while(l<r-1){
llong mid = (l+r)>>1;
if(get_sum(mid, 1) < x){
l = mid;
p1 = mid;
}
else
r = mid;
}
x-=get_sum(p1, 1);
//二分求x属于哪个数
l=0, r=p1+1;
while(l<r-1){
llong mid = (l+r)>>1;
if(get_sum(mid, 0) < x){
l = mid;
p2 = mid;
}
else
r = mid;
}
x-=get_sum(p2++, 0);
//第几位
while(p2){
ans[tot++] = p2%10;
p2/=10;
}
cout<<ans[tot-x]<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin>>q;
while(q--){
cin>>n;
solve(n);
}
return 0;
}