题解 - CSP/NOIP 2021

CSP-J 2021 解题报告

当前做法得分: 100+100+100+100=400100 + 100 + 100 + 100 = 400。

分糖果

分析

实际上，就是在 [L,R][L, R] 的区间里面取一个数，使得它对 nn 取模得的余数最大。

显然，答案的最大值不超过 n−1n - 1。

答案不为 n−1n - 1 时，显然，R mod n≥L mod nR \bmod n \ge L \bmod n。

所以，我们只要判断区间里面有没有向 nn 取余得 n−1n - 1 的数即可。

如何判定？显然，直接判断 ⌊Ln⌋\lfloor \frac{L}{n} \rfloor 与 ⌊Rn⌋\lfloor \frac{R}{n} \rfloor 是否相等即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <cstdio>
using namespace std;

int main() {
  int N(0), L(0), R(0);
  scanf("%d%d%d", &N, &L, &R);
  if (R / N == L / N) {
    printf("%d\n", R % N);
  } else {
    printf("%d\n", N - 1);
  }
  return 0;
}

插入排序

分析

注意到类型 11 的操作数量较少，所以我们可以暴力修改。

首先预处理，排序。对于每一个修改，我们直接将对应的数前后移动，进行插入排序。询问时输出即可。注意，需要一个映射数组。

预处理需要 O(nlog⁡n)\mathcal O(n\log{n})，修改需要 O(5000n)\mathcal O(5000n)，询问需要 O(Q)\mathcal O(Q)，可以通过。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Num {
  int id, ele;
  Num(int i = -1, int e = 0) : id(i), ele(e) {}
};
bool operator<(Num lhs, Num rhs) {
  return lhs.ele == rhs.ele ? lhs.id < rhs.id : lhs.ele < rhs.ele;
}

int main() {
  int N(0), M(0);
  cin >> N >> M;
  vector<Num> nums(N);
  for (int i(0); i != N; ++i) {
    nums[i].id = i;
    cin >> nums[i].ele;
  }
  sort(nums.begin(), nums.end());
  vector<int> mp(N);  // bef->now 映射数组
  for (int i(0); i != N; ++i) {
    mp[nums[i].id] = i;
  }
  for (int op(0), x(0), v(0); M--;) {
    cin >> op >> x;
    --x;
    if (op == 1) {
      cin >> v;
      x = mp[x];
      nums[x].ele = v;
      // 暴力修改 插入排序
      while (x && nums[x] < nums[x - 1]) {
        swap(mp[nums[x].id], mp[nums[x - 1].id]);
        swap(nums[x], nums[x - 1]);
        --x;
      }
      while (x + 1 < N && nums[x + 1] < nums[x]) {
        swap(mp[nums[x + 1].id], mp[nums[x].id]);
        swap(nums[x + 1], nums[x]);
        ++x;
      }
    }
    if (op == 2) {
      cout << mp[x] + 1 << endl;
    }
  }
  return 0;
}

网络连接

分析

简易的模拟题。我们可以按照题目对合法地址串的规定，一条条实行。全题只要能判好是否合法，剩下的就是用 map 弄过去。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

bool isvalid(const string& ad) {
  vector<string> nums(1);
  for (int i(0), dot_cnt(0), dd_cnt(0);; ++i) {
    if (i == ad.size()) {
      if (dot_cnt != 3 || dd_cnt != 1) return false;
      break;
    }
    switch (ad[i]) {
      case '.':
        if (dd_cnt) return false;
        ++dot_cnt;
        nums.push_back("");
        break;
      case ':':
        if (dot_cnt != 3) return false;
        ++dd_cnt;
        nums.push_back("");
        break;
      default:
        if (!isdigit(ad[i])) return false;
        nums.back() += ad[i];
    }
    if (dot_cnt > 3 || dd_cnt > 1) return false;
  }
  for (int i(0); i != nums.size(); ++i) {
    if (nums[i].empty() || (i < 4 && nums[i].size() > 3) ||
        (i == 4 && nums[i].size() > 5))
      return false;
    if (nums[i] == "0") continue;
    if (nums[i][0] == '0') return false;
    int n(0);
    for (string::const_iterator j(nums[i].begin()); j != nums[i].end(); ++j)
      n = (n << 3) + (n << 1) + (*j - '0');
    if ((i < 4 && n > 255) || (i == 4 && n > 65535)) return false;
  }
  return true;
}

