郑州轻工业大学-23级新生C语言周赛(4)题目解析

057610

本次题解提供C/C++两种写法，部分题目两种写法区别很小，所以部分题目没有C++题解

比赛信息

比赛名称：23级新生C语言周赛(4)

比赛命题：宋甲一、魏煜丰、王果

比赛平台：郑州轻工业大学在线评测系统

比赛复现：ZZULIOJ – 测试平台

比赛时间：2023.11.19 14:00:00 ~ 17:00:00

参赛对象：郑州轻工业大学2023级新生(包含部分校外新生)

直播回放：

题目难度

图片[1],郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网

题目详解

图片[2],郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网

作为一个程序员，这种题目肯定要用不同的姿势解锁O_o

CV姿势1：

#include <stdio.h>

int main()
{
    printf(
        "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO\n"
        "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO\n"
        "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO\n"
        "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO\n"
        "OOOOOOooooooooooooooooOOOOOOOOOOOOOO@@OO@@@@@@@@OO@@OOOOOOOOOOOOO\n"
        "ooooooooooooooooooooooooooooooOOOO@@  @@        @@  @@OOOOOOOOOOO\n"
        "oooooooooooooooooooooooooooooooooo@@                @@OOOOOOOOOOO\n"
        "oooooooo..............oooooooooo@@                  @@OOOOOOOOOOO\n"
        "..............................@@          @@    @@    @@OOOOOOOOO\n"
        ".........                 @@@@                        @@OOOOOOOOO\n"
        "..          @@@@@@@@@@@@@@                  @@@@      @@OOOOOOOOO\n"
        "          @@                            @@    @@  @@  @@OOOOOOOOO\n"
        "            @@@@@@                        @@@@@@@@    @@OOOOOOOOO\n"
        "                @@                                    @@OOOOOOOOO\n"
        "                @@                                    @@OOOOOOOOO\n"
        "                @@                                    @@OOOOOOOOO\n"
        "      ..........@@                                    @@OOOOOOOOO\n"
        "..................@@                                  @@OOOOOOOOO\n"
        "..................@@                                @@OOOOOOOOOOO\n"
        "......oooooooooooo@@    @@@@    @@@@@@@@    @@@@    @@OOOOOOOOOOO\n"
        "oooooooooooooooooo@@    @@OO@@  @@OOOOOO@@  @@@@    @@OOOOOOOOOOO\n"
        "oooooooooooooooooooo@@  @@OOOO@@OOOOOOOOOO@@OOOO@@  @@OOOOOOOOOOO\n"
        "ooooooOOOOOOOOOOOOOOOO@@OOOOOOOOOOOOOOOOOOOOOOOOOO@@OOOOOOOOOOOOO\n"
        "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO\n"
        "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO"
    );
    return 0;
}

CV姿势2：

#include <iostream>
using namespace std;

int main()
{
    cout<<
R"(OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOooooooooooooooooOOOOOOOOOOOOOO@@OO@@@@@@@@OO@@OOOOOOOOOOOOO
ooooooooooooooooooooooooooooooOOOO@@  @@        @@  @@OOOOOOOOOOO
oooooooooooooooooooooooooooooooooo@@                @@OOOOOOOOOOO
oooooooo..............oooooooooo@@                  @@OOOOOOOOOOO
..............................@@          @@    @@    @@OOOOOOOOO
.........                 @@@@                        @@OOOOOOOOO
..          @@@@@@@@@@@@@@                  @@@@      @@OOOOOOOOO
          @@                            @@    @@  @@  @@OOOOOOOOO
            @@@@@@                        @@@@@@@@    @@OOOOOOOOO
                @@                                    @@OOOOOOOOO
                @@                                    @@OOOOOOOOO
                @@                                    @@OOOOOOOOO
      ..........@@                                    @@OOOOOOOOO
..................@@                                  @@OOOOOOOOO
..................@@                                @@OOOOOOOOOOO
......oooooooooooo@@    @@@@    @@@@@@@@    @@@@    @@OOOOOOOOOOO
oooooooooooooooooo@@    @@OO@@  @@OOOOOO@@  @@@@    @@OOOOOOOOOOO
oooooooooooooooooooo@@  @@OOOO@@OOOOOOOOOO@@OOOO@@  @@OOOOOOOOOOO
ooooooOOOOOOOOOOOOOOOO@@OOOOOOOOOOOOOOOOOOOOOOOOOO@@OOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO)"
<<endl;
    return 0;
}

