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;
}