int main() {
  int N(0);
  cin >> N;
  string op, ad;
  map<string, int> dict;
  for (int i(0); i != N; ++i) {
    cin >> op >> ad;
    if (!isvalid(ad)) {
      cout << "ERR" << endl;
      continue;
    }
    if (op == "Server") {
      if (dict.find(ad) == dict.end())
        cout << "OK" << endl, dict[ad] = i + 1;
      else
        cout << "FAIL" << endl;
    }
    if (op == "Client") {
      if (dict.find(ad) == dict.end())
        cout << "FAIL" << endl;
      else
        cout << dict[ad] << endl;
    }
  }

  return 0;
}

小熊的果篮

分析

第一眼看过去，就肯定感觉跟链表有关。

我们考虑用循环队列去维护每一个块，一旦遇到相邻的两个块合并即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
  int N(0);
  cin >> N;
  vector<int> num(N), nxt(N, -1), head, tail;
  queue<int> heads;
  for (int i(0), cur(0); i != N; ++i) {
    cin >> num[i];
    if (!i || num[i - 1] != num[i]) {
      heads.push(head.size());
      if (i) tail.push_back(i - 1);
      head.push_back(i);
    } else
      nxt[i - 1] = i;
  }
  tail.push_back(N - 1);
  while (!heads.empty()) {
    int sz = heads.size();
    while (sz--) {
      int cur(heads.front());
      heads.pop();
      cout << head[cur] + 1 << ' ';
      head[cur] = nxt[head[cur]];
      if (~head[cur] && heads.back() < cur &&
          num[head[cur]] == num[head[heads.back()]]) {
        nxt[tail[heads.back()]] = head[cur];
        tail[heads.back()] = tail[cur];
        head[cur] = -1;
      }
      if (~head[cur]) {
        heads.push(cur);
      }
    }
    cout << endl;
  }

  return 0;
}

CSP-S 2021 解题报告

当前做法得分: 100+100+100+100=400100 + 100 + 100 + 100 = 400。

廊桥分配

分析

首先有一个定论：无论廊桥总数多少，每架飞机对应的廊桥是唯一的。

意思就是，比如有一架飞机，当有 55 架飞机时它对应第 44 架，那么当只有 44 个廊桥时它还对应第 44 架。只有三个廊桥时，它就不能乘廊桥。

原因是，廊桥分配遵循先到先得原则。

所以，我们可以处理出来每架飞机对应的廊桥编号，用优先队列。然后投入桶里，对桶进行前缀和，就得到了廊桥数量对应的飞机数量。再枚举分配给哪边多少个，就完成了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Pair {
  int first, second;
  Pair(int fst = 0, int sec = 0) : first(fst), second(sec) {}
};
bool operator<(Pair a, Pair b) { return a.first > b.first; }  // 优先队列的规则
bool cmp(Pair a, Pair b) {
  return a.first == b.first ? a.second < b.second : a.first < b.first;
}  // 排序的规则

void process(int M, vector<int>& buckets) {
  vector<Pair> vec(M);
  for (vector<Pair>::iterator i(vec.begin()); i != vec.end(); ++i)
    cin >> i->first >> i->second;
  sort(vec.begin(), vec.end(), cmp);
  // 用优先队列来维护可用的廊桥与正在使用廊桥的飞机
  priority_queue<int, vector<int>, greater<int> > bridges;
  priority_queue<Pair> usings;
  vector<int> id;
  for (vector<Pair>::const_iterator i(vec.begin()); i != vec.end(); ++i) {
    while (!usings.empty() &&
           usings.top().first <= i->first) {  // 用完廊桥就归还
      bridges.push(usings.top().second);
      usings.pop();
    }
    int cur(0);
    if (bridges.empty())  // 需要新廊桥
      cur = id.size(), id.push_back(0);
    else
      cur = bridges.top(), bridges.pop();
    ++id[cur];                          // 放入桶里
    usings.push(Pair(i->second, cur));  // 启用廊桥
  }
  buckets.assign(id.size() + 1, 0);
  for (int i(1); i != buckets.size(); ++i)
    buckets[i] = buckets[i - 1] + id[i - 1];  // 对桶进行前缀和
}

int main() {
  int N(0), M1(0), M2(0);
  cin >> N >> M1 >> M2;
  vector<int> buckets1(M1), buckets2(M2);
  process(M1, buckets1);
  process(M2, buckets2);
  int res(0);
  for (size_t i(0); i <= N; ++i)  // 枚举
    res = max(res, buckets1[min(buckets1.size() - 1, i)] +
                       buckets2[min(buckets2.size() - 1, N - i)]);
  cout << res << endl;

  return 0;
}

