T-1题目：2013 高斯日记

问题描述：
大数学家高斯有一个好习惯：无论如何都要记日记。
他的日记有一股与众不同的地方，他从不注明年月日，而是用一个整数代替：
比如4210。后来人们知道，那个整数是日记，他代表高斯出生后的第几天，
这或许也是好习惯，他时刻提醒着主人:日记又过去一天，还有多少时光
可以浪费呢？高斯出生于：1777年4月30日。
在高斯发现一个重要定理的日记上标注着：5343
因此可以算出那天是：1791年12月15日。
高斯获得博士学位的那天日记上写着：8113。
请你算出高斯获得博士学位的年月日。

输出格式：yyyy-mm-dd
样例输出：1980-03-21

答案

1799-07-16

C++代码

#include <iostream>
using namespace std;

bool isLeapYear(int y){
    return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0;
}

int main(){
    int y = 1777;
    int m = 4;
    int d = 30;

    for(int i = 1; i <= 8112; i ++){//题目中生日那天算一天
        if(m == 12 && d == 31){//更新年
            y ++;
            m = 1;
            d = 1;
            continue;
        }

        if((m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 ) && d == 31){
            m ++;
            d = 1;
            continue;
        }

        if((m == 4 || m == 6 || m == 9 || m == 11) && d == 30){
            m ++;
            d = 1;
            continue;
        }

        if(isLeapYear(y) && m == 2 && d == 29){
            m ++;
            d = 1;
            continue;
        }

        if(!isLeapYear(y) && m == 2 && d == 28){
            m ++;
            d = 1;
            continue;
        }

        d ++;
    }

    cout << y << ' ' << m << ' ' << d << endl;

    return 0;
}

T-2 题目: 马虎的算式 简单枚举

小明是个急性子，上小学的时候经常把老师写在黑板上的题目抄错了。
有一次，老师出的题目是：36 x 495 = ?
他却给抄成了：396 x 45 = ?
但结果却很戏剧性，他的答案竟然是对的！！
因为 36 * 495 = 396 * 45 = 17820
类似这样的巧合情况可能还有很多，比如：27 * 594 = 297 * 54
假设 a b c d e 代表1~9不同的5个数字（注意是各不相同的数字，且不含0）
能满足形如： ab * cde = adb * ce 这样的算式一共有多少种呢？
请你利用计算机的优势寻找所有的可能，并回答不同算式的种类数。
满足乘法交换律的算式计为不同的种类，所以答案肯定是个偶数。
答案直接通过浏览器提交。注意：只提交一个表示最终统计种类数的数字，
不要提交解答过程或其它多余的内容。

答案

142

C ++代码

#include <iostream>
using namespace std;

int main(){
    int cnt = 0;
    for(int a = 1; a <= 9; a ++){
        for(int b = 1; b <= 9; b ++){
            for(int c = 1; c <= 9; c ++){
                for(int d = 1; d <= 9; d ++){
                    for(int e = 1; e <= 9; e ++){
                        if(a == b || a == c || a == d || a == e) continue;
                        if(b == c || b == d || b == e) continue;
                        if(c == d || c == e) continue;
                        if(d == e) continue;
                        if((a * 10 + b) * (c * 100 + d * 10 + e) == (a * 100 + d * 10 + b) * (c * 10 +e))
                        cnt ++;
                    }
                }
            }
        }
    }
    cout << cnt << endl;

    return 0;
}

T-3 题目标题: 第39级台阶 类似斐波拉契数列

小明刚刚看完电影《第39级台阶》，离开电影院的时候，
他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。
那么，上完39级台阶，有多少种不同的上法呢？
请你利用计算机的优势，帮助小明寻找答案。
要求提交的是一个整数。
注意：不要提交解答过程，或其它的辅助说明文字。

结果：

51167078

解题思路一

递归求解

C++代码

#include <iostream>

using namespace std;
const int N = 50;

int cnt;//方案数
/**
* n表示剩余阶梯数
* step表示已走步数
*/
void f(int n, int step){
    if(n < 0) return;
    if(n == 0 && step % 2 == 0) {
        cnt ++;
        return ;
    }

    f(n - 1, step + 1);
    f(n - 2, step + 1);
}

int main(){
    f(39, 0);
    cout << cnt << endl;
    return 0;
}

解题思路二

动态规划

具体思路

闫氏DP分析法

一、状态表示：f[i][j]
1. 集合：走到第i层台阶,且步数模2为j的所有方案的集合.
2. 属性：方案数

二、状态计算：
1. 思想-----集合的划分
2. 集合划分依据：根据最后一步走了多少个台阶,即一个台阶或两个台阶进行划分,划分为两类
3. 具体划分为2类：
1. 跨一层台阶：f[i - 1][(j - 1 + 2) % 2]
2. 跨两层台阶：f[i - 2][(j - 1 + 2) % 2]
f[i][j] = f[i - 1][(j - 1 + 2) % 2] + f[i - 2][(j - 1 + 2) % 2];)
注：(j - 1 + 2) % 2保证余数合法，即为正余数

C ++代码

#include <iostream>

using namespace std;
const int N = 50;
int f[N][2];

int main(){
    f[0][0] = 1;//走到0层台阶,步数模2为0的方案数是1.
    f[0][1] = 0;//走到0层台阶,步数模2为1的方案数是0.
    f[1][0] = 0;//走到1层台阶,步数模2为0的方案数是0.
    f[1][1] = 1;//走到1层台阶,步数模2为1的方案数是1.

    for(int i = 2; i <= N; i ++){
        for(int j = 0; j <= 1; j ++){
            f[i][j] = f[i - 1][(j - 1 + 2) % 2] + f[i - 2][(j - 1 + 2) % 2];
        }
    }

    cout << f[39][0] << endl;

    return 0;
}