你以为cv很聪明？看题干了没，大佬？这道题是有输入的！你直接读取再输出也可以~

#include <stdio.h>
 
int main()
{
    char str[25][100];
    for(int i=0;i<25;i++)
    {
        gets(str[i]);
        printf("%s\n",str[i]);
    }
    return 0;
}

Tips：梅开二度

图片[3],郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网
#include <stdio.h>

int main()
{
    printf(
        "thinking is important\n"
        "stl is useful\n"
        "algorithm is useless"
    );
    return 0;
}

解析：这里就是简单的根据题中所给关系，生成对应的 4*4矩阵

根据题目的描述，输出数组 matrix[1] 中的第 i 行第 j 列的数字与输入数组 matrix[0] 中的第 i 行第 j 列的数字满足以下关系：

matrix[1][i][j]+=matrix[0][i-1][j-1];
matrix[1][i][j]+=matrix[0][i-1][j];
matrix[1][i][j]+=matrix[0][i-1][j+1];

matrix[1][i][j]+=matrix[0][i][j-1];
matrix[1][i][j]+=matrix[0][i][j];
matrix[1][i][j]+=matrix[0][i][j+1];

matrix[1][i][j]+=matrix[0][i+1][j-1];
matrix[1][i][j]+=matrix[0][i+1][j];
matrix[1][i][j]+=matrix[0][i+1][j+1];

这里要注意题目中的一句话：其中当 ai, j 中 i 或 j 有一个下标大于 4 或 小于 1 时， ai, j = 0
这句话提示了我们在编程过程中的一种常见错误：数组越界

  • 为了保证遍历数组时起始位置的安全，根据上面的关系，当 i=0 和 j=0 时，关系式中的 i-1 和 j-1 的值就是 -1，那么此时就会引起数组越界导致程序崩溃，所以我们要让计次从 i=1 和 j=1 开始循环。
  • 为了保证遍历数组时结束位置的安全，从关系式中可以看到存在 i+1 和 j+1，那么当我们的计次循环来到了第 4 次时， i+1 和 j+1的值都是 5，这也就说明，我们的二维数组的最小成员数是 6，那么如果我们还是按直觉走，把这个二维数组定义成大小是 4 的数组，那么到这个地方就会出现数组越界，导致程序崩溃。

还有一个在编写代码时很容易被忽略的问题：数组初始化

  • 如果在定义数组后，不对数组的成员进行初始化赋值，可能会导致其数值不确定 ( 可能不为 0 )，从而就会导致计算结果出现错误。

由此可以分析得出，通过这种定义方式，题目中要求的：其中当 ai, j 中 i 或 j 有一个下标大于 4 或 小于 1 时， ai, j = 0 也就恰好满足了。因为在输入数字的过程中，i=0、j=0 和 i=5、j=5 的情况已经被跳过了，它们默认是数值就是 0，不需要再去特别地设置了。

这里为了记录方便，我将这个数组定义成了三维数组，第一维作为这个矩阵的ID，代表输入的矩阵和转换后输出的矩阵。代码如下：

C语言：

#include <stdio.h>

int main()
{
    //初始化数组元素为0，防止数值混乱
    int matrix[2][6][6]={0};
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            scanf("%d",&matrix[0][i][j]);
        }
    }
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            matrix[1][i][j]+=matrix[0][i-1][j-1];
            matrix[1][i][j]+=matrix[0][i-1][j];
            matrix[1][i][j]+=matrix[0][i-1][j+1];

            matrix[1][i][j]+=matrix[0][i][j-1];
            matrix[1][i][j]+=matrix[0][i][j];
            matrix[1][i][j]+=matrix[0][i][j+1];

            matrix[1][i][j]+=matrix[0][i+1][j-1];
            matrix[1][i][j]+=matrix[0][i+1][j];
            matrix[1][i][j]+=matrix[0][i+1][j+1];

            printf("%d ",matrix[1][i][j]);
        }
        printf("\n");
    }
    return 0;
}

C++：

#include <iostream>
#include <string>
using namespace std;

