Tribleave's Blog

0%

CSP-J/S2021第二轮题解

发表于 更新于 分类于

CSP-J 2021

题目 考点
分糖果 数学
插入排序 插入排序
网络连接 模拟
小熊的果篮 双向链表

CSP-S 2021

题目 考点
廊桥分配 模拟优化
括号序列 区间DP
回文 模拟、贪心
交通规划 最短路、区间动态规划

Junior

分糖果

题意

选择 $[L, R]$ 中的某个数 $x$， 使得 $x \mod k$ 的结果最大。

思路

分两种情况考虑：

  • 若 $L$ 和 $R$ 对 $k$ 取模后在同一区间，则必然在 $x = R$ 位置取到最大值；
  • 否则 $[L, R]$ 必然跨越多个区间，则取模后的结果必然有 $k - 1$。

而对于是否在同一区间，在除以 $k$ 后，商是否一致判断即可。

参考代码

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  ll n, l, r;
  cin >> n >> l >> r;
  if (l / n != r / n) cout << n - 1 << endl;
  else cout << r % n << endl;
  return 0;
}

插入排序

题意

给定长度为 $n (n \le 8000)$ 的整数序列 $a_i$，有 $Q$ 种操作：

  1. $x$ $v$：修改序列 $a$ 中的第 $x$ 个元素 $a_x$ 为 $v$，该操作次数不超过5000次；
  2. $x$：将数组进行稳定排序，求原先第 $x$ 个元素排序后的位置。

思路

不如维护将原先所有的 $a_i$ 排序后的升序数组。
对于所有操作，我们需要维护原位置到有序数组中的映射。

  • 对于 1 操作，找到 $a_x$ 对应位置，显然修改值将使其往前或往后。
    联系到题目中提示的插入排序，可以不断向前/向后比较。注意同时维护映射关系。
  • 对于 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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 8e3+5;
int a[N];
pii p[N];

int main() {
  ios::sync_with_stdio(false);
  int n, q; cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    p[i] = {a[i], i};
  }
  sort(p + 1, p + 1 + n);
  for (int i = 1; i <= n; i++) a[p[i].second] = i;
  for (int i = 0, op, x, v; i < q; i++) {
    cin >> op; 
    // 5000 * 8000 = 4e7
    if (op == 1) {
      cin >> x >> v;
      int pos = a[x];
      p[pos].first = v;
      while (pos > 1 && p[pos] < p[pos - 1]) {
        swap(a[p[pos].second], a[p[pos - 1].second]);
        swap(p[pos], p[pos - 1]);
        pos--;
      } 
      while (pos < n && p[pos] > p[pos + 1]) {
        swap(a[p[pos].second], a[p[pos + 1].second]);
        swap(p[pos], p[pos + 1]);
        pos++;
      }
    } else {
      cin >> x;
      cout << a[x] << endl;
    }
  }
  return 0;
}

网络连接

题意

解析带端口的IP地址串，按服务器和客户端角色判断连接情况。

思路

若将带端口的IP地址串记为 a.b.c.d:e，则需要检查的项目有：

  • 有三个点号和一个冒号分隔字符串，且冒号出现在最后；
  • $a,b,c,d,e$ 均不为空，且不含有前导零；
  • $0 \le a,b,c,d \le 255$, $0 \le e \le 65535$。

可将对字符串的解析抽象为函数，简化代码逻辑。

参考代码

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
#include <bits/stdc++.h>
using namespace std;
map<string, int> dict;
const int IP = 256;
const int PORT = 65536;

bool check(string s, int limit) {
  // ".0.0.1:80" -> ""
  if (s.empty()) return false;
  // "0127.0.0.1:80" -> "0127"
  if (s[0] == '0' && s.size() > 1) return false;
  int val = 0;
  for (int i = 0; i < s.size(); i++) {
    val = val * 10 + s[i] - '0'; 
    if (val >= limit) return false;
  }
  return true;
}

bool parse(string ip) {
  string s = "";
  int dot_cnt = 0, port_cnt = 0;
  for (int i = 0; i < ip.size(); i++) {
    if (ip[i] == '.') dot_cnt += 1;
    if (ip[i] == ':') {
      if (dot_cnt != 3) return false;
      port_cnt += 1;
    }
    if (!isdigit(ip[i])) {
      if (!check(s, IP)) return false;
      s = "";
    } else s += ip[i];
  }
  return check(s, PORT) && dot_cnt == 3 && port_cnt == 1;
}

