暑假培训最后一次比赛答案详解

题目链接：acm.suse.edu.cn

A.求阶乘

模板题， 不过可以优化一下，使用记忆化搜索，针对与n!， 我们需要求(n-1)!,…. 而这些我们可能在前面就已经算过了的，所以没有必要每次都进行递归，采用记忆化搜索是个解决时间的好办法，拿时间换空间。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 91;
ll f[N];

ll d(int x) {
  if (f[x]) return f[x];
  if (x == 1 || x == 0) return 1;
  return f[x] = x * d(x - 1) % 97;
}

int main() {
  
  string s;
  getline(cin, s);
  istringstream ss(s);
  int x;
  bool f = false;
  while (ss >> x) {
    if (!f) {
      cout << d(x);
      f = true;
    } else cout << " " << d(x);
  }
  
  
  return 0;
}

当然也可以直接先初始化一下也行。

B.选择排序

模板

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 210;
ll a[N];
int n, m;
int main() {
  
  string s;
  getline(cin, s);
  istringstream ss(s);
  while (ss >> a[n]) n ++;
  scanf("%d", &m);
  // m次循环
  for (int i = 0; i < m; i ++ ) {
    int m = i; // 每次循环找到最大值，并和这次循环的第一个元素进行交换
    for (int j = i + 1; j < n; j ++ ) if (a[m] > a[j]) m = j;
    if (m != i) swap(a[i], a[m]);
  }
  // 打印结果
  for (int i = 0; i < n; i ++ ) {
    if (i) cout << " " << a[i];
    else cout << a[i];
  }
  return 0;
}

C.斐波拉契数列

模板题，可以使用记忆化搜索，降低时间复杂度

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a[110];

int main() {
  a[1] = 1;
  a[2] = 1;
  for (int i = 3; i <= 92; i ++ ) a[i] = a[i - 1] + a[i - 2];
  string s;
  getline(cin, s);
  istringstream ss(s);
  bool f = false;
  int x;
  while (ss >> x) {
    if (f) cout << " " << a[x];
    else {
      cout << a[x];
      f = true;
    }
  }
  return 0;
}

D.快速幂模板

不懂的直接去看文档

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a, b, c;

ll mul(ll a, ll b) {
  ll res = 1;
  while (b) {
    if (b & 1) res = (res * a) % c;
    a = (a * a) % c;
    b >>= 1;
  }
  return res;
}

int main() {
  cin >> a >> b >> c;
  a = a % c;
  cout << mul(a, b);
  
  return 0;
}

E.飞机上升或者下降

两种思路，一种是递归，另外一种是动态规划（就是递归+记忆化搜索）

递归：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int ans;
//int f[N][N][N];
void dfs(int a, int b, int h) {
  // 不能在上升，并且还可以下降一次，并且当前高度是1，则满足题意 
  if (h == 1 && a == 0 && b == 1) {
    ans ++;
    return;
  }
  if (h < 0) return; // 如果当前高度已经是负数了， 
  if (h > b) return; // 如果当前高度就算一直下降，也不能降到0 
//	cout << a << " - " << b << " - "<< h << endl;
// 如果一直上升，最后下降还剩余一些下降的次数，那么就不满足
  // 要么上升，要么下降 
  if (a > 0) dfs(a - 1, b, h * 2);
  if (b > 0) dfs(a, b - 1, h - 1);
}

signed main() {
  int a, b, h;
  cin >> a >> b >> h;
  dfs(a, b, h);
  cout << ans << endl;
  return 0;
}

动态规划：

#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int f[N][N][N];
// 检查当前如果一直上升的话
// 如果高度还是小于可以下降的次数
// 那么一定不行 
bool check(int a, int b, int c) {
  int res = c;
  for (int i = 0; i < a; i ++ ) res *= 2;
  return res >= b;
}

int main() {
  int a, b, h;
  cin >> a >> b >> h;
  int max_k = h;
  for (int i = 0; i <= a; i ++ ) { // 上升 次数 
    for (int j = 1; j <= b; j ++ ) { // 下降 次数 
      for (int k = 1; k <= j; k ++ ) { // 高度, 当前高度不能超过剩余的下降次数 
        // 如果当前只能下降则答案为 1 
        if (i == 0 && j == k) f[i][j][k] = 1;
        // 当前状态一共有两个操作，一个是上升，一个是下降，
        // 先看下降，如果check下降的操作没有问题，并且当前不只是只能下降 
        // 那么下降的操作就是合法的，下降的后的状态应该+=当前状态的答案 
        if (check(i, j + 1, k + 1) && !(i == 0 && j == k)) f[i][j + 1][k + 1] += f[i][j][k];
        // 如果当前k != 1(k/2!=0) 
        // 并且上升之前的状态合法 
        // 并且当前是由 某一个状态上升过来的（n*2 一定是偶数） 
        if (k / 2 != 0 && check(i + 1, j, k / 2) && k % 2 == 0) f[i + 1][j][k / 2] += f[i][j][k];
      }
    }
  }
  cout << f[a][b][h] << endl;
  return 0;
}

