个人练习-PAT甲级-1103 Integer Factorization

2023-10-17 22:18

本文主要是介绍个人练习-PAT甲级-1103 Integer Factorization,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805364711604224

题目大意:给出三个整数N,K,P,要求将N分解成K个整数的P次方之和。如果分解不唯一,取这K个数之和最大的序列;如果还不唯一,则取大的序列(从大到小排序,a[i]=b[i]a[i+1]>b[i+1],则a[]更大)

这种题型碰到的不多,开始根本没思路,想着暴力枚举那肯定超时。看了柳神代码后惊为天人,这么短的代码就OK了。看了一遍思路应该就是DFS+剪枝。

首先,确定这K个底数的范围,最大的就是NP次方,讲所有可能的底数的P次方存进一个数组base[]里,方便之后使用。

    int num = 0;while (pow(num, P) <= N) {base.push_back(pow(num, P));num++;}

之后用一个长度为K的vectortmp_ans来存当前的答案,pos表示到第几位为止是有效的(即当前填到第几位了)。

开始时我想的是不用固定长度的vector,直接push_back()pop_back(),这样就不用传pos了,但看了柳神答案后才发现这样子太蠢了,反正正确答案只有一个,错误的总会被覆盖掉,推进推出太麻烦了。

而且如果无解,也不需要用到序列来判断,而是根据max_base_ans即所有基底的和是否是-1来判断就好了。因为如果有了一个合法的序列,max_base_ans肯定就大于0了,这个合法的序列也会被存到ans中。

另外,扫描是从大到小扫描的,解决了取更大序列的要求。

	while (idx > 0) {if (tmp_sum + base[idx] <= N) {tmp_ans[pos] = idx;DFS(idx, tmp_sum + base[idx], base_sum + idx, pos + 1);}if (idx == 1)return;idx--;}

剪枝:如果已经有K个数了,除非次方和等于N切基底和更大,否则不要。

    if (pos == K) {if (tmp_sum == N && base_sum > max_base_sum) {ans = tmp_ans;max_base_sum = base_sum;}return;}

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>using namespace std;int N, K, P;
int max_base_sum, pos;
vector<int> base;
vector<int> ans, tmp_ans;void DFS(int idx, int tmp_sum, int base_sum, int pos) {if (pos == K) {if (tmp_sum == N && base_sum > max_base_sum) {ans = tmp_ans;max_base_sum = base_sum;}return;}while (idx > 0) {if (tmp_sum + base[idx] <= N) {tmp_ans[pos] = idx;DFS(idx, tmp_sum + base[idx], base_sum + idx, pos + 1);}if (idx == 1)return;idx--;}
}int main() {max_base_sum = -1;pos = 0;scanf("%d %d %d", &N, &K, &P);int num = 0;while (pow(num, P) <= N) {base.push_back(pow(num, P));num++;}tmp_ans.resize(K);DFS(base.size()-1, 0, 0, 0);if (max_base_sum == -1) {printf("Impossible");}else {printf("%d =", N);for (int i = 0; i < K; i++) {if (i != 0)printf(" +");printf(" %d^%d", ans[i], P);}}return 0;
}

这篇关于个人练习-PAT甲级-1103 Integer Factorization的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

RabbitMQ练习(AMQP 0-9-1 Overview)

1、What is AMQP 0-9-1 AMQP 0-9-1(高级消息队列协议)是一种网络协议,它允许遵从该协议的客户端(Publisher或者Consumer)应用程序与遵从该协议的消息中间件代理(Broker,如RabbitMQ)进行通信。 AMQP 0-9-1模型的核心概念包括消息发布者(producers/publisher)、消息(messages)、交换机(exchanges)、

HomeBank:开源免费的个人财务管理软件

在个人财务管理领域,找到一个既免费又开源的解决方案并非易事。HomeBank&nbsp;正是这样一个项目,它不仅提供了强大的功能,还拥有一个活跃的社区,不断推动其发展和完善。 开源免费:HomeBank 是一个完全开源的项目,用户可以自由地使用、修改和分发。用户友好的界面:提供直观的图形用户界面,使得非技术用户也能轻松上手。数据导入支持:支持从 Quicken、Microsoft Money

【Rust练习】12.枚举

练习题来自:https://practice-zh.course.rs/compound-types/enum.html 1 // 修复错误enum Number {Zero,One,Two,}enum Number1 {Zero = 0,One,Two,}// C语言风格的枚举定义enum Number2 {Zero = 0.0,One = 1.0,Two = 2.0,}fn m

MySql 事务练习

事务(transaction) -- 事务 transaction-- 事务是一组操作的集合,是一个不可分割的工作单位,事务会将所有的操作作为一个整体一起向系统提交或撤销请求-- 事务的操作要么同时成功,要么同时失败-- MySql的事务默认是自动提交的,当执行一个DML语句,MySql会立即自动隐式提交事务-- 常见案例:银行转账-- 逻辑:A给B转账1000:1.查询

html css jquery选项卡 代码练习小项目

在学习 html 和 css jquery 结合使用的时候 做好是能尝试做一些简单的小功能,来提高自己的 逻辑能力,熟悉代码的编写语法 下面分享一段代码 使用html css jquery选项卡 代码练习 <div class="box"><dl class="tab"><dd class="active">手机</dd><dd>家电</dd><dd>服装</dd><dd>数码</dd><dd

分布式系统的个人理解小结

分布式系统:分的微小服务,以小而独立的业务为单位,形成子系统。 然后分布式系统中需要有统一的调用,形成大的聚合服务。 同时,微服务群,需要有交流(通讯,注册中心,同步,异步),有管理(监控,调度)。 对外服务,需要有控制的对外开发,安全网关。

Java IO 操作——个人理解

之前一直Java的IO操作一知半解。今天看到一个便文章觉得很有道理( 原文章),记录一下。 首先,理解Java的IO操作到底操作的什么内容,过程又是怎么样子。          数据来源的操作: 来源有文件,网络数据。使用File类和Sockets等。这里操作的是数据本身,1,0结构。    File file = new File("path");   字

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

014.Python爬虫系列_解析练习

我 的 个 人 主 页:👉👉 失心疯的个人主页 👈👈 入 门 教 程 推 荐 :👉👉 Python零基础入门教程合集 👈👈 虚 拟 环 境 搭 建 :👉👉 Python项目虚拟环境(超详细讲解) 👈👈 PyQt5 系 列 教 程:👉👉 Python GUI(PyQt5)文章合集 👈👈 Oracle数据库教程:👉👉 Oracle数据库文章合集 👈👈 优

如何快速练习键盘盲打

盲打是指在不看键盘的情况下进行打字,这样可以显著提高打字速度和效率。以下是一些练习盲打的方法: 熟悉键盘布局:首先,你需要熟悉键盘上的字母和符号的位置。可以通过键盘图或者键盘贴纸来帮助记忆。 使用在线打字练习工具:有许多在线的打字练习网站,如Typing.com、10FastFingers等,它们提供了不同难度的练习和测试。 练习基本键位:先从学习手指放在键盘上的“家位”开始,通常是左手的