ICMTechnex2017与Codeforces第400轮（合并组）C题：莫莉的化学物质分析

作者：手机用户2602921931 | 来源：互联网 | 2024-11-05 15:59

在解决区间相关问题时，我发现自己经常缺乏有效的思维方式，即使是简单的题目也常常需要很长时间才能找到解题思路，而一旦得到提示便能迅速理解。题目要求对一个包含n个元素的数组进行操作，并给出一个参数k，具体任务是……

感觉自己做有关区间的题目方面的思维异常的差...有时简单题都搞半天还完全没思路,,然后别人提示下立马就明白了。。。&＃61;_&＃61;

题意&＃xff1a;给一个含有n个元素的数组和k&＃xff0c;问存在多少个区间的和值为k的次方数。

题解&＃xff1a;先处理出前缀和sum[i]。然后扫一遍这个前缀和数组&＃xff1a;对于每个sum[i]&＃xff0c;从k的0次方开始枚举&＃xff0c;检查map[ sum[i]-k^m ]是否大于0&＃xff0c;&＃xff0c;即之前是否出现过和值为sum[i]-k^m的前缀和&＃xff1b;如果出现过和值为sum[i]-k^m的前缀和&＃xff0c;则说明在前缀i和前缀和值为sum[i]-k^m的这两个前缀之间所包含的那个区间&＃xff0c;和值就是为k^m的。另外&＃xff0c;记得特判1和-1&＃xff0c;&＃xff0c;(终测就wa这了...&＃61;_&＃61;)

1 /**
2 *&＃64;author Wixson
3 */
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include <set>
10 #include
11 #include
12 #include
13 #include
14 #include
15 const int inf&＃61;0x3f3f3f3f;
16 const double PI&＃61;acos(-1.0);
17 const double EPS&＃61;1e-8;
18 using namespace std;
19 typedef long long ll;
20 typedef pair<int,int> P;
21
22 const ll Max&＃61;1e14;
23 int n,k;
24 ll a[100050];
25 ll sum[100050];
26 mapint> book;
27 int main()
28 {
29 //freopen("input.txt","r",stdin);
30 scanf("%d%d",&n,&k);
31 for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;) scanf("%I64d",&a[i]),sum[i]&＃61;sum[i-1]&＃43;a[i];
32 //
33 if(k&＃61;&＃61;1)
34 {
35 book[0]&＃61;1;
36 ll ans&＃61;0;
37 for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;)
38 {
39 ans&＃43;&＃61;book[sum[i]-1];
40 book[sum[i]]&＃43;&＃43;;
41 }
42 printf("%I64d\n",ans);
43 }
44 else if(k&＃61;&＃61;-1)
45 {
46 book[0]&＃61;1;
47 ll ans&＃61;0;
48 for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;)
49 {
50 ans&＃43;&＃61;book[sum[i]&＃43;1];
51 ans&＃43;&＃61;book[sum[i]-1];
52 book[sum[i]]&＃43;&＃43;;
53 }
54 printf("%I64d\n",ans);
55 }
56 else
57 {
58 book[0]&＃61;1;
59 ll ans&＃61;0;
60 for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;)
61 {
62 ll temp&＃61;1;
63 while(temp<&＃61;Max)
64 {
65 ans&＃43;&＃61;book[sum[i]-temp];
66 temp*&＃61;k;
67 }
68 book[sum[i]]&＃43;&＃43;;
69 }
70 printf("%I64d\n",ans);
71 }
72 return 0;
73 }

转:https://www.cnblogs.com/geek1116/p/6480862.html

推荐阅读

string
JSOI2010 蔬菜庆典：树结构中的无限大权值问题

本文探讨了 JSOI2010 的蔬菜庆典问题，主要关注如何处理非根非叶子节点的无限大权值情况。通过分析根节点及其子树的特性，提出了有效的解决方案，并详细解释了算法的实现过程。 ... [详细]

蜡笔小新 2024-12-22 18:57:48
string
丽江客栈选择问题

本文介绍了一道经典的算法题，题目涉及在丽江河边的n家特色客栈中选择住宿方案。两位游客希望住在色调相同的两家客栈，并在晚上选择一家最低消费不超过p元的咖啡店小聚。我们将详细探讨如何计算满足条件的住宿方案总数。 ... [详细]

蜡笔小新 2024-12-22 20:15:25
string
HTTP请求与响应机制详解