F.铺地板：

由于我的板砖是1*2的长方形，所以没有那么难进行dp。

我设：f[i]为当走廊长度为i时，一共有多少中方案，那么很明显，f[1] = 1；f[2] = 2(两个横着或者竖着)

那么如果为3呢，那么答案应该是在f[2]的基础上，横着放一块砖，或者是在f[1]的基础上，竖着放两块砖（如果在f[1]的基础上横着放两块砖，与在f[2]的基础上横着放一块砖没区别）所以我们就可以简单的推出他的递推公式了：

$$fi = \begin{cases} f_{i-1} + f{i-2}, &i\ge3\\ 1, &i<3 \end{cases}$$

所以代码非常简单：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 110;
int a[N], n;
int b[N];
signed main() {
  a[1] = 1;
  a[2] = 2;
  string s;
  getline(cin, s);
  istringstream ss(s);
  while(ss >> b[n]) n ++ ;
  for (int i = 3; i < 91; i ++ ) a[i] = a[i - 1] + a[i - 2]; 
  for (int i = 0; i < n; i ++ ) {
    cout << a[b[i]] << " ";
  }
  
  return 0;
}

G.需要写多少个2

首先，可以进行推理一波，123应该是等于在一百的基础上再加上23对应的答案

相信每个人都会暴力，可以自己先暴力看看结果

首先[0, 100)和[100, 200)这两个区间里面出现2的次数应该是一模一样的，因为这两个的百位都不是2，所以只用看十位和个位，同理，[300，1000)里面出现2的次数就应该等于 7 乘以[0, 100)区间的次数，这是相当有规律的，再看[200, 300)这个区间里面出现2的次数也应该是有规律的。

我们不要去在意 33中的22 出现了两次2， 我们可以直接进行“按位运算”，我计算完[20, 30)这个区间里面有10个数后，我再去算你的个位出现的次数就行了。

比如说我现在算[0, 30], 那么这个区间应该被划分为[0, 20), [20, 30), [30, 30], 一部分是从0到20的前一个（如果是1w的话，自然就是19999，这个看情况）,一部分是最高位就是2的部分，最后一部分也和第一部分是一样的。

然后我再去算每个区间出现2的总和，而第一个区间的最高位是小于2的，所以第一个区间也可以分为两个小的区间，这两个小的区间的值应该是一模一样的。

显而易见，针对一位数判断这个是否出现了2，我只需要判断它是否大于等于2即可。第三个区间的算法也是这样的。

对于每一位，我之去看它当前位出现2的次数是多少就可以了，比如[20, 29]这个区间，十位上2出现了十次，个位上出现了1次，那么总的就出现了11次。

那么对于这中间这个区间的算法我们也就知道了。

but， 换个思路，针对于[20, 30)这个区间，它应该是再[0, 10)出现的次数的基础上多了十位上这个2，一共多出现了10次，而[200, 300)这个区间，同理可得，它应该是再[0, 100)的基础上多了100个2，那么就有规律所寻了，无论当前出现的是多少，我都乘上对应的数（第一个区间和第三个区间是一样的，而第二个区间比第一个区间多一点东西，这个东西需要我们去单独运算），抛开这个多出来的东西，那么这个位上出现的次数就可以直接计算出来。

那么题目大概就可以这么做：

1234 =>[0, 1000] + [0, 234] + [2000, 1234],前面那个是一个较为完整的区间，而且千位上是小于2的数，所以可以直接得到对应的答案。

而第一个区间由规律可得答案是300，

再看第三个区间，第三个区间就是我们上面说的第二个区间多出来的数，很明显，在这里是一个空集，所以是0

而第二个区间就需要我们再去慢慢计算，这个问题就变成了一个小问题，而小问题一直递归下去，直到为0为止。

再算[0, 234] = 2 * [0, 100] + [0, 23] + [200, 234]