括号序列

分析

一眼，显然是区间 DP。

我们考虑直接用 fl,rf_{l,r} 表示区间内合法的序列数。

然而，我们发现，如果直接维护可能在 AB / ASB 转移中算重。

所以我们考虑维护 fl,r,0/1f_{l,r,0/1}。0 表示最后一次转移是加上一对括号，即左右括号配对；1 表示左右括号不配对，最后一次转移为 AB / ASB。

转移就很简单了。

规则一：直接判断即可，O(1)O(1)。

规则二：考虑枚举最右边的一个左右括号配对串，设为 [j,r)[j,r)；枚举可以全为星号的串 [i,j)[i,j)；答案就为 (fl,i,0+fl,i,1)×fj,r,0(f_{l,i,0} + f_{l,i,1}) \times f_{j,r,0}，未优化为 O(n2)O(n^2)。

规则三：从左往右、从右往左枚举两端可能的 SS 串，直接判断，O(n)O(n)。

我们发现规则二如果不优化，时复 O(n4)O(n^4)，荣获 65pts。

我们考虑维护双指针，同时维护 ii、jj，都是单调往右走，动态维护 ∑fj,r,0\sum{f_{j,r,0}}。最后的时间复杂度是 O(n3)O(n^3)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;

const int DVS = 1e9 + 7;
const int MXN = 505;
char str[MXN];
uint cnt[MXN][MXN][2], cbs[MXN][MXN];
int N, K;

inline bool match(int l, int r) {
  return (str[l] == '(' || str[l] == '?') &&
         (str[r - 1] == ')' || str[r - 1] == '?');
}

int main() {
  cin >> N >> K >> str;
  for (int i(0); i != N; ++i) {
    cbs[i][i] = 1;
    if (str[i] == '*' || str[i] == '?') {
      cbs[i][i + 1] = 1;
      for (int j(max(0, i - K + 1)); j != i; ++j) cbs[j][i + 1] = cbs[j][i];
    }
  }
  cbs[N][N] = 1;
  for (int i(0); i < N - 1; ++i) cnt[i][i + 2][0] = match(i, i + 2);
  for (int len(3); len <= N; ++len) {
    for (int l(0), r(len); r <= N; ++l, ++r) {
      if (!match(l, r)) continue;
      cnt[l][r][0] = (cbs[l + 1][r - 1] +
                      (cnt[l + 1][r - 1][0] + cnt[l + 1][r - 1][1]) % DVS) %
                     DVS;
      for (int i(l + 2); i < r - 2 && cbs[l + 1][i]; ++i)
        cnt[l][r][0] =
            (cnt[l][r][0] + (cnt[i][r - 1][0] + cnt[i][r - 1][1]) % DVS) % DVS;
      for (int i(r - 2); i > l + 2 && cbs[i][r - 1]; --i)
        cnt[l][r][0] =
            (cnt[l][r][0] + (cnt[l + 1][i][0] + cnt[l + 1][i][1]) % DVS) % DVS;
      for (uint i(l + 2), j(i - 1), rp(0); i < r - 1; ++i) {
        if (j <= i) {
          j = i, rp = 0;
        }
        while (cbs[i][j] && j < r - 1) rp = (rp + cnt[j++][r][0]) % DVS;
        cnt[l][r][1] = (cnt[l][r][1] +
                        (cnt[l][i][0] + cnt[l][i][1]) % DVS * 1LL * rp % DVS) %
                       DVS;
        rp = (rp + DVS - cnt[i][r][0]) % DVS;
      }
    }
  }
  cout << (cnt[0][N][0] + cnt[0][N][1]) % DVS << endl;
  return 0;
}

回文

分析

我们只要手动模拟如何取第一个数，就会发现：它是四指针！

我们用逆向思维，外层指针的运动对应的必然是内层指针也要运动，以满足回文属性。

所以我们每次贪心：如果我们第 kk 个选 xx，倒数第 kk 个能不能也选 xx？优先考虑当前选 L，然后在内层两指针尝试匹配，然后考虑 R，都不行就输出 -1。

因为一个数至多出现 22 次，所以这个贪心是必然最优、不会影响到后续动作的。

这题就做完了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;

int read() {
  int x(0);
  char c(getchar());
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  return x;
}

constexpr int MXN = 1000005;
int arr[MXN], T, N;
char str[MXN];

