A - Simple Palindrome
1、先对字母进行分配，每个字母分到 n / 5个
2、对剩余字母进行分配，前n % 5 个字母每一个分配一个
3、分别将其输出，相同字母放在一起，如果相同字母分开，就会出现如“ABA”这样的回文子串。
AC代码：
#include<bits/stdc++.h>
using namespace std;
char ss[7] = {' ','a','e','i','o','u'};
int n;
void solve(){
cin >> n;
int num1 = n / 5;
int num2 = n % 5;
int num[7];
memset(num, 0, sizeof num);
for(int i = 1; i <= 5; ++i){
num[i] = num1;
}
for(int i = 1; i <= num2; ++i){
num[i]++;
}
for(int i = 1; i <= 5; ++i){
for(int j = 1; j <= num[i]; ++j){
cout<<ss[i];
}
}
cout << endl;
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int _;
cin >> _;
while(_--){
solve();
}
return 0;
}
B1 - The Strict Teacher (Easy Version)
1、因为只有两个老师，所以分两种情况判断
<1>学生在老师中间 ans = (两老师之间的距离) / 2；
<2>学生在墙和老师中间 ans = 老师距离墙的距离
AC代码：
#include<bits/stdc++.h>
using namespace std;
int n, m, q;
int m1, m2, q1;
void solve(){
cin >> n >> m >> q;
cin >> m1 >> m2;
cin >> q1;
if((m1 < q1 && q1 < m2) || (m1 > q1 && q1 > m2)){
cout << labs(m1 - m2) / 2;
}else if( q1 > m1 && q1 > m2){
cout<< (n - max(m1, m2));
}else if(q1 < m2 && q1 < m1){
cout<< min(m1, m2) - 1;
}
cout << endl;
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int _;
cin >> _;
while(_--){
solve();
}
return 0;
}
B2 - The Strict Teacher (Hard Version)
1、二分查找在学生之前的第一个老师和在学生之后的老师第一个老师
2、分类判断就行了
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n, m, q;
int a[N], num;
void solve() {
cin >> n >> m >> q;
for (int i = 0; i < m; ++i) {
cin >> a[i];
}
sort(a, a + m);
for (int i = 1; i <= q; ++i) {
cin >> num;
// 找到第一个大于 num 的数
int greaterIdx = upper_bound(a, a + m, num) - a;
// 找到第一个大于等于 num 的数，也就是可以用 lower_bound - 1 来得到小于 num 的数
int smallerIdx = lower_bound(a, a + m, num) - a - 1;
// 输出结果
if (smallerIdx < 0) {
// 如果不存在小于 num 的数
cout << a[greaterIdx] - 1;
} else if (greaterIdx >= m) {
// 如果不存在大于 num 的数
cout << n - a[smallerIdx];
}else {
cout<<(a[greaterIdx] - a[smallerIdx]) / 2;
}
cout<<endl;
}
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int _;
cin >> _;
while (_--) {
solve();
}
return 0;
}
C - Lazy Narek
动态规划
每次更新以某个字母为结尾的最大得分
初始化：
- 设定一个
dp数组来存储以“narek”中的各个字母结尾时的最大分数，初始值为极小值，只有dp[0]（以'n'结尾）初始化为0。
动态规划过程：
- 对每个字符串 s[i]，通过以下步骤更新dp数组：
- 储存上一轮的结果到
ndp。 - 遍历“narek”的每个字母，通过
lower_bound查找每个字符在s[i]中出现的情况。 - 如果当前字符是所需字母且符合顺序，则增加分数；否则减少分数。
- 储存上一轮的结果到
更新分数：
- 更新
ndp[next]，记录以下一个字母为结尾时的最大分数。 - 将
dp更新为ndp，为下一轮计算做准备。
结果计算：
- 最终结果
ans初始化为0，遍历dp数组，计算得分并考虑到未选择字符对对手得分的影响，得到最大值。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const string narek = "narek";
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t; cin >> t;
while(t--){
int n, m;
cin >> n >>m;
vector<string> s(n);
for(int i = 0; i < n; ++i) cin >> s[i];
//dp数组存储的是当前以narek中任一字母结尾能达到的最大分数
//首先初始化初始分数为最小值
vector<int> dp(5, int(-1e9)), ndp;
dp[0] = 0;
for(int i = 0; i < n; ++i){
//储存上一轮结束时的结果
ndp = dp;
//遍历每一个字母
for(int j = 0; j < 5; ++j){
//如果当前字母没有前驱
//例：以a开头，是非法的，跳过
if(dp[j] == int(-1e9))continue;
//初始化当前分数为零， 我们下一个要找的字母为j
int counted_score = 0, next = j;
//遍历当前字符串
for(int k = 0; k < m; ++k){
//找当前字符有没有 narek中出现
int ind = narek.find(s[i][k]);
//没找到，跳过当前循环 查找 下一个字符
if(ind == -1) continue;
//如果下一个字母是我们需要的
if(next == ind){
next = (next + 1) % 5;
//我们的分数加一
counted_score++;
}else{
//否则我们的分数减一
counted_score--;
}
}
//更新以next结尾的最大分数
ndp[next] = max(ndp[next], dp[j] + counted_score);
}
//更新dp数组
dp = ndp;
}
//因为什么都不选的结果为零，但是选了可能导致分数为负数
//因此初始化ans的值为0
int ans = 0;
for(int i = 0; i < 5; ++i){
//减 2 * i的原因是，如果不以最后一个字符结尾，我们的分不加，对手的分数增加
//因此我们的分数需减去两倍
ans = max(ans, dp[i] - 2 * i);
}
cout << ans <<endl;
}
return 0;
}