# 题目大意
给定一个字符串 S，t 是其子串，如果 t0 和 tlast 都是字符 t 的话，它就会有一个值，字符串长度−2字符t的个数−2
请你求出最大的这个值
# 题解
- 1≤len≤100
# 题解
其实题目很容易，但是为什么写在这呢？
是因为，在写这题的时候，用了 vector，在其大小为 0 的时候，我访问了 idx.size() - 1
此时会有一个神奇的事情发生，这个的结果并不是 −1，而是一个超级大的数，为什么呢？
这是由于 .size() 的类型是无符号整数，当 −1 后，直接溢出了，进而会造成 TLE
# 题目大意
你有 n 个茶包，第 i 个茶包里有 Ai 包茶，口味为 i
现在你和庄家做一个游戏，游戏难度在 [1,i=1∑nAi]，假设为 b
- 你申明一个整数 x，b≤x≤i=1∑nAi
- 庄家从桌子上选 x 包茶给你
- 你从 x 包茶中选择 b 包
- 如果这 b 包都是一个口味，那么你赢了
你现在有 Q 个问题，第 j 个问题是
- 一个难度为 Bj 的游戏，你能获胜的最小整数 x 是多少（必须赢）
# 题解
我要从你给我的一堆茶中，选 b 包同样口味的
站在庄家的角度
→ 如果一开始，某个茶包中的茶数量 <b，庄家可以把这个茶包里的茶全部给我；然后可以找到第一个 ≥b 的茶包（ idx ），1→idx−1 都可以给我 → 二分找 b、前缀和计算前 idx−1 个
接下来，是不是有 n−b 个茶包里面的茶 ≥b，如果给我 (n−b)∗(b−1) 包，那我就赢不了
也就是说，再多给我一包，我就赢了
x = pre[idx - 1] + (n - b) * (b - 1) + 1
C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void solve () {
cin >> n >> q, a = vector<int>(n + 1), pre = vector<int>(n + 1);
for (int i = 1, x; i <= n; i++)
cin >> a[i];
sort(a.begin() + 1, a.end());
for (int i = 1; i <= n; i++)
pre[i] = pre[i - 1] + a[i];
while (q--) {
int res = 0;
cin >> b;
if (b > a[n]) {
cout << -1 << '\n';
continue;
}
int idx = lower_bound(a.begin() + 1, a.begin() + n + 1, b) - a.begin();
res += pre[idx - 1] + (n - idx + 1) * (b - 1) + 1;
cout << res << '\n';
}
}
|
# 题目大意
给你一个长度为 n 的，只由 0/1 组成的字符串 s，你可以执行任意次一下操作
- 任选两个相邻的字符，两者相同则变为 1，否则变为 0
如果一个字符串能通过若干次这种操作，变为一个 1，则称这个字符串为好字符串
现在给你一个字符串，问其中，有多少个字串是好字符串
# 数据范围
- 1≤n≤105
# 题解
不难发现，只要字符串中，0 的个数是偶数个，那么这个字符串就是好字符串
利用 桶 的思想，计算个数
C++1
2
3
4
5
6
7
8
9
10
11
| void solve () {
cin >> n, s = " " + s, t[0]++;
for (int i = 1; i <= n; i++) {
cnt += (s[i] == '0');
res += t[cnt % 2]++;
}
cout << res << '\n';
}
|
# 题目大意
给定 n 个点，每个点的坐标是 (xi,yi)，保证不存在三点共线，请问一共能确定多少个梯形
# 数据范围
- 4≤N≤2000
- 0≤Xi,Yi≤107
# 题解
题目答案 = 一对边平行的数量 - 平行四边形的数量
C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| int n;
vector<PII> a;
map<PII, int> xl;
unordered_map<double, int> f;
void solve () {
cin >> n, a = vector<PII>(n);
int res = 0;
for (int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second;
for (int j = 0; j < i; j++) {
xl[{a[i].first + a[j].first, a[i].second + a[j].second}]++;
}
}
for (auto t : xl)
res -= t.second * (t.second - 1) / 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
double xx = a[i].first - a[j].first, yy = a[i].second - a[j].second;
if (xx == 0)
f[-1e8]++;
else
f[yy / xx]++;
}
}
for (auto t : f)
res += t.second * (t.second - 1) / 2;
cout << res << '\n';
}
|
