专栏文章

B 7 月 2 日作业 Solution

bbjzjh
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minccof7
此快照首次捕获于
2025/12/02 00:06
3 个月前
此快照最后确认于
2025/12/02 00:06
3 个月前
查看原文

数字 “2”

Description

给定正整数 nn，求 1−10n1 - 10^n 这 10n10^n 个整数有几个 22。
n≤1000n \le 1000

Solution

一道简单的找规律题，我们使用暴力代码先算出前几个的答案。
11
219
3271
43439
540951
通过一些推导瞎搞可以发现，如果设 fif_i 为 n=in = i 时的答案，那么递推式为：
fi={i=1    fi=1i>1    fi=fi−1×9+10if_i= \begin{cases} i = 1 \;\;f_i=1 \\ i > 1 \;\;f_i = f_{i-1}\times9+10^i \end{cases}
不要问我怎么想出来的
需要使用高精度...

Code

Code

采果子 (fruit）

Description

有 nn 棵树，树上的果子采摘需要的时间 cic_i，树上有 aia_i 颗果实，所有果实的价值为 sis_i，不过采摘这些果实有一个条件，如果你采摘了第 ii 颗树上的果实，假设你下一次采摘的树编号为 jj，那么要保证 si≤sjs_i \le s_j。

Solution

裸的 01 背包，什么，你说那个条件？可以发现如果不满足条件只要交换顺序即可满足。

Code

Code

Order（order）

Description

给定一字符串 ss（∣s∣≤200|s|\le200）,按字典序输出他的全排列。

Solution

解法一

使用 Dfs\text{Dfs} 求全排列，不在多说。
不给出 Code。

解法 2

Warning
这是 C++ 党专属的福利！
STL 大法好！
看到这题的同时就想到了 next_permutation 和 map。map 是用来去重的，大家因该都知道，不知道的话 map 介绍
这里着重描述一下 next_permutation 的作用，这里引用一段 OI Wiki 的描述：
将当前排列更改为 全排列中的下一个排列。如果当前排列已经是 全排列中的最后一个排列（元素完全从大到小排列），函数返回 false 并将排列更改为 全排列中的第一个排列（元素完全从小到大排列）；否则，函数返回 true。
非常的好用，对吧。
详见代码:
Code

跳棋 （ chess）

Description

给定数组 aa，aia_i 表示走到 ii 时的代价，一开始你在 11，若上一次走了 stepstep 步，第一次走时视 step=0step=0，前进会走 step+1step + 1 步，后退则仍然是 stepstep 步。求到达的最小代价。

Solution

考虑 dp\text{dp}，发现可以设状态 fi,jf_{i,j} 为当前在位置 ii，这一步走了 jj 步的最小代价，考虑列出转移方程，推导可以发现是以下柿子：
fi,j=min⁡(fi−j,j−1,fi+j,j)+aif_{i,j}=\min(f_{i-j,j-1}, f_{i+j,j})+a_i
然后我们就可以快乐的进行转移了。

Code

Code

最大利润 (profit）

Description

题面过于复杂，请读者查看原题面。
题面

Solution

题目不会讲，直接放代码。

Code

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
double p,q,f[40];
int main(){
	cin>>m>>n>>a>>b>>p>>q;
	if(a>b) f[m]=a;
	else f[m]=b;
	p=1-p;
	q=1-q;
	for(int i=m-1;i>=1;i--){
		if(a-b+f[i+1]*(p-q)>0) f[i]=a+f[i+1]*p;
		else f[i]=b+f[i+1]*q;
	}
	printf("%.5lf",f[1]*n);
}

制作唱片（cd）

Descripiton

有 nn 首歌，第 ii 首歌长度为 tit_i，你要选出最多的歌曲，可以分成 mm 组，每组中的歌总长度不能超过 tt，且要按顺序选，（比如第一组是 11 和 33，第二组就只能从 44 开始选），求最多能选几个。

Solution

我们先来思考如果确定了选哪几首歌，如何判断是否合法，其实因为他要按顺序选，所以只需要从前往后扫一遍，每当总长度大于 tt 时，就分下一组。
之后加上一个二进制枚举就好了。

Code

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...