int main()
{
    int matrix[2][6][6]={0};
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            cin>>matrix[0][i][j];
        }
    }

    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            int res=0;
            for(int x=-1;x<=1;x++)
            {
                for(int y=-1;y<=1;y++)
                {
                    res+=matrix[0][i+x][j+y];
                }
            }
            cout<<res<<" \n"[j==4];
        }
    }
    return 0;
}

解析：此题目用到了 线性代数 – 高斯消元，通过逐级消元，我们可以依次得到原矩阵的各个元素；如果想要详细了解 高斯消元，就去CSDN或者网上搜索资料进行学习，询问学长也可以哦。不过如果你有耐心，可以通过加减法消元，代入 i 和 j 进行推导，也是可以的哦。下面是我的一个部分推导过程，仅供参考：

图片[4],郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网

当然，也可以通过拼凑做，不过这个多少有点不太好想到，下面来简单说一下（Zero学长提供的思路）：

先推出中间4个元素，然后把边上的元素搞出来，再搞角落上的元素，列出未知数比较容易看出来：

图片[5],郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网

用上图中 天蓝颜色 圈出来的三个矩阵，通过拼凑，就可以推出来a[2][3]，同理 a[2][2] a[2][3] a[3][2] a[3][3]

图片[6],郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网

用上图中 品红颜色 圈出来的两个矩阵，通过拼凑和推出来的a[2][3] a[3][3]，就可以推出来a[4][3]，同理 a[1][2] a[1][3] a[2][1] a[2][4] a[3][1] a[3][4] a[4][2] a[4][3]

代码如下：

#include <stdio.h>

int main()
{
    int matrix[2][6][6]={0};
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            scanf("%d",&matrix[1][i][j]);
        }
    }
    /*--------------矩阵消元求解过程--------------*/
    matrix[0][3][3]=(matrix[1][2][2]-matrix[1][2][1])-(matrix[1][1][2]-matrix[1][1][1]);
    matrix[0][2][2]=(matrix[1][3][3]-matrix[1][3][4])-(matrix[1][4][3]-matrix[1][4][4]);
    matrix[0][2][3]=(matrix[1][3][2]-matrix[1][3][1])-(matrix[1][4][2]-matrix[1][4][1]);
    matrix[0][3][2]=(matrix[1][2][3]-matrix[1][2][4])-(matrix[1][1][3]-matrix[1][1][4]);

    matrix[0][3][1]=matrix[1][2][2]-matrix[1][1][2]-matrix[0][3][2]-matrix[0][3][3];
    matrix[0][2][1]=matrix[1][3][2]-matrix[1][4][2]-matrix[0][2][2]-matrix[0][2][3];
    matrix[0][1][2]=matrix[1][2][3]-matrix[1][2][4]-matrix[0][2][2]-matrix[0][3][2];
    matrix[0][1][3]=matrix[1][2][2]-matrix[1][2][1]-matrix[0][2][3]-matrix[0][3][3];
    matrix[0][2][4]=matrix[1][3][3]-matrix[1][4][3]-matrix[0][2][2]-matrix[0][2][3];
    matrix[0][3][4]=matrix[1][2][3]-matrix[1][1][3]-matrix[0][3][2]-matrix[0][3][3];
    matrix[0][4][2]=matrix[1][3][3]-matrix[1][3][4]-matrix[0][2][2]-matrix[0][3][2];
    matrix[0][4][3]=matrix[1][3][2]-matrix[1][3][1]-matrix[0][2][3]-matrix[0][3][3];

    matrix[0][1][1]=matrix[1][1][1]-matrix[0][1][2]-matrix[0][2][1]-matrix[0][2][2];
    matrix[0][1][4]=matrix[1][1][4]-matrix[0][1][3]-matrix[0][2][3]-matrix[0][2][4];
    matrix[0][4][1]=matrix[1][4][1]-matrix[0][3][1]-matrix[0][3][2]-matrix[0][4][2];
    matrix[0][4][4]=matrix[1][4][4]-matrix[0][4][3]-matrix[0][3][4]-matrix[0][3][3];
    /*--------------矩阵消元求解过程--------------*/
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            printf("%d ",matrix[0][i][j]);
        }
        printf("\n");
    }
    return 0;
}

