Competition2：HRZ学英语

Competition2：HRZ学英语

题目描述
瑞神今年大三了，他在寒假学会了英文的26个字母，所以他很兴奋！于是他让他的朋友TT考考他，TT想到了一个考瑞神的好问题：给定一个字符串，从里面寻找连续的26个大写字母并输出！但是转念一想，这样太便宜瑞神了，所以他加大了难度：现在给定一个字符串，字符串中包括26个大写字母和特殊字符’?’，特殊字符’？'可以代表任何一个大写字母。现在TT问你是否存在一个位置连续的且由26个大写字母组成的子串，在这个子串中每个字母出现且仅出现一次，如果存在，请输出从左侧算起的第一个出现的符合要求的子串，并且要求，如果有多组解同时符合位置最靠左，则输出字典序最小的那个解！如果不存在，输出-1！ 这下HRZ蒙圈了，他刚学会26个字母，这对他来说太难了，所以他来求助你，请你帮他解决这个问题，报酬是可以帮你打守望先锋。
注意，题目要求的是 第一个出现的，字典序最小的！

输入格式
输入只有一行，一个符合题目描述的字符串。

输出格式
输出只有一行，如果存在这样的子串，请输出，否则输出-1

输入样例1

ABC??FGHIJK???OPQR?TUVWXY?

输出样例1

ABCDEFGHIJKLMNOPQRSTUVWXYZ

输入样例2

AABCDEFGHIJKLMNOPQRSTUVW??M

输出样例2

-1

解题思路
这道题的目的就是，输出第一个符合要求的子串，符合什么要求呢？

• 这个子串的长度为26
• 这个子串中要出现每个大写英文字母
• 这个子串中如果有癞子的话，需要按照字典序最小输出，如样例1所示

那么怎么获取这样的子串呢？
从前往后遍历这个字符串的每一个字符所接的长度为26的子串？不可取。

这里的思路是：尺取法

首先划两个int变量，作为这把“尺子”的两端，初始化均为0。
每次循环，把右端往右挪一位，此举可以增大尺子的长度。
如果当前的尺子内容不满足题目要求，就继续挪右端。
如果当前的尺子内容满足了题目要求，那么如果其中有问号符（即癞子），就把这些问号符转化成让这个子串的字典序最小的情况即可，然后输出。
如果当前的尺子内容不满足题目要求且长度大于了26，那么就把左端也挪一位。

