CSP-S 卷

完成下面的判断题和单选题。

1  #include <cstdio>
2  using namespace std;
3  int n;
4  int a[100];
5 
6  int main() {
7      scanf("%d", &n);
8      for (int i = 1; i <= n; ++i)
9          scanf("%d", &a[i]);
10      int ans = 1;
11      for (int i = 1; i <= n; ++i) {
12          if (i > 1 && a[i] < a[i - 1])
13              ans = i;
14          while (ans < n && a[i] >= a[ans + 1])
15              ++ans;
16          printf("%d\n", ans);
17      }
18      return 0;
19  }

本题中 $t$ 是 $s$ 的子序列的意思是：从 $s$ 中删去若干个字符，可以得到 $t$；特别的，如果 $s=t$，那么 $t$ 也是 $s$ 的子序列；空串是任何串的子序列。例如，acd 是 abcde 的子序列，acd 是 acd 的子序列，但 adc 不是 abcde 的子序列。

s[x..y] 表示 s[x]...s[y] 共 $y-x+1$ 个字符构成的字符串，若 $x>y$ 则 s[x..y] 是空串。t[x..y] 同理。

1  #include <iostream>
2  #include <string>
3  using namespace std;
4  const int maxl = 202;
5  string s, t;
6  int pre[maxl], suf[maxl];
7 
8  int main() {
9      cin >> s >> t;
10      int slen = s.length(), tlen = t.length();
11      for (int i = 0, j = 0; i < slen; ++i) {
12          if (j < tlen && s[i] == t[j]) ++j;
13          pre[i] = j; // t[0..j-1]是s[0..i]的子序列
14      }
15      for (int i = slen - 1, j = tlen - 1; i >= 0; --i) {
16          if (j >= 0 && s[i] == t[j]) --j;
17          suf[i] = j; // t[j+1..tlen-1]是s[i..slen-1]的子序列
18      }
19      suf[slen] = tlen - 1;
20      int ans = 0;
21      for (int i = 0, j = 0, tmp = 0; i <= slen; ++i) {
22          while (j <= slen && tmp >= suf[j] + 1) ++j;
23          ans = max(ans, j - i - 1);
24          tmp = pre[i];
25      }
26      cout << ans << endl;
27      return 0;
28  }

提示：

t[0..pre[i]-1] 是 s[0..i] 的子序列；

t[suf[i]+1..tlen-1] 是 s[i..slen-1] 的子序列。

1  #include <iostream>
2  using namespace std;
3 
4  int n;
5  int d[1000];
6 
7  int main() {
8      cin >> n;
9      for (int i = 0; i < n; ++i)
10          cin >> d[i];
11      int ans = -1;
12      for (int i = 0; i < n; ++i)
13          for (int j = 0; j < n; ++j)
14              if (d[i] < d[j])
15                  ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
16      cout << ans;
17      return 0;
18  }

假设输入的 $n$ 和 d[i] 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题。

1  #include <iostream>
2  #include <cstdlib>
3  using namespace std;
4 
5  int n;
6  int d[10000];
7 
8  int find(int L, int R, int k) {
9      int x = rand() % (R - L + 1) + L;
10      swap(d[L], d[x]);
11      int a = L + 1, b = R;
12      while (a < b) {
13          while (a < b && d[a] < d[L])
14              ++a;
15          while (a < b && d[b] >= d[L])
16              --b;
17          swap(d[a], d[b]);
18      }
19      if (d[a] < d[L])
20          ++a;
21      if (a - L == k)
22          return d[L];
23      if (a - L < k)
24          return find(a, R, k - (a - L));
25      return find(L + 1, a - 1, k);
26  }
27 
28  int main() {
29      int k;
30      cin >> n;
31      cin >> k;
32      for (int i = 0; i < n; ++i)
33          cin >> d[i];
34      cout << find(0, n - 1, k);
35      return 0;
36  }

假设输入的 $n$、$k$ 和 d[i] 都是不超过 $10000$ 的正整数，且 $k$ 不超过 $n$，并假设 rand() 函数产生的是均匀的随机数，完成下面的判断题和单选题。

