第一题
题目描述
黑塔是一个喜欢转圈圈的女孩子。
有一天，黑塔遇到了n个怪物，第i个怪物的生命值为h_i.
由于被守护者之影禁用了普通攻击，黑塔现在只能使用E技能攻击敌人。具体地说，黑塔每次使用E技能，会对敌方全体造成E点伤害。
除此之外，每当一个怪物的生命值首次减小到其最大生命值的50%及以下(含50%)时，如果敌方尚有怪物存活(生命值大于零)，那么黑塔就会自动释放一次追加攻击“转圈”，对敌方全体造成R点伤害。如果一次攻击同时使多个敌人满足以上条件，那么黑塔也会连续释放多次“转圈圈”，直到“转圈圈”次数耗尽或者敌人全部倒下为止。在“转圈圈”结束之前，黑塔无法再次使用E技能。
作为天才俱乐部#83的天才，黑塔只用了0.0114514秒就算出了自己需要使用多少次E技能才能击败这些怪物，以及在这个过程中她会释放多少次“转圈圈”。她觉得这个问题太简单了，于是将其留给了你作为课后习题。
输入描述
第一行一个正整数T，表示有T组数据。对于每一组数据，第一行一个正整数n，表示怪物的数量;第二行n个正整数h_1,h_2,……,h_n,表示每个怪物的生命值;第三行两个正整数E,R，分别表示黑塔E技能的伤害和“转圈圈”的伤害。1<=n<=10^5,1<=T<=10,1<=h_i, E,R<=10^9。
输出描述
对于每一组数据，输出一行两个正整数cntE,cntR,分别表示黑塔使用E技能的次数和“转圈圈”的次数
第二题
搜索旋转数组（力扣原题）
题目链接
第三题
忘截图了，题目大意就是给定字符串s，对于q个询问，判断询问字符串word是否是s的非连续子串，输出是的子串的个数（ 1<= s.size() <= 50000, 1 <= q <= 5000, 1 <= word <= 50)
思路
我们预处理出来每一个字符后面的存在的字母的最近位置，然后处理每一个询问。
实现时为了快速的判断应该从哪开始找，我们用哈希表存每一个字母最先出现的位置。
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <unordered_map>
using namespace std;
const int N = 50010;
int son[N][26];
int cnt[26];
int main()
{
string s;
cin >> s;
vector<string> word;
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
string t;
cin >> t;
word.push_back(t);
}
unordered_map<char, int> h;
for(int i = 0; i < s.size(); i++)
{
int u = s[i] - 'a';
cnt[u]++;
if(h.find(s[i]) == h.end()) h[s[i]] = i;
}
for(int i = 0; i < s.size(); i++)
{
int u = s[i] - 'a';
cnt[u]--;
for(int j = 0; j < 26; j++)
{
// 后面存在该字母时才往后找
if(cnt[j])
{
for(int k = i + 1; k < s.size(); k++)
{
int x = s[k] - 'a';
if(x == j)
{
son[i][j] = k;
break;
}
}
}
}
}
int res = 0;
for(int i = 0; i < n; i++)
{
if(h.find(word[i][0]) != h.end())
{
int p = h[word[i][0]];
bool flag = true;
for(int j = 1; j < word[i].size(); j++)
{
int u = word[i][j] - 'a';
if(son[p][u] == 0)
{
flag = false;
break;
}
p = son[p][u];
}
if(flag) res++;
}
}
cout << res;
return 0;
}