详细过程看代码：
(如果题目要求改为“整个字符串中符合要求的子串中字典序最小的”，那么只需要修改一下获取ans的那几行代码即可)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <cstring>using namespace std;string input;
string ans;int hasIn[26];//为1时表示对应字母在动态队列中
int pos[26];//对应字母的位置,为-1时说明不在队列中
int black;//癞子
int newhasIn[26];//临时hasInint CtoI(char x)
{if (x == '?') return 100;//?映射为100,即癞子else return (x - 65);//A映射为0，Z映射为25
}int main()
{cin >> input;if (input.length() < 26){cout << -1 << endl;return 0;}bool isOK = false;memset(hasIn, 0, sizeof hasIn);memset(pos, -1, sizeof pos);int left, right;//动态队列的左右指针left = right = 0;black = 0;if (CtoI(input[0]) == 100){black++;}else{hasIn[CtoI(input[0])] = 1;pos[CtoI(input[0])] = 0;}while (right < input.length()){right++;int cur = CtoI(input[right]);if (cur == 100){black++;}else{if (hasIn[cur]){//弹出左侧的int temp = pos[cur];for (int i = left; i <= pos[cur]; i++)//i表示位置{int cur_t = CtoI(input[i]);//cur_t表示i处的那个字母if (cur_t == 100){black--;}else{hasIn[cur_t] = 0;pos[cur_t] = -1;}}left = temp + 1;}hasIn[cur] = 1;pos[cur] = right;}if ((right - left) == 25){string newstr = input.substr(left, 26);if (black > 0)//如果有癞子{for (int i = 0; i <= 25; i++){newhasIn[i] = hasIn[i];}for (int i = 0; i <= 25; i++){if (newstr[i] == '?'){for (int j = 0; j <= 25; j++){if (newhasIn[j] == 0){newhasIn[j] = 1;newstr[i] = j + 65;break;}}}}}if (newstr.length() == 26){ans = newstr;isOK = true;break;}left++;}}if (!isOK) cout << "-1" << endl;else cout << ans << endl;return 0;}

Competition2：HRZ学英语

题目描述
瑞神今年大三了，他在寒假学会了英文的26个字母，所以他很兴奋！于是他让他的朋友TT考考他，TT想到了一个考瑞神的好问题：给定一个字符串，从里面寻找连续的26个大写字母并输出！但是转念一想，这样太便宜瑞神了，所以他加大了难度：现在给定一个字符串，字符串中包括26个大写字母和特殊字符’?’，特殊字符’？'可以代表任何一个大写字母。现在TT问你是否存在一个位置连续的且由26个大写字母组成的子串，在这个子串中每个字母出现且仅出现一次，如果存在，请输出从左侧算起的第一个出现的符合要求的子串，并且要求，如果有多组解同时符合位置最靠左，则输出字典序最小的那个解！如果不存在，输出-1！ 这下HRZ蒙圈了，他刚学会26个字母，这对他来说太难了，所以他来求助你，请你帮他解决这个问题，报酬是可以帮你打守望先锋。
注意，题目要求的是 第一个出现的，字典序最小的！

输入格式
输入只有一行，一个符合题目描述的字符串。

输出格式
输出只有一行，如果存在这样的子串，请输出，否则输出-1

输入样例1

ABC??FGHIJK???OPQR?TUVWXY?

输出样例1

ABCDEFGHIJKLMNOPQRSTUVWXYZ

输入样例2

AABCDEFGHIJKLMNOPQRSTUVW??M

输出样例2

-1

解题思路
这道题的目的就是，输出第一个符合要求的子串，符合什么要求呢？

• 这个子串的长度为26
• 这个子串中要出现每个大写英文字母
• 这个子串中如果有癞子的话，需要按照字典序最小输出，如样例1所示

那么怎么获取这样的子串呢？
从前往后遍历这个字符串的每一个字符所接的长度为26的子串？不可取。

这里的思路是：尺取法

首先划两个int变量，作为这把“尺子”的两端，初始化均为0。
每次循环，把右端往右挪一位，此举可以增大尺子的长度。
如果当前的尺子内容不满足题目要求，就继续挪右端。
如果当前的尺子内容满足了题目要求，那么如果其中有问号符（即癞子），就把这些问号符转化成让这个子串的字典序最小的情况即可，然后输出。
如果当前的尺子内容不满足题目要求且长度大于了26，那么就把左端也挪一位。

详细过程看代码：
(如果题目要求改为“整个字符串中符合要求的子串中字典序最小的”，那么只需要修改一下获取ans的那几行代码即可)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <cstring>using namespace std;string input;
string ans;int hasIn[26];//为1时表示对应字母在动态队列中
int pos[26];//对应字母的位置,为-1时说明不在队列中
int black;//癞子
int newhasIn[26];//临时hasInint CtoI(char x)
{if (x == '?') return 100;//?映射为100,即癞子else return (x - 65);//A映射为0，Z映射为25
}int main()
{cin >> input;if (input.length() < 26){cout << -1 << endl;return 0;}bool isOK = false;memset(hasIn, 0, sizeof hasIn);memset(pos, -1, sizeof pos);int left, right;//动态队列的左右指针left = right = 0;black = 0;if (CtoI(input[0]) == 100){black++;}else{hasIn[CtoI(input[0])] = 1;pos[CtoI(input[0])] = 0;}while (right < input.length()){right++;int cur = CtoI(input[right]);if (cur == 100){black++;}else{if (hasIn[cur]){//弹出左侧的int temp = pos[cur];for (int i = left; i <= pos[cur]; i++)//i表示位置{int cur_t = CtoI(input[i]);//cur_t表示i处的那个字母if (cur_t == 100){black--;}else{hasIn[cur_t] = 0;pos[cur_t] = -1;}}left = temp + 1;}hasIn[cur] = 1;pos[cur] = right;}if ((right - left) == 25){string newstr = input.substr(left, 26);if (black > 0)//如果有癞子{for (int i = 0; i <= 25; i++){newhasIn[i] = hasIn[i];}for (int i = 0; i <= 25; i++){if (newstr[i] == '?'){for (int j = 0; j <= 25; j++){if (newhasIn[j] == 0){newhasIn[j] = 1;newstr[i] = j + 65;break;}}}}}if (newstr.length() == 26){ans = newstr;isOK = true;break;}left++;}}if (!isOK) cout << "-1" << endl;else cout << ans << endl;return 0;}