void process_server(string ip, int id) {
  bool valid = parse(ip);
  if (!valid) {cout << "ERR" << endl; return;}
  if (dict.count(ip)) {cout << "FAIL" << endl; return;}
  dict[ip] = id;
  cout << "OK" << endl;
}

void process_client(string ip) {
  bool valid = parse(ip);
  if (!valid) {cout << "ERR" << endl; return;}
  if (!dict.count(ip)) {cout << "FAIL" << endl; return;}
  cout << dict[ip] << endl;
}

int main() {
  ios::sync_with_stdio(false);
  int n; cin >> n;
  for (int i = 1; i <= n; i++) {
    string name, ip;
    cin >> name >> ip;
    if (name[0] == 'S') process_server(ip, i);
    else process_client(ip);
  }
  return 0;
}

小熊的果篮

题意

有两类共 $n$ 个水果拍成一排，称连续的排在一起的同一种水果称为“块”。

每次将每一个“块”中最左边的水果同时挑出。重复该操作直至水果用完。

每次水果被挑出后“块”会发生动态变化。

思路

尝试建模每个块，使用块头来表示每个块的开始位置，即第一个元素或与上一个元素类型不同的位置。

每个元素之间使用双向链表相连接。

对于每次输出选出的元素，我们只需要依次输出块头元素，并从双向链表中删除该元素。

当块头元素输出后，需要更新块头列表。
考虑在原块头位置的下一个元素，只有当：

  • 该下一个元素与原块头位置的上一个元素类型不同；
  • 该下一个元素不是原块头。

则能够成为新的块头位置。

参考代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
struct Node {
  int pre, nxt, v;
}a[N];
vector<int> head, nxt_head;

int main() {
  ios::sync_with_stdio(false);
  int n; cin >> n;
  a[0].v = a[n + 1].v = -1;
  a[0].nxt = 1;
  a[n + 1].pre = n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].v;
    a[i].pre = i - 1;
    a[i].nxt = i + 1;
    if (a[i].v != a[i - 1].v) head.push_back(i);
  }
  while(head.size()) {
    nxt_head.clear();
    for (int id : head) {
      cout << id << " ";
      Node& node = a[id];
      a[node.pre].nxt = node.nxt;
      a[node.nxt].pre = node.pre;
      if (node.v == a[node.nxt].v && node.v != a[node.pre].v)
        nxt_head.push_back(node.nxt);
    }
    cout << endl;
    swap(head, nxt_head);
  }
  return 0;
}

Senior

廊桥分配

参考代码

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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5+5;
struct Airline {
  int st, ed, nxt, vis;
  bool operator < (const Airline& other) const {
    return (st < other.st) || (st == other.st && ed < other.ed);
  }
};
struct Airport {
  Airline airline[N];
  vector<int> ans;
  set<pii> st;
  void link(int m) {
    st.clear();
    for (int i = 1; i <= m; i++) st.insert({airline[i].st, i});
    for (int i = 1; i <= m; i++) {
      if (airline[i].vis) continue;
      int current = i;
      while (true) {
        airline[current].vis = 1;
        st.erase({airline[current].st, current});
        const auto& it = st.upper_bound({airline[current].ed, 0});
        if (it != st.end()) {
          airline[current].nxt = (*it).second;
          current = (*it).second;
          st.erase(it);
        } else break;
      }
    }
  }
  void solve(int n, int m) {
    sort(airline + 1, airline + 1 + m);
    link(m);
    ans = vector<int>(n + 1);
    int current = 1;
    for (int i = 1; i <= n; i++) {
      int x = current >= m ? 0 : current;
      ans[i] = ans[i - 1];
      while (x) {
        ans[i]++;
        airline[x].vis = 2;
        x = airline[x].nxt;
      }
      while(current <= m && airline[current].vis == 2) current++;
    }
  }
}port[2];