bool able(int a, int b, int c, int d) {
  for (int i(1), n(N - 2); i < n; ++i, --n) {
    if (a < b && arr[a] == arr[b]) {
      str[i] = 'L', str[n] = 'L', ++a, --b;
    } else if (a <= b && c <= d && arr[a] == arr[c]) {
      str[i] = 'L', str[n] = 'R', ++a, ++c;
    } else if (a <= b && c <= d && arr[b] == arr[d]) {
      str[i] = 'R', str[n] = 'L', --b, --d;
    } else if (c < d && arr[c] == arr[d]) {
      str[i] = 'R', str[n] = 'R', ++c, --d;
    } else {
      return false;
    }
  }
  return true;
}

void print() {
  for (int i(0); i != N; ++i) putchar(str[i]);
  putchar(10);
}

int main() {
  T = read();
  while (T--) {
    N = read() << 1;
    for (int i(0); i != N; ++i) arr[i] = read();
    int m(find(arr + 1, arr + N, arr[0]) - arr);
    str[0] = 'L', str[N - 1] = 'L';
    if (able(1, m - 1, m + 1, N - 1)) {
      print();
      continue;
    }
    m = find(arr, arr + N - 1, arr[N - 1]) - arr;
    str[0] = 'R', str[N - 1] = 'L';
    if (able(0, m - 1, m + 1, N - 2)) {
      print();
    } else {
      putchar('-'), putchar('1'), putchar(10);
    }
  }
  return 0;
}

交通规划

分析

首先从 k=2k=2 的部分分发现它想要找的是一组比较像割的东西。我们知道割一般用流做，这里 k>2k>2 应该是不好做，所以转平面图最短路。

然后发现要达成相邻不同颜色的附加点之间的无界面之间做两两匹配即可。进一步，我们发现它可以在环上形成括号序列状物，因为交叉一定可以变成包含。所以断环为链做区间 DP。

时间复杂度 O(∑knm+k3)O(\sum knm+k^3)，空间复杂度 O(nm+k2)O(nm+k^2)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MXN = 505;
const int MXK = 55;
const int MXV = 250105;
const int MXE = MXV * 4;
int N, M, B, T, K, bdp[4 * MXN], bde[4 * MXN];
int dist[MXV], cst[MXK][MXK], ans, res[MXK * 2][MXK * 2];
int head[MXV], to[MXE], len[MXE], nxt[MXE], egsz;
tuple<int, int, int> pts[MXK];

inline int read() {
  int x(0), c(getchar());
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + (c - '0'), c = getchar();
  return x;
}
inline void write(int x) {
  static char buf[14];
  if (!x) {
    putchar('0');
    return;
  }
  int d(0);
  while (x) buf[d++] = x % 10 + '0', x /= 10;
  while (d) putchar(buf[--d]);
}

inline int pt(int x, int y) { return x * (M - 1) + y; }
inline void addedge(int x, int y, int w) {
  to[egsz] = y, len[egsz] = w, nxt[egsz] = head[x], head[x] = egsz++;
  to[egsz] = x, len[egsz] = w, nxt[egsz] = head[y], head[y] = egsz++;
}
inline void remedge(int x, int y) {
  egsz -= 2;
  head[x] = nxt[head[x]], head[y] = nxt[head[y]];
}
inline bool useless(int p) { return get<2>(pts[p]) == get<2>(pts[(p + 1) % K]); }
inline int get_bdid(int x) {
  if (x >= 2 * M + N) --x;
  if (x >= M + N) --x;
  if (x >= M) --x;
  return x;
}
inline void setbd(int id, int p, int e) { bdp[id] = p, bde[id] = e; }

void calsp(int S) {
  for (int i(0); i != B + K; ++i) dist[i] = INF;
  priority_queue<pair<int, int>> pq;
  pq.push(make_pair(dist[S] = 0, S));
  while (!pq.empty()) {
    int d(-pq.top().first), c(pq.top().second);
    pq.pop();
    if (dist[c] != d) continue;
    for (int i(head[c]); ~i; i = nxt[i]) {
      int n(to[i]), l(len[i]);
      if (dist[n] > d + l)
        dist[n] = d + l, pq.push(make_pair(-dist[n], n));
    }
  }
}

