A. 这是一道签到题
题目的背景是基于简单的博弈论Nim游戏，但细心者可以发现小明和小美的名字的首字母一致，所以只需要进行读入，直接输出"XM"即可通过本题
#include<stdio.h>
int n, x;
void solve()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &x);
puts("XM");
}
int main()
{
int T = 1;
scanf("%d", &T);
while (T--) solve();
return 0;
}
B. ACMer
判断每一组中1的个数是否大于2，如果大于2，则数量加一
#include<stdio.h>
int n, x, cnt = 0;
void solve()
{
int sum = 0;
for (int i = 0; i < 3; i++) // 读入三个数字
{
scanf("%d", &x);
sum += x;
}
if (sum >= 2) cnt++;
}
int main()
{
int T;
scanf("%d", &T);
while (T--) solve();
printf("%d\n", cnt);
return 0;
}
C. Stock Exchange(Easy Version)
观察题目我们发现数据的范围非常的小，1 ≤ n ≤ 2000，因此我们可以采取时间复杂度为 \(O(n^2)\) 的算法，也就是暴力的枚举每一个区间，寻找哪一对天数的股票价值的差最大。
#include<iostream>
const int N = 2010;
int n, a[N];
int max(int a, int b) // 比较 a b 大小并返回最大值的函数
{
return a >= b ? a : b;
}
void solve()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
{
ans = max(ans, a[j] - a[i]);
}
printf("%d\n", ans);
}
int main()
{
int T = 1;
while (T--) solve();
return 0;
}
D. Stock Exchange(Hard Version)
观察题目我们发现n的数据范围非常的大，因此我们不能再使用时间复杂度为\(O(n^2)\)的算法，而只能使用时间复杂度为\(O(n)\)或者\(O(n logn)\)的算法。
而对于本题我们想到贪心，在一次遍历的过程中动态地修改最小值，并计算最大值。
#include<iostream>
const int N = 1e6 + 10;
int n, a[N];
int min(int a, int b)
{
return a >= b ? b : a;
}
int max(int a, int b)
{
return a >= b ? a : b;
}
int main()
{
scanf("%d", &n);
int Min = 1e9, ans = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
Min = min(Min, a[i]);
ans = max(ans, a[i] - Min);
}
printf("%d", ans);
return 0;
}
E. /\
没啥好说的，注意转义字符 \
#include<stdio.h>
int main()
{
printf("/\\");
return 0;
}
F. BOX
简单的几何问题，如果给定点的三个坐标值都在长方体的三个坐标值确定的范围之内，则该点在盒子中。
#include<stdio.h>
class Point // 笔者写几何类题目的时候比较喜欢定义一个类 Point 表示点
{
public:
int x, y, z;
void read() { scanf("%d%d%d", &x, &y, &z); } // 定义一个函数使得读入更方便
};
int z0, h, u0, v0, u1, v1;
int min(int a, int b)
{
return a > b ? b : a;
}
int max(int a, int b)
{
return a > b ? a : b;
}
bool check(Point p)
{
if (p.z >= z0 && p.z <= z0 + h
&& p.x >= min(u0, u1) && p.x <= max(u0, u1)
&& p.y >= min(v0, v1) && p.y <= max(v0, v1))
return 1;
return 0;
}
void solve()
{
scanf("%d%d%d%d%d%d", &z0, &h, &u0, &v0, &u1, &v1);
int q;
scanf("%d", &q);
while (q--)
{
Point p;
p.read(); // 读入点的坐标；
puts(check(p) ? "YES" : "NO"); // 如果满足在盒子内部则输出"YES"
// 这里的语法可能用的比较繁琐，能理解就行
}
}
int main()
{
int T = 1;
while (T--) solve();
return 0;
}
G. 数学考试
思维题。
-
首先要能发现，当\(n\)，\(m\)是偶数时，即可以一半 \(1\) 为正数，一半 \(1\) 的负数，组内消化掉。
-
当 \(n\) 是奇数时，即当 \(1\) 的个数是奇数的时，显然 \(n - 1\) 是偶数，那么 必然能把 \(n - 1\) 个 \(1\) 分成 \((n - 1) / 2\) 组，那么每组中的两个 \(1\)， 一个前面是 "+" ，一个前面是 "-" ，则一定可以把 \(n - 1\) 个 \(1\) 抵消掉，无论 \(2\) 有多少个，也无法与最后剩下的那个奇数 \(1\) 相消，得证：当 \(n\) 为奇数是， 一定无法使数组之和等于 \(0\)。
-
当 \(2\) 的个数\(m\)是奇数时，当且仅当 \(1\) 的个数为偶数，且 \(1\) 个数不为 \(0\) 才可以存在两个 \(1\) 和多出来的那个 \(2\) 相消。
而除此之外的所有情况都存在一种可能性使得数组的元素之和等于 \(0\).
#include<stdio.h>
void solve()
{
int n, m;
scanf("%d%d", &n, &m);
if (n & 1) // 判断是奇数
{
puts("NO");
return;
}
if (m % 2 && !n) // n == 0 而且 m 是奇数
{
puts("NO");
return;
}
puts("YES");
}
int main()
{
int T;
scanf("%d", &T);
while (T--) solve();
return 0;
}
H. 200个数字
首先想到使用数组 cnt[i] 记录 数字i 出现的个数。
其次我们发现数字i可能是负数，那么增加一个偏移量就行了，譬如 偏移量 C = 110，那么此时 cnt[10] 记录就是 -100 出现的个数 计算公式如 -100 + C = 10；
此时从高向低遍历一遍，找到出现次数最多的数字，由于从高向低遍历，则一定满足该数字是出现次数一样多的数字里面的最大的。
#include<stdio.h>
const int C = 110; // 偏移量
int cnt[400], n;
void solve()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
cnt[x + C]++;
}
int Max = 0, ans = -1e9;
for (int i = -100 + C; i <= 100 + C; i++)
{
if (Max <= cnt[i])
{
Max = cnt[i];
ans = i - C;
}
}
printf("%d\n", ans);
}
int main()
{
int T = 1;
while (T--) solve();
return 0;
}