int main() {
  ios::sync_with_stdio(false);
  int n, m1, m2; cin >> n >> m1 >> m2;
  for (int i = 1; i <= m1; i++) {
    auto& airline = port[0].airline[i];
    cin >> airline.st >> airline.ed;
  }
  for (int i = 1; i <= m2; i++) {
    auto& airline = port[1].airline[i];
    cin >> airline.st >> airline.ed;
  }
  port[0].solve(n, m1); port[1].solve(n, m2);
  int ans = 0;
  for (int i = 0; i <= n; i++)
    ans = max(ans, port[0].ans[i] + port[1].ans[n - i]);
  cout << ans << 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
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505;
const int MOD = 1e9+7;
ll astarisk[N][N];
ll f[N][N]; // (-), AB, ASB
ll g[N][N]; // AS
ll p[N][N]; // (-), AB
ll q[N][N]; // (-): (), (S), (A), (AS), (SA)

int n, k;
char s[N];

bool left(int i) {return s[i] == '(' || s[i] == '?';}
bool right(int i) {return s[i] == ')' || s[i] == '?';}
bool star(int i) {return s[i] == '*' || s[i] == '?';}
bool bracket(int l, int r) {return left(l) && right(r);}

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> k >> s + 1;
  for (int i = 1; i <= n + 1; i++) astarisk[i][i - 1] = 1;
  for (int i = 1; i <= n; i++) for(int j = i; j <= n; j++) {
    if (star(j) && j - i + 1 <= k) astarisk[i][j] = astarisk[i][j - 1];
  }
  for (int i = n; i >= 1; i--) for (int j = i + 1; j <= n; j++) {
    if (bracket(i, j)) {
      q[i][j] = (astarisk[i + 1][j - 1] + f[i + 1][j - 1]) % MOD;
      for (int l = 1; l <= min(k, j - i - 2); l++) {
        q[i][j] = (q[i][j] + astarisk[i + 1][i + l] * f[i + l + 1][j - 1]) % MOD;
        q[i][j] = (q[i][j] + astarisk[j - l][j - 1] * f[i + 1][j - l - 1]) % MOD;
      }
    }
    p[i][j] = q[i][j];
    for (int k = i + 1; k <= j; k++)
      p[i][j] = (p[i][j] + q[i][k] * p[k + 1][j]) % MOD;
    for (int l = 1; l <= min(k, j - i); l++)
      g[i][j] = (g[i][j] + p[i][j - l] * astarisk[j - l + 1][j]) % MOD;
    f[i][j] = p[i][j];
    for (int k = i + 1; k <= j; k++)
      f[i][j] = (f[i][j] + g[i][k] * f[k + 1][j]) % MOD;
  }
  cout << f[1][n] << 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
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int a[N << 1], fir[N], sec[N];
char s[N << 1];
int n;

bool process(int l, int r, int inner) {
  int head = 1, tail = 2 * n - 2, lb = inner - 1, rb = inner + 1;
  for (int i = 1; i < n; i++) {
    if (sec[a[l]] == lb) {s[head++] = 'L'; s[tail--] = 'L'; l++; lb--;}
    else if (sec[a[l]] == rb) {s[head++] = 'L'; s[tail--] = 'R'; l++; rb++;}
    else if (fir[a[r]] == lb) {s[head++] = 'R'; s[tail--] = 'L'; r--; lb--;}
    else if (fir[a[r]] == rb) {s[head++] = 'R'; s[tail--] = 'R'; r--; rb++;}
    else return false;
  }
  return true;
}

int main() {
  int T; scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    memset(fir, 0, (n + 1) * sizeof(int));
    for (int i = 1; i <= 2 * n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= 2 * n; i++) {
      if (!fir[a[i]]) fir[a[i]] = i;
      else sec[a[i]] = i;
    }
    s[2 * n - 1] = 'L'; s[2 * n] = '\0';
    s[0] = 'L'; if (process(2, 2 * n, sec[a[1]])) {printf("%s\n", s); continue;}
    s[0] = 'R'; if (process(1, 2 * n - 1, fir[a[2 * n]])) {printf("%s\n", s); continue;}
    puts("-1");
  }
  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
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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 505;
const int K = 55;

struct Node{
  int x, y;
  ll dis;
  bool operator < (const Node& other) const {
    return dis > other.dis;
  }
};

int v[N][N], h[N][N];
pii entry[N << 2], point[K];
vector<pii> start[K];
ll G[K][K], dis[N][N], f[N][N];

int n, m;

void dijkstra(int s) {
  priority_queue<Node> pq;
  for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) dis[i][j] = INF;
  for (auto& p : start[s]) {
    dis[p.first][p.second] = 0;
    pq.push({p.first, p.second, 0});
  }
  while (!pq.empty()) {
    Node cur = pq.top(); pq.pop();
    if (cur.dis > dis[cur.x][cur.y]) continue;
    if (cur.x > 0) {
      Node nxt = Node({cur.x - 1, cur.y, cur.dis + h[cur.x][cur.y]});
      if (nxt.dis < dis[nxt.x][nxt.y]) {
        dis[nxt.x][nxt.y] = nxt.dis;
        pq.push(nxt);
      }
    }
    if (cur.x < n) {
      Node nxt = Node({cur.x + 1, cur.y, cur.dis + h[cur.x + 1][cur.y]});
      if (nxt.dis < dis[nxt.x][nxt.y]) {
        dis[nxt.x][nxt.y] = nxt.dis;
        pq.push(nxt);
      }
    }
    if (cur.y > 0) {
      Node nxt = Node({cur.x, cur.y - 1, cur.dis + v[cur.x][cur.y]});
      if (nxt.dis < dis[nxt.x][nxt.y]) {
        dis[nxt.x][nxt.y] = nxt.dis;
        pq.push(nxt);
      }
    }
    if (cur.y < m) {
      Node nxt = Node({cur.x, cur.y + 1, cur.dis + v[cur.x][cur.y + 1]});
      if (nxt.dis < dis[nxt.x][nxt.y]) {
        dis[nxt.x][nxt.y] = nxt.dis;
        pq.push(nxt);
      }
    }
  }
}

