Geometric Progression---cf 567C(求组合方式,map离散)
2024-08-30 16:20:23
题目链接:http://codeforces.com/contest/567/problem/C
题意就是有n个数现在要让 ai aj ak 构成公比为K的等比数列(i < j < k);求有多少种组合方法;
我们可以对 a[i] 找 a[i]/k 和 a[i]*k ,设a[i]前面有 x个a[i]/k ;后面有y个 a[i]*k ;那么答案就是所有的x*y的和;由于数据比较大无法引用下标, 所以用map离散一下
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
#include <string>
using namespace std;
#define INF 0x3f3f3f3f
#define met(a, b) memset(a, b, sizeof(a))
#define N 200005
typedef long long LL; int main()
{
int n; LL k, a[N]; while(scanf("%d %I64d", &n, &k)!=EOF)
{
map<LL, LL> mp1, mp2; for(int i=; i<=n; i++)
{
scanf("%I64d", &a[i]); mp1[a[i]]++;
} LL ans = ; for(int i=n; i>=; i--)///倒着来便于统计mp2[x]的个数,即倒着来的数的个数;
{
mp1[a[i]] --;///正着来的要减减; if(a[i]%k==) ans += mp1[a[i]/k] * mp2[a[i]*k]; mp2[a[i]] ++;
} printf("%I64d\n", ans);
}
return ;
}
这是一个用二分写的,不用map离散化的代码;
LL a[maxn], b[maxn], l[maxn], r[maxn], n, m;
LL bin_sreach (LL x)
{
LL high = m-, low = ;
while (high >= low)
{
LL mid = (high + low) / ;
if (b[mid] == x)
return mid;
if (b[mid] < x)
low = mid + ;
else
high = mid -;
}
return n;
}
int main ()
{
LL k;
while (scanf ("%I64d %I64d", &n, &k) != EOF)
{
for (LL i=; i<n; i++)
{
scanf ("%I64d", &a[i]);
b[i] = a[i];
}
sort (b, b+n);
m = unique(b, b+n) - b;
memset (l, , sizeof(l));
memset (r, , sizeof(r));
for (LL i=; i<n; i++)
{
LL x = bin_sreach(a[i]);
l[x] ++;
}
__int64 ans = ;
for (LL i=n-; i>=; i--)
{
LL x, y, z;
x = y = n;
z = bin_sreach(a[i]);
l[z] --;
if (a[i] % k == )
x = bin_sreach(a[i]/k);
y = bin_sreach(a[i]*k);
ans += l[x] * r[y];
r[z] ++;
}
printf ("%I64d\n", ans);
}
return ;
}
最新文章
- SQL SERVER触发器游标小记
- zabbix告警“Zabbix poller processes more than 75% busy”
- 【Java基础】Java面试题目整理与解说(二)
- java数据结构学习(一)之二分查找
- python方式实现scoket通信
- python 函数1
- BZOJ 1864: [Zjoi2006]三色二叉树( 树形dp )
- python中逐行读取文件的最佳方式_Drupal_新浪博客
- android模拟器网络设置(局域网)
- Kafka 源代码分析之ByteBufferMessageSet
- ddos攻击和cc攻击的区别和防护!!
- Struts2-整理笔记(一)介绍、搭建、流程、详解struts.xml
- mysql-workbench工具update(更新)失败的解决办法
- 生成Area URL链接
- css 子盒子上下居中 文字溢出省略号
- c# 状态机实现
- MAC MYSQ忘记密码重置方法
- hive学习-测试数据
- java 反射 报错:Attempt to get java.lang.Integer field ";..."; with illegal data type conversion to int
- linux -- chcp
热门文章
- /proc/modules分析
- hive中关键字作为列名的方法
- Linux解决删除文件后空间没有释放问题_端口占用问题
- hdu6121 Build a tree 模拟
- Unity3d优化总结1
- Apt encounters errors with bad GPG keys [duplicate]
- (转)spring IOC、DI理解
- 判断ActiveX控件是Desgin Mode还是Runtime Mode
- MySQL Error: PROCEDURE xmdk.query_all_plan can&#39;t return a result set in the given context
- WPF 的拖拽操作(DragDrop)