I'm a teapot
题意
给你一个字符串，判断是否以"tea"结尾。
思路
取末尾3个字符，判断是否与tea相等。
题解
#include <iostream>
#include <string>
using namespace std;
int main() {
int N;
string S;
cin >> N >> S;
if (N < 3) {
cout << "No\n";
} else {
if (S[N - 3] == 't' and S[N - 2] == 'e' and S[N - 1] == 'a') {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
}
B - You're a teapot
题意
给你一个字符串，定义其填充率为在首位都为t且长度大于2的情况下，t的数量占中间总字符个数的比例。返回子串中最大的填充率。
思路
直接遍历每种可能，并计算填充率。
题解
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
int n = s.size();
double ans = 0;
// 枚举子串开始的地方
for (int i = 0; i < n; i++) {
if (s[i] != 't') continue;
// 枚举子串结束的地方（i + 2 是因为长度至少为3）
for (int j = i + 2; j < n; j++) {
if (s[j] != 't') continue;
int x = 0;
for (int k = i; k <= j; k++) {
if (s[k] == 't') x++;
}
int len = (j - i + 1);
double item = (double)(x - 2) / (double)(len - 2);
if (item > ans) ans = item;
}
}
printf("%.15lf", ans);
return 0;
}
C - Flush
题意
桌面上有若干口味的茶包若干种，对于每个询问b，返回最小的x使得在x中必然包含b个相同口味的茶包。
思路
根据抽屉原理，庄家为了避免在x中出现b个相同口味的茶包，他会尽可能平均的选择每一种口味，直到该口味完全被选完。最坏情况下，对于难度b，每种口味都会被选择min(A[i], b-1)次，此时只需令x+1，则在x中必然出现b个相同口味的茶包。即
但是这种方法时间复杂度太高，无法通过。由于实际上我们只需要一个门槛，该点左边的A[i]需要累加，右边则是茶包口味数乘以b-1。所以我们可以提前计算前缀和。然后通过二分查找找到门槛(b-1)的位置即可。
题解
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<long long> A(n), B(q);
for(int i = 0; i < n; i++) cin >> A[i];
for(int i = 0; i < q; i++) cin >> B[i];
// 排序并计算完整的前缀和数组
sort(A.begin(), A.end());
vector<long long> presum(n + 1, 0);
for(int i = 0; i < n; i++) {
presum[i + 1] = presum[i] + A[i];
}
long long sum = presum[n]; // 总茶包数
for(auto& b : B) {
if (b > sum) {
cout << "-1" << endl;
continue;
}
long long threshold = b - 1;
// 找到第一个大于threshold的元素位置
int index = upper_bound(A.begin(), A.end(), threshold) - A.begin();
long long ans = presum[index] + threshold * (n - index) + 1;
if (ans > sum) {
cout << "-1" << endl;
} else {
cout << max(ans, b) << endl;
}
}
return 0;
}
D - XNOR Operation
题意
给你一个长度为N的二进制字符串，找出满足下面条件的子串的数量
- 进行下列操作任意次，字符串可以变为"1"
- 选择两个相邻的数，进行同或运算，用结果替换参加运算的两个数。
思路
从同或运算的角度来分析有下面几种情况
- 00 -> 1
- 01 -> 0
- 10 -> 0
- 11 -> 1
可以看到，0的数量要不减2，要不不变，已知最终结果为"1"，逆向思考则可以推断源字符串中0的数量必然为偶数。
即字符串中0的数量为偶数是该字符串是优美字符串的必要条件
其次，对于任意一个字符串，由于01 -> 0且10 -> 0，即0可以"消灭"与其相邻的1，从而使得所有的0聚集在一起，此时如果0的数量为偶数，则根据00 -> 1所有的0都可以转化为1，由于11 -> 1所有的1也可以合并成"1"。
即字符串中0的数量为偶数是该字符串是优美字符串的充分条件
综上有该字符串是优美字符串等价于字符串中0的数量为偶数。
于是我们将原问题转化为了如下问题：
给你一个长度为N的二进制字符串，找出其所有满足0的数量为偶数的子串的数量。
对于这种在找子串的问题，可以通过递推方法较快地求得。
我们从源字符串的左边开始读取，每添加一个字符，若该字符为0，则之前的字符串中0的数量奇偶交换。若为1，则之前的字符串中0的数量奇偶不变，同时偶串的数量+1（因为1本身算一个子串，且"1"中0的数量为0）。
即令一维数组dp[i]为子串s[0...i]中0的数量为偶数的子串的数量。
则有
而结果则为dp的总和。
题解
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n; cin >> n;
string s; cin >> s;
long long dp[n];
if(s[0] == '0') {
dp[0] = 0;
} else {
dp[0] = 1;
}
for(long long i = 1; i < n; i++){
if(s[i] == '0') {
dp[i] = i - dp[i-1];
} else {
dp[i] = dp[i-1] + 1;
}
}
long long ans = 0;
for (int i = 0; i < n; i++) ans+=dp[i];
cout << ans << endl;;
}