ll dp(int l, int r) {
  if (l > r) return 0;
  if (f[l][r] != -1) return f[l][r];
  if (l + 1 == r) return f[l][r] = G[l][r];
  f[l][r] = INF;
  for (int k = l + 1; k <= r; k += 2)
    f[l][r] = min(f[l][r], G[l][k] + dp(l + 1, k - 1) + dp(k + 1, r));
  return f[l][r];
}

int main() {
  int T;
  scanf("%d%d%d", &n, &m, &T);
  for (int i = 1; i < n; i++) for (int j = 1; j <= m; j++) scanf("%d", &v[i][j]);
  for (int i = 1; i <= n; i++) for (int j = 1; j < m; j++) scanf("%d", &h[i][j]);
  for (int i = 0; i < m; i++) entry[i] = {0, i};
  for (int i = m; i < m + n; i++) entry[i] = {i - m, m};
  for (int i = m + n; i < 2 * m + n; i++) entry[i] = {n, 2 * m + n - i};
  for (int i = 2 * m + n; i < 2 * (m + n); i++) entry[i] = {2 * m + 2 * n - i, 0};
  while (T--) {
    int k; scanf("%d", &k);
    for (int i = 0, x; i < k; i++) {
      scanf("%d%d%d", &x, &point[i].first, &point[i].second);
      if (point[i].first <= m) v[0][point[i].first] = x;
      else if (point[i].first <= m + n) h[point[i].first - m][m] = x;
      else if (point[i].first <= 2 * m + n) v[n][2 * m + n - point[i].first + 1] = x;
      else h[2 * (m + n) - point[i].first + 1][0] = x;  
    }
    sort(point, point + k);
    int source = 0;
    for (int i = 1; i < k; i++) 
      if (point[i].second != point[i - 1].second) {
        start[source].clear();
        for (int j = point[i - 1].first; j < point[i].first; j++)
          start[source].push_back(entry[j]);
        source++;
      }
    if (point[0].second != point[k - 1].second) {
      start[source].clear();
      for (int j = point[k - 1].first; j < 2 * (n + m); j++)
        start[source].push_back(entry[j]);
      for (int j = 0; j < point[0].first; j++) 
        start[source].push_back(entry[j]);
      source++;
    }
    for (int i = 0; i < source - 1; i++) {
      dijkstra(i);
      for (int j = i + 1; j < source; j++) {
        ll d = INF;
        for (auto& p : start[j]) d = min(d, dis[p.first][p.second]);
        G[i][j] = G[j][i] = d;
      }
    }
    memset(f, -1, sizeof(f));
    printf("%lld\n", dp(0, source - 1));
    for (int i = 0; i <= m; i++) v[0][i] = v[n][i] = 0;
    for (int i = 0; i <= n; i++) h[i][0] = h[i][m] = 0;
  }
  return 0;
}