[C++知识库]蓝桥杯C/C++百校真题赛（1期）Day1题解（九进制转十进制、数字三角形）

Q1 进制转化

进制转化，口算啥的都行。

#include <iostream>
using namespace std;
int main()
{
  cout << 2 + 2 * 9 + 2 * 9 * 9 * 9 << endl;
  return 0;
}

Q2 数字三角形

#include<iostream>
using namespace std;

const int N = 110;
int f[N][N];
int main()
{
  int n;
  cin >> n;
  for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= i; ++j)
      cin >> f[i][j];

    
  for(int i = 2; i <= n; ++i)
    for(int j = 1; j <= i; ++j)
      f[i][j] += max(f[i - 1][j], f[i - 1][j - 1]);

  if(n & 1) cout << f[n][n + 1 >> 1] << endl;
  else cout << max(f[n][n >> 1], f[n][n / 2 + 1]) << endl;
}

一开始写魔怔了以为是状态机模型。。实际上没有那么复杂，要求左右走的次数不相差超过1，有这样一个性质，若n为奇数，则答案为f[n][n / 2 + 1], 若n为偶数，则答案为f[n][ n / 2, n / 2 + 1].
$以下给出简单证明:$

$$\begin{gathered} 原命题等价于若有奇数层，则满足左右走次数不差超过1的方案一定最后 \\ 一定停在最后一层的中间。若有偶数层，则一定停在最靠近中间的两个 \\ 中的一个。反之亦然。 \\ 只证明奇数情况，偶数情况类似： \\ 先证明充分性： \\ 因为有奇数层，所以有偶数次移动机会。在第一层开始的时候， \\ 我们停在对应最后一层中?n/2?的中间位置.由于移动次数不相差超过1， \\ 所以左右移动次数相同，最后仍在?n/2?的位置。 \\ 再证必要性： \\ 反证法：假设能通过左右移动次数相差超过1的方式来到最后 \\ 一层的中间，每次向左移动都会让终点向左偏移一格，向右同理， \\ 若移动次数相差超过1，最后必然不能还停在中间位置。所以必要性成立。 \end{gathered}$$