题目链接 题目 非官方代码
B - Pursuing the Happiness
题目大意
交换换一个字符串中的两个字符，使得结果不含子串
happiness
，如果无法完成则输出
NO
，否则输出
YES
以及交换的两个字符的下标。
思路 - 贪心
①如果这个字符串中子串
happiness
的个数大于
2
，则必定无法完成，输出NO； ②如果这个字符串中的子串
happiness
的个数等于
2
，则交换第一个happiness的
h
和第二个happiness的
a
；
③如果这个字符串中的子串happiness的个数等于
1
，则交换第一个happiness的
h
和a； ④如果这个字符串中不含子串
happiness
，此时要选择相同的字符交换，否则可能使得交换后的字符串含有
happiness
，如果不存在相同的字符，则必定不含有能够组成
happiness
的字符，选择最前的两个字符交换即可。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN =
200013;
const char HAPPINESS[] = {
"happiness"};
char s[MAXN];
int cnt, fir[
3], cnt_s, fir_s[
3], len;
bool judge(
int sta) {
for(
int i =
0; i <
9; ++i) {
if(s[sta + i] != HAPPINESS[i]) {
return false;
}
}
return true;
}
void solve() {
cnt =
0;
cnt_s =
0;
len =
strlen(s +
1);
for(
int i =
1; i <= len; ++i) {
if(s[i] ==
's' && cnt_s <
2) {
fir_s[cnt_s++] = i;
}
if(judge(i)) {
if(cnt ==
2) {
printf(
"NO\n");
return ;
}
fir[cnt++] = i;
}
}
printf(
"YES\n");
if(cnt ==
2) {
printf(
"%d %d\n", fir[
0], fir[
1] +
1);
}
else if(cnt ==
1){
printf(
"%d %d\n", fir[
0], fir[
0] +
1);
}
else {
if(cnt_s ==
2) {
printf(
"%d %d\n", fir_s[
0], fir_s[
1]);
}
else {
printf(
"1 2\n");
}
}
}
int main() {
while(
1 ==
scanf(
"%s", s +
1)) {
solve();
}
return 0;
}
B. Urn with Balls
题目大意
一个壶中有
a
个红球、b个绿球和
c
个颜色未知的球（红色或绿色），可以从这个壶中一次性拿出一些球，但要满足红球的个数不超过n，绿球的个数不超过
m
，求最多能拿多少球？
思路 - 贪心
①a c<=n && b c<=m，此时取出全部球也不会违反要求，答案为
a+b+c
； ②
a+c>n && b+c<=m
，此时只要不违反红球的规则即可，答案为
n
；
③a c>n && b c>n，此时两个规则都不能违反，所以只能取两个的较小值，答案为
min(n,m)
； ④
a+c<=n && b+c>n
，此时只要不违反绿球的规则即可，答案为
m
。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long a, b, c, n, m, ans;
int main() {
while(
5 ==
scanf(
"%I64d%I64d%I64d%I64d%I64d", &a, &b, &c, &n, &m)) {
if(a c <= n && b c <= m) {
printf(
"%I64d\n", a b c);
}
else if(a c > n) {
printf(
"%I64d\n", b c > m ? min(n, m) : n);
}
else {
printf(
"%I64d\n", m);
}
}
return 0;
}
D. Jumps
题目大意
一只青蛙在数轴上跳，但每次向左或向右只能跳固定的长度，有n中长度，分别为
ai
，青蛙初始在
0
，请问青蛙能否跳到x？
思路 - 数学
这道题和最大不能组成的数类似，所以直接判断所有长度的最大公约数能否被
x
整除即可，如果能则能到达x，否则不能到达
x
。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, x, gcd, a;
int main() {
while(
2 ==
scanf(
"%d%d", &n, &x)) {
scanf(
"%d", &gcd);
for(
int i =
1; i < n; i) {
scanf(
"%d", &a);
gcd = __gcd(gcd, a);
}
printf(
"%s\n",
abs(x) % gcd ==
0 ?
"YES" :
"NO");
}
return 0;
}
E. Bonuses and Teleports
题目大意
数轴上有n个传送点，位置分别为
ti
，
m
个奖金，位置分别为bi，一个人初始在
t1
，求拿完所有的奖金在回到
t1
时所走的最短距离？
思路 - 贪心 && 二分
两个传送点之间的奖金有两种拿法： ①从右边的传送点出发，拿完所有的奖金，然后再回到右边的传送点； ②从左边的传送点出发，拿一部分奖金（可以不拿，也可以全部都拿），然后回到左边的传送点，再从右边的传送点出发，拿剩余的奖金，然后再回到右边的传送点。
取两个传送点之间的所有奖金走的最短距离，就是上面两种情况下结果的最小值。
找两个传送点之间的奖金可以通过二分。
为了方便，再在
−INF
处和
INF
处分别添加一个传送点。
总时间复杂度：
O(max(nlogm,m))
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN =
200003;
const long long INF =
0x3f3f3f3f3f3f3f3f;
int n, m, pos;
long long t[MAXN], b[MAXN];
int sta, des;
long long ans;
int binSearch(
int l,
int r,
int key) {
int mid;
while(l <= r) {
mid = (l + r) >>
1;
if(b[mid] <= key) {
l = mid +
1;
}
else {
r = mid -
1;
}
}
return l;
}
int main() {
while(
2 ==
scanf(
"%d%d", &n, &m)) {
t[
0] = -INF;
t[n +
1] = INF;
for(
int i =
1; i <= n; ++i) {
scanf(
"%I64d", t + i);
}
for(
int i =
0; i < m; ++i) {
scanf(
"%I64d", b + i);
}
b[m] = INF +
1;
sta =
0;
ans =
0;
for(
int i =
0; i <= n; ++i) {
des = binSearch(sta, m, t[i +
1]) -
1;
if(sta <= des && b[des] <= t[i +
1]) {
long long tmp = min((b[des] - t[i]), (t[i +
1] - b[sta])) <<
1;
while(sta < des) {
tmp = min(tmp, ((b[sta] - t[i]) + (t[i +
1] - b[sta +
1])) <<
1);
++sta;
}
ans += min(tmp, t[i +
1] - t[i]);
sta = des +
1;
}
}
printf(
"%I64d\n", ans);
}
return 0;
G. I love Codeforces
题目大意
每个人初始有自己的昵称，然后按照时间顺序给出一些人的改昵称的规则，
a
b表示
a
的昵称将变为I_love_加上
b
当前的昵称，最后给出第一人的昵称。
思路 - 模拟
对每个人维护其前面有的I_love_的个数
cnt
，其最后的初始昵称的人
ori
，最后按照题意输出即可。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN =
200003;
int n, m, a, b;
char name[MAXN][
29];
int cnt[MAXN], ori[MAXN];
int main() {
while(
1 ==
scanf(
"%d", &n)) {
for(
int i =
1; i <= n; ++i) {
scanf(
"%s", name[i]);
cnt[i] =
0;
ori[i] = i;
}
scanf(
"%d", &m);
while(m-- >
0) {
scanf(
"%d%d", &a, &b);
cnt[a] = cnt[b] +
1;
ori[a] = ori[b];
}
for(
int i = cnt[
1]; i >
0; --i) {
printf(
"I_love_");
}
printf(
"%s\n", name[ori[
1]]);
}
return 0;
}
H. Perfect Ban
题目大意
有一个
n × m
的矩阵，去掉一行和一列中的所有数，使得剩下的数中最大值最小，求行和列的下标？
思路 - 贪心
找到数组中最大的元素的一个位置（如果存在多个，且能够完全去掉，则通过枚举行和列可找到最优解，如果不能完全去掉，随便选择即可），枚举删除行（列），然后在找到剩下的数中的最大的数的一个位置，删除列（行），再找到剩下的数中最大的数
mx
，输出上面两种情况中
mx
最小的即可。
刚开始想得比较复杂，考虑了每一行和每一列的全部的数，结果
WA
在第
54
组数据。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN =
1003;
int n, m;
int a[MAXN][MAXN];
bool isRow;
void getMax(
int r,
int c,
int& rr,
int& cc) {
int mx =
0;
for(
int i =
1; i <= n; ++i) {
if(i != r) {
for(
int j =
1; j <= m; ++j) {
if(j != c && mx < a[i][j]) {
rr = i;
cc = j;
mx = a[i][j];
}
}
}
}
}
int main() {
while(
2 ==
scanf(
"%d%d", &n, &m)) {
for(
int i =
1; i <= n; ++i) {
for(
int j =
1; j <= m; ++j) {
scanf(
"%d", &a[i][j]);
}
}
int fir_r, fir_c;
getMax(
0,
0, fir_r, fir_c);
int sec_r, sec_c;
getMax(fir_r,
0, sec_r, sec_c);
int tri_r, tri_c;
getMax(
0, fir_c, tri_r, tri_c);
int r, c;
getMax(fir_r, sec_c, r, c);
int rr, cc;
getMax(tri_r, fir_c, rr, cc);
if(a[r][c] < a[rr][cc]) {
printf(
"%d %d\n", fir_r, sec_c);
}
else {
printf(
"%d %d\n", tri_r, fir_c);
}
}
return 0;
}
M. Last Man Standing
题目大意
有
n
个人，每个人可以向其他人开枪杀死他，现给出每个人杀的人数，求一个合法的击杀顺序。
思路 - 贪心
从杀人最少的开始设置两个指针fir和
sec
，分别指向还能杀的人的数目最少的那个人 和 下一次会被杀的人，然后按照提议往前扫一遍即可。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN =
200003;
int n, a[MAXN], fir, sec;
long long sum;
int main() {
while(
1 ==
scanf(
"%d", &n)) {
sum =
0;
for(
int i =
1; i <= n; ++i) {
scanf(
"%d", a + i);
sum += a[i];
}
if(sum >= n) {
printf(
"NO\n");
}
else {
printf(
"YES\n");
fir = sec = n;
while(a[fir] ==
0) {
--fir;
}
while(fir >
0) {
printf(
"%d %d\n", fir, sec--);
if(--a[fir] ==
0) {
--fir;
}
}
}
}
return 0;
}
