CodeForces - 272B Dima and Sequence 函数/思维

2024-06-09 04:18

本文主要是介绍CodeForces - 272B Dima and Sequence 函数/思维,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Dima and Sequence

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Dima got into number sequences. Now he’s got sequence a1, a2, …, an, consisting of n positive integers. Also, Dima has got a function f(x), which can be defined with the following recurrence:

f(0) = 0;
f(2·x) = f(x);
f(2·x + 1) = f(x) + 1.
Dima wonders, how many pairs of indexes (i, j) (1 ≤ i < j ≤ n) are there, such that f(ai) = f(aj). Help him, count the number of such pairs.

Input
The first line contains integer n (1 ≤ n ≤ 105). The second line contains n positive integers a1, a2, …, an (1 ≤ ai ≤ 109).

The numbers in the lines are separated by single spaces.

Output
In a single line print the answer to the problem.

Please, don’t use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples
input
3
1 2 4
output
3
input
3
5 3 1
output
1
Note
In the first sample any pair (i, j) will do, so the answer is 3.

In the second sample only pair (1, 2) will do.

题意理解:本题的意思是给出一个函数,满足三个条件:f(0)=0;
f(x)=f(2x);f(2x+1)=f(x)+1;我觉得解题思路在于观察规律;
由递推可知f(1)=f(2)=f(4)=f(8)……=1;本来打算打表;后来才发现规律找错了……此题要解决的话要从后向前推出所有函数值,找出函数值相同的数,通过排列组合从中选出一对就是答案

#include<iostream>
#include<cstdio>
using namespace std;
long long f[40]={0};//数组要设大一点
int main()
{int n;scanf("%d",&n);while(n--){ int sum=0;//意思是当x为当前值时的函数值int x;scanf("%d",&x);while(x){if(x&1)//如果x是奇数,则函数值+1,一直往前递推,最后可以得出f(x)的“祖先”{sum++;x=(x-1)/2;}else x/=2;//如果是偶数则不变}f[sum]++;//函数值位sum的x有几个}long long ans=0;for(int i=0;i<40;i++)ans+=f[i]*(f[i]-1)/2;//选对数printf("%I64d\n",ans);return 0;
}

这篇关于CodeForces - 272B Dima and Sequence 函数/思维的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1044197

相关文章

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

MySQL高级查询之JOIN、子查询、窗口函数实际案例

《MySQL高级查询之JOIN、子查询、窗口函数实际案例》:本文主要介绍MySQL高级查询之JOIN、子查询、窗口函数实际案例的相关资料,JOIN用于多表关联查询,子查询用于数据筛选和过滤,窗口函... 目录前言1. JOIN(连接查询)1.1 内连接(INNER JOIN)1.2 左连接(LEFT JOI

MySQL中FIND_IN_SET函数与INSTR函数用法解析

《MySQL中FIND_IN_SET函数与INSTR函数用法解析》:本文主要介绍MySQL中FIND_IN_SET函数与INSTR函数用法解析,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友一... 目录一、功能定义与语法1、FIND_IN_SET函数2、INSTR函数二、本质区别对比三、实际场景案例分

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

C语言函数递归实际应用举例详解

《C语言函数递归实际应用举例详解》程序调用自身的编程技巧称为递归,递归做为一种算法在程序设计语言中广泛应用,:本文主要介绍C语言函数递归实际应用举例的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录前言一、递归的概念与思想二、递归的限制条件 三、递归的实际应用举例(一)求 n 的阶乘(二)顺序打印

C/C++错误信息处理的常见方法及函数

《C/C++错误信息处理的常见方法及函数》C/C++是两种广泛使用的编程语言,特别是在系统编程、嵌入式开发以及高性能计算领域,:本文主要介绍C/C++错误信息处理的常见方法及函数,文中通过代码介绍... 目录前言1. errno 和 perror()示例:2. strerror()示例:3. perror(

Kotlin 作用域函数apply、let、run、with、also使用指南

《Kotlin作用域函数apply、let、run、with、also使用指南》在Kotlin开发中,作用域函数(ScopeFunctions)是一组能让代码更简洁、更函数式的高阶函数,本文将... 目录一、引言:为什么需要作用域函数?二、作用域函China编程数详解1. apply:对象配置的 “流式构建器”最

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程