T1 HRZ的序列
题目
相较于咕咕东，瑞神是个起早贪黑的好孩子，今天早上瑞神起得很早，刷B站时看到了一个序列aa，他对这个序列产生了浓厚的兴趣。
他好奇是否存在一个数KK，使得一些数加上KK，一些数减去KK，一些数不变，使得整个序列中所有的数相等。
其中对于序列中的每个位置上的数字，至多只能执行一次加运算或减运算或是对该位置不进行任何操作。
由于瑞神只会刷B站，所以他把这个问题交给了你！
样例输入输出
输入格式
输入第一行是一个正整数tt表示数据组数。
接下来对于每组数据，输入的第一个正整数nn表示序列aa的长度，随后一行有nn个整数，表示序列aa。
输出格式
输出共包含tt行，每组数据输出一行。对于每组数据，如果存在这样的K，输出"YES"，否则输出“NO”。（输出不包含引号）
样例输入
2
5
1 2 3 4 5
5
1 2 3 4 5
样例输出
NO
NO
解析
序列中只可能有三个数，只可能是排序后的最小值、最大值和最小最大值的平均值。我们在将序列排序后，序列中的最小值一定是第一个，最大值一定是最后一个。如果序列中有且最多有三个数，那么第三个数一定是第一和最后一个数的平均值。找到这三个数字后，我们遍历序列，只要有不满足的就返回no。否则为yes。
代码
#include <iostream>
#include <algorithm>
using namespace std;
long long a[10005];
int main(){
int t;
cin >> t;
for(int i = 0 ; i < t ; i++)
{
int n;
cin >> n;
for(int j = 0 ; j < n ; j++)
cin >> a[j];
sort(a, a + n);
long long mid;
mid = (a[0] + a[n - 1]) / 2;
int flag = 0;
for(int j = 0 ; j < n ; j++)
{
if(flag == 1)
break;
if(a[j] != a[0] && a[j] != a[n - 1] && a[j] != mid)
{
cout << "NO" << endl;
flag = 1;
}
else
continue;
}
if(flag == 0)
cout << "YES" << endl;
}
}
回顾
这道题其实很简单，只要想明白它只能有三个数就行。易错点数的范围要用long long，刚开始我也没发现，在做第三题时发现第三题数据范围达到10的18次方需要开long long时刻意回来检查才发现的。
T2 HRZ学英语
题目
瑞神今年大三了，他在寒假学会了英文的26个字母，所以他很兴奋！
于是他让他的朋友TT考考他，TT想到了一个考瑞神的好问题：给定一个字符串，从里面寻找 连续的26个大写字母 并输出！
但是转念一想，这样太便宜瑞神了，所以他加大了难度：现在给定一个字符串，字符串中包括26个大写字母和特殊字符’?’，特殊字符’？'可以代表任何一个大写字母。
现在TT问你是否存在一个 位置连续的且由26个大写字母组成的子串 ，在这个子串中每个字母出现且仅出现一次，如果存在，请输出从左侧算起的第一个出现的符合要求的子串，并且要求，如果有多组解同时符合位置最靠左，则输出字典序最小的那个解！如果不存在，输出-1！
这下HRZ蒙圈了，他刚学会26个字母，这对他来说太难了，所以他来求助你，请你帮他解决这个问题，报酬是可以帮你打守望先锋。
说明：字典序 先按照第一个字母，以 A、B、C……Z 的顺序排列；如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，SIGH 和 SIGHT），那么把短者排在前。例如
AB??EFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABDCEFGHIJKLMNOPQRSTUVWXYZ
上面两种填法，都可以构成26个字母，但是我们要求字典序最小，只能取前者。
注意，题目要求的是 第一个出现的， 字典序最小的
样例输入输出
输入格式
输入只有一行，一个符合题目描述的字符串。
输出格式
输出只有一行，如果存在这样的子串，请输出，否则输出-1
样例输入1
ABC??FGHIJK???OPQR?TUVWXY?
样例输出1
ABCDEFGHIJKLMNOPQRSTUVWXYZ
样例输入2
AABCDEFGHIJKLMNOPQRSTUVW??M
样例输出2
-1
解析
用一个数组str [26] 去标记26个字母是否都存在，从第一个字母开始遍历，记录出现的字母，当遇到重复的字母时停止本次遍历，然后继续从下一个字母开始遍历，直到出现26位字母不重复（但是可以包含“？”）。之后按要求按字典序将“ ？”替换成需要的字母即可。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstring>
using namespace std;
char a[1000005];
int str[27];
int tag;
int main(){
cin >> a;
int flag = 0;
int n = strlen(a);
for(int i = 0 ; i < n - 25 ; i++)
{
memset(str, 0, sizeof(str));
flag = 0;
for(int j = i ; j < i + 26 ; j++)
{
if(a[j] == '?')
continue;
else
{
if(str[a[j] - 'A'] == 1)
{
flag = 1;
break;
}
else
str[a[j] - 'A'] = 1;
}
}
if(flag == 0)
{
for(int j = i ; j < 26 + i ; j++)
{
if(a[j] == '?')
{
for(char k = 'A' ; k <= 'Z' ; k++)
{
if(str[k - 'A'] == 0)
{
str[k - 'A'] = 1;
a[j] = k;
break;
}
}
}
}
tag = i;
break;
}
}
if(flag == 0)
{
for(int j = tag ; j < 26 + tag ; j++)
cout << a[j];
cout << endl;
return 0;
}
else
cout << "-1" << endl;
}
回顾
这道题很简单，想清楚遍历的方式，就能很快的写出来。利用每次只遍历26个字母，不满足则返回的方式可以让这题写起来很简单，省略掉一些刚开始考虑的判断条件。
T3 咕咕东的奇妙序列
题目
咕咕东 正在上可怕的复变函数，但对于稳拿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)
接下来第i+1行表示第i个输入k_i，表示询问第k_i
项数字。(1<=k_i<=10^{18})(1<=k i<=10 ^18 )
输出格式
输出包含q行
第i行输出对询问k_ik i的输出结果。
样例输入
5
1
3
20
38
56
样例输出
1
2
5
2
0
解析
先说一下思路（刚开始不是这么做的，因为原来的做法有问题就重构了，这个放在回顾里谈）：
这题很容易想明白，它的问题就在于如何妥善的处理当递增序列10位或者100位以上后，每个数字占多位的情况。
同样的，这道题要采用一种类似前缀和的思想。
我们把这个数列按每组递增分成一块一块，1，12，123，…
在第1到第9块，每相邻的两块之间数字个数相差1；
第10块到第99块，每相邻的两块之间数字个数相差2；
第10i块到10i+1-1块，每相邻的两块之间数字个数相差i + 1。
有了这个规律，我们就可以根据数字的位置来知道它的值了。
找位置，当然要用二分的方法。通过两次二分，一次用来查找它在第几块，一次用来查找它在块中的位置，就能找出它的值。
代码
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
long long ans[1000000] = {0};
long long getsum(long long x) {return x * (x + 1) >> 1;}
long long getsum1(long long x){
long long ans = 0, i = 1, j = 1;
for ( ; j * 10 <= x ; i++, j *= 10 )
ans += i * getsum(j * 9) + i * j * 9 * (x - j * 10 + 1);
return ans + i * getsum(x - j + 1);
}
long long getsum2(long long x){
long long ans = 0, i = 1, j = 1;
for ( ; j * 10 <= x ; i++, j *= 10)
ans += i * j * 9;
return ans + i * (x - j + 1);
}
int main(){
int q;
cin >> q;
while(q--)
{
long long k;
cin >> k;
long long l = 0, r = 1e9;
long long mid = 0;
long long a = 0;
while(l < r - 1)
{
mid = (l + r) >> 1;
if(getsum1(mid) < k)
{
l = mid;
a = mid;
}
else
{
r = mid;
}
}
k -= getsum1(a);
long long ll = 0, rr = a + 1;
long long b = 0;
while(ll < rr - 1)
{
mid = (ll + rr) >> 1;
if(getsum2(mid) >= k)
{
rr = mid;
}
else
{
ll = mid;
b = mid;
}
}
k -= getsum2(b);
b++;
int i = 0;
for( ; b > 0 ; b = b / 10)
{
ans[i] = b % 10;
i++;
}
cout << ans[i - k] << endl;
}
}
回顾
这道题刚刚拿到，我一看序列操作，又是多次求值，根据前一晚上复习的内容，前缀和就开始写了。但是当时每太理清楚这些数字的关系，到交卷前都没有写完，就把题目里56个数字输进去造了一个常量数组，骗了30分，总共230还可以接受。
之后补题的时候，因为太久忘了原来的思路就干脆重写了（其实是骗分的时候忘了保存写了一半的代码）…然后提交的时候在第7个点WA掉了，看数据范围应该是k到1018的那几组数据也就是需要long long的地方出了问题。我跟同学讨论了一下，同学告诉我尽量不要用数组去操作long long的数据，数据太大了很容易出错。想起来这道题是某巨卡网站上的，就去搜了一下大佬们的思路，后来看到二分这个优美的思路，就根据他的思路重构了代码。以后要注意尽量避免long long型数据的操作。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
