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

推荐阅读

main
java写简易五子棋游戏。

importjava.io.*;importjava.util.*;publicclass五子棋游戏{staticintm1;staticintn1;staticfinalintS ... [详细]

蜡笔小新 2024-11-20 17:34:54
main
UVALive 8201 - BBP 公式计算圆周率

在1995年，Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后，Bailey 和 Borwein 在他们的论文中发表了这一发现，这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]

蜡笔小新 2024-11-21 18:32:57
main
二维码的实现与应用

本文介绍了二维码的基本概念、分类及其优缺点，并详细描述了如何使用Java编程语言结合第三方库（如ZXing和qrcode.jar）来实现二维码的生成与解析。 ... [详细]

蜡笔小新 2024-11-21 17:10:15
main
Singleton单例模式和DoubleChecked Locking双重检查锁定模式

问题描述现在，不管开发一个多大的系统（至少我现在的部门是这样的），都会带一个日志功能；在实际开发过程中 ... [详细]

蜡笔小新 2024-11-21 15:14:45
main
自定义字符串连接函数（避免使用标准库函数）

本文介绍如何手动实现一个字符串连接函数，该函数不依赖于C语言的标准字符串处理函数，如strcpy或strcat。函数原型为void concatenate(char *dest, char *src)，其主要作用是将源字符串src追加到目标字符串dest的末尾。 ... [详细]

蜡笔小新 2024-11-20 17:39:42
case
H5技术实现经典游戏《贪吃蛇》

本文将分享一个使用HTML5技术实现的经典小游戏——《贪吃蛇》。通过H5技术，我们将探讨如何构建这款游戏的两种主要玩法：积分闯关和无尽模式。 ... [详细]

蜡笔小新 2024-11-21 20:16:59
config
Beetl模板引擎初探

Beetl是一款先进的Java模板引擎，以其丰富的功能、直观的语法、卓越的性能和易于维护的特点著称。它不仅适用于高响应需求的大型网站，也适合功能复杂的CMS管理系统，提供了一种全新的模板开发体验。 ... [详细]

蜡笔小新 2024-11-21 16:57:10
main
Go语言中接口型函数的应用与解析

本文深入探讨了Go语言中的接口型函数，通过实例分析其灵活性和强大功能，帮助开发者更好地理解和运用这一特性。 ... [详细]

蜡笔小新 2024-11-21 12:21:19
main
Go从入门到精通系列视频之go编程语言密码学哈希算法（二）

Go从入门到精通系列视频之go编程语言密码学哈希算法（二） ... [详细]

蜡笔小新 2024-11-21 10:55:36
main
深入理解C++构造函数

本文详细介绍了C++中的构造函数，包括其定义、特点以及如何通过构造函数进行对象的初始化。此外，还探讨了转换构造函数的概念及其在不同情境下的应用，以及如何避免不必要的隐式类型转换。 ... [详细]

蜡笔小新 2024-11-21 10:41:14
main
解决JavaScript中法语字符排序问题

在开发一个使用JavaScript、HTML和CSS的Web应用时，遇到从SQLite数据库中提取的法语词汇排序不正确的问题，特别是带重音符号的字母未按预期排序。 ... [详细]

蜡笔小新 2024-11-21 09:08:57
config
将图像平移到画布中心python_python – Tkinter画布缩放移动/平移

高级缩放示例.就像谷歌地图一样.它仅缩放图块,但不缩放整个图像.因此,缩放的瓷砖占据了恒定的记忆,并且不会为大型缩放图像调整大小的图像.对于简化的缩放示例lookhere.在Win ... [详细]

蜡笔小新 2024-11-20 15:47:04
byte
protobuf 使用心得：解析与编码陷阱

本文记录了一次在广告系统中使用protobuf进行数据交换时遇到的问题及其解决过程。通过这次经历，我们将探讨protobuf的特性和编码机制，帮助开发者避免类似的陷阱。 ... [详细]

蜡笔小新 2024-11-20 14:35:41
c语言
c语言二元插值,二维线性插值c语言

c语言二元插值,二维线性插值c语言 ... [详细]

蜡笔小新 2024-11-20 12:20:16
jsp
嵌套列表的扁平化处理

本文介绍了一种方法，用于遍历嵌套列表中的每个元素。如果元素是整数，则将其添加到结果数组中；如果元素是一个列表，则递归地遍历这个列表。此方法特别适用于处理复杂数据结构中的嵌套列表。 ... [详细]

蜡笔小新 2024-11-20 10:31:42

手机用户2602921931

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

Tags | 热门标签

RankList | 热门文章