第一个区间由规律可得答案是20， 第三个区间中的元素个数应该是234 - 200 + 1 = 35个

又被递归变成了一个子问题[0, 34] …….

但是注意，极限情况下，最多就出现了10^n个，所以不要加太多了。

$$f(1234) = f(1000)+f(234)+count([2000, 1234])\\ =300+f(234)+0\\ =300+20*2+f(34)+count([200, 234])\\ = 300 + 40 + 35 + f(34)\\ =375+3*1+f(4) + count([20, 34])\\ =375+3+1+count([20,29])\\ =375+4+10\\ =389\\$$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll a[15];
int c(ll n) {
  int res = 0;
  while (n) {
    res ++;
    n /= 10;
  }
  return res;
}

ll f(ll n) {
  if (n < 0) n = -n;
  
  int len = c(n); // 长度 
  if (n <= 0) return 0;
  if (len == 1) return n >= 2;
  
  int l = (n / pow(10, len - 1)); // 最高位 
  ll res = a[len - 1] * l; 
  ll r = n - l * pow(10, len - 1); // 去掉最高位 
  
  if (l == 2) res += r + 1;
  else if (l != 1) res += pow(10, len - 1);
  
  return res + f(r);
}


int main() {
  
  for (int i = 0; i <= 15; i ++ ) a[i] = i * pow(10, i - 1);
  
  string s;
  getline(cin, s);
  istringstream ss(s);
  bool f1 = false;
  while (ss >> n)
    if (f1) cout << " " << f(n);
    else {
      cout << f(n);
      f1 = true;
    }
  return 0;
}

H.等边三角形

读题，必须是等边三角形，必须是全部用完，仔细思考一下就知道了，它每条边的长度必须是所有棍子的和的1/3，如果超过了这个必然是错的

所以我们就可以进行大量的剪梅了。如果不进行大量的剪梅，肯定是要超时的。

我们用dfs(i, j, k, sum)来表示第一个边的长度是i，第二个边的长度是j， 第三个边的长度是k， 总共用了sum个棍子

第一个剪梅：如果当前已经找到答案了，就不要再继续递归找答案了

第二个剪梅：如果已经用完了，但是其中一个为0，直接结束

第三个剪梅：如果还剩一个棍子，但是其中两个还是0，直接结束

第四个if是判断答案。

再看循环体中的代码：遍历每一个棍子，如果这个棍子没有用过，那么我就可以使用它：

• 第四个剪梅：如果加到第一条边后，长度不大于平均值，就可以给
• 第五个剪梅：如果加到第二条边后，长度不大于平均值，就可以给
• 第六个剪梅：如果加到第三条边后，长度不大于平均值，就可以给

如果看不懂这个循环和if(3*(a + d[i]) < avg)里面三行代码什么意思就不用继续看了，回去看深搜的模板，说明你还没有看懂深搜

#include <bits/stdc++.h>
using namespace std;
//typedef long long ll;
//const int N = 1e5 + 10;
int n, t, d[30], avg;
bool vis[30];
bool f = false;
void dfs(int a, int b, int c, int sum) {
  if (f) return;
  if (sum == n && (!a || !b || !c)) return;
  if (sum == n - 1) {
    // 如果是最后一次了，并且 有两个为0
    if ((a && !b && !c) || (!a && b && !c) || (!a && !b && c)) return;
  }
  if (a == b && b == c && a != 0 && sum == n) {
    f = true;
    return;
  }
  for (int i = 0; i < n; i ++ ) {
    if (!vis[i]) {
      if (3 * (a + d[i]) <= avg) {
        vis[i] = true;
        dfs(a + d[i], b, c, sum + 1);
        vis[i] = false;
      }
      if (3 * (b + d[i]) <= avg) {
        vis[i] = true;
        dfs(a, b + d[i], c, sum + 1);
        vis[i] = false;
      }
      if (3 * (c + d[i]) <= avg) {
        vis[i] = true;
        dfs(a, b, c + d[i], sum + 1);
        vis[i] = false;
      }
    }
  }
}
int main() {
  scanf("%d", &t);
  while (t -- ) {
    f = false;
    avg = 0;
    scanf("%d", &n);
    memset(vis, 0, sizeof vis);
    for (int i = 0; i < n; i ++ ) {
      scanf("%d", d + i);
      avg += d[i];
    }
    sort(d, d + n, greater<int>());
    dfs(0, 0, 0, 0);
    if (f) puts("yes");
    else puts("no");
  }
  return 0;
}