题意

给一个三角形，每个下层的数等于它正上方，左上方和右上方的数的和

求，第n行第一个偶数的位置。

限制：n 不大于$10^{9}10^9$

方法

模拟(TLE)

因为只关心奇偶，奇偶满足可加性，所以我们可以直接模拟过程，完成第n层奇偶性的计算。从而得到答案

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)
typedef long long ll;
int main(){
    int n;
    while(~scanf("%d",&n)){
        deque<int> v = {1}; // 当前行
        while(n > 1){
            deque<int> newv = {};
            rep(i,0,v.size()){ // 计算下一行的每一个
                newv.push_back((v[i] // 正上
                               +(i+1 < v.size()?v[i+1]:0) // 右上
                               +(i-1 >= 0?v[i-1]:0))%2); // 左上
            }
            v = newv;
            v.push_front(1); // 首位 放置1
            v.push_back(1);
            n--;
        }
        int pos = -1;
        rep(i,0,v.size()){
            if(v[i]%2==0){ // 找到第一个偶数
                pos = i+1;
                break;
            }
        }
        printf("%d\n",pos);
    }
    return 0;
}

复杂度分析

时间复杂度: 因为模拟了从开始到第n层的计算，所以时间复杂度为$O(n^2)O(n^2)$

空间复杂度: 始终只会有当前层和下一层的状态，所以空间复杂度为$O(n)O(n)$

数学

直接考虑边界, 开始枚举

如果从左边开始的4个分别是 1010那么有

产生了循环节

因此产生了模2为0的位置的循环节 2,3,2,4

注意到第三排左侧就是 1010开始，所以得到代码

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)
typedef long long ll;
int main(){
    int n;
    int cycle[]={2,3,2,4};
    while(~scanf("%d",&n)){
        printf("%d\n",n<=2?-1:cycle[(n-3)%4]); // 开始两个，或者在循环节里
    }
    return 0;
}

复杂度分析

时间复杂度: 读入和常数运算代价，所以时间复杂度为常数$O(1)O(1)$

空间复杂度: 只用了常数大小的额外空间，所以空间复杂度为$O(1)O(1)$