解析：这道题目考察位运算中的异或运算；再准确一些，就是考察异或运算中的归零性：a ^ a = 0

由题目中给出的美丽值 x 与数列 a1、a2、a3 … an 的关系 x ^ a1 ^ a2 ^ a3 ^ … ^ an = 0，并结合异或运算中的归零性可知：a1 ^ a2 ^ a3 ^ … ^ an = x 。

所以，我们只需要将数组中所有的数字进行异或运算，得出来的结果就是美丽值 x

代码如下：

#include <stdio.h>

int main()
{
    int count=0;
    int res=0;
    scanf("%d",&count);

    while(count--)
    {
        int num=0;
        scanf("%d",&num);
        res^=num;
    }
    printf("%d",res);
    return 0;
}

解析：该题目也是对二进制位运算的考察，以及对于二进制数的一些性质的考察。

小知识：2的幂的二进制形式中，只有一位是 1，其他位均为 0

图片[7],郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网

那么我们如何来判断一个数的二进制里只有一个 1 呢？这里我们引入按位与的知识：

首先我们来观察一下下面这张图上，这些数字的二进制特点：

图片[8],郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网

从以上数字中，我们可以发现，2的幂二进制中只有一位是 1，其余位都是 0；而将其减去 1之后，我们会发现，二进制上原来是 1 的位置变成了 0，而且在这一位之后的所有位置上的数字都从原来的 0，都变成了 1。通俗地来讲，2的幂数字减去 1 之后，其得到的结果的二进制位上的有效数字，与原来相反，即 1 变成 0，0 变成 1。

那么下面我们来说说按位与 (&) ：
按位与就是将整数从十进制转化为二进制数，上下按位比较，在这个位置上只要有 0 ，那么运算结果的这个位置上也是 0 ，只有两个位置都是 1 ，运算结果的这个位置上才是 1：

Bin100110101
Bin201011100
&(按位与后)00010100
按位与演示说明

那么通过按位与，再结合2的幂与其减一后数字二进制的关系，我们可以得到以下过程：

24=16 (BIN)00010000
16-1=15 (BIN)00001111
&(按位与后)00000000
25=32 (BIN)00100000
32-1=31 (BIN)00011111
&(按位与后)00000000

由此我们可以得出一个结论：设正整数 n 为2的幂，那么 n & n-1 = 0，由此这道题目我们可以利用2的幂的二进制特点，来快速解决，避免了因为计次循环而带来的时间复杂度的提升。

代码如下：

#include <stdio.h>

int main()
{
    int count=0;
    int res=0;
    scanf("%d",&count);

    while(count--)
    {
        int num=0;
        scanf("%d",&num);
        if(!((num)&(num-1)))
        {
            res++;
        }
    }
    printf("%d",res);
    return 0;
}

解析：使用标准输入输出函数读入IP地址的四个字段整数，然后依次按其八位二进制输出即可。此处使用C++中的bitset库函数会更方便一些。

代码如下：

C语言：

#include <stdio.h>
#include <stdlib.h>
void ToBinary(int num) {
    for (int i = 7; i >= 0; i--) {
        int bit = (num >> i) & 1;
        printf("%d", bit);
    }
}

int main()
{
    int nums[4];
    scanf("%d.%d.%d.%d",&nums[0],&nums[1],&nums[2],&nums[3]);
    for(int i=0;i<4;i++)
    {
        ToBinary(nums[i]);
    }
    return 0;
}

C++：

#include <iostream>
#include <bitset>
using namespace std;

int main()
{
    int nums[4];
    for(int i=0;i<4;i++)
    {
        //ignore的作用是忽略输入IP时的小数点
        cin>>nums[i];cin.ignore();
        //bitset<8>可以将十进制数转化为八位二进制
        cout<<bitset<8>(nums[i]);
    }
    cout<<endl;
    return 0;
}

解析：很多人估计看到死长死长的题干，以为这是模拟题，但其实这道题目的解法，很数学！

首先我们分析题目最后给的平均每秒伤害ADPS的公式：
平均每秒伤害计算公式：ADPS = 一个周期内所有法术修正后的伤害之和 ÷ (一个周期内所有法术的释放延迟所需时间之和 + 法杖充能时间)，下面我们引用题目所给例子：

图片[9],郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网

