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
Weight the Tree（树形dp）

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

蜡笔小新 2024-12-26 15:55:56
int
古代密码变换问题

本题探讨了一种字符串变换方法，旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量，从而确定转换的可能性。 ... [详细]

蜡笔小新 2024-12-28 09:18:22
int
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
int
深入理解KMP算法中的next数组：北大OJ 2406题解

本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

蜡笔小新 2024-12-28 11:30:01
int
C++实现经典排序算法

本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出，帮助读者全面了解这些排序方法的特点。 ... [详细]

蜡笔小新 2024-12-27 19:25:14
int
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
int
Splay Tree 区间操作优化

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

蜡笔小新 2024-12-26 18:47:12
int
C++ 中的数组与动态数组初始化

本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度，而 vector 是一种可扩展的容器，允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景，并提供了代码示例以加深理解。 ... [详细]

蜡笔小新 2024-12-26 15:38:03
int
洛谷 P4116 树上操作：颜色变换与路径查询

本题涉及一棵由N个节点组成的树（共有N-1条边），初始时所有节点均为白色。题目要求处理两种操作：一是改变某个节点的颜色（从白变黑或从黑变白）；二是查询从根节点到指定节点路径上的第一个黑色节点，若无则输出-1。 ... [详细]

蜡笔小新 2024-12-26 10:22:20
copy
探索1000以内的完美数：因数和等于自身

本文探讨了如何在1000以内找到所有完美数，即一个数的因数（不包括自身）之和等于该数本身。例如，6是一个完美数，因为1 + 2 + 3 = 6。通过编程实现这一过程，可以更好地理解完美数的特性。 ... [详细]

蜡笔小新 2024-12-25 19:21:06
int
Codeforces Round #566 (Div. 2) A~F个人题解

Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意：给你一个的表格，你 ... [详细]

蜡笔小新 2024-12-25 18:41:21
int
C++: 实现基于类的四面体体积计算

本文介绍如何使用C++编程语言，通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式，并提供了两种不同的实现方式。 ... [详细]

蜡笔小新 2024-12-27 14:31:39
int
长春大学软件工程：二叉排序树实验报告

本实验主要探讨了二叉排序树（BST）的基本操作，包括创建、查找和删除节点。通过具体实例和代码实现，详细介绍了如何使用递归和非递归方法进行关键字查找，并展示了删除特定节点后的树结构变化。 ... [详细]

蜡笔小新 2024-12-26 15:32:56
int
魔兽世界：备战策略

本文探讨了《魔兽世界》中红蓝两方阵营在备战阶段的策略与实现方法，通过代码展示了双方如何根据资源和兵种特性进行战士生产。 ... [详细]

蜡笔小新 2024-12-25 19:03:01
int
POJ 1691 矩形涂色问题 (DFS/状态压缩DP)

本题通过将每个矩形视为一个节点，根据其相对位置构建拓扑图，并利用深度优先搜索（DFS）或状态压缩动态规划（DP）求解最小涂色次数。本文详细解析了该问题的建模思路与算法实现。 ... [详细]

蜡笔小新 2024-12-25 18:27:21

手机用户2602921931

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

Tags | 热门标签

RankList | 热门文章