csp 如此编码 C语言(回归唠嗑版)
熟悉的开篇废话,最近其实在研究那个web开发这一块,导致csp联系就减少了,好久没更csp的帖子了,尽管明天就要考了,但是嘞,能看一道是一道呗对吧。
等过段时间我把web开发这一块整明白了就发帖子,把我这个错误大王犯过的疑难杂症整理成一个帖子嘿嘿,饼先画到这。
其实这个题我之前有写过一次,但是就拿第一个示例来讲,输出的1总是少一个,我就很疑惑,今天把这周的事忙的差不多了,就又写了一次,没想到一次就写出来啦!!我太棒啦
我上回错的点就是从c[i]的那个循环那里,里边的对b[j]循环是<=n;这个就错了,应该是到i,细节决定成败啊老铁们,还是简单的,代码请看最后。
试题编号:?? ?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 便可按照如下公式算出:
易知,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
样例1输出
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
样例2输入
4 0
2 3 2 5
样例2输出
0 0 0 0
样例3输入
7 23333
3 5 20 10 4 3 10
样例3输出
2 2 15 7 3 1 0
样例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 的余数具有如下性质:
其中 % 表示取余运算。令 j 取不同的值,则有如下等式:
m % c1 = c0×b1
m % c2 = c0×b1+c1×b2
m % c3 = c0×b1+c1×b2+c2×b3?
代码:
?
#include<stdio.h>
int main()
{
int n,m;
scanf("%d %d",&n,&m);
int a[n];
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int c[n],cheng;
c[0]=1;
for(int i=1;i<=n;i++)
{
cheng=1;
for(int j=1;j<=i;j++)
{
cheng=cheng*a[j];
}
c[i]=cheng;
}
int b[n];
b[1]=m%c[1];
printf("%d",b[1]);
for(int i=2;i<=n;i++)
{
b[i]=((m%c[i])-(m%c[i-1]))/c[i-1];
printf(" %d",b[i]);
}
return 0;
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!