新生娱乐赛第二场
D. 第一站
思路
考察基础输出。
代码
#include <stdio.h>
int main()
{
printf("Hello world!");
return 0;
}
E. 启程
一道考察选择结构的例题
思路
打车起步价 \(a\) 元，当已行走路程 \(s\) 超过 \(b\) 公里后，价格变为 \(a + (s - b) * c\) ，将最终价格和地铁价格比较。
代码
#include <stdio.h>
int main()
{
int a, b, c, x, d;
scanf("%d %d %d %d %d", &a, &b, &c, &x, &d);
int res = a;
if (x > b) res += (x - b) * c;
if (res > d) printf("Subway");
else printf("Taxi");
return 0;
}
N. 心爱的食物
一道考察循环的例题
思路
已知沈墨轩喜欢吃的食物种类，和该食物当前的数量，根据前面的同学要吃的食物，如果是沈墨轩喜欢吃的食物，则该食物的数量减一，最后判断一下沈墨轩喜欢吃的食物数量是否是大于零的数即可。
代码
#include <stdio.h>
const int N = 1e5 + 10;
int main()
{
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
int sum = 0;
for (int i = 1; i <= n; i ++)
{
int x;
scanf("%d", &x);
if (i == k) sum = x;
}
for (int i = 1; i <= m; i ++)
{
int x;
scanf("%d", &x);
if (x == k) sum --;
}
if (sum <= 0) printf("QnQ");
else printf("^_^");
return 0;
}
I. a+b(Easy version)
一道考察循环和数据类型的题目。
思路
对于输入的两个数，求和即可，记得要使用 \(long \ long\)，因为对于 \(10^{18}\) 级别的数是无法使用 \(int\) 进行存储的。
代码
#include <stdio.h>
const int N = 1e5 + 10;
int main()
{
int t;
scanf("%d", &t);
while (t --)
{
long long a, b;
scanf("%lld %lld", &a, &b);
printf("%lld\n", a + b);
}
return 0;
}
a+b(Hard version)
模拟题，对高精度算法的引导
前置知识：选择结构、循环结构
思路
每个数位对齐，进行相加，注意进位操作，最后按顺序输出结果即可。
代码
#include <stdio.h>
const int N = 1e5 + 10;
int a[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++)
scanf("%d", &a[i]);
int t = 0; // 表示进位的大小
int m;
scanf("%d", &m);
for (int i = 1; i <= m; i ++)
{
int x;
scanf("%d", &x);
a[i] += x; // 求和
}
if (m > n) n = m;
for (int i = 1; i <= n; i ++)
{
a[i] += t;
t = a[i] / 10; // 求进位
a[i] %= 10; // 求该数位最终保留一位为多少
printf("%d", a[i]);
}
if (t) printf("%d", t);
return 0;
}
C. 消消数
思维题
前置知识点：选择结构，循环结构
思路
一个数如果遇见比自己小的数，则可以将该较小数消除，则可以考虑到最大数无法通过这种消除方式被消除掉，于此可以贪心的用最大数将其余数都消除掉，但着手解决最大数问题。
一个数和另一个与之相等的数会一起消除。在最终只剩最大数的情况，考虑两两配对，则明显的最终一定是剩1或是全部消除。
代码
#include <stdio.h>
const int N = 1e6 + 10;
int a[N];
int main()
{
int n;
scanf("%d", &n);
int maxv = -1000000, cnt = 0;
for (int i = 1; i <= n; i ++)
{
int x;
scanf("%d", &x);
if (x > maxv) maxv = x, cnt = 0;
if (x == maxv) cnt ++;
}
printf("%d", cnt % 2);
return 0;
}
G. 军训游戏
思维题
前置知识：循环结构、排序算法
思路
两个同学在跑道上同时同速相对而行，相遇后就调转方向继续跑。思维转换，将反向去掉，两人擦肩而过，和原题意的结果相同：有两个同学同速跑向两个终点。由此，带入到更多人的情况同样适用，所以题目转换为：左部分同学跑向右边的终点，右部分同学跑向左边的终点，取一个最大时间。
题目没有说同学分散位置是从小到大给出，要进行排序。
代码
#include <stdio.h>
const int N = 1e6 + 10;
int a[N];
int main()
{
int t;
scanf("%d", &t);
while (t --)
{
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i ++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i ++)
for (int j = 1; j <= m - i; j ++)
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
int num = n - a[1];
if (num > a[m]) printf("%d\n", num);
else printf("%d\n", a[m]);
}
return 0;
}
L. AC自动机（假的）
一道模拟题
前置知识：双指针
思路
正确答案是程序结果的子序列，子序列的定义是对于原序列不连续的删去一部分元素后余下的保留原相对位置的序列。所以，我们可以考虑，枚举程序结果序列的同时匹配答案序列，如果在当前位置上的测序结果序列元素和答案序列元素相等，则可以匹配答案序列的下一个，否则要一直匹配当前的答案序列元素。
代码
#include <stdio.h>
#include <string.h>
const int N = 1e6 + 10;
char a[N], b[N];
int main()
{
int t;
scanf("%d", &t);
while (t --)
{
scanf("%s", a);
scanf("%s", b);
int n = strlen(a), m = strlen(b);
int j = 0;
for (int i = 0; i < m; i ++) // 枚举程序序列
if (b[i] == a[j]) j ++; // 匹配答案序列，如果相等就匹配下一个
if (j == n) printf("AC\n");
else printf("WA\n");
}
return 0;
}
B. GCD棋盘
规律题
前置知识：最大公约数
思路
写出一组 \(n \times n\) 的矩阵，表示GCD棋盘
1 1 1 1 1 1 1
1 2 1 2 1 2 1
1 1 3 1 1 3 1
1 2 1 4 1 2 1
1 1 1 1 5 1 1
1 2 1 2 1 6 1
1 1 1 1 1 1 7
考虑如果用最笨方法，一步一步慢慢走，可以发现到每个 \((m, m)\) 的格子距离比上一个 \((m-1, m-1)\) 的格子要多出 2 步。
观察棋盘可以发现对于所有大于2的偶数点附近一定有一个 2 的数值，且两者的距离是2步，而所有大于2的偶数点相对 \((2, 2)\) 点的步数一定超过 2，此时可以在 \((2, 2)\) 点使用传送为最佳。再考虑奇数，发现在小于 \(n\) 的奇数附近也一定出现 2 的数值，同理此时在 \((2, 2)\) 点使用传送为最佳。最后思考 \(n\) 恰好为奇数的情况，发现还是传送到附近的 2 的数值的点上再走到目标点是最佳的。
代码
#include <stdio.h>
#include <string.h>
const int N = 1e6 + 10;
char a[N], b[N];
int main()
{
int t;
scanf("%d", &t);
while (t --)
{
int n, m;
scanf("%d %d", &n, &m);
if (m == 1) printf("0\n"); // 特殊情况，就在（1，1）格子上
else if (m == 2) printf("2\n"); // 到（2，2）格子，无论在什么情况下都是2步
else if (m == 3) printf("4\n"); // 到 （3，3）格子，发现使用传送或是直接走的步数是一样的，且特殊情况 n = 3时无法使用传送
else {
if (m % 2) {
// 奇数点同样借助（2，2）使用传送
if (m == n) printf("6\n"); // 特殊情况，发现n=m且n为奇数情况下，距离其最近的2的点要走4步
else printf("4\n");
}
else printf("4\n"); // 传送到偶数点要借助（2，2）点使用传送，最终步数为4
}
}
return 0;
}
H. 数组的循环右移
模拟题
数组处理，对循环结构的深入掌握
思路
按题意进行模拟即可，有几个细节处理。
- \(t\) 的数值可能会大于 \([l,r]\) 区间的总长，当循环长度为区间长度的时候是没有意义的，考虑将 \(t\) 值缩小，\(t = t \% (r - l + 1)\)
- 区间右移，可以发现第 i 个元素最终会在第 \((i - l + t) \% (r - l + 1) + l\) 的位置上。
代码
#include <stdio.h>
#include <string.h>
const int N = 1e6 + 10;
int a[N], b[N];
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
while (m --)
{
int l, r, k;
scanf("%d %d %d", &l, &r, &k);
int num = r - l + 1; // 计算区间长度
k %= num; // 缩小右移位置
// 枚举区间
for (int i = l; i <= r; i ++)
{
int pos = ((i - l + k) % num) + l; // 计算该元素最终会移动到的位置
b[pos] = a[i]; // 借助一个数组来暂存元素，避免被覆盖
}
for (int i = l; i <= r; i ++) a[i] = b[i];
}
for (int i = 1; i <= n; i ++) printf("%d ", a[i]);
return 0;
}
K. 找点
思路
将每个点存下，枚举所有位置的点，如果符合要求就答案记录加一。
代码
#include <stdio.h>
#include <string.h>
#include <math.h>
const int M = 25;
const int N = 1e6 + 10;
int a[M][M];
struct node {
int x, y;
} p[N];
int main()
{
int n, dx, dy;
scanf("%d %d %d", &n, &dx, &dy);
for (int i = 1; i <= n; i ++)
{
int x, y;
scanf("%d %d", &x, &y);
// 存点
a[x][y] ++;
p[i] = {x, y};
}
for (int i = 1; i <= n; i ++)
{
int res = 0;
for (int j = 1; j <= 20; j ++)
for (int k = 1; k <= 20; k ++)
if (a[j][k] && abs(p[i].x - j) <= dx && abs(p[i].y - k) >= dy) res += a[j][k];
printf("%d ", res);
}
return 0;
}
O. 送分题
前置知识：博弈论
思路
可以想到最小值一定是最快被减到零的数，所以对于先手来说：
- 如果第一个数不是最小值那么先手就可以把最小数交换过来交给后手处理，且不论后手进行任何操作，先手始终交换最小数给后手，最终一定是最小数先减到零，后手必输。
- 如果第一个数是最小数，那么无论先手进行任何操作，后手始终选择交换最小数，则先手必输。
以上的操作是最优策略，也是最快策略，也即操作的回合数包括最基本的最小值的减一和交换回合，第一种情况要多进行一步交换操作。
代码
#include <stdio.h>
#include <string.h>
#include <math.h>
const int M = 25;
const int N = 1e6 + 10;
int a[N];
int main()
{
int t;
scanf("%d", &t);
while (t --)
{
int n;
scanf("%d", &n);
int minv = 2e9;
for (int i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
if (a[i] < minv) minv = a[i];
}
if (a[1] == minv) printf("LJQ %d\n", 2 * minv);
else printf("SMX %d\n", 2 * minv + 1);
}
return 0;
}
A. 这是一道签到题（你信吗）
思路
两种操作：三种原矿各取一个做一个能量元件或一种原矿取三个做一个能量元件，最终每四个能量元件换一个玉璧。
贪心思路，先尽可能使用第一种方法制作元件直到第一种不行后再使用第二种，或尽可能使用第二种方法制作元件知道第二种不行后再使用第一种，然后再从这两种方法中取一个最大值。
代码
#include <stdio.h>
int n;
int main()
{
int t;
scanf("%d", &t);
while (t --)
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
int minv = a;
if (b < minv) minv = b;
if (c < minv) minv = c;
int num = minv + (a - minv) / 3 + (b - minv) / 3 + (c - minv) / 3;
int res = a / 3 + b / 3 + c / 3;
a %= 3;
b %= 3;
c %= 3;
if (b < a) a = b;
if (c < a) a = c;
res += a;
if (num > res) res = num;
printf("%d\n", (res + 3) / 4);
}
return 0;
}
M. 放置能量石
前置知识：前缀和、数学
思路
最优策略放置能量石，可以观察到长度为偶数的土地先手必败，长度为奇数的土地先手必胜。所以预先统计每场比赛的沈墨轩胜负情况，做一个前缀和。对于前 \(x\) 场一胜一负的不同搭配方案，简单组合数学，假设前 \(x\) 场胜 \(n\) 场则拜 \(x - n\) 场，搭配方案为 \(n \times (x - n)\) 个。
代码
#include <stdio.h>
const int N = 1e5 + 10;
long long a[N], s[N];
int main()
{
int t;
scanf("%d", &t);
while (t --)
{
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++)
{
scanf("%lld", &a[i]);
a[i] %= 2;
}
for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];
while (m --)
{
int op, l, r;
scanf("%d", &op);
if (op) {
scanf("%d", &l);
printf("%lld\n", s[l] * (l - s[l]));
}
else {
scanf("%d %d", &l, &r);
printf("%lld\n", s[r] - s[l - 1]);
}
}
}
return 0;
}