【蓝桥杯冲冲冲】进阶搜索 Anya and Cubes

2024-01-31 10:12

本文主要是介绍【蓝桥杯冲冲冲】进阶搜索 Anya and Cubes,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

蓝桥杯备赛 | 洛谷做题打卡day22

文章目录

  • 蓝桥杯备赛 | 洛谷做题打卡day22
  • Anya and Cubes
    • 题面翻译
    • 输入格式
    • 输出
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 样例 #2
      • 样例输入 #2
      • 样例输出 #2
    • 样例 #3
      • 样例输入 #3
      • 样例输出 #3
    • 提示
    • 题解代码
    • 我的一些话

在这里插入图片描述

输入格式

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后成功编译并运行出正确结果真的会感到很幸福!

  • 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识,之前的博文我都有写,欢迎大家关注我,翻阅自取哦~

  • 不管什么都要坚持吧,三天打鱼两天晒网无法形成肌肉记忆和做题思维,该思考的时候一定不要懈怠,今天就说这么多啦,欢迎评论留言,一起成长:)

这篇关于【蓝桥杯冲冲冲】进阶搜索 Anya and Cubes的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/663412

相关文章

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

MySQL进阶之路索引失效的11种情况详析

《MySQL进阶之路索引失效的11种情况详析》:本文主要介绍MySQL查询优化中的11种常见情况,包括索引的使用和优化策略,通过这些策略,开发者可以显著提升查询性能,需要的朋友可以参考下... 目录前言图示1. 使用不等式操作符(!=, <, >)2. 使用 OR 连接多个条件3. 对索引字段进行计算操作4

JavaScript中的reduce方法执行过程、使用场景及进阶用法

《JavaScript中的reduce方法执行过程、使用场景及进阶用法》:本文主要介绍JavaScript中的reduce方法执行过程、使用场景及进阶用法的相关资料,reduce是JavaScri... 目录1. 什么是reduce2. reduce语法2.1 语法2.2 参数说明3. reduce执行过程

Python进阶之Excel基本操作介绍

《Python进阶之Excel基本操作介绍》在现实中,很多工作都需要与数据打交道,Excel作为常用的数据处理工具,一直备受人们的青睐,本文主要为大家介绍了一些Python中Excel的基本操作,希望... 目录概述写入使用 xlwt使用 XlsxWriter读取修改概述在现实中,很多工作都需要与数据打交

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。