A
给你一个长度为 \(n\) 的字符串 \(s\)，判断 \(s\) 是否满足以下条件：
- \(s\) 的第一个字符是大写字母，其余字符都是小写字母。
代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
char s[105];
int main() {
scanf("%s", s + 1);
int len = strlen(s + 1);
if(s[1] < 'A' || s[1] > 'Z') {
printf("No\n");
return 0;
}
for (int i = 2; i <= len; i++) {
if(s[i] < 'a' || s[i] > 'z') {
printf("No\n");
return 0;
}
}
printf("Yes\n");
return 0;
}
B
给你一个由小写英文字母组成的字符串 \(s\)。请找出在 \(s\) 中出现频率最高的字符。如果存在多个这样的字符，请输出按字典序最早的那个。
思路：
用 \(tong_i\) 表示字母表中第 \(i\) 个字母出现的次数。
注意，字符串里的每个字符其实是他们的 \(\text{ASCII}\) 码值而非第几个字母。
然后遍历一遍 \(26\) 个字母，找出出现最多的中出现最早的输出即可。
代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
char s[1005];
int tong[105];
int main() {
scanf("%s", s + 1);
int len = strlen(s + 1);
for (int i = 1; i <= len; i++) {
tong[s[i] - 'a' + 1] ++;
}
int maxn = -1;
int maxx;
for (int i = 1; i <= 26; i++) {
if(tong[i] > maxn) {
maxn = tong[i];
maxx = i;
}
}
printf("%c", char(maxx + 'a' - 1));
return 0;
}
C
冰箱里有 \(n\) 种配料，\(1, 2,\dots,N\)。配料 \(i\) 有 \(Q_i\) 克。
有 \(2\) 种菜。制作一份 A 菜，需要 \(A_i\) 克的配料 \(i\)。制作一份 B 菜，需要 \(B_i\) 克配料 \(i\)。每种菜只能做整数份。
最多可以制作多少份菜？
思路：
注意到 \(A_i, B_i, Q_i \le 10^6\)，也就是说每种菜最多能做 \(10^6\) 份。枚举 A 菜的数量 \(i\)，从 \(1\sim 10^6\)，算出做 \(i\) 份 A 菜，每种配料需要多少，然后看看用剩下的配料最多能做多少份 B 菜，与答案取 \(\max\)。
代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5 + 5;
int n;
int q[15], a[15], b[15];
int qq[15];
int ans;
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &q[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%lld", &b[i]);
}
for (int i = 0; i <= 1000000; i++) {
bool f = true;
for (int j = 1; j <= n; j++) {
qq[j] = q[j];
if(i * a[j] > qq[j]) {
f = false;
break;
}
else {
qq[j] -= i * a[j];
}
}
if(!f) continue;
int nowans = LONG_LONG_MAX;
for (int j = 1; j <= n; j++) {
if(b[j]) {
nowans = min(nowans, qq[j] / b[j]);
}
}
ans = max(ans, nowans + i);
}
printf("%lld\n", ans);
return 0;
}
D
推销下我的题解，点个赞呗QwQ
给定一张 \(n\) 个点的无向图，第 \(i\) 个点和第 \(i \bmod n + 1\) 个点之间有一条边。
现在要断掉一条边，然后按照给定顺序遍历全部点，求最小代价。
思路:
设 \(v_i\) 为断掉第 \(i\) 座桥之后所花费的代价。
考虑从 \(a\) 城市到 \(b\) 城市的代价。有两种情况：
-
走 \(a,a+1,a+2,\cdots,b\)，代价为 \(b-a\)；
-
走 \(a,a-1,a-2,\cdots,b\)，代价为 \(n+a-b\)。
如果断掉的桥在 \(1\) 号路线上，我们只能走 \(2\) 号路线；反之只能走 \(1\) 号路线。我们显然可以通过 \(m-1\) 次暴力操作求出 \(v_i\)，总复杂度 \(\Theta (nm)\)，但是数据范围太大，不可行。
考虑优化。我们不难发现，我们每次对一段的区间的加法操作总是一段连续区间（因为 \(1\) 和 \(n\) 之间也有一条边），而且加的数还是定值，显然可以差分。直接套差分板子，最后求一遍前缀和，答案即为 \(\min_{i=1}^{n}v_i\)。
代码:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
int n, m;
int x[MAXN];
long long v[MAXN];
long long ans = LONG_LONG_MAX;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m ;i++) {
scanf("%d", &x[i]);
}
auto dist = [&] (int from, int to) {
if(from <= to) return to - from;
else return n + to - from;
};
auto add = [&] (int from, int to, int num) {
if(from <= to) {
v[from + 1] += num;
v[to + 1] -= num;
}
else {
v[from + 1] += num;
v[n + 1] -= num;
v[1] += num;
v[to + 1] -= num;
}
};
for (int i = 1; i < m; i++) {
add(x[i], x[i + 1], dist(x[i + 1], x[i]));
add(x[i + 1], x[i], dist(x[i], x[i + 1]));
}
for (int i = 1; i <= n; i++) {
v[i] += v[i - 1];
ans = min(ans, v[i]);
}
printf("%lld", ans);
return 0;
}