int main() {
  memset(head, -1, sizeof head);
  N = read(), M = read(), T = read(), B = (N - 1) * (M - 1);
  for (int i(0), x(0); i != N - 1; ++i)
    for (int j(0); j != M; ++j) {
      x = read();
      if (j == 0) setbd(2 * M + 2 * N - 5 - i, pt(i, j), x);
      else if (j != M - 1) addedge(pt(i, j), pt(i, j - 1), x);
      else setbd(M - 1 + i, pt(i, j - 1), x);
    }
  for (int i(0), x(0); i != N; ++i)
    for (int j(0); j != M - 1; ++j) {
      x = read();
      if (i == 0) setbd(j, pt(i, j), x);
      else if (i != N - 1) addedge(pt(i, j), pt(i - 1, j), x);
      else setbd(2 * M + N - 4 - j, pt(i - 1, j), x);
    }
  while (T--) {
    K = read();
    for (int i(0), x(0), p(0), t(0); i != K; ++i)
      x = read(), p = read() - 1, t = read(), pts[i] = make_tuple(p, x, t);
    sort(pts, pts + K);
    bool no_use(true);
    for (int i(0); i != K; ++i)
      if (!useless(i)) no_use = false;
    if (no_use) {
      puts("0");
      continue;
    }
    for (int i(0); i != K; ++i) {
      addedge(B + (i + K - 1) % K, B + i, get<1>(pts[i]));
      pts[i] =
        make_tuple(get_bdid(get<0>(pts[i])), get<1>(pts[i]), get<2>(pts[i]));
    }
    for (int i(0), it(0); i != 2 * M + 2 * N - 4; ++i) {
      while (get<0>(pts[it]) == i) it = (it + 1) % K;
      addedge(bdp[i], B + (it + K - 1) % K, bde[i]);
    }

    for (int i(0); i != K; ++i) {
      calsp(B + i);
      for (int j(0); j != K; ++j) cst[i][j] = dist[B + j];
    }
    for (int i(0); i <= 2 * K; ++i) res[i][i] = 0;
    for (int i(0); i != 2 * K; ++i) res[i][i + 1] = (useless(i % K) ? 0 : INF);
    for (int len(2); len <= K; ++len) {
      for (int i(0); i + len <= 2 * K; ++i) {
        int r(i + len);
        if (useless(i % K) || useless((r - 1) % K)) {
          int a(i), b(r);
          while (a < b && useless(a % K)) ++a;
          while (b > a && useless((b - 1) % K)) --b;
          res[i][r] = res[a][b];
          continue;
        }
        res[i][r] = min(INF, res[i + 1][r - 1] + cst[i % K][(r - 1) % K]);
        for (int j(i + 1); j < r; ++j)
          res[i][r] = min(res[i][r], res[i][j] + res[j][r]);
      }
    }
    ans = INF;
    for (int i(0); i != K; ++i) ans = min(ans, res[i][i + K]);
    write(ans), putchar('\n');

    for (int i(0); i != K; ++i)
      remedge(B + (i + K - 1) % K, B + i);
    for (int i(0), it(0); i != 2 * M + 2 * N - 4; ++i) {
      while (get<0>(pts[it]) == i) it = (it + 1) % K;
      remedge(bdp[i], B + (it + K - 1) % K);
    }
  }
  return 0;
}

NOIP 2021 解题报告

当前做法得分: 100+100+100+32=332100 + 100 + 100 + 32 = 332。

报数

分析

一眼看，不能报某些数的倍数……

1≤x≤1071 \le x \le 10^7……

筛它！

这题就做完了。

注意边界为 107+110^7 + 1，不然对于极限数会炸开。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
using namespace std;

const int SIZE = 1e7 + 2;
bool invalid[SIZE];
int nxt[SIZE];

bool has7(int x) {
  for (; x; x /= 10) {
    if (x % 10 == 7) return true;
  }
  return false;
}

int main() {
  for (int i(1), bef(0); i != SIZE; ++i) {
    if (!invalid[i] && has7(i)) {
      for (int j(1); i * j < SIZE; ++j) {
        invalid[i * j] = true;
      }
    }
  }
  for (int i(SIZE - 2), bef(SIZE - 1); i; --i) {
    if (invalid[i])
      nxt[i] = -1;
    else
      nxt[i] = bef, bef = i;
  }
  int T(0);
  scanf("%d", &T);
  for (int x(0); T--;) {
    scanf("%d", &x);
    printf("%d\n", nxt[x]);
  }
  return 0;
}

数列

分析

直接从小往大 DP 即可，模拟比较高几位的具体状态，具体见代码，复杂度 O(mn4)O(mn^4)。思路还挺绕。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

const int DVS = 998244353;
const int MXN = 35;
const int MXM = 105;
int comb[MXN][MXN], cnt[MXM][MXN][MXN][MXN], pw[MXN];
int N, M, K, ans;

