A
一道简单的语法题,直接输出"hello nowcoder"即可。
代码
#include <stdio.h>
int main()
{
printf("hello nowcoder");
}
B
也是一道语法题,考察分支结构。根据题意进行判断输出即可。
代码
#include <stdio.h>
int main()
{
int a, b;
scanf("%d %d", &a, &b);
if (a > b) {
printf(">");
}
else if (a < b) {
printf("<");
}
else {
printf("=");
}
}
C
一道考察循环结构的语法题,枚举1~n,对于每个数,进行mod10运算,获取最低位上的数进行判断是否是目标数,如果是则答案加一。
代码
#include <stdio.h>
int count(int x, int t)
{
int res = 0;
while (x)
{
if (x % 10 == t) res ++;
x /= 10;
}
return res;
}
int main()
{
int n, x;
scanf("%d %d", &n, &x);
int ans = 0;
for (int i = 1; i <= n; i ++)
{
ans += count(i, x);
}
printf("%d", ans);
return 0;
}
D
一道很不错的题,解法不唯一,纯用作考察循环结构也行。 以下我的解析:
根据题意,可以有如下规律:
发放的金币总量是
\[total = 1 + 2^2 + 3^2 + {\cdots} + d^2 + k,\qquad k<(d+1)^2 \]发放天数是
\[day=1+2+3+{\cdots}+d+k^{'} = \frac{(1+d)*d}{2}+k^{'}, \qquad k^{'}<d+1 \]由此可见我们只需循环枚举金币数n,每次减去天数k和金币数加上k*k,当剩余天数k>=n时特殊处理,答案加上n*k。
代码
#include <stdio.h>
int main()
{
int n;
scanf("%d", &n);
int total = 0, k = 1;
while (n >= k)
{
total += k * k;
n -= k;
k ++;
}
total += n * k;
printf("%d", total);
return 0;
}
但我们可以注意到在\(day = \frac{(1 + d)*d}{2} {\le}n\)时,我们是做一个\(\sum_{i=1}^{d}i^2=\frac{d*(d+1)*(2*d+1)}{6}\),做完这个求和再特殊处理k即可,看如下代码,注意公式可能超过int范围。
#include <stdio.h>
#include <math.h>
#define ll long long
int main()
{
int n;
scanf("%d", &n);
ll d = (sqrt(1 + 8 * n) - 1) / 2; // 求根公式
int total = d * (d + 1) * (2 * d + 1) / 6;
total += (n - d * (d + 1) / 2) * (d + 1);
printf("%d", total);
return 0;
}
一道不错的算法入门,主要是思考如何用算法优化到接近\(O(1)\)
E
一个算法入门题吧,当然只跑循环枚举也能解题,这里主要引入一下欧几里得算法(gcd),不细讲,大家自行查找资料。
题意提取就是寻找三个数的最小公倍数。
gcd算法就是求两个数的最大公因数,而可知最小公倍数=两个数的乘积除以最大公约数。这题就明了了,先求前两个数的最小公倍数,再和最后一个求最小公倍数。
代码
#include <stdio.h>
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a; // 辗转相除法,翁恺貌似讲过,大家翻翻视频
}
int main()
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
int num = a * b / gcd(a, b);
int res = num * c / gcd(num, c);
printf("%d", res);
}
再贴一道暴力跑循环的题解,仅适用此题
#include <stdio.h>
int main()
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
int res = 0;
for (int i = 1; i <= a * b * c; i ++)
if (i % a == 0 && i % b == 0 && i % c == 0)
{
res = i;
break;
}
printf("%d", res);
return 0;
}
F
题目大意是告诉一个等差数列的首项和公差,问你在第\(l\)和\(r\)项之间是奇数多、偶数多还是一样多。
根据最基本的数值计算:
由此,公差为偶数时,首项为奇数则数列都是奇数,首项为偶数则数列都是偶数;公差为奇数时,数列都是一个奇偶交叉的数列,这时就考虑询问的区间,如果询问区间个数是一个偶数,则区间内奇偶一定是相同的;如果询问的个数是一个奇数,思考第\(l\)项是什么数,因为奇数个数数列区间首项和尾项一定是相同的性质,每两个一组,则多出的那个决定了答案。
\[奇偶奇偶奇偶奇偶奇\\ 偶奇偶奇偶奇偶奇偶\\ \]让数列从1开始标号,可以发现一个性质,首项是奇数的数列,偶数项一定偶数,奇数项一定是奇数;首项是偶数的数列,偶数项一定奇数,奇数项一定是偶数,到此,我们可以根据询问的区间首项\(l\)来得出答案。
代码
#include <stdio.h>
#define ll long long
int a, k, q;
int main()
{
scanf("%d %d %d", &a, &k, &q);
a %= 2, k %= 2; // 简化,1是奇数,0是偶数
while (q --)
{
int l, r;
scanf("%d %d", &l, &r);
if (!k) // 公差为偶数时
{
if (a) {
printf("1\n");
} else {
printf("-1\n");
}
}
else
{
if ((r - l) % 2) { // 区间个数是偶数
printf("0\n");
} else if ((a + l) % 2) { // 根据首项和l的奇偶性判断
printf("-1\n");
} else {
printf("1\n");
}
}
}
return 0;
}
G
一个经典的贪心题,引入算法贪心。
贪心算法,如字面意思,在每一步操作都进行最贪婪步骤,意图以最快或最优达成目标。
题目意思是从0开始+1或+3到达目标点,其中+3不能连续进行,问最小步骤数。显然的,要最快,必然是贪婪做最多的+3操作,快速靠近目标点,然后再用+1补上。但+3不能连续操作,那么就要中间插入+1操作,必然贪婪的插入最少的+1操作,由此解法就明显了。
代码
#include <stdio.h>
#define ll long long
ll n;
int main()
{
scanf("%d", &n);
// 既然是保证+1间隔+3操作,就以这两个为一组,让总数mod4,恰好整除步数就是n/2
if (n % 4 == 0) {
printf("%lld", n / 4 * 2);
} else if (n % 4 == 1 || n % 4 == 3) {
printf("%lld", n / 4 * 2 + 1); // 差1或3,我们是可以一步到达的
} else {
printf("%lld", n / 4 * 2 + 2); // 差2,只能两次+1操作
}
return 0;
}
H
全场最难,思维题
mex和gcd的定义看题目,这里不细讲。
根据题目,首先处理特殊情况,全0下,答案必是0,因为gcd(0,0) = 0
思考
- 当\(mex \ge 2\)时,此时区间内一定有0,1两个数,则gcd一定等于1,那么这时就要让mex值最大即可,mex最大的情况就是全数组都选。
- 当\(mex=0\)时,答案一定为0,不用考虑gcd
- 当\(mex=1\)时,区间一定有0,而选择的数越多,gcd数一定越小,所以要选最少的数,我们只需再选与0相邻的数。
代码
#include <stdio.h>
#include <stdbool.h>
#define ll long long
const int N = 1e5 + 10;
int n, res;
int a[N];
ll sum;
bool st[N];
int max(int a, int b)
{
return a > b ? a : b;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
sum = sum + a[i];
st[a[i]] = 1;
}
// 特殊判断全0的情况
if (sum == 0) {
printf("%d", 0);
return 0;
}
// 找出全部数的mex
while (st[res]) res ++;
// 找0相邻的数,取一个最大。
for (int i = 1; i <= n; i ++)
if (a[i] == 0) {
res = max(res, a[i - 1]);
res = max(res, a[i + 1]);
}
printf("%d", res);
return 0;
}