如上图所示的法杖有 5 个火花弹和 1 个修正法术，这个修正法术的右边有 3 个火花弹，它们的伤害值为 13，施放延迟为 0.10s，修正法术左边有 2 个火花弹，它们的伤害为 3，施放延迟为 0.05s。

  • 一个周期内所有法术修正后的伤害之和 = 3*(修正法术左边的火花弹数量) + 13*(修正法术右边的火花弹数量) 
  • 一个周期内所有法术的释放延迟所需时间之和 = 0.05*(修正法术左边的火花弹数量) + 0.10*(修正法术右边的火花弹数量) 
  • 法杖充能时间 = 0.05
  • 则平均每秒伤害 ADPS = (3*2 + 13*3) / (0.05*2 + 0.10*3 + 0.05) = 100

请你注意我在公式中标红的地方，由题目可知，n 代表火花弹总数量，m 代表修正法术总数量。
我们设修正法术左边的火花弹数量为 x，那么修正法术右边的火花弹数量就为 n – x
修正法术左边的火花弹的伤害为 3，修正法术右边的火花弹的伤害为 3 + 10*m
那么一个周期内所有法术修正后的伤害之和=3*x + (n – x)*(3 + 10*m)
一个周期内所有法术的释放延迟所需时间之和(外加法杖充能时间)=0.05*x + (0.05+0.05*m)*(n – x) + 0.05

由此，我们可以得到一个关于 x 的一元一次方程，其中y=ADPS：

图片[10],郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网

对其进行求导可以发现，它在给定的 x 范围内单调递减，所以 x 越小，y 越大，故当 x 取 0 时，y 取得最大值，此时，平均每秒伤害取得最大值。

代码如下：

#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T);

    for (int t = 0; t < T; t++) {
        int n, m;
        scanf("%d %d", &n, &m);

        double res=n*(3+10*m)/(0.05*n*(m+1)+0.05);
        printf("%.2lf\n",res);
    }
    return 0;
}

解析：此题目关键在于寻找与这个数字相邻最近且最小的质数。
根据题意，如果这个数本身就是质数，那么 NearPrime(x) = x，如果不是，就寻找与 x 最接近的一个质数，如果这样子的质数有两个则为较小的那个数。

首先我们需要先定义判断质数的函数：

int is_prime(int num) {
    if (num < 2) {
        return 0;
    }
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) {
            return 0;
        }
    }
    return 1;
}

接着我们定义一个函数原型为 near_prime(int x) 的函数来求得题目要求的质数，我们根据题意来编写代码：

  • 首先判断输入的数是否是质数，如果是质数，就返回其本身
  • 接着我们定义两个整形变量，一个依次递减，一个依次递增，分别代表其左右两边的数
  • 使用while，判断递减或递增后的数是否是质数，如果两个都不是质数，那么就继续递减或递增；如果其中一个是质数，首先判断递减的数值是否是质数，如果是，就返回递减的数值，如果不是，就返回递增的数值。这样就保证了返回的数一定是最小的。

接着我们就可以根据题目要求，填入相应的参数，之后把结果相乘，即可得到答案。

代码如下：

C语言：

#include <stdio.h>

int is_prime(int num) {
    if (num < 2) {
        return 0;
    }
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) {
            return 0;
        }
    }
    return 1;
}
int near_prime(int x) {
    //首先判断输入的数是否是质数
    if (is_prime(x)) {
        return x;
    }
    //定义两个整形变量，一个依次递减，一个依次递增，分别代表其左右两边的数
    int lower = x - 1;
    int upper = x + 1;

    //判断递减或递增后的数是否是质数，如果两个都不是质数，那么就继续递减或递增
    while (!is_prime(lower) && !is_prime(upper)) {
        lower--;
        upper++;
    }
    //如果其中一个是质数，首先判断递减的数值是否是质数，如果是，就返回递减的数值，如果不是，就返回递增的数值
    if (is_prime(lower)) {
        return lower;
    } else {
        return upper;
    }
}
int solve() {
    int x;
    scanf("%d", &x);
    int prime1 = near_prime(x);
    int prime2 = near_prime(97 - x);
    printf("%d", prime1 * prime2);
}
int main() {
    solve();
    return 0;
}

C++：

#include <iostream>