// i digits;
// chose j;
// add k i;
// before, there are l 1s;
// from now on, the status is s;
// f[i][j][l][s] * C(N - j, k) -> f[i + 1][j + k][l + (s + k) & 1][(s + k) >> 1]
// f[m][n][?][?]
// mnnkk

int main() {
  cin >> N >> M >> K;
  comb[0][0] = 1;
  for (int i(1); i <= N; ++i) {
    comb[i][0] = 1;
    for (int j(1); j <= i; ++j)
      comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % DVS;
  }
  cnt[0][0][0][0] = 1;
  for (int i(0), v(0); i <= M; ++i) {
    cin >> v;
    pw[0] = 1;
    for (int j(1); j <= N; ++j) pw[j] = pw[j - 1] * 1LL * v % DVS;
    for (int j(0); j <= N; ++j)
      for (int k(0); j + k <= N; ++k)
        for (int l(0); l <= K; ++l)
          for (int s(0); s <= N; ++s)
            (cnt[i + 1][j + k][l + ((s + k) & 1)][(s + k) >> 1]
             += cnt[i][j][l][s] * 1LL * pw[k] % DVS * comb[N - j][k] % DVS) %= DVS;
  }
  for (int j(0), pp(0); j <= N; ++j) {
    int cp(j);
    pp = 0;
    while (cp) pp += cp & 1, cp >>= 1;
    for (int i(0); i + pp <= K; ++i)
      (ans += cnt[M + 1][N][i][j]) %= DVS;
  }
  cout << ans << endl;
  return 0;
}

方差

分析

什么比赛有 2 道神奇 DP 呢。

观察操作，其实是交换差分。结论是：差分呈单谷时最优（我就不会证了，感觉上比较有道理吧）。

推式子。

1n∑i=1n(ai−aˉ)2=1n∑i=1n(ai−1n∑i=1nai)2=1n∑i=1n(ai2−2×ai×1n∑i=1nai+1n2(∑i=1nai)2)=(1n∑i=1nai2)−2(1n2∑i=1n(ai∑j=1naj))+(1n2∑i=1nai)2=1n(∑i=1nai2)−1n2(∑i=1nai)2\begin{aligned} &\frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2 \\ =& \frac{1}{n} \sum_{i = 1}^{n} (a_i - \frac{1}{n} \sum_{i = 1}^{n} a_i)^2 \\ =& \frac{1}{n} \sum_{i = 1}^{n} {(a_i^2 - 2 \times a_i \times \frac{1}{n} \sum_{i = 1}^{n} a_i + \frac{1}{n^2}(\sum_{i = 1}^{n} a_i)^2)} \\ =& (\frac{1}{n} \sum_{i = 1}^{n} a_i^2) - 2(\frac{1}{n^2} \sum_{i = 1}^{n} (a_i \sum_{j = 1}^{n} a_j)) + (\frac{1}{n^2} \sum_{i = 1}^{n} a_i)^2 \\ =& \frac{1}{n}(\sum_{i = 1}^{n} a_i^2) - \frac{1}{n^2}(\sum_{i = 1}^{n} a_i)^2\end{aligned}

乘上 n2n^2，就变成了 n(∑i=1nai2)−(∑i=1nai)2n(\sum_{i = 1}^{n} a_i^2) - (\sum_{i = 1}^{n} a_i)^2。

感觉 ∑i=1nai\sum_{i = 1}^{n} a_i 比较容易拿捏，那就把状态的一维设为它，另一维表示已经往前后插了前几个差分，值为最小的 ∑i=1nai2\sum_{i = 1}^{n} a_i^2。这样直接做，是 O(n2a)O(n^2a)。

最后一档分 aa 很小，告诉我们非 00 的差分很少，00 差分我们就不做了，那就只会做 aa 轮，复杂度 O(na2)O(na^2)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
int main() {
  typedef long long ll;
  const int INF = 0x3f3f3f3f;
  int N(0);
  cin >> N;
  vector<int> dif(N), sum(N);
  for (int i(0); i != N; ++i) cin >> dif[i];
  for (int i(N - 1); i; --i) dif[i] -= dif[i - 1];
  sort(dif.begin() + 1, dif.end());
  for (int i(1); i != N; ++i) sum[i] = sum[i - 1] + dif[i];
  int S = N * sum[N - 1], mn(0), mx(0);
  vector<int> cur(S + 1, INF), nxt(S + 1, INF);
  cur[0] = 0;
  for (int i(1); i != N; ++i) {
    if (!dif[i]) continue;
    for (int j(0); j <= S; ++j) {
      if (cur[j] == INF) continue;
      if (j + sum[i] <= S) {
        nxt[j + sum[i]]
            = min(nxt[j + sum[i]], cur[j] + sum[i] * sum[i]);
      }
      if (j + i * dif[i] <= S) {
        nxt[j + i * dif[i]]
            = min(nxt[j + i * dif[i]],
                cur[j] + 2 * dif[i] * j + i * dif[i] * dif[i]);
      }
    }
    cur.swap(nxt);
    nxt.assign(S + 1, INF);
  }
  ll ans = INT64_MAX;
  for (int i(0); i <= S; ++i)
      ans = min(ans, N * 1LL * cur[i] - i * 1LL * i);
  cout << ans << endl;
  return 0;
}

