HRZ的序列

基本思路

首先求出序列的最大值ma和最小值mi，然后遍历序列，对于既不是最大值也不是最小值的数ai，如果该序列是符合要求的序列，2*ai = mi + ma。

完整代码

#include<iostream>
#include<cmath>
using namespace std;
int T;
long long a[200000];
int main ()
{ios::sync_with_stdio(false);cin>>T;for(int k=0;k<T;k++){int n;cin>>n;for(int i=0;i<n;i++)	cin>>a[i];bool flag=true;long long mi=a[0];long long ma=a[0];for(int i=0;i<n;i++){if(a[i] > ma)	ma=a[i];if(a[i] < mi)	mi=a[i];}for(int i=0;i<n;i++){if(a[i] != ma && a[i] != mi){if(2 * a[i] != ma + mi){flag = false;break;}}}if (flag)	cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}

HRZ学英语

基本思路

穷举所有可能的满足要求的字符串起始位置i(0 到 n-26)，判断从i开始的长为26的字符串是否符合要求，第一个符合要求的子串。
判断时可以使用数组vis记录哪些字母出现过，若不重复的字母数量 + ‘?’ 数量 = 26，则符合要求。
确定每一个’?‘处填什么符号的方法是：从左到右遍历所有’?’，对于每一个’?’，寻找没有出现过的字典序最低的字母填充。

完整代码

#include<iostream>
#include<string>
using namespace std;
string s;
int n;
int vis[200];
int cnt, scnt;
int e;
bool check(int i)
{for(int j='A';j<='Z';j++)	vis[j]=0;cnt=0;scnt=26;e=i+26;for(int j=i;j<e;j++){if(s[j] == '?')	scnt--;else{if(vis[s[j]])	return false;else{vis[s[j]]=1;cnt++;}}}if(cnt == scnt)	return true;return false;
}
void reqS(int i)
{if(cnt == 26){for(int j=i;j<e;j++)	cout<<s[j];cout<<endl;}else{int p='A';for(int j=i;j<e;j++){if(s[j] == '?'){while(vis[p])	p++;cout<<char(p);vis[p]=1;}else cout<<s[j];}cout<<endl;}
}
int main ()
{ios::sync_with_stdio(false);cin>>s;n = s.length();if(n < 26)	cout<<-1<<endl;else{int r = n - 26;bool flag = false;for(int i=0;i<=r;i++){if(check(i)){reqS(i);flag=true;break;}}if(!flag)	cout<<-1<<endl;}return 0;
} 

咕咕东的奇妙序列

基本思路

1. 序列中每部分的长度是有规律的：
   · 前9部分的长度符合以1为公差的等差数列；
   · 之后的90个部分长度符合以2为公差的等差数列；
   · 之后的900个部分长度符合以3为公差的等差数列；
   · ···
2. 可以逐级的进行查找，假设上面的每个等差数列涵盖的区域称为块:
   · 首先找到查询的k属于哪一块；
   · 然后找到k属于块里的第几个部分；
   · 再从这个部分中查找出k属于第几个数；
   · 最后判断k属于这个数中第几位，这一位即是要找的答案。
3. 由于数据规模很大，查找k属于块中的那一部分以及查找k是这个部分的第几位数时应该采取二分查找的策略。
4. 另外，也可暴力构造数列(可借助字符串流，详见代码2)，前6个点k不超过$10^6$，直接构造是完全可以拿到60分的。

完整代码

#include<iostream>
using namespace std;
long long an(long long a, long long d, long long i)
{return a + d * i;
}
long long S(long long a, long long d, long long l, long long r)
{return (an(a, d, l) + an(a, d, r)) * (r-l+1) / 2;
} 
int query(long long k)
{long long a=0, d=1, n=9;while(k > S(a, d, 1, n)){k -= S(a, d, 1, n);a = an(a, d, n);d += 1;n *= 10;}long long l=1, r=n+1;long long mid;while(l < r){mid = l+r>>1;if(k > S(a, d, 1, mid))	l = mid+1;else	r = mid;	}k -= S(a, d, 1, l-1);long long num=0, dn=1;n = 9;while(k > dn * n){k -= dn * n;dn += 1;num += n;n *= 10;}l = 1, r = n;while(l < r){mid = l+r>>1;if(k > mid*dn)	l = mid+1;else r = mid;}k -= (l-1)*dn;num += l-1;num += 1;dn -= k;while(dn > 0){dn--;num /= 10;}return num % 10; 
}
int main ()
{int q;cin>>q;long long k;for(int i=0;i<q;i++){cin>>k;cout<<query(k)<<endl;}return 0;
} 

完整代码2(构造)

#include<iostream>
#include<sstream>
using namespace std;
long long k;
int t;
string s;
stringstream ss;
void build()
{int n=1;int cnt = 1000000; //防止构造超时 while(cnt>0){for(int i=1;i<=n;i++){ss<<i;cnt--; }n++;	}ss>>s;
} 
int main()
{build();cin>>t;for(int i=0;i<t;i++){cin>>k;cout<<s[k-1]<<endl;}return 0;
}