QLU-第六次训练
B 数列
传送门
题目描述
给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：
1，3，4，9，10，12，13，…
（该序列实际上就是：30，31，30+31，32，30+32，31+32，30+31+32，…）
请你求出这个序列的第N项的值（用10进制数表示）。
例如，对于k=3，N=100，正确答案应该是981。
输入
输入只有1行，为2个正整数，用一个空格隔开：k N
（k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）。
输出
输出为计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*109）。
（整数前不要有空格和其他符号）。
样例输入
3 100
样例输出
981这个题可以模拟也可以找规律，，这里就不介绍模拟了，说一下找规律的做法
我们可以注意到这个题有个提示要用10进制输出，为什么要强调这个呢？
看一下给出的例子
k=3时，数列为：1,3,4,9,10,12,13...
转换成三进制就是：1,10,11,100,101,110,111..
是不是感觉有些熟悉？全是由0,1组成，那就试试将它们当做二进制转换成十进制，就是
1,2,3,4,5,6,7..
显然,第n项就是n.
程序就把这个过程逆回去，先把n转换成二进制，再把它当成K进制，重新转换为十进制.
#include
#define exp 1e-8
#define mian main
#define pii pair
#define pll pair
#define ll long long
#define pb push_back
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define w(x) while(x--)
#define int_max 2147483647
#define lowbit(x) (x)&(-x)
#define gcd(a,b) __gcd(a,b)
#define pq(x) priority_queue
#define ull unsigned long long
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pl(a,n) next_permutation(a,a+n)
#define ios ios::sync_with_stdio(false)
#define met(a,x) memset((a),(x),sizeof((a)))
using namespace std;
int n,k;
stacks;
int main()
{while(~scanf("%d%d",&n,&k)){while(k){s.push(k%2);k/=2;}ll ans=0;while(!s.empty()){ans+=s.top()*pow(n,s.size()-1);s.pop();}printf("%lld\n",ans);}
}
C 摆花
传送门
题目描述
小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 m 盆。
通过调 查顾客的喜好，小明列出了顾客最喜欢的 n 种花，从 1 到 n 标号。
为了在门口展出更多种花， 规定第 i 种花不能超过 ai盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到 大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。
输入
第一行包含两个正整数 n 和 m，中间用一个空格隔开。
第二行有 n 个整数，每两个整数之间用一个空格隔开，依次表示 a1、a2、……an。
输出
输出只有一行，一个整数，表示有多少种方案。
注意：因为方案数可能很多，请输出 方案数对 1000007 取模的结果。
样例输入
2 4
3 2
样例输出
2
提示
【输入输出样例说明】
有 2 种摆花的方案，分别是(1，1，1，2)， (1，1，2，2)。
括号里的 1 和 2 表示两种花， 比如第一个方案是前三个位置摆第一种花，第四个位置摆第二种花。
这是一个DP的题目，我们用一个二维数组记录即可，一维数组a[i]表示每种花有多少个。
ans[i][j]表示选了前i种花共j个，当前的第i种可以选0到a[i]个，因为也可以不选这种花，那么我们就可以得出状态转移方程
ans[i][j]=ans[i][j]+ans[i-1][j-k] (ans[i-1][j-k]表示前i-1种选了j-k个）
需要注意的是ans[0][0]一开始要初始化为1，因为第一种花一个也不选也是一种情况。
#include
#define exp 1e-8
#define mian main
#define pii pair
#define pll pair
#define ll long long
#define pb push_back
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define w(x) while(x--)
#define int_max 2147483647
#define lowbit(x) (x)&(-x)
#define gcd(a,b) __gcd(a,b)
#define pq(x) priority_queue
#define ull unsigned long long
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pl(a,n) next_permutation(a,a+n)
#define ios ios::sync_with_stdio(false)
#define met(a,x) memset((a),(x),sizeof((a)))
#define mod 1000007
using namespace std;
int ans[110][110],n,m,a[110];
int main()
{while(~scanf("%d%d",&n,&m)){met(ans,0);for(int i=1;i<=n;i++)sc(a[i]);ans[0][0]=1; //第一种花选0个也是一种方案for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)for(int k=0;k<=a[i];k++)if(j>=k){ans[i][j]+=ans[i-1][j-k];ans[i][j]%=mod;}printf("%d\n",ans[n][m]%mod);}
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！