网站不备案不能访问吗,泾阳县建设局网站,内蒙古工程建设协会官方网站,asp.net网站改版 旧网站链接蓝桥杯备赛 | 洛谷做题打卡day22 文章目录 蓝桥杯备赛 | 洛谷做题打卡day22Anya and Cubes题面翻译输入格式输出题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 样例 #3样例输入 #3样例输出 #3 提示题解代码我的一些话 Anya and Cubes … 蓝桥杯备赛 | 洛谷做题打卡day22 文章目录 蓝桥杯备赛 | 洛谷做题打卡day22Anya and Cubes题面翻译输入格式输出题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 样例 #3样例输入 #3样例输出 #3 提示题解代码我的一些话 Anya and Cubes 题面翻译 给你 n n n 个数 n ≤ 25 n\le 25 n≤25。初始序列为 a i , 0 ≤ a i ≤ 1 0 9 a_i,\ 0\le a_i\le 10^9 ai, 0≤ai≤109。 你有 k k k 个 ! ! !每个 ! ! ! 可以使序列中的一个数变成 a i ! a_i! ai!。同一个数至多变一次 例如 5 ! 120 5!120 5!120。 求选出任意个数使他们和的等于 S S S 的方案数 输入格式 第一行 n , k , S n,k,S n,k,S。 第二行 n n n 个数分别代表 a i a_i ai。 输出 一行一个整数选出数的合法方案数。 感谢 s_a_b_e_r 提供的翻译。 题目描述 Anya loves to fold and stick. Today she decided to do just that. Anya has $ n $ cubes lying in a line and numbered from $ 1 $ to $ n $ from left to right, with natural numbers written on them. She also has $ k $ stickers with exclamation marks. We know that the number of stickers does not exceed the number of cubes. Anya can stick an exclamation mark on the cube and get the factorial of the number written on the cube. For example, if a cube reads $ 5 $, then after the sticking it reads $ 5! $, which equals $ 120 $. You need to help Anya count how many ways there are to choose some of the cubes and stick on some of the chosen cubes at most $ k $ exclamation marks so that the sum of the numbers written on the chosen cubes after the sticking becomes equal to $ S $. Anya can stick at most one exclamation mark on each cube. Can you do it? Two ways are considered the same if they have the same set of chosen cubes and the same set of cubes with exclamation marks. 输入格式
The first line of the input contains three space-separated integers $ n $, $ k $ and $ S\ (1\le n\le25,\ 0\le k\le n,\ 1\le S\le10^{16})$ — the number of cubes and the number of stickers that Anya has, and the sum that she needs to get.
The second line contains $ n $ positive integers $ a_{i}\ ( 1\le a_{i}\le10^{9}) $ — the numbers, written on the cubes. The cubes in the input are described in the order from left to right, starting from the first one.
Multiple cubes can contain the same numbers.
输出格式
Output the number of ways to choose some number of cubes and stick exclamation marks on some of them so that the sum of the numbers became equal to the given number $ S $ .
样例 #1
样例输入 #1
2 2 30
4 3样例输出 #1
1样例 #2
样例输入 #2
2 2 7
4 3样例输出 #2
1样例 #3
样例输入 #3
3 1 1
1 1 1样例输出 #3
6提示
In the first sample the only way is to choose both cubes and stick an exclamation mark on each of them.
In the second sample the only way is to choose both cubes but don’t stick an exclamation mark on any of them.
In the third sample it is possible to choose any of the cubes in three ways, and also we may choose to stick or not to stick the exclamation mark on it. So, the total number of ways is six.
题解代码 学会利用新知自己多试试并尝试积攒一些固定解答方案debug以下是题解代码 ~ #include bits/stdc.h
using namespace std;
typedef long long ll;
ll ans[25], res[25], S;
int n, m, maxDep;
bool f;
bool IDDFS(ll p, ll q, int dep)
{if (dep maxDep){if (p 1 q res[dep - 1] (q ans[dep] || !ans[dep])){res[dep] q;memcpy(ans, res, sizeof(res));return true;}return false;}if (dep maxDep - 1){for (ll z (q 2) / p / p 1; z min((S 1) / p, S * S / q); z){ll delta p * p * z * z - (q 2) * z, s sqrt(delta);if (s * s ! delta || p * z s 1)continue;res[dep] p * z - s 1, res[dep 1] p * z s 1;if (res[dep 1] ans[dep 1] || !ans[dep 1]){memcpy(ans, res, sizeof(res));return true;}}return false;}ll l max(res[dep - 1], (q - 1) / p) 1LL, r (maxDep - dep 1) * q / p;bool flag false;for (int i l; i r; i){ll tx p * i - q, ty q * i, g __gcd(tx, ty);res[dep] i;if (IDDFS(tx / g, ty / g, dep 1))flag true;}return flag;
}
int main()
{
#ifndef ONLINE_JUDGEfreopen(data.in, r, stdin);// freopen(data.out, w, stdout);
#endifscanf(%d%d, n, m);while (!f){S 100, maxDep;while (S 1e7 !f)S (S 3) (S 1), f IDDFS(n, m, 1);}for (int i 1; i maxDep; i)printf(%lld , ans[i]);return 0;
}我的一些话 今天学习进阶搜索深搜属于比较难的部分需要多动脑多思考思路还是很好掌握的虽然一次性AC有一定难度需要通盘的考虑和理解以及扎实的数据结构基础才能独立写出AC代码。但无论难易大家都要持续做题保持题感喔一起坚持(o´ωo) 如果有非计算机专业的uu自学的话关于数据结构的网课推荐看b站上青岛大学王卓老师的课讲的很细致有不懂都可以私信我喔 总结来说思路很重要多想想多在草稿纸上画画用测试数据多调试debug后成功编译并运行出正确结果真的会感到很幸福 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识之前的博文我都有写欢迎大家关注我翻阅自取哦~ 不管什么都要坚持吧三天打鱼两天晒网无法形成肌肉记忆和做题思维该思考的时候一定不要懈怠今天就说这么多啦欢迎评论留言一起成长
