Successione di Fixoracci

NC26111. Successione di Fixoracci

描述

动态规划(Dynamic programming，简称dp)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。例如，假设小x一步能爬1层或2层台阶，求小x爬n层台阶共有几种方法，就可以用dp计算：设 $F_i$ 代表小x爬i层台阶共有几种方法，则 $F_i=F_{i-1}+F_{i-2}$ 。

小x是练习时长两年半的acm练习生，喜欢口胡、dp、线段树。妙就妙在，不管是什么题目，无论多难，小x都能用他喜欢的三样东西AC。

你可能不相信，但其实他口胡了一个定理：所有题目，都可以转化成在x数列上的操作。只要先dp出题目对应的x数列，再用线段树随便维护一下，就可以过了。以下给出x数列的定义：

$T_0=a$

$T_1=b$

$T_n=T_{n-1}\oplus T_{n-2}(n \geq 2)$

其中 $\oplus$ 为异或运算。

现在小x已经用dp求出了a和b的值。现在你只要求出 $T_n$ 是多少，就可以通过这道题目。

输入描述

输入三个正整数a,b,n，含义见题目描述。

其中

输出描述

输出一个整数，代表前两项为a,b的x数列在下标为n处的值。

示例1

输入:

1 2 2

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 460K, 提交时间: 2019-06-08 13:43:21

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long s[3],n;
    cin>>s[0]>>s[1]>>n;
    s[2]=s[0]^s[1];
    n%=3;
    cout<<s[n]<<endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 480K, 提交时间: 2019-06-09 14:24:06

#include<iostream>
using namespace  std;
long long a,b,n;
int main()
{cin>>a>>b>>n;
if(n%3==2)cout<<(a^b);else if (n%3==0)cout<<a;
else cout<<b;
}

Python3(3.5.2) 解法, 执行用时: 26ms, 内存消耗: 3564K, 提交时间: 2019-06-08 13:12:01

a,b,c=map(int,input().split());
c%=3;
if c==0:
    print(a);
elif c==1:
    print(b);
else:
    print(a^b);

上一题

下一题

详情