CCF-CSP 202209-1 如此编码 C语言（满分通过代码+题解）-Toy模板网

这篇具有很好参考价值的文章主要介绍了CCF-CSP 202209-1 如此编码 C语言（满分通过代码+题解）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

试题编号： 202209-1

试题名称：如此编码

时间限制： 1.0s

内存限制： 512.0MB

问题描述：

题目背景

某次测验后，顿顿老师在黑板上留下了一串数字 23333 便飘然而去。凝望着这个神秘数字，小 P 同学不禁陷入了沉思……

题目描述

已知某次测验包含 n 道单项选择题，其中第 i 题（1≤i≤n）有 ai 个选项，正确选项为 bi，满足 ai≥2 且 0≤bi<ai。比如说，ai=4 表示第 i 题有 4 个选项，此时正确选项 bi 的取值一定是 0、1、2、3 其中之一。

顿顿老师设计了如下方式对正确答案进行编码，使得仅用一个整数 m 便可表示 b1,b2,⋯,bn。

首先定义一个辅助数组 ci，表示数组 ai 的前缀乘积。当 1≤i≤n 时，满足：
ci=a1×a2×⋯×ai

特别地，定义 c0=1。

于是 m 便可按照如下公式算出：
m=∑i=1nci−1×bi=c0×b1+c1×b2+⋯+cn−1×bn

易知，0≤m<cn，最小值和最大值分别当 bi 全部为 0 和 bi=ai−1 时取得。

试帮助小 P 同学，把测验的正确答案 b1,b2,⋯,bn 从顿顿老师留下的神秘整数 m 中恢复出来。

输入格式

从标准输入读入数据。

输入共两行。

第一行包含用空格分隔的两个整数 n 和 m，分别表示题目数量和顿顿老师的神秘数字。

第二行包含用空格分隔的 n 个整数 a1,a2,⋯,an，依次表示每道选择题的选项数目。

输出格式

输出到标准输出。

输出仅一行，包含用空格分隔的 n 个整数 b1,b2,⋯,bn，依次表示每道选择题的正确选项。

样例1输入

15 32767
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Data

样例1输出

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Data

样例2输入

4 0
2 3 2 5

Data

样例2输出

0 0 0 0

Data

样例3输入

7 23333
3 5 20 10 4 3 10

Data

样例3输出

2 2 15 7 3 1 0

Data

样例3解释

i	1	2	3	4	5	6	7
ai	3	5	20	10	4	3	10
bi	2	2	15	7	3	1	0
ci−1	1	3	15	300	3000	12000	36000

子任务

50% 的测试数据满足：ai 全部等于 2，即每道题均只有两个选项，此时 ci=2i；

全部的测试数据满足：1≤n≤20，ai≥2 且 cn≤109（根据题目描述中的定义 cn 表示全部 ai 的乘积）。

提示

对任意的 1≤j≤n，因为 cj+1,cj+2,⋯ 均为 cj 的倍数，所以 m 除以 cj 的余数具有如下性质：
m % cj=∑i=1jci−1×bi
其中 % 表示取余运算。令 j 取不同的值，则有如下等式：

m % c1=c0×b1

m % c2=c0×b1+c1×b2

m % c3=c0×b1+c1×b2+c2×b3

...

解题思路：与大多数往年的第一题一样，跟着题目要求走就行，具体就是用两个数组，根据题目所给的公式，一个用来计算Ci，一个用来计算Bi，最后单独输出Bi即可。

解题代码：

#include<stdio.h>
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);

	int i;
	int a[21] = { 0 };
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
	}

	int tmp = 1;
	int c[21] = { 0 };
	c[0] = 1;
	for (i = 1; i <= n; i++)
	{		
		tmp *= a[i];
		c[i] = tmp;
	}

	int b[21] = { 0 };
	tmp = 0;
	for (i = 1; i <= n; i++) //先存整个Ci-1 × Bi
	{	
		b[i] = m % c[i] - tmp;
		tmp += b[i];
	}

	for (i = 1; i <= n; i++)
	{
		printf("%d ", b[i] / c[i - 1]);//最后输出再除以Ci-1
	}
	return 0;
}

看完觉得有觉得帮助的话不妨点赞收藏鼓励一下，有疑问或看不懂的地方或有可优化的部分还恳请朋友们留个评论，多多指点，谢谢朋友们！文章来源地址https://www.toymoban.com/news/detail-413539.html

到了这里，关于CCF-CSP 202209-1 如此编码 C语言（满分通过代码+题解）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！