首页 > 其他分享 >POI2012ROZ-Fibonacci Representation

POI2012ROZ-Fibonacci Representation

时间:2024-04-25 09:05:11浏览次数:22  
标签:POI2012ROZ min int res fib Fibonacci Representation vec

POI #Year2012 #数学

贪心的每次选择最接近的两个数,\(x=min(x-fib_{i-1},fib_i-x)\)

// Author: xiaruize
const int N = 2e5 + 10;

vector<int> vec;
int n;

void solve()
{
	int res = 0;
	cin >> n;
	while (n)
	{
		auto it = upper_bound(ALL(vec), n);
		n = min(n - (*prev(it)), (*it) - n);
		res++;
	}
	cout << res << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	vec.push_back(1);
	vec.push_back(2);
	while (vec[vec.size() - 1] + vec[vec.size() - 2] <= 1e18)
		vec.push_back(vec[vec.size() - 1] + vec[vec.size() - 2]);
	cin >> testcase;
	while (testcase--)
		solve();
#ifndef ONLINE_JUDGE
	cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
	cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
	return 0;
}

标签:POI2012ROZ,min,int,res,fib,Fibonacci,Representation,vec
From: https://www.cnblogs.com/xiaruize/p/18156737

相关文章

  • CF1634F Fibonacci Additions
    Statement:给出两个长度为\(n\)的序列\(a,b\),每次在\(a\)或\(b\)上\([l,r]\)操作,一次操作将会使\([l,r]\)中的数分别加上\(fib[1],fib[2]...,fib[r-l+1]\),每次操作完询问\(a,b\)是否在模\(mod\)意义下相等。Solution:先简化问题,令\(c_i=a_i-b_i\),问题......
  • 6-1 使用函数输出指定范围内Fibonacci数的个数
    本题要求实现一个计算Fibonacci数的简单函数,并利用其实现另一个函数,输出两正整数m和n(0<m<n≤100000)之间的所有Fibonacci数的数目。所谓Fibonacci数列就是满足任一项数字是前两项的和(最开始两项均定义为1)的数列,fib(0)=fib(1)=1。其中函数fib(n)须返回第n项Fibonacci数;函数Prin......
  • 52 Things: Number 13: Outline the use and advantages of projective point represe
    52Things:Number13:Outlinetheuseandadvantagesofprojectivepointrepresentation.52件事:第13件:概述投影点表示的用途和优点。 Thisisthelatestinaseriesofblogpoststoaddressthelistof '52ThingsEveryPhDStudentShouldKnow' todoCryptogr......
  • 论文阅读-Causality Inspired Representation Learning for Domain Generalization
    标题:CausalityInspiredRepresentationLearningforDomainGeneralization会议:CVPR统计学上的相关(stastisticaldependence)不一定表示因果关系。CIRL旨在挖掘内在的因果机制(intrinsiccausalmechanism)。名词解释:DG(DomainGeneralization)域泛化SCM(StructuralCau......
  • [ARC060F] Best Representation
    题意给定一个字符串\(s\)。设一个字符串\(t\)是好的,当且仅当不存在一个\(\text{Period}\)能整除\(|t|\)。求最小的划分段数使得每段都是好的,及最小的划分段数的方案数。Sol考虑两种特殊情况:\(s\)有长度为\(1\)的\(\text{Period}\)。\(s\)本身就是好串。前者......
  • 蓝桥杯 试题 基础练习 Fibonacci数列
    问题描述Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少。输入格式输入包含一个整数n。输出格式输出一行,包含一个整数,表示Fn除以10007的余数。说明:在本题中,答案是要求Fn除以10007的余数,因此我们只要......
  • QOJ #1280.Fibonacci Partition/Fibonacci性质大杂烩
    QOJ#1280.FibonacciPartition(为什么布置的作业题没有任何可见AC记录啊/kk)拿下了QOJ上的用户首杀(同时目前也是QOJ可见的submission中唯一一个过掉这个题的,另一个是vjudge上我的提交)。也许是这个题实在是太冷门了,但是从Fibonacci-Lucas数列的性质应用上是一道非常......
  • Domain Agnostic Learning with Disentangled Representations
    DomainAgnosticLearningwithDisentangledRepresentations1.Introduction本文研究了领域不可知论学习(DAL),这是一个比较困难但实际的问题,即知识从一个标记的源领域转移到多个未标记的目标领域。领域不可知学习的主要挑战是:(1)目标数据具有混合的领域,这阻碍了主流特征对齐......
  • Fibonacci
    Fibonacci思路可以发现,连续的三个字母不全相同,所以|s|\(\le\)3*|t||S|枚举一下即可(好像能证明但是不会),1e6左右所以只要暴力算出来一段S,然后枚举起点开始匹配即可40分\(O(|S|*|s|)\)枚举即可100分使用类似倍增的方法st[i][j]表示从t[i]......
  • 佳佳的 Fibonacci
    和lyh想的差不多,我认为我写的会更详细一些。dyc好厉害。完全想不到这样的做法。给你两个整数\(n\),\(m\),让你求以下式子的值。\[T(n)=\sum_{i=1}^{n}f(i)\timesi\bmodm\]对于斐波那契数列\(f(n)=f(n-1)+f(n-2)\)这样的性质,使用前缀和化简式子是个好东西。式子就变......