题目链接: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 ;
}

最新文章

  1. SQL SERVER触发器游标小记
  2. zabbix告警“Zabbix poller processes more than 75% busy”
  3. 【Java基础】Java面试题目整理与解说(二)
  4. java数据结构学习(一)之二分查找
  5. python方式实现scoket通信
  6. python 函数1
  7. BZOJ 1864: [Zjoi2006]三色二叉树( 树形dp )
  8. python中逐行读取文件的最佳方式_Drupal_新浪博客
  9. android模拟器网络设置(局域网)
  10. Kafka 源代码分析之ByteBufferMessageSet
  11. ddos攻击和cc攻击的区别和防护!!
  12. Struts2-整理笔记(一)介绍、搭建、流程、详解struts.xml
  13. mysql-workbench工具update(更新)失败的解决办法
  14. 生成Area URL链接
  15. css 子盒子上下居中 文字溢出省略号
  16. c# 状态机实现
  17. MAC MYSQ忘记密码重置方法
  18. hive学习-测试数据
  19. java 反射 报错:Attempt to get java.lang.Integer field &quot;...&quot; with illegal data type conversion to int
  20. linux -- chcp

热门文章

  1. /proc/modules分析
  2. hive中关键字作为列名的方法
  3. Linux解决删除文件后空间没有释放问题_端口占用问题
  4. hdu6121 Build a tree 模拟
  5. Unity3d优化总结1
  6. Apt encounters errors with bad GPG keys [duplicate]
  7. (转)spring IOC、DI理解
  8. 判断ActiveX控件是Desgin Mode还是Runtime Mode
  9. MySQL Error: PROCEDURE xmdk.query_all_plan can&#39;t return a result set in the given context
  10. WPF 的拖拽操作(DragDrop)