模测模测
A HRZ的序列
题目
相较于咕咕东，瑞神是个起早贪黑的好孩子，今天早上瑞神起得很早，刷B站时看到了一个序列aaa，他对这个序列产生了浓厚的兴趣。
他好奇是否存在一个数KKK，使得一些数加上KKK，一些数减去KKK，一些数不变，使得整个序列中所有的数相等。
其中对于序列中的每个位置上的数字，至多只能执行一次加运算或减运算或是对该位置不进行任何操作。
由于瑞神只会刷B站，所以他把这个问题交给了你！
输入
输入第一行是一个正整数 t t t表示数据组数。
接下来对于每组数据，输入的第一个正整数nnn表示序列aaa的长度，随后一行有nnn个整数，表示序列aaa
输出
输出共包含ttt行，每组数据输出一行。对于每组数据，如果存在这样的K，输出"YES"，否则输出“NO”。（输出不包含引号）
输入样例：
2
5
1 2 3 4 5
5
1 2 3 4 5
输出样例：
NO
NO
image.png
（附：这个很重要）
其实这题挺简单的，就是要看有几种数字，倘若有三种以上数字，直接NO，不可能存在的。假如有三种以下的数字，直接YES，倘若有三种数字，要看看是不是等差数列。。
麻烦的就是请看一看数据范围……。开long long（感谢不杀之恩，不开long long就丢了十分）
#include<iostream>
#include<set>
using namespace std;
set<long long> l;
int main()
{
int m;
long long n;
cin>>m;
for(int ml=0;ml<m;ml++)
{
l.clear();
cin>>n;
long long a;
for(int i=0;i<n;i++)
{
scanf("%lld",&a);
l.insert(a);
}
if(l.size()==3)
{
set<long long>::iterator it=l.begin();
long long d=*it;
it++;
long long b=*it;
it++;
long long c=*it;
long long dl=b-d;long long bl=c-b;
if(dl!=bl)
{
cout<<"NO"<<endl;
}
else
{
cout<<"YES"<<endl;
}
}
else if(l.size()>3)
{
cout<<"NO"<<endl;
}
else if(l.size()<3)
{
cout<<"YES"<<endl;
}
}
return 0;
}
B： HRZ学英语
题目
瑞神今年大三了，他在寒假学会了英文的26个字母，所以他很兴奋！
于是他让他的朋友TT考考他，TT想到了一个考瑞神的好问题：给定一个字符串，从里面寻找 连续的26个大写字母 并输出！
但是转念一想，这样太便宜瑞神了，所以他加大了难度：现在给定一个字符串，字符串中包括26个大写字母和特殊字符’?’，特殊字符’？'可以代表任何一个大写字母。
现在TT问你是否存在一个 位置连续的且由26个大写字母组成的子串 ，在这个子串中每个字母出现且仅出现一次，如果存在，请输出从左侧算起的第一个出现的符合要求的子串，并且要求，如果有多组解同时符合位置最靠左，则输出字典序最小的那个解！如果不存在，输出-1！
这下HRZ蒙圈了，他刚学会26个字母，这对他来说太难了，所以他来求助你，请你帮他解决这个问题，报酬是可以帮你打守望先锋。
说明：字典序 先按照第一个字母，以 A、B、C……Z 的顺序排列；如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，SIGH 和 SIGHT），那么把短者排在前。例如
AB??EFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABDCEFGHIJKLMNOPQRSTUVWXYZ
上面两种填法，都可以构成26个字母，但是我们要求字典序最小，只能取前者。
注意，题目要求的是 第一个出现的， 字典序最小的 ！
输入
输入只有一行，一个符合题目描述的字符串。
输出
输出只有一行，如果存在这样的子串，请输出，否则输出-1
输入样例：
ABC??FGHIJK???OPQR?TUVWXY?
输出样例：
ABCDEFGHIJKLMNOPQRSTUVWXYZ
这题就得了十分，当时真的让我感觉万分心痛QAQ。原因很简单。。。试试A？？？？？？A？？？？？？？？？？？？？？？？？？？？？？这样的数据。
一开始我是考虑的，先用一个bool数组（二十六的容量）记录从A开始的字母有没有出现，假如没有就继续遍历，标记上这个字母。假如有了就说明重复出现，那从这个位置开始全部清零（显然是错的）。。
为了改变这个遍历的bug，加上对时间要求并不高，我直接把从新开始的地方放在上个出现该字母的位置后面一个（是的，肯定浪费时间，但这题真的对时间不会有啥要求orz）？直接标记自由变量，然后输出的时候该位置有字母的输出字母，无字母有问号的按字典序输出最小的（
#include<iostream>
#include<string>
#include<cstring>
#include<string.h>
using namespace std;
struct ok
{
int weizhi;
int zimu;
};
int main()
{
ok a[27];
int a2[27];
char b[26];
char t[27];
memset(a,0,sizeof(a));
memset(a2,0,sizeof(a2));
int ziyou=0;
string x;
cin>>x;
int l=x.length();
bool yes=0;
int number=0;
int begin=0;
for(int i=0;i<=l;i++)
{
if(number==26)
{
b[26]='\0';
printf("%s\n",b);
yes=1;
break;
}
if(number+ziyou==26)
{
int biaoji=0;
int biaoji2=0;
for(int p=1;p<=26;p++)
{
if(a[p].zimu==0)
{
t[biaoji]=p+64;
biaoji++;
}
/* else
{
}*/
}
int tk=0;
for(int p=1;p<=26;p++)
{
// cout<<" l"<<b[1]<<endl;
// cout<<"lp"<<a2[1]<<endl;
if(a2[p]==0)
{
cout<<b[p-1];
}
else
{
cout<<t[tk];
tk++;
}
}
cout<<endl;
yes=1;
break;
}
int k=x[i];
if(i==l) break;
if(x[i]=='?')
{
ziyou++;
a2[number+ziyou]=1;
}
else if(a[k-64].zimu==0)
{
b[number+ziyou]=x[i];
// cout<<x[i]<<endl;
number++;
a[k-64].zimu=1;
a[k-64].weizhi=i;
}
else if(a[k-64].zimu==1)
{
number=0;
ziyou=0;
memset(a,0,sizeof(a));
memset(a2,0,sizeof(a2));
a[k-64].zimu=1;
int w=a[k-64].weizhi;
a[k-64].weizhi=i;
i=w+1;
// b[0]=x[i];
// cout<<x[i]<<endl;
}
}
if(!yes)
{
cout<<"-1"<<endl;
}
return 0;
}
具体的就在代码里面了。
C：咕咕东的奇妙序列
题目：
咕咕东 正在上可怕的复变函数，但对于稳拿A Plus的 咕咕东 来说，她早已不再听课。
此时她在睡梦中突然想到了一个奇怪的无限序列：112123123412345…
这个序列由连续正整数组成的若干部分构成，其中第一部分包含1至1之间的所有数字，第二部分包含1至2之间的所有数字，第三部分包含1至3之间的所有数字，第i部分总是包含1至i之间的所有数字。
所以，这个序列的前56项会是11212312341234512345612345671234567812345678912345678910，其中第1项是1，第3项是2，第20项是5，第38项是2，第56项是0。
咕咕东 现在想知道第 k 项数字是多少！但是她睡醒之后发现老师讲的东西已经听不懂了，因此她把这个任务交给了你。
输入：
输入由多行组成。
第一行一个整数q表示有q组询问(1<=q<=500)(1<=q<=500)(1<=q<=500)
接下来第 i+1行表示第i个输入 ki ，表示询问第 ki项数字。(1<=ki<=1018) (1<=ki<=10^18)
输出：
输出包含 q 行
输入样例：
5
1
3
20
38
56
输出样例：
1
2
5
2
0
第i行输出对询问 ki 的输出结果。
……暴力一定会超时，
但我为了不暴力写的爆零了 爆零了。0 .0
image.png
image.png
（字很难看QAQ，但大抵思路真的研究一下午，这个二分也很灵巧
#include<iostream>
#include<cmath>
using namespace std;
long long sum1[11];//i位有多少
long long sum2[11];//i位一共有多少
int wei;
long long dingjie(long long q)
{
long long w=q;
for(int i=1;i<10;i++)
{
if(w<=sum2[i])
{
wei=i;
w-=sum2[i-1];
return w;
}
}
wei=10;
return w-sum2[9];
}
long long queding(long long weizhi,int wei)
{
long long sum;
long long k=0;
long long left=1;
long long right=1;
for(int i=0;i<wei;i++)
{
right*=10;
}
right-=1;
while(left<=right)
{
long long mid=(left+right)/2;
long long number=(sum1[wei-1]+sum1[wei-1]+wei+wei*mid)*mid/2;
if(number<weizhi)
{
left = mid + 1;
k = mid;
}
else
{
right = mid - 1;
}
}
return (sum1[wei-1]+wei+sum1[wei-1]+wei*k)*(k)/2;
}
int main()
{
sum1[0]=0;sum2[0]=0;
sum1[1]=9;
for(long long i=2;i<10;i++)
{
sum1[i]=sum1[i-1]+9*i*pow(10,i-1);
}
/*for(long long i=1;i<10;i++)
{
cout<<sum1[i]<<endl;
}*/
sum2[1]=45;
long long cntx=10;
for(long long i=2;i<10;i++)
{
sum2[i]=((i+sum1[i-1]+sum1[i])*9*cntx)/2;
cntx*=10;
}
for(int i=2;i<10;i++)
{
sum2[i]+=sum2[i-1];
}
/* for(int i=1;i<10;i++)
{
cout<<sum2[i]<<endl;
}*/
long long n;
cin>>n;
while(n--)
{
long long q;
// q=n;
cin>>q;
long long p=dingjie(q);//p现在是几位数范围内的位次
long long go=queding(p,wei);
p-=go;//p现在是哪个加法之内的位数
int pl=1;
for(int i=1;i<10;i++)
{
if(p<sum1[i])
{
p-=sum1[i-1];
pl=i;
break;
}
}
long long wssss;
if(p%pl==0)
{
wssss=p/pl-1;
p=pl;
}
else
{
wssss=p/pl;
p=p-pl*wssss;
}
// wssss=p/pl;//p是现在的位次(此范围只有weici位数);
// p=p-pl*wssss;
long long c=pow(10,pl-1);
// int jieya=10;
c+=wssss;
long long kt[15];
for(int i=pl;i>0;i--)
{
kt[i]=c%10;
c=c/10;
}
cout<<kt[p]<<endl;
}
return 0;
}