1  #include <iostream>
2  #include <queue>
3  using namespace std;
4 
5  const int maxl = 2000000000;
6 
7  class Map {
8      struct item {
9          string key; int value;
10      } d[maxl];
11      int cnt;
12      public:
13      int find(string x) {
14          for (int i = 0; i < cnt; ++i)
15              if (d[i].key == x)
16                  return d[i].value;
17          return -1;
18      }
19      static int end() { return -1; }
20      void insert(string k, int v) {
21          d[cnt].key = k; d[cnt++].value = v;
22      }
23  } s[2];
24 
25  class Queue {
26      string q[maxl];
27      int head, tail;
28      public:
29      void pop() { ++head; }
30      string front() { return q[head + 1]; }
31      bool empty() { return head == tail; }
32      void push(string x) { q[++tail] = x; }
33  } q[2];
34 
35  string st0, st1;
36  int m;
37 
38  string LtoR(string s, int L, int R) {
39      string t = s;
40      char tmp = t[L];
41      for (int i = L; i < R; ++i)
42          t[i] = t[i + 1];
43      t[R] = tmp;
44      return t;
45  }
46 
47  string RtoL(string s, int L, int R) {
48      string t = s;
49      char tmp = t[R];
50      for (int i = R; i > L; --i)
51          t[i] = t[i - 1];
52      t[L] = tmp;
53      return t;
54  }
55 
56  bool check(string st, int p, int step) {
57      if (s[p].find(st) != s[p].end())
58          return false;
59      ++step;
60      if (s[p ^ 1].find(st) == s[p].end()) {
61          s[p].insert(st, step);
62          q[p].push(st);
63          return false;
64      }
65      cout << s[p ^ 1].find(st) + step << endl;
66      return true;
67  }
68 
69  int main() {
70      cin >> st0 >> st1;
71      int len = st0.length();
72      if (len != st1.length()) {
73          cout << -1 << endl;
74          return 0;
75      }
76      if (st0 == st1) {
77          cout << 0 << endl;
78          return 0;
79      }
80      cin >> m;
81      s[0].insert(st0, 0); s[1].insert(st1, 0);
82      q[0].push(st0); q[1].push(st1);
83      for (int p = 0;
84          !(q[0].empty() && q[1].empty());
85          p ^= 1) {
86          string st = q[p].front(); q[p].pop();
87          int step = s[p].find(st);
88          if ((p == 0 &&
89              (check(LtoR(st, m, len - 1), p, step) ||
90              check(RtoL(st, 0, m), p, step)))
91              ||
92              (p == 1 &&
93              (check(LtoR(st, 0, m), p, step) ||
94              check(RtoL(st, m, len - 1), p, step))))
95              return 0;
96      }
97      cout << -1 << endl;
98      return 0;
99  }

完成下面的判断题和单选题。

1  #include <iostream>
2  #include <cmath>
3  using namespace std;
4 
5  const double r = acos(0.5);
6 
7  int a1, b1, c1, d1;
8  int a2, b2, c2, d2;
9 
10  inline int sq(const int x) { return x * x; }
11  inline int cu(const int x) { return x * x * x; }
12 
13  int main()
14  {
15      cout.flags(ios::fixed);
16      cout.precision(4);
17 
18      cin >> a1 >> b1 >> c1 >> d1;
19      cin >> a2 >> b2 >> c2 >> d2;
20 
21      int t = sq(a1 - a2) + sq(b1 - b2) + sq(c1 - c2);
22 
23      if (t <= sq(d2 - d1)) cout << cu(min(d1, d2)) * r * 4;
24      else if (t >= sq(d2 + d1)) cout << 0;
25      else {
26          double x = d1 - (sq(d1) - sq(d2) + t) / sqrt(t) / 2;
27          double y = d2 - (sq(d2) - sq(d1) + t) / sqrt(t) / 2;
28          cout << (x * x * (3 * d1 - x) + y * y * (3 * d2 - y)) * r;
29      }
30      cout << endl;
31      return 0;
32  }

假设输入的所有数的绝对值都不超过 $1000$，完成下面的判断题和单选题。

1  #include <algorithm>
2  #include <iostream>
3  using namespace std;
4 
5  int n, a[1005];
6 
7  struct Node
8  {
9      int h, j, m, w;
10 
11      Node(const int _h, const int _j, const int _m, const int _w):
12          h(_h), j(_j), m(_m), w(_w)
13      { }
14 
15      Node operator+(const Node &o) const
16      {
17          return Node(
18              max(h, w + o.h),
19              max(max(j, o.j), m + o.h),
20              max(m + o.w, o.m),
21              w + o.w);
22      }
23  };
24 
25  Node solve1(int h, int m)
26  {
27      if (h > m)
28          return Node(-1, -1, -1, -1);
29      if (h == m)
30          return Node(max(a[h], 0), max(a[h], 0), max(a[h], 0), a[h]);
31      int j = (h + m) >> 1;
32      return solve1(h, j) + solve1(j + 1, m);
33  }
34 
35  int solve2(int h, int m)
36  {
37      if (h > m)
38          return -1;
39      if (h == m)
40          return max(a[h], 0);
41      int j = (h + m) >> 1;
42      int wh = 0, wm = 0;
43      int wht = 0, wmt = 0;
44      for (int i = j; i >= h; i--) {
45          wht += a[i];
46          wh = max(wh, wht);
47      }
48      for (int i = j + 1; i <= m; i++) {
49          wmt += a[i];
50          wm = max(wm, wmt);
51      }
52      return max(max(solve2(h, j), solve2(j + 1, m)), wh + wm);
53  }
54 
55  int main()
56  {
57      cin >> n;
58      for (int i = 1; i <= n; i++) cin >> a[i];
59      cout << solve1(1, n).j << endl;
60      cout << solve2(1, n) << endl;
61      return 0;
62  }