棋局

分析 - 32pts

模拟！！！根据各条道路的类型，在 bfs 的框架上乱搞就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
#include <cctype>
#include <cstdio>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

const int DIRs = 4;
const int Xs[] = {0, 0, 1, -1};
const int Ys[] = {1, -1, 0, 0};

void read(int& x) {
  char c(' ');
  x = 0;
  while (isspace(c)) {
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 3) + (x << 1) + (c - 48);
    c = getchar();
  }
}

void read(char& c) {
  c = ' ';
  while (isspace(c)) {
    c = getchar();
  }
}

void print(int x) {
  if (x < 10) {
    putchar(x + 48);
    return;
  }
  print(x / 10);
  putchar(x % 10 + 48);
}

namespace Task01 {
bool check(const vector<vector<char> >& he, const vector<vector<char> >& sh) {
  for (vector<vector<char> >::const_iterator i(he.begin()); i != he.end();
       ++i) {
    for (vector<char>::const_iterator j(i->begin()); j != i->end(); ++j) {
      if (*j == '2' || *j == '3') return false;
    }
  }
  for (vector<vector<char> >::const_iterator i(sh.begin()); i != sh.end();
       ++i) {
    for (vector<char>::const_iterator j(i->begin()); j != i->end(); ++j) {
      if (*j == '2' || *j == '3') return false;
    }
  }
  return true;
}
int main(int N, int M, int Q, vector<vector<char> >& he,
         vector<vector<char> >& sh) {
  vector<vector<int> > color(N, vector<int>(M, -1)),
      level(N, vector<int>(M, -1));
  for (int col(0), lv(0), x(0), y(0); Q--;) {
    read(col), read(lv), read(x), read(y);
    --x, --y;
    color[x][y] = col, level[x][y] = lv;
    int ans(0);
    if (x && sh[x - 1][y] == '1' &&
        (color[x - 1][y] != col && level[x - 1][y] <= lv)) {
      ++ans;
    }
    if (y && he[x][y - 1] == '1' &&
        (color[x][y - 1] != col && level[x][y - 1] <= lv)) {
      ++ans;
    }
    if (x != N - 1 && sh[x][y] == '1' &&
        (color[x + 1][y] != col && level[x + 1][y] <= lv)) {
      ++ans;
    }
    if (y != M - 1 && he[x][y] == '1' &&
        (color[x][y + 1] != col && level[x][y + 1] <= lv)) {
      ++ans;
    }
    print(ans);
    puts("");
  }
  return 0;
}
}  // namespace Task01

