比赛信息
题目难度
正确率分布情况:
题目详解
解析:这是一道使用数字按照特定规律输出的题目,其中的思维点在于对于数字倒序输出的写法以及对输出规律的观察分析:
首先我们可以看到,偶数行是按照顺序输出的,奇数行是按照逆序输出的,且最大数为n的平方。
1——2——3
6——5——4
7——8——9
对于输出数字的计算,举个例子:
比如我们现在第一个数是
6+(3-1)=8
(7-1)+(3-1-1)=7
(8-2)+(3-1-1-1)=6
也即:
6+(3-1)-0=8
6+(3-1)-2=7
6+(3-1)-4=6
通过观察,我们可以知道,在确定了第一个数之后,剩下的数字都可以倒序推算出来:
基数+(输出个数-1)-所在列数*2=当前列数字
那么直接使用代码即可实现,此处使用到了嵌套循环来控制输出的行与列:
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int num = 1;
for (int i = 0; i < n; i++) { //以 i 控制输出 行 位置
for (int j = 0; j < n; j++) { //以 j 控制输出 列 位置
if (i % 2 == 0) {
// 偶数行从左到右输出
printf("%d ", num);
} else {
// 奇数行从右到左输出
printf("%d ", num + n - 1 - 2 * j);
}
num++;
}
printf("\n");
}
return 0;
}
同时也可以使用数组来实现:
(1)、C99动态数组
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int square[n][n];
int num = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i % 2 == 0) {
square[i][j] = num;
} else {
square[i][n - j - 1] = num;
}
num++;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", square[i][j]);
}
printf("\n");
}
return 0;
}
(2)、malloc动态数组
#include <stdio.h>
#include <stdlib.h>
int main() {
int n;
scanf("%d", &n);
int** square=(int**)malloc(n*sizeof(int*));
for(int i=0;i<n;i++)
{
square[i]=(int*)malloc(n*sizeof(int));
}
int num = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i % 2 == 0) {
square[i][j] = num;
} else {
square[i][n - j - 1] = num;
}
num++;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", square[i][j]);
}
printf("\n");
}
return 0;
}
通过转换光的路径能证明出来,不存在NO的情况。只要证明无NO的情况就很好确定了。
接下来我们证明不存在NO的情况:
对于第一次反射,我们沿对应反射边翻转矩形
因为是在矩形内部反射,所以只是相对位置改变,但是这样我们就能将光的路线变成直线
所以对于光线有没有打到某个角落,就转换成了,在一个n,m的矩形坐标系中能否经过整数点。
又因为光线的角度为45°所以就有是否存在整数 a , b 使得以下式子成立: a × n = b × m = k
对于确定的n,m而言 ,k 自然就是两个数的公倍数,求第一次反射到的角,那么 k 就是两个数的最小公倍数,显然对于确定的两个正整数,最小公倍数一定存在。
至此,一定有解,得证 。接下来我们考虑如何确定是哪一个角。
回到我们这个图像
我们的矩形是我们翻转过去的,而且最终一定打在右上角,所以我们原路再翻转回来就能确定位置啦。而左右翻转次数就是 k / n , 上下翻转次数就是 k / m。这道题到这就已经解决了,但是如果我们已经证明出来了不存在NO的情况,确定答案角我们有更好的方法。因为是45°入射显然无论怎么反射,一定是以下四种情况之一。
对于这四种情况,我们发现,光线前进一格横纵坐标之和的奇偶性不发生改变,最后打到的角也在光线路径上,所以也满足这个条件。两个边长n,m如果有一个奇数或者全是奇数,剩下三个角只有一个角满足坐标之和为偶数。 如果两个全是偶数,那么我们可以一直除 2 找比它的更小的相似矩形,因为边长 3 4 和边长 6 8 的矩形,光线路径肯定是相似的,打到角的位置自然不变。
代码如下:
#include <bits/stdc++.h>
using namespace std;
int a, b;
void k2() {
cout << a << " 0" << endl;
return;
}
void k1() {
cout << "0 " << b << endl;
return;
}
void k3() {
cout << a << " " << b << endl;
return;
}
int gcd(int x, int y) {
return x == 0 ? y : gcd(y % x, x);
}
signed main() {
int t;
cin >> t;
while (t--) {
cin >> a >> b;
int n = gcd(a, b);
int x = a / n, y = b / n;
cout << "YES" << endl;
if (x % 2 && y % 2) {
k3();
}
else if(x%2&&y%2==0){
k1();
}
else k2();
}
return 0;
}
解析:本题考查字符串翻转写法,同时还增加了难度,按照区间翻转。
此处我们使用
代码如下:
(1)、C语言
#include <stdio.h>
void reverseString(char *str, int l, int r) {
// 翻转字符串中从l到r区间的字符
for (int i = 0; i < (r - l + 1) / 2; i++) { //从两边向内翻转,只需要翻转一半的次数
char temp = str[l - 1 + i];
str[l - 1 + i] = str[r - 1 - i];
str[r - 1 - i] = temp;
}
}
int main() {
// 输入字符串的长度和翻转次数
int n, m;
scanf("%d %d", &n, &m);
// 输入初始字符串
char initial_string[n + 1];
scanf("%s", initial_string);
// 对字符串进行 m 次翻转
for (int i = 0; i < m; i++) {
// 输入翻转区间l和r
int l, r;
scanf("%d %d", &l, &r);
// 进行翻转
reverseString(initial_string, l, r);
}
// 输出最终结果
printf("%s\n", initial_string);
return 0;
}
(2)、Python
def reverse_string(s, l, r):
# 将字符串 s 中从 l 到 r 区间的字符进行翻转
return s[:l-1] + s[l-1:r][::-1] + s[r:]
def main():
# 输入字符串的长度和翻转次数
n, m = map(int, input().split())
# 输入初始字符串
initial_string = input()
# 对字符串进行 m 次翻转
for _ in range(m):
# 输入翻转区间 l 和 r
l, r = map(int, input().split())
# 进行翻转
initial_string = reverse_string(initial_string, l, r)
# 输出最终结果
print(initial_string)
if __name__ == "__main__":
main()
解析:本题是对高中学过的排列组合的考察(插空法)。
我们可以把需要涂色的格子分成三种(每种都是2×1个一个小格子组成的)。
这三种分别是:
1.上面是黑块,下面是白块
2.上面是白块,下面是黑块
3.上下都是白块
我们先把n-1个有黑块单位拼接到一起,将纯白块的单位插到n-1个单位的空中就可以求出方案数了。
当将白块插入后白块左右两部分是有可能是这两种情况中的任意一种。
所以每插入一个空就会多产生2×2种方案,方案数就是(n-2)×4;对于最左侧和最右侧两种特殊情况各会提供两种方案,所以方案数就是(n-1)×4。要注意的是对于n=1的情况,这时候没有黑块所以只有一种方案,分类讨论一下即可。
代码如下:
#include<stdio.h>
int main()
{
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
int ans;
if (n == 1) {
ans = 1;
}
else {
ans = (n - 1) * 4;
}
printf("%d\n", ans);
}
return 0;
}
解析:定义两个数组,将两个数组里的数字元素一一对应进行对比,如果
代码如下:
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int a[n], b[n];
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (int i = 0; i < n; i++) {
scanf("%d", &b[i]);
}
for (int i = 0; i < n; i++) {
// 判断奇偶性是否相同
if ((a[i] % 2 == 0 && b[i] % 2 == 0) || (a[i] % 2 == 1 && b[i] % 2 == 1)) {
continue;
} else {
// 如果奇偶性不同,输出NO并结束
printf("NO\n");
return 0;
}
}
// 所有数字的奇偶性都相同,输出YES
printf("YES\n");
return 0;
}
解析:如果我们打算列出所有可能一种骰子就有4种可能,最多就达到417种可能,在给定的时间下肯定是不行的。
我们考虑观察两个骰子的所有可能,能想到的自然是两个骰子各自的可能数一一组合
我们观察到点数之和,在每一斜线相同,对于某一个点数,能对其造成贡献的就是错位的数量。
继续移动第二个骰子的点:
持续这个过程直到两个数列不相交,我们就得到了两个骰子的所有情况。对于多一个骰子的情况,我们以此类推,不过是将前两个骰子的合成 一个骰子,并且每个点数的出现次数也不再为一。
每个骰子状态与前几个骰子的状态一一结合,线性后移就能的得出答案。我们类比6面骰子写4面骰子,用代码实现这个过程,提前将所有组合 答案存到数组里面,询问时对应输出及可。
代码如下:
#include<stdio.h>
int main()
{
int n,q;
scanf("%d%d",&n,&q);
int dp[ 20 ][ 1001 ];
int i=0 , j=0;
dp[ 0 ][ 0 ]=1;
for( i=1; i<=n; i++ )
{
for( j=1;j<=1000;j++)
{
int te=0;
for( int e=-1; e>=-4; e-- )
{
if( j+e>=0 ) te+=dp[ i-1 ][ j+e ];
}
dp[ i ][ j ]=te;
}
}
while(q--)
{
int k;
scanf("%d",&k);
printf("%d\n",dp[n][k]);
}
return 0;
}
解析:模拟题主要是读懂题意,根据学生的回答最终可以统计出 1~60 一共多少学号出现过,最后判断是否满足两个条件之一即可。
代码如下:
#include<stdio.h>
int main()
{
int k, n;
scanf("%d%d", &k, &n);
char s[5];
int sign[65] = { 0 };
int i = 0;
int num = 0;
for (i = 1; i <= 60; i++) {
scanf("%s", s);
scanf("%d", &num);
if (num >= 1 && num <= 60) sign[num] = 1;
}
int sum = 0;
for (i = 1; i <= 60; i++) {
if (sign[i] == 1) sum++;
}
if (sum < k || sum - n>7) printf("YES\n");
else printf("NO\n");
return 0;
}
解析:当我们取得第k张卡牌将会得到这张卡牌所有的数字,将这上面的卡牌记录一下,遍历一下这些数字所对应的卡牌,将这些对应卡牌上的数字记录一下,最后遍历一下所有数字,即可统计出来一共得出多少种数字。
代码如下:
#include<stdio.h>
int a[1010][1010], num[1010], st[1010];
int main() {
int n, k, ans = 0;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &num[i]);
for (int j = 1; j <= num[i]; j++) {
scanf("%d", &a[i][j]);
}
}
for (int i = 1; i <= num[k]; i++) {
int flag = a[k][i];
st[flag]++;
for (int j = 1; j <= num[flag]; j++) {
st[a[flag][j]]++;
}
}
for (int i = 1; i <= 1000; i++) {
if (st[i] > 0) ans++;
}
printf("%d\n", ans);
}
解析:1乘任何数都等于他本身,所以在这题里面只需要考虑 2 的个数即 可。我们需要找到一个点使两边2的数量相等即可达到目的。
当序列中没有给出2时,我们输出1即可。
设序列中所有2的数量为num,当 num为奇数时,我们是找不到一个点使两边2的数量相等,输出-1;当num为偶数时,第num/2个2满 足题意,我们又要输出满足题意最小的下标,所以输出这个2的下标 即可。
代码如下:
#include<stdio.h>
int a[1010];
int main() {
int n, k = 0, num = 0, cnt = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if (a[i] == 2) num++;
}
if (num % 2 == 1) {
printf("-1");
}
else {
for (int i = 1; i <= n; i++) {
if (a[i] == 2) cnt++;
if (cnt == num / 2) {
k = i;
break;
}
}
printf("%d\n", k);
}
return 0;
}
解析:这里考察对函数
在函数
我要输出
代码如下:
#include <stdio.h>
int main()
{
printf("int用%%d输入输出,long int用%%ld输入输出,long long int用%%lld输入输出");
return 0;
}
以上解析来自 官方解析 与 本人部分解析拓展,如有问题,请留言指出,喵~
暂无评论内容