CCF-CSP真题《202209-1 如此编码》思路+python，c++满分题解

亦凉 2023-09-27 11:53 96阅读 0赞

> 想查看其他题的真题及题解的同学可以前往查看：[CCF-CSP真题附题解大全][CCF-CSP]

<table> 
 <tbody> 
  <tr> 
   <td>试题编号：</td> 
   <td>202209-1</td> 
  </tr> 
  <tr> 
   <td>试题名称：</td> 
   <td>如此编码</td> 
  </tr> 
  <tr> 
   <td>时间限制：</td> 
   <td>1.0s</td> 
  </tr> 
  <tr> 
   <td>内存限制：</td> 
   <td>512.0MB</td> 
  </tr> 
  <tr> 
   <td>问题描述：</td> 
   <td> <h3>题目背景</h3> <p>某次测验后，顿顿老师在黑板上留下了一串数字&nbsp;23333&nbsp;便飘然而去。凝望着这个神秘数字，小 P 同学不禁陷入了沉思……</p> <h3>题目描述</h3> <p>已知某次测验包含&nbsp;n&nbsp;道单项选择题，其中第&nbsp;i&nbsp;题（1≤i≤n）有&nbsp;ai&nbsp;个选项，正确选项为&nbsp;bi，满足&nbsp;ai≥2&nbsp;且&nbsp;0≤bi&lt;ai。比如说，ai=4&nbsp;表示第&nbsp;i&nbsp;题有&nbsp;4&nbsp;个选项，此时正确选项&nbsp;bi&nbsp;的取值一定是&nbsp;0、1、2、3&nbsp;其中之一。</p> <p>顿顿老师设计了如下方式对正确答案进行编码，使得仅用一个整数&nbsp;m&nbsp;便可表示&nbsp;b1,b2,⋯,bn。</p> <p>首先定义一个辅助数组&nbsp;ci，表示数组&nbsp;ai&nbsp;的前缀乘积。当&nbsp;1≤i≤n&nbsp;时，满足：<br> ci=a1×a2×⋯×ai</p> <p>特别地，定义&nbsp;c0=1。</p> <p>于是&nbsp;m&nbsp;便可按照如下公式算出：</p> <p><img alt="" height="62" src="https://img-blog.csdnimg.cn/fa9868cbb8174009a1fef63ff13e57bc.png" width="374"></p> <p>易知，0≤m&lt;cn，最小值和最大值分别当&nbsp;bi&nbsp;全部为&nbsp;0&nbsp;和&nbsp;bi=ai−1&nbsp;时取得。</p> <p>试帮助小&nbsp;P&nbsp;同学，把测验的正确答案&nbsp;b1,b2,⋯,bn&nbsp;从顿顿老师留下的神秘整数&nbsp;m&nbsp;中恢复出来。</p> <h3>输入格式</h3> <p>从标准输入读入数据。</p> <p>输入共两行。</p> <p>第一行包含用空格分隔的两个整数&nbsp;n&nbsp;和&nbsp;m，分别表示题目数量和顿顿老师的神秘数字。</p> <p>第二行包含用空格分隔的&nbsp;n&nbsp;个整数&nbsp;a1,a2,⋯,an，依次表示每道选择题的选项数目。</p> <h3>输出格式</h3> <p>输出到标准输出。</p> <p>输出仅一行，包含用空格分隔的&nbsp;n&nbsp;个整数&nbsp;b1,b2,⋯,bn，依次表示每道选择题的正确选项。</p> <h3>样例1输入</h3> 
    <blockquote> 
     <p>15 32767<br> 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2</p> 
    </blockquote> <h3>样例1输出</h3> 
    <blockquote> 
     <p>1 1 1 1 1 1 1 1 1 1 1 1 1 1 1</p> 
    </blockquote> <h3>样例2输入</h3> 
    <blockquote> 
     <p>4 0<br> 2 3 2 5</p> 
    </blockquote> <h3>样例2输出</h3> 
    <blockquote> 
     <p>0 0 0 0</p> 
    </blockquote> <h3>样例3输入</h3> 
    <blockquote> 
     <p>7 23333<br> 3 5 20 10 4 3 10</p> 
    </blockquote> <h3>样例3输出</h3> 
    <blockquote> 
     <p>2 2 15 7 3 1 0</p> 
    </blockquote> <h3>样例3解释</h3> 
    <table> 
     <thead> 
      <tr> 
       <th>i</th> 
       <th>1</th> 
       <th>2</th> 
       <th>3</th> 
       <th>4</th> 
       <th>5</th> 
       <th>6</th> 
       <th>7</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>ai</td> 
       <td>3</td> 
       <td>5</td> 
       <td>20</td> 
       <td>10</td> 
       <td>4</td> 
       <td>3</td> 
       <td>10</td> 
      </tr> 
      <tr> 
       <td>bi</td> 
       <td>2</td> 
       <td>2</td> 
       <td>15</td> 
       <td>7</td> 
       <td>3</td> 
       <td>1</td> 
       <td>0</td> 
      </tr> 
      <tr> 
       <td>ci−1</td> 
       <td>1</td> 
       <td>3</td> 
       <td>15</td> 
       <td>300</td> 
       <td>3000</td> 
       <td>12000</td> 
       <td>36000</td> 
      </tr> 
     </tbody> 
    </table><h3>子任务</h3> <p>50%&nbsp;的测试数据满足：ai&nbsp;全部等于&nbsp;2，即每道题均只有两个选项，此时&nbsp;ci=2i；</p> <p>全部的测试数据满足：1≤n≤20，ai≥2&nbsp;且&nbsp;cn≤109（根据题目描述中的定义&nbsp;cn&nbsp;表示全部&nbsp;ai&nbsp;的乘积）。</p> <h3>提示</h3> <p>对任意的&nbsp;1≤j≤n，因为&nbsp;cj+1,cj+2,⋯&nbsp;均为&nbsp;cj&nbsp;的倍数，所以&nbsp;m&nbsp;除以&nbsp;cj&nbsp;的余数具有如下性质：</p> <p><img alt="" height="86" src="https://img-blog.csdnimg.cn/6b98a39e7cd0415e8c6afe2f54f2ff3a.png" width="263"></p> <p><br> 其中&nbsp;%&nbsp;表示取余运算。令&nbsp;j&nbsp;取不同的值，则有如下等式：<br> m&nbsp;%&nbsp;c1 = c0×b1</p> <p>m&nbsp;%&nbsp;c2 = c0×b1+c1×b2</p> <p>m&nbsp;%&nbsp;c3 = c0×b1+c1×b2+c2×b3⋯</p> </td> 
  </tr> 
 </tbody> 
