【codeforces 776C】Molly's Chemicals
2024-08-31 20:26:51
【题目链接】:http://codeforces.com/contest/776/problem/C
【题意】
让你找区间[i,j]
使得sum[i..j]=k^t,这里t=0,1,2,3..
-10<=k<=10
求出区间个数;
【题解】
/*
k^0==1
要求选[l,r]
sum[l..r]==k^t,t>=0,t=1,2,3...
前缀和
pre[i]-pre[j] =k^t; j∈[1..i-1]
pre[i]=k^t+pre[j-1];
把dic[k^t+pre[j-1]]++;这里t∈....
累加前缀和之后直接ans+=dic[pre[i]];
注意处理一下k=1和k=-1的情况(不一样的!);
*/
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int N = 1e5+100;
LL pre[N],a[N],temp[200],ans = 0;
int n, k,ma = 0;
map <LL, LL> dic;
int main()
{
//freopen("F:\\rush.txt", "r", stdin);
rei(n), rei(k);
LL t = 1;
temp[0] = 1;
if (k == 1||k==-1)
{
if (k == 1)
{
ma = 0;
temp[0] = 1;
}
else
{
ma = 1;
temp[0] = 1;
temp[1] = -1;
}
}
else
{
while (abs(t*k) < 1e15)
{
ma++;
t = t*k;
temp[ma] = t;
}
}
rep1(i, 1, n)
rel(a[i]);
rep1(i, 0, ma)
dic[temp[i] + 0]++;
rep1(i, 1, n)
{
pre[i] = pre[i - 1] + a[i];
ans += dic[pre[i]];
rep1(j, 0, ma)
dic[pre[i] + temp[j]]++;
}
printf("%lld\n", ans);
return 0;
}
最新文章
- java线程学习
- Hello Mybatis 04 使用spring-mybatis
- Oracle-- (RANK) 排名函数
- 前端见微知著工具篇:Bower组件管控
- Node.js简介
- C++异常处理的问题
- Storm(2) - Log Stream Processing
- P2763: [JLOI2011]飞行路线
- java web项目,java类中获得WEB-INF路径
- 理解lua 语言中的点、冒号与self
- Beta No.5
- 【XSY3042】石像 拓扑排序 状压DP 洲阁筛
- 编程语言分类,安装python解释器,变量
- Android开发之漫漫长途 Ⅶ——Android消息机制(Looper Handler MessageQueue Message)
- ELK Stack (2) —— ELK + Redis收集Nginx日志
- JAVA I/O(四)网络Socket和ServerSocket
- 什么是Ajax?Ajax的原理是什么?Ajax的核心技术是什么?Ajax的优缺点是什么?
- 如何使用科大 mirrors 加速 pip?
- POJ 1797 Heavy Transportation 【最大生成树的最小边/最小瓶颈树】
- elasticsearch.net search入门使用指南中文版
热门文章
- git在本地分支上 git pull远程分支时,状况
- 【例题 7-4 UVA - 524】Prime Ring Problem
- 【JAVASE】Java同一时候抛出多个异常
- html doctype作用
- fatfs输出目录
- 多类 SVM 的损失函数及其梯度计算
- autohotkey 自动登录输入用户名密码 getElementsByTagName/getElementsByClassName/getElementById
- [TypeScript] Distinguishing between types of Strings in TypeScript
- POJ3171 Cleaning Shifts DP,区间覆盖最值
- 初识Visual Studio Code 一.使用Visual Studio Code 开发C# 控制台程序