CSP 历届真题题解（持续更新中）

2021.12

1 序列查询

重点在于计算每个下标出现的次数，规律是下标为i-1的出现次数是a[i]-a[i-1]。代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x7fffffff;
const int N = 1e7 + 5;
const int mod = 1e9 + 7;

ll a[N];

int main() {
  ll m, n;
  cin >> m >> n;
  for (ll i = 1; i <= m; i++) {
    scanf("%lld", &a[i]);
  }
  a[m + 1] = n;
  ll ans = 0;
  for (ll i = 1; i <= m + 1; i++) {
    ans += (a[i] - a[i - 1]) * (i - 1);
  }
  cout << ans << '\n';
  return 0;
}

3 登机牌条码

常规大模拟题

本人水平有限，下面的代码只能跑出前40分。重点在于理清当大写、小写、数字三种模式转换的关系。（见下图）

后面60分想要拿到，就需要模拟出一个多项式除法了。可见在考场上想拿全分还是很难的。前40分代码见下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x7fffffff;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int mazi[N];
int dat[N];
int cntm, cntd;
int cntr;
int r[N], dx[N];
bool isA(char ch) {
  if (ch >= 'A' && ch <= 'Z')
    return true;
  return false;
}
bool isa(char ch) {
  if (ch >= 'a' && ch <= 'z')
    return true;
  return false;
}
bool isnum(char ch) {
  if (ch >= '0' && ch <= '9')
    return true;
  return false;
}
// 计算码字
void getMazi(string str) {
  int len = str.size();
  cntm = 0;     // mazi数组的长度
  int sta = 1;  // 1为大写模式，2为小写模式，3位数字模式
  for (int i = 0; i < len; i++) {
    if (isA(str[i])) {
      if (sta == 1) {
        mazi[++cntm] = (int)(str[i] - 'A');
      } else if (sta == 2) {
        sta = 1;
        mazi[++cntm] = 28;
        mazi[++cntm] = 28;
        mazi[++cntm] = (int)(str[i] - 'A');
      } else if (sta == 3) {
        sta = 1;
        mazi[++cntm] = 28;
        mazi[++cntm] = (int)(str[i] - 'A');
      }
    } else if (isa(str[i])) {
      if (sta == 1) {
        sta = 2;
        mazi[++cntm] = 27;
        mazi[++cntm] = (int)(str[i] - 'a');
      } else if (sta == 2) {
        mazi[++cntm] = (int)(str[i] - 'a');
      } else if (sta == 3) {
        sta = 2;
        mazi[++cntm] = 27;
        mazi[++cntm] = (int)(str[i] - 'a');
      }
    } else if (isnum(str[i])) {
      if (sta == 1) {
        sta = 3;
        mazi[++cntm] = 28;
        mazi[++cntm] = (int)(str[i] - '0');
      } else if (sta == 2) {
        sta = 3;
        mazi[++cntm] = 28;
        mazi[++cntm] = (int)(str[i] - '0');
      } else if (sta == 3) {
        mazi[++cntm] = (int)(str[i] - '0');
      }
    }
  }
  if (cntm & 1) {
    mazi[++cntm] = 29;
  }
  // 合并码字
  cntd = 0;
  for (int i = 1; i <= cntm; i += 2) {
    int tt = mazi[i] * 30 + mazi[i + 1];
    dat[++cntd] = tt;
  }
  return;
}

int main() {
  int w, s;
  cin >> w >> s;
  string str;
  cin >> str;
  int k = (s == -1) ? 0 : pow(2, s + 1);  //校验码字数目
  getMazi(str);
  int num = ceil(1.0 * (cntd + 1) / w) * w;
  cout << num << '\n';  // 长度
  dx[++cntdx] = num;
  // 码字
  for (int i = 1; i <= cntd; i++) {
    cout << dat[i] << '\n';
    dx[++cntdx] = dat[i];
  }
  // 填充数据
  for (int i = 1; i <= num - (cntd + 1); i++) {
    cout << "900\n";
    dx[++cntdx] = 900;
  }
  return 0;
}

2021.4

1 灰度直方图

桶排一遍即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x7fffffff;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;

int tt[N];
int a[505][505];

int main() {
  int n, m, l;
  cin >> n >> m >> l;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
      tt[a[i][j]]++;
    }
  for (int i = 0; i < l; i++) {
    cout << tt[i] << " ";
  }
  return 0;
}

2 邻域均值

考察二维前缀和，计算公式如下，可以在o(n^2)时间算出sum数组。
s u m i , j = a i , j + s u m i − 1 , j + s u m i , j − 1 − s u m i − 1 , j − 1 sum_{i,j}=a_{i,j}+sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1} sumi,j​=ai,j​+sumi−1,j​+sumi,j−1​−sumi−1,j−1​
计算均值的时候需要考虑一下边界情况，即数组下标不能越界，一定是在你所设置的范围之内，这里我把范围定在了[0,n]。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x7fffffff;
const int N = 605;
const int mod = 1e9 + 7;

int a[N][N];
int sum[N][N];

int main() {
  int n, l, r, t;
  scanf("%d%d%d%d", &n, &l, &r, &t);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      scanf("%d", &a[i][j]);
      sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int rlb = max(0, i - r - 1), clb = max(0, j - r - 1);
      int rrb = min(n, i + r), crb = min(n, j + r);
      int s = sum[rrb][crb] - sum[rrb][clb] - sum[rlb][crb] + sum[rlb][clb];
      int num = (rrb - rlb) * (crb - clb);
      if (s <= num * t)
        ans++;
    }
  }
  cout << ans << '\n';
  return 0;
}

如有不足，恳请指正！！