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

相关文章

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++中,模板是实现泛型编程

kotlin的函数forEach示例详解

《kotlin的函数forEach示例详解》在Kotlin中,forEach是一个高阶函数,用于遍历集合中的每个元素并对其执行指定的操作,它的核心特点是简洁、函数式,适用于需要遍历集合且无需返回值的场... 目录一、基本用法1️⃣ 遍历集合2️⃣ 遍历数组3️⃣ 遍历 Map二、与 for 循环的区别三、高

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

MySQL中COALESCE函数示例详解

《MySQL中COALESCE函数示例详解》COALESCE是一个功能强大且常用的SQL函数,主要用来处理NULL值和实现灵活的值选择策略,能够使查询逻辑更清晰、简洁,:本文主要介绍MySQL中C... 目录语法示例1. 替换 NULL 值2. 用于字段默认值3. 多列优先级4. 结合聚合函数注意事项总结C

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》:本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口?Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链

MySQL 日期时间格式化函数 DATE_FORMAT() 的使用示例详解

《MySQL日期时间格式化函数DATE_FORMAT()的使用示例详解》`DATE_FORMAT()`是MySQL中用于格式化日期时间的函数,本文详细介绍了其语法、格式化字符串的含义以及常见日期... 目录一、DATE_FORMAT()语法二、格式化字符串详解三、常见日期时间格式组合四、业务场景五、总结一、

golang panic 函数用法示例详解

《golangpanic函数用法示例详解》在Go语言中,panic用于触发不可恢复的错误,终止函数执行并逐层向上触发defer,最终若未被recover捕获,程序会崩溃,recover用于在def... 目录1. panic 的作用2. 基本用法3. recover 的使用规则4. 错误处理建议5. 常见错