长春理工大学第十四届程序设计竞赛(重现赛)F.Successione di Fixoracci
2024-08-25 10:58:45
链接:https://ac.nowcoder.com/acm/contest/912/F
题意:
动态规划(Dynamic programming,简称dp)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。例如,假设小x一步能爬1层或2层台阶,求小x爬n层台阶共有几种方法,就可以用dp计算:设FiFi代表小x爬i层台阶共有几种方法,则Fi=Fi−1+Fi−2Fi=Fi−1+Fi−2。
小x是练习时长两年半的acm练习生,喜欢口胡、dp、线段树。妙就妙在,不管是什么题目,无论多难,小x都能用他喜欢的三样东西AC。
你可能不相信,但其实他口胡了一个定理:所有题目,都可以转化成在x数列上的操作。只要先dp出题目对应的x数列,再用线段树随便维护一下,就可以过了。以下给出x数列的定义:
T0=aT0=a
T1=bT1=b
Tn=Tn−1⊕Tn−2(n≥2)Tn=Tn−1⊕Tn−2(n≥2)
其中⊕⊕为异或运算。
现在小x已经用dp求出了a和b的值。现在你只要求出TnTn是多少,就可以通过这道题目
思路:
a xor b = c,a xor c = b, b xor c = a.
得到数列从0项开始是a,b,c循环。
代码:
#include <bits/stdc++.h> using namespace std; typedef long long LL; int main()
{
LL res[3];
LL n;
cin >> res[0] >> res[1] >> n;
res[2] = res[0]^res[1];
cout << res[n%3] << endl; return 0;
}
最新文章
- eclipse 快捷键
- ThinPHP命名空间,连接数据库是要修改的配置文件,Model数据模型层,跨控制器调用,如何获取系统常量信息,
- 形参是ofstream
- java中的static关键词
- BZOJ 1271 秦腾与教学评估
- css在各浏览器中的兼容问题
- 简单实用的Android ORM框架TigerDB
- UIBezierPathStudyDemo
- GB2312引进和使用的字体
- wxWidgets刚開始学习的人导引(1)——前言
- 【同行说】Android图片处理技术资料汇总(一)
- bzoj2125 最短路
- 基于查表的整数霍夫变换方法实现(matlab)
- [补档]暑假集训D3总结
- 关于C++函数返回局部对象的详细分析
- visual编译通过后,debug报错找不到*.dll
- 深入理解CSS系列(二):为什么height:100%不生效?
- Vim for Windows --ctags
- Python全栈开发-Day7-面向对象编程2
- UEditor编辑器两个版本任意文件上传漏洞分析