int main() {
  int T(0);
  read(T);
  while (T--) {
    int N(0), M(0), Q(0);
    read(N), read(M), read(Q);
    vector<vector<char> > he(N, vector<char>(M - 1)),
        sh(N - 1, vector<char>(M));
    for (int i(0); i != N; ++i) {
      for (int j(0); j != M - 1; ++j) {
        read(he[i][j]);
      }
    }
    for (int i(0); i != N - 1; ++i) {
      for (int j(0); j != M; ++j) {
        read(sh[i][j]);
      }
    }
    if (Task01::check(he, sh)) {
      Task01::main(N, M, Q, he, sh);
      continue;
    }
    vector<vector<int> > color(N, vector<int>(M, -1)),
        level(N, vector<int>(M, -1));
    for (int col(0), lv(0), x(0), y(0); Q--;) {
      read(col), read(lv), read(x), read(y);
      --x, --y;
      color[x][y] = col, level[x][y] = lv;
      int ans(0);
      vector<vector<bool> > vis(N, vector<bool>(M));
      queue<pair<int, int> > q;
      q.push(make_pair(x, y));
      vis[x][y] = true;
      while (!q.empty()) {
        pair<int, int> cur(q.front());
        q.pop();
        int nx = cur.first, ny = cur.second;
        if (nx && sh[nx - 1][ny] == '3' && !vis[nx - 1][ny]) {
          vis[nx - 1][ny] = true;
          if (~color[nx - 1][ny] || ~level[nx - 1][ny]) {
            ans += color[nx - 1][ny] != col && level[nx - 1][ny] <= lv;
          } else
            ++ans, q.push(make_pair(nx - 1, ny));
        }
        if (ny && he[nx][ny - 1] == '3' && !vis[nx][ny - 1]) {
          vis[nx][ny - 1] = true;
          if (~color[nx][ny - 1] || ~level[nx][ny - 1]) {
            ans += color[nx][ny - 1] != col && level[nx][ny - 1] <= lv;
          } else
            ++ans, q.push(make_pair(nx, ny - 1));
        }
        if (nx != N - 1 && sh[nx][ny] == '3' && !vis[nx + 1][ny]) {
          vis[nx + 1][ny] = true;
          if (~color[nx + 1][ny] || ~level[nx + 1][ny]) {
            ans += color[nx + 1][ny] != col && level[nx + 1][ny] <= lv;
          } else
            ++ans, q.push(make_pair(nx + 1, ny));
        }
        if (ny != M - 1 && he[nx][ny] == '3' && !vis[nx][ny + 1]) {
          vis[nx][ny + 1] = true;
          if (~color[nx][ny + 1] || ~level[nx][ny + 1]) {
            ans += color[nx][ny + 1] != col && level[nx][ny + 1] <= lv;
          } else
            ++ans, q.push(make_pair(nx, ny + 1));
        }
      }
      if (x && sh[x - 1][y] == '1' && !vis[x - 1][y]) {
        if (color[x - 1][y] != col && level[x - 1][y] <= lv) ++ans;
      } else if (x && sh[x - 1][y] == '2') {
        for (int nx(x), ny(y); nx && sh[nx - 1][ny] == '2'; --nx) {
          if (~color[nx - 1][ny] || ~level[nx - 1][ny]) {
            if (!vis[nx - 1][ny])
              ans += color[nx - 1][ny] != col && level[nx - 1][ny] <= lv;
            break;
          }
          if (!vis[nx - 1][ny]) ++ans;
        }
      }
      if (y && he[x][y - 1] == '1' && !vis[x][y - 1]) {
        if (color[x][y - 1] != col && level[x][y - 1] <= lv) ++ans;
      } else if (y && he[x][y - 1] == '2') {
        for (int nx(x), ny(y); ny && he[nx][ny - 1] == '2'; --ny) {
          if (~color[nx][ny - 1] || ~level[nx][ny - 1]) {
            if (!vis[nx][ny - 1])
              ans += color[nx][ny - 1] != col && level[nx][ny - 1] <= lv;
            break;
          }
          if (!vis[nx][ny - 1]) ++ans;
        }
      }
      if (x != N - 1 && sh[x][y] == '1' && !vis[x + 1][y]) {
        if (color[x + 1][y] != col && level[x + 1][y] <= lv) ++ans;
      } else if (x != N - 1 && sh[x][y] == '2') {
        for (int nx(x), ny(y); nx != N - 1 && sh[nx][ny] == '2'; ++nx) {
          if (~color[nx + 1][ny] || ~level[nx + 1][ny]) {
            if (!vis[nx + 1][ny])
              ans += color[nx + 1][ny] != col && level[nx + 1][ny] <= lv;
            break;
          }
          if (!vis[nx + 1][ny]) ++ans;
        }
      }
      if (y != M - 1 && he[x][y] == '1' && !vis[x][y + 1]) {
        if (color[x][y + 1] != col && level[x][y + 1] <= lv) ++ans;
      } else if (y != M - 1 && he[x][y] == '2') {
        for (int nx(x), ny(y); ny != M - 1 && he[nx][ny] == '2'; ++ny) {
          if (~color[nx][ny + 1] || ~level[nx][ny + 1]) {
            if (!vis[nx][ny + 1])
              ans += color[nx][ny + 1] != col && level[nx][ny + 1] <= lv;
            break;
          }
          if (!vis[nx][ny + 1]) ++ans;
        }
      }
      print(ans);
      puts("");
    }
  }

  return 0;
}
题解
#数据结构 #ad-hoc #模拟 #链表 #动态规划 #计数
题解 - CSP/NOIP 2021
http://sunsetglow95.github.io/2022/03/08/sol-2021/
作者
SunsetGlow95
发布于
2022年3月8日
许可协议