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

推荐阅读

int
CUGB图论专题：排水系统中的最大流问题 - EK与Dinic算法解析

本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率，使用经典的EK（Edmonds-Karp）和Dinic算法进行求解。 ... [详细]

蜡笔小新 2024-12-25 17:47:23
int
毕业设计：基于机器学习与深度学习的垃圾邮件（短信）分类算法实现

本文详细介绍了如何使用机器学习和深度学习技术对垃圾邮件和短信进行分类。内容涵盖从数据集介绍、预处理、特征提取到模型训练与评估的完整流程，并提供了具体的代码示例和实验结果。 ... [详细]

蜡笔小新 2024-12-25 17:38:50
int
Winter-1-C A + B II 问题解析与代码实现

本文介绍了 Winter-1-C A + B II 问题的详细解题思路和测试数据。该问题要求计算两个大整数的和，并输出结果。我们将深入探讨如何处理大整数运算，确保在给定的时间和内存限制下正确求解。 ... [详细]

蜡笔小新 2024-12-24 12:26:05
int
最小路径覆盖与强连通分量的应用：国王的问题

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

蜡笔小新 2024-12-23 18:42:12
int
递推算法与大数处理

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

蜡笔小新 2024-12-23 12:18:55
int
编写有趣的VBScript恶作剧脚本

本文将介绍如何编写一些有趣的VBScript脚本，这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例，帮助您了解VBScript的基本语法和功能。 ... [详细]

蜡笔小新 2024-12-28 09:46:23
int
分页插件3指定到某一页

前言--页数多了以后需要指定到某一页（只做了功能，样式没有细调）html ... [详细]

蜡笔小新 2024-12-27 15:19:01
int
Java 序列化接口详解

本文深入探讨了 Java 中的 Serializable 接口，解释了其实现机制、用途及注意事项，帮助开发者更好地理解和使用序列化功能。 ... [详细]

蜡笔小新 2024-12-27 15:06:12
int
UNP 第9章：主机名与地址转换

本章探讨了用于在主机名和数值地址之间进行转换的函数，如gethostbyname和gethostbyaddr。此外，还介绍了getservbyname和getservbyport函数，用于在服务器名和端口号之间进行转换。 ... [详细]

蜡笔小新 2024-12-27 11:26:39
int
Unity 客户端框架设计：UI管理系统的构建

本文详细介绍了如何构建一个高效的UI管理系统，集中处理UI页面的打开、关闭、层级管理和页面跳转等问题。通过UIManager统一管理外部切换逻辑，实现功能逻辑分散化和代码复用，支持多人协作开发。 ... [详细]

蜡笔小新 2024-12-27 10:28:40
int
Splay Tree 区间操作优化

本文详细介绍了使用Splay Tree进行区间操作的实现方法，包括插入、删除、修改、翻转和求和等操作。通过这些操作，可以高效地处理动态序列问题，并且代码实现具有一定的挑战性，有助于编程能力的提升。 ... [详细]

蜡笔小新 2024-12-26 18:47:12
int
Apache Jena 中 Txn.executeWrite 方法详解与代码示例

本文详细介绍了 Apache Jena 库中的 Txn.executeWrite 方法，通过多个实际代码示例展示了其在不同场景下的应用，帮助开发者更好地理解和使用该方法。 ... [详细]

蜡笔小新 2024-12-26 17:55:52
int
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
int
Tetris 排名系统 (拓扑排序与并查集的应用)

本题旨在通过给定的评级信息，利用拓扑排序和并查集算法来确定全球 Tetris 高手排行榜。题目要求判断是否可以根据提供的信息生成一个明确的排名表，或者是否存在冲突或信息不足的情况。 ... [详细]

蜡笔小新 2024-12-24 21:03:51
int
图论问题解析：POJ2762 从u到v或从v到u的可达性判断（强连通分量缩点与单向连通性检测）

本文深入探讨了POJ2762问题，旨在通过强连通分量缩点和单向连通性的判断方法，解决有向图中任意两点之间的可达性问题。文章详细介绍了算法原理、实现步骤，并附带完整的代码示例。 ... [详细]

蜡笔小新 2024-12-24 10:44:24

手机用户2602921931

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

Tags | 热门标签

RankList | 热门文章