假设输入的所有数的绝对值都不超过 $1000$，完成下面的判断题和单选题。

1  #include <iostream>
2  #include <string>
3  #include <vector>
4 
5  using namespace std;
6 
7  int f(const string &s, const string &t)
8  {
9      int n = s.length(), m = t.length();
10 
11      vector<int> shift(128, m + 1);
12 
13      int i, j;
14 
15      for (j = 0; j < m; j++)
16          shift[t[j]] = m - j;
17 
18      for (i = 0; i <= n - m; i += shift[s[i + m]]) {
19          j = 0;
20          while (j < m && s[i + j] == t[j]) j++;
21          if (j == m) return i;
22      }
23 
24      return -1;
25  }
26 
27  int main()
28  {
29      string a, b;
30      cin >> a >> b;
31      cout << f(a, b) << endl;
32      return 0;
33  }

假设输入字符串由 ASCII 可见字符组成，完成下面的判断题和单选题。

1  #include <iostream>
2 
3  using namespace std;
4 
5  const int MAXN = 105;
6 
7  int n, m, k, val[MAXN];
8  int temp[MAXN], cnt[MAXN];
9 
10  void init()
11  {
12      cin >> n >> k;
13      for (int i = 0; i < n; i++) cin >> val[i];
14      int maximum = val[0];
15      for (int i = 1; i < n; i++)
16          if (val[i] > maximum) maximum = val[i];
17      m = 1;
18      while (maximum >= k) {
19          maximum /= k;
20          m++;
21      }
22  }
23 
24  void solve()
25  {
26      int base = 1;
27      for (int i = 0; i < m; i++) {
28          for (int j = 0; j < k; j++) cnt[j] = 0;
29          for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;
30          for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];
31          for (int j = n - 1; j >= 0; j--) {
32              temp[cnt[val[j] / base % k] - 1] = val[j];
33              cnt[val[j] / base % k]--;
34          }
35          for (int j = 0; j < n; j++) val[j] = temp[j];
36          base *= k;
37      }
38  }
39 
40  int main()
41  {
42      init();
43      solve();
44      for (int i = 0; i < n; i++) cout << val[i] << ' ';
45      cout << endl;
46      return 0;
47  }

假设输入的 $n$ 为不大于 $100$ 的正整数，$k$ 为不小于 $2$ 且不大于 $100$ 的正整数，val[i] 在 int 表示范围内，完成下面的判断题和单选题。

1  #include <iostream>
2  #include <algorithm>
3 
4  using namespace std;
5 
6  const int MAXL = 1000;
7 
8  int n, k, ans[MAXL];
9 
10  int main(void)
11  {
12      cin >> n >> k;
13      if (!n) cout << 0 << endl;
14      else
15      {
16          int m = 0;
17          while (n)
18          {
19              ans[m++] = (n % (-k) + k) % k;
20              n = (ans[m - 1] - n) / k;
21          }
22          for (int i = m - 1; i >= 0; i--)
23              cout << char(ans[i] >= 10 ?
24          ans[i] + 'A' - 10 :
25          ans[i] + '0');
26          cout << endl;
27      }
28      return 0;
29  }

假设输入的 $n$ 在 int 范围内，$k$ 为不小于 $2$ 且不大于 $36$ 的正整数，完成下面的判断题和单选题。

1  #include <iostream>
2  using namespace std;
3 
4  unsigned short f(unsigned short x) {
5      x ^= x << 6;
6      x ^= x >> 8;
7      return x;
8  }
9 
10  int main() {
11      unsigned short x;
12      cin >> x;
13      unsigned short y = f(x);
14      cout << y <<endl;
15      return 0;
16  }

假设输入的 $x$ 是不超过 $65535$ 的自然数，完成下面的判断题和单选题。