bool is_prime(int num) {
    if (num < 2) return false;
    for (int i = 2; i * i <= num; ++i)
        if (num % i == 0) return false;
    return true;
}
int near_prime(int x) {
    //首先判断输入的数是否是质数
    if (is_prime(x)) return x;

    //定义两个整形变量，一个依次递减，一个依次递增，分别代表其左右两边的数
    int lower = x - 1;
    int upper = x + 1;

    //判断递减或递增后的数是否是质数，如果两个都不是质数，那么就继续递减或递增
    while (!is_prime(lower) && !is_prime(upper)) lower--, upper++;

    //如果其中一个是质数，首先判断递减的数值是否是质数，如果是，就返回递减的数值，如果不是，就返回递增的数值
    if (is_prime(lower)) return lower;
    else return upper;
}

void solve() {
    int x;
    std::cin >> x;

    int prime1 = near_prime(x);
    int prime2 = near_prime(97 - x);

    std::cout << prime1*prime2 << std::endl;
}

int main() {
    solve();
    return 0;
}

求方案数，用到动态规划的思想，话不多说，直接上图：

图片[11],郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网

样例给出了如图字符串，让我们求有多少种方案能拾起ACM，我们只能按顺序捡，所以上图有两种拾起方案。分别如下：

图片[12],郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网
图片[13],郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网

OK，然后我们对样例分析，我们只能按顺序捡起ACM，逐个分析，我们把这串字符串成为S，S1是A，S2是C，依次类推。我们在S1处捡到了A，在S2处捡到了C，最后只能在S3或S5处捡到C，所以只有俩种方案，因为我们不可能在S4处捡到A再返回去S2处找C。

我们来换一个样例：

图片[14],郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网

猜一猜有几种

答案是五种：

图片[15],郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网

仔细观察，我们不难发现，每一个C都可以由前面的A转移过来，每一个M都可以由前面的C转移过来，有起始节点，有终止节点，每一个节点代表一个状态，任何一个非起始节点都可以从其它节点转移过来，此所谓状态转移！

由此我们就可以得出答案了，只要求出所有的M能从多少个C中转移过来，那么就是答案了。

代码如下：

C语言：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int len=0,a=0,c=0,res=0;
    scanf("%d",&len);

    char* str=(char*)malloc(len*sizeof(char));
    scanf("%s",str);

    for(int i=0;i<len;i++)
    {
        if(str[i]=='A') a++;
        if(str[i]=='C') c+=a;
        if(str[i]=='M') res+=c;
    }

    printf("%d",res);
    return 0;
}

C++：


#include <iostream>
#include <string>
using namespace std;

int main()
{
    int len=0,a=0,c=0,res=0;
    cin>>len;
    string str;cin>>str;
    for(auto temp:str)
    {
        if(temp=='A') a++;
        if(temp=='C') c+=a;
        if(temp=='M') res+=c;
    }
    cout<<res<<endl;
    return 0;
}

dp状态转移方程：


#include <stdio.h>
#include <string.h>

#define MOD 1000000007  //不取模数据会溢出
void solve(int n, char *s) {
    char target[] = "ACM";
    int dp[n + 1][4];
    memset(dp, 0, sizeof(dp));
    
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 3; j++) {
            dp[i][j] = dp[i - 1][j];
            if (s[i - 1] == target[j - 1]) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
            }
        }
    }
    printf("%d", dp[n][3]);
}

int main() {
    int n;
    scanf("%d", &n);

    char s[n];
    scanf("%s", s);

    solve(n, s);
    return 0;
}

本次题目解析没有参考官方题解，如若出现错误，请及时评论或私信指出~