</table>

**真题来源：**[如此编码][Link 1]

> 感兴趣的同学可以如此编码进去进行练习提交

**python满分题解：**

# 输入n题目数量和m神秘数字
    n, m = map(int, input().split())
    # 输入n道选择题的选项数字
    a = list(map(int, input().split()))
    # 设置b数组来存放每道选择题的正确选项
    b = []
    # c为c0，初始值为1
    c = 1
    # tc为辅助值，即为t的下一个值
    tc = 1
    # temp为辅助值，为记录除了此次的C*B之前所有C*B的值的和
    temp = 0
    # 通过循环进行每道题答案的更新
    for i in a:
        # 将tc的值进行更新为此时c的下一个值
        tc = i*c
        # 向b数组中添加此时题目的正确选项
        b.append((m%tc-temp)//c)
        # 更新temp的值
        temp += c*b[-1]
        # 更新c的值
        c = tc
    # 输出每道题的正确选项
    print(*b)

**运行结果：**

![30b56cf52af94a89a38fbf49925c733c.png][]

**代码简化：**

# 输入n题目数量和m神秘数字
    n, m = map(int, input().split())
    # 输入n道选择题的选项数字
    a = list(map(int, input().split()))
    # 设置b数组来存放每道选择题的正确选项
    b = []
    # c为c0，初始值为1
    c = 1
    # tc为辅助值，即为t的下一个值
    tc = 1
    # 通过循环进行每道题答案的更新
    for i in a:
        # 将tc的值进行更新为此时c的下一个值
        tc = i*c
        # 向b数组中添加此时题目的正确选项
        b.append((m%tc)//c)
        # 更新c的值
        c = tc
    # 输出每道题的正确选项
    print(*b)

**简化原因：**

> 我们可以发现原来代码中的temp是为了减去公式中之前的![\\sum\_\{i=1\}^\{j\}c\_\{i-1\}\*b\_\{i\}][sum_i_1_j_c_i-1_b_i]的，他是恒小于c的，所以我们用整除//的话减去和不减去是一样的，可以省去。

--------------------

**c++ 满分题解：**

#include<iostream>
    using namespace std;
    
    const int N = 21;
    int n, m;
    int a[N];
    int b[N];
    int c = 1, tc = 1;
    
    int main() {
        cin >> n >> m;
        for (int i = 0; i <n; i++)
            cin >> a[i];
        for (int i = 0; i <n; i++) {
            tc = a[i] * c;
            b[i] = int((m % tc) / c);
            c = tc;
            cout << b[i] << ' ';
        }
        
        return 0;
    }

**运行结果：**

![5c1c1e3a743d47adac382eb075f62f32.png][]

[CCF-CSP]: https://blog.csdn.net/weixin_53919192/article/details/124893395?spm=1001.2014.3001.5502
[Link 1]: http://118.190.20.162/view.page?gpid=T153
[30b56cf52af94a89a38fbf49925c733c.png]: https://img-blog.csdnimg.cn/30b56cf52af94a89a38fbf49925c733c.png
[sum_i_1_j_c_i-1_b_i]: https://latex.csdn.net/eq?%5Csum_%7Bi%3D1%7D%5E%7Bj%7Dc_%7Bi-1%7D*b_%7Bi%7D
[5c1c1e3a743d47adac382eb075f62f32.png]: https://img-blog.csdnimg.cn/5c1c1e3a743d47adac382eb075f62f32.png