本文深入探讨了HTTP请求和响应对象的使用，详细介绍了如何通过响应对象向客户端发送数据、处理中文乱码问题以及常见的HTTP状态码。此外，还涵盖了文件下载、请求重定向、请求转发等高级功能。 ... [详细]

蜡笔小新 2024-12-23 20:40:08
bit
最小路径覆盖与强连通分量的应用：国王的问题

本题探讨了在一个有向图中，如何根据特定规则将城市划分为若干个区域，使得每个区域内的城市之间能够相互到达，并且划分的区域数量最少。题目提供了时间限制和内存限制，要求在给定的城市和道路信息下，计算出最少需要划分的区域数量。 ... [详细]

蜡笔小新 2024-12-23 18:42:12
string
如何高效清空C++标准输入缓冲区

本文探讨了在C++中如何有效地清空输入缓冲区，确保程序只处理最近的输入并丢弃多余的输入。我们将介绍一种不阻塞的方法，并提供一个具体的实现方案。 ... [详细]

蜡笔小新 2024-12-23 15:44:01
java
递推算法与大数处理

本问题探讨了在特定条件下排列儿童队伍的方法数量。题目要求计算满足条件的队伍排列总数，并使用递推算法和大数处理技术来解决这一问题。 ... [详细]

蜡笔小新 2024-12-23 12:18:55
express
2018-2019学年第六周《Java数据结构与算法》学习总结

本文总结了2018-2019学年第六周在《Java数据结构与算法》课程中的学习内容，重点介绍了非线性数据结构——树的相关知识及其应用。 ... [详细]

蜡笔小新 2024-12-22 16:43:19
java
深入解析Java枚举及其高级特性

本文详细介绍了Java枚举的概念、语法、使用规则和应用场景，并探讨了其在实际编程中的高级应用。所有相关内容已收录于GitHub仓库[JavaLearningmanual](https://github.com/Ziphtracks/JavaLearningmanual)，欢迎Star并持续关注。 ... [详细]

蜡笔小新 2024-12-22 14:46:52
string
PHP 过滤器详解

本文深入探讨了 PHP 中的过滤器机制，包括常见的 $_SERVER 变量、filter_has_var() 函数、filter_id() 函数、filter_input() 函数及其数组形式、filter_list() 函数以及 filter_var() 和其数组形式。同时，详细介绍了各种过滤器的用途和用法。 ... [详细]

蜡笔小新 2024-12-23 19:05:02
express
Servlet 表单处理：GET 和 POST 请求的深入解析

本文详细探讨了HTML表单中GET和POST请求的区别，包括它们的工作原理、数据传输方式、安全性及适用场景。同时，通过实例展示了如何在Servlet中处理这两种请求。 ... [详细]

蜡笔小新 2024-12-23 18:09:59
express
在Xcode中配置自定义文本样式

本文探讨了如何在iOS开发环境中，特别是在Xcode 6.1中，设置和应用自定义文本样式。我们将详细介绍实现方法，并提供一些实用的技巧。 ... [详细]

蜡笔小新 2024-12-23 14:36:31
java
JavaScript 基础语法指南

本文详细介绍了 JavaScript 的基础语法，包括变量、数据类型、运算符、语句和函数等内容，旨在为初学者提供全面的入门指导。 ... [详细]

蜡笔小新 2024-12-23 10:54:44
string
深入理解C++ map的删除与交换操作

本文详细介绍了C++中map容器的多种删除和交换操作，包括clear、erase、swap、extract和merge方法，并提供了完整的代码示例。 ... [详细]

蜡笔小新 2024-12-23 08:29:59
string
解决QT交叉编译时遇到的qatomic_i386.h:132错误

在进行QT交叉编译时，可能会遇到与目标架构不匹配的宏定义问题。例如，当为ARM或MIPS架构编译时，需要确保使用正确的宏（如QT_ARCH_ARM或QT_ARCH_MIPS），而不是默认的QT_ARCH_I386。本文将详细介绍如何正确配置编译环境以避免此类错误。 ... [详细]

蜡笔小新 2024-12-22 19:19:44
string
Qt QTableView 内嵌控件的实现方法

本文详细介绍了在 Qt QTableView 中嵌入控件的多种方法，包括使用 QItemDelegate、setIndexWidget 和 setIndexWidget 结合布局管理器。每种方法都有其适用场景和优缺点。 ... [详细]

蜡笔小新 2024-12-22 18:03:16

手机用户2602921931

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章