------本文已结束，感谢您的阅读------
THE END
ACMOJ题解比赛题解
# ACM# 题目解析
喜欢就支持一下吧
点赞10 分享
Frex的头像,网络安全爱好者中心-神域博客网
Dev c++安装环境配置【配置较简单】另一个学习C语言编译工具,网络安全爱好者中心-神域博客网
Dev c++安装环境配置【配置较简单】另一个学习C语言编译工具
Dev c++安装环境配置【配置较简单】另一个学习C语言编译工具
9个月前 1003
VScode安装配置环境-全网原创最详细教程【学习C语言第一步!】,网络安全爱好者中心-神域博客网
VScode安装配置环境-全网原创最详细教程【学习C语言第一步!】
VScode安装配置环境-全网原创最详细教程【学习C语言第一步!】
9个月前 1000
郑州轻工业大学-23级新生C语言周赛(1)题目解析,网络安全爱好者中心-神域博客网
郑州轻工业大学-23级新生C语言周赛(1)题目解析
郑州轻工业大学-23级新生C语言周赛(1)题目解析
9个月前 814
郑州轻工业大学-23级新生C语言周赛(3)题目解析,网络安全爱好者中心-神域博客网
郑州轻工业大学-23级新生C语言周赛(3)题目解析
郑州轻工业大学-23级新生C语言周赛(3)题目解析
8个月前 462
[SHCTF]新生赛 – 部分Reverse题目解析,网络安全爱好者中心-神域博客网
[SHCTF]新生赛 – 部分Reverse题目解析
[SHCTF]新生赛 – 部分Reverse题目解析
9个月前 459
郑州轻工业大学-23级新生C语言周赛(2)题目解析,网络安全爱好者中心-神域博客网
郑州轻工业大学-23级新生C语言周赛(2)题目解析
郑州轻工业大学-23级新生C语言周赛(2)题目解析
8个月前 389
相关推荐
郑轻OJ前50题答案+详细解析,网络安全爱好者中心-神域博客网
郑轻OJ前50题答案+详细解析
郑轻OJ前50题答案+详细解析
9个月前 1374
郑轻OJ51~100题答案+详细解析,网络安全爱好者中心-神域博客网
郑轻OJ51~100题答案+详细解析
郑轻OJ51~100题答案+详细解析
9个月前 1163
郑轻OJ101~150题答案+详细解析【已更新】,网络安全爱好者中心-神域博客网
郑轻OJ101~150题答案+详细解析【已更新】
郑轻OJ101~150题答案+详细解析【已更新】
9个月前 1084
郑州轻工业大学-23级新生C语言周赛(1)题目解析,网络安全爱好者中心-神域博客网
郑州轻工业大学-23级新生C语言周赛(1)题目解析
郑州轻工业大学-23级新生C语言周赛(1)题目解析
9个月前 814
郑州轻工业OJ全部答案题解合集[前200更新完毕],网络安全爱好者中心-神域博客网
郑州轻工业OJ全部答案题解合集[前200更新完毕]
郑州轻工业OJ全部答案题解合集[前200更新完毕]
9个月前 782
郑州轻工业大学-23级新生C语言周赛(4)题目解析,网络安全爱好者中心-神域博客网
郑州轻工业大学-23级新生C语言周赛(4)题目解析
郑州轻工业大学-23级新生C语言周赛(4)题目解析
8个月前 576
评论 抢沙发
头像
善语结善缘,恶语伤人心
提交
头像

昵称

取消
昵称

请填写用户信息：

  • 昵称(必填)
  • 邮箱(必填)
常用语
请选择评论常用语：
  • 1、谢谢博主分享！
  • 2、博主NB，666
  • 3、感谢楼主分享！
  • 4、感谢大佬分享！
  • 5、教程很好用，谢谢！
 夸夸
夸夸
还有吗！没看够！
表情
[aoman][baiyan][bishi][bizui][cahan][ciya][dabing][daku][deyi][doge][fadai][fanu][fendou][ganga][guzhang][haixiu][hanxiao][zuohengheng][zhuakuang][zhouma][zhemo][zhayanjian][zaijian][yun][youhengheng][yiwen][yinxian][xu][xieyanxiao][xiaoku][xiaojiujie][xia][wunai][wozuimei][weixiao][weiqu][tuosai][tu][touxiao][tiaopi][shui][se][saorao][qiudale][qinqin][qiaoda][piezui][penxue][nanguo][liulei][liuhan][lenghan][leiben][kun][kuaikule][ku][koubi][kelian][keai][jingya][jingxi][jingkong][jie][huaixiao][haqian][aini][OK][qiang][quantou][shengli][woshou][gouyin][baoquan][aixin][bangbangtang][xiaoyanger][xigua][hexie][pijiu][lanqiu][juhua][hecai][haobang][caidao][baojin][chi][dan][kulou][shuai][shouqiang][yangtuo][youling]
图片

    暂无评论内容