CSP-S 卷

1  #include <iostream>
2  #include <cmath>
3  #include <vector>
4  #include <algorithm>
5  using namespace std;
6 
7  long long solve1(int n) {
8      vector<bool> p(n+1, true);
9      vector<long long> f(n+1, 0), g(n+1, 0);
10      f[1] = 1;
11      for (int i = 2; i * i <= n; i++) {
12          if (p[i]) {
13              vector<int> d;
14              for (int k = i; k <= n; k *= i) d.push_back(k);
15              reverse(d.begin(), d.end());
16              for (int k : d) {
17                  for (int j = k; j <= n; j += k) {
18                      if (p[j]) {
19                          p[j] = false;
20                          f[j] = i;
21                          g[j] = k;
22                      }
23                  }
24              }
25          }
26      }
27      for (int i = sqrt(n) + 1; i <= n; i++) {
28          if (p[i]) {
29              f[i] = i;
30              g[i] = i;
31          }
32      }
33      long long sum = 1;
34      for (int i = 2; i <= n; i++) {
35          f[i] = f[i / g[i]] * (g[i] * f[i] - 1) / (f[i] - 1);
36          sum += f[i];
37      }
38      return sum;
39  }
40 
41  long long solve2(int n) {
42      long long sum = 0;
43      for (int i = 1; i <= n; i++) {
44          sum += i * (n / i);
45      }
46      return sum;
47  }
48 
49  int main() {
50      int n;
51      cin >> n;
52      cout << solve1(n) << endl;
53      cout << solve2(n) << endl;
54      return 0;
55  }

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

1  #include <vector>
2  #include <algorithm>
3  #include <iostream>
4 
5  using namespace std;
6 
7  bool f0(vector<int>& a, int m, int k) {
8      int s = 0;
9      for (int i = 0, j = 0; i < a.size(); i++) {
10          while (a[i] - a[j] > m) j++;
11          s += i - j;
12      }
13      return s >= k;
14  }
15 
16  int f(vector<int>& a, int k) {
17      sort(a.begin(), a.end());
18 
19      int g = 0;
20      int h = a.back() - a[0];
21      while (g < h) {
22          int m = g + (h - g) / 2;
23          if (f0(a, m, k)) {
24              h = m;
25          } else {
26              g = m + 1;
27          }
28      }
29 
30      return g;
31  }
32 
33  int main() {
34      int n, k;
35      cin >> n >> k;
36      vector<int> a(n, 0);
37      for(int i = 0; i < n; i++) {
38          cin >> a[i];
39      }
40      cout<< f(a, k) << endl;
41      return 0;
42  }

假设输入总是合法的，且 $|a[i]|\le 10^8$、$n\le 10000$ 和 $1\le k\le \frac{n(n-1)}{2}$，完成下面的判断题和单选题。

1  #include <iostream>
2  using namespace std;
3 
4  const int N = 1000;
5  int c[N];
6 
7  int logic(int x, int y) {
8      return (x & y) ^ ((x ^ y) | (~x & y));
9  }
10  void generate(int a, int b, int *c) {
11      for (int i = 0; i < b; i++) {
12          c[i] = logic(a, i) % (b + 1);
13      }
14  }
15  void recursion(int depth, int *arr, int size) {
16      if (depth <= 0 || size <= 1) return;
17      int pivot = arr[0];
18      int i = 0, j = size - 1;
19      while (i <= j) {
20          while (arr[i] < pivot) i++;
21          while (arr[j] > pivot) j--;
22          if (i <= j) {
23              int temp = arr[i];
24              arr[i] = arr[j];
25              arr[j] = temp;
26              i++; j--;
27          }
28      }
29      recursion(depth - 1, arr, j + 1);
30      recursion(depth - 1, arr + i, size - i);
31  }
32 
33  int main() {
34      int a, b, d;
35      cin >> a >> b >> d;
36      generate(a, b, c);
37      recursion(d, c, b);
38      for (int i = 0; i < b; ++i) cout << c[i] << " ";
39      cout << endl;
40  }

1   #include <iostream>
2  #include <string>
3  using namespace std;
4 
5  const int P = 998244353, N = 1e4+10, M = 20;
6  int n, m;
7  string s;
8  int dp[1<<M];
9 
10  int solve() {
11      dp[0] = 1;
12      for (int i = 0; i < n; ++i) {
13          for (int j = (1<<(m-1))-1; j >= 0; --j) {
14              int k = (j<<1)|(s[i]-'0');
15              if (j != 0 || s[i] == '1')
16                  dp[k] = (dp[k] + dp[j]) % P;
17          }
18      }
19      int ans = 0;
20      for (int i = 0; i < (1<<m); ++i) {
21          ans = (ans + 1ll * i * dp[i]) % P;
22      }
23      return ans;
24  }
25  int solve2() {
26      int ans = 0;
27      for (int i = 0; i < (1<<n); ++i) {
28          int cnt = 0;
29          int num = 0;
30          for (int j = 0; j < n; ++j) {
31              if (i & (1<<j)) {
32                  num = num * 2 + (s[j]-'0');
33                  cnt++;
34              }
35          }
36          if (cnt <= m) (ans += num) %= P;
37      }
38      return ans;
39  }
40 
41  int main() {
42      cin >> n >> m;
43      cin >> s;
44      if (n <= 20) {
45          cout << solve2() << endl;
46      }
47      cout << solve() << endl;
48      return 0;
49  }

1   #include <iostream>
2  #include <cstring>
3  #include <algorithm>
4  using namespace std;
5 
6  const int maxn = 1000000+5;
7  const int P1 = 998244353, P2 = 1000000007;
8  const int B1 = 2, B2 = 31;
9  const int K1 = 0, K2 = 13;
10 
11  typedef long long ll;
12 
13  int n;
14  bool p[maxn];
15  int p1[maxn], p2[maxn];
16 
17  struct H {
18      int h1, h2, l;
19      H(bool b = false) {
20          h1 = b + K1;
21          h2 = b + K2;
22          l = 1;
23      }
24      H operator + (const H & h) const {
25          H hh;
26          hh.l = l + h.l;
27          hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;
28          hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;
29          return hh;
30      }
31      bool operator == (const H & h) const {
32          return l == h.l && h1 == h.h1 && h2 == h.h2;
33      }
34      bool operator < (const H & h) const {
35          if (l != h.l) return l < h.l;
36          else if (h1 != h.h1) return h1 < h.h1;
37          else return h2 < h.h2;
38      }
39  } h[maxn];
40 
41  void init() {
42      memset(p, 1, sizeof(p));
43      p[0] = p[1] = false;
44      p1[0] = p2[0] = 1;
45      for (int i = 1; i <= n; ++i) {
46          p1[i] = (1ll * B1 * p1[i-1]) % P1;
47          p2[i] = (1ll * B2 * p2[i-1]) % P2;
48          if (!p[i]) continue;
49          for (int j = 2 * i; j <= n; j += i) {
50              p[j] = false;
51          }
52      }
53  }
54 
55  int solve() {
56      for (int i = n; i; --i) {
57          h[i] = H(p[i]);
58          if (2 * i + 1 <= n) {
59              h[i] = h[2 * i] + h[i] + h[2 * i + 1];
60          } else if (2 * i <= n) {
61              h[i] = h[2 * i] + h[i];
62          }
63      }
64      cout << h[1].h1 << endl;
65      sort(h + 1, h + n + 1);
66      int m = unique(h + 1, h + n + 1) - (h + 1);
67      return m;
68  }
69 
70  int main() {
71      cin >> n;
72      init();
73      cout << solve() << endl;
74  }

1  #include <algorithm>
2  #include <cstdio>
3  #include <cstring>
4  bool flag[27];
5  int n;
6  int p[27];
7  int ans = 0;
8  void dfs(int k) {
9      if (k == n + 1){
10          ++ ans;
11          return;
12      }
13      for (int i = 1; i <= n; ++i) {
14          if (flag[i]) continue;
15          if (k > 1 && i == p[k - 1] + 1) continue;
16          p[k] = i;
17          flag[i] = true;
18          dfs(k + 1);
19          flag[i] = false;
20      }
21      return;
22  }
23  int main() {
24      scanf("%d", &n);
25      dfs(1);
26      printf("%d\n", ans);
27      return 0;
28  }

1  #include <algorithm>
2  #include <cstdio>
3  #include <cstring>
4  #define ll long long
5  int cnt_broken = 0;
6  int cnt_check = 0;
7  int n, k;
8  inline bool check(int h) {
9      printf("now check:%d\n", h);
10      ++cnt_check;
11      if (cnt_broken == 2) {
12          printf("You have no egg!\n");
13          return false;
14      }
15      if (h >= k) {
16          ++cnt_broken;
17          return true;
18      } else {
19          return false;
20      }
21  }
22  inline bool assert_ans(int h) {
23      if (h == k) {
24          printf("You are Right using %d checks\n", cnt_check);
25          return true;
26      } else {
27          printf("Wrong answer!\n");
28          return false;
29      }
30  }
31  inline void guess1(int n) {
32      for (int i = 1; i <= n; ++i) {
33          if (check(i)) {
34              assert_ans(i);
35              return;
36          }
37      }
38  }
39  inline void guess2(int n) {
40      int w = 0;
41      for (w = 1; w * (w + 1) / 2 < n; ++w)
42      ;
43      for (int ti = w, nh = w;; --ti, nh += ti, nh = std::min(nh, n)) {
44          if (check(nh)) {
45              for (int j = nh - ti + 1; j < nh; ++j) {
46                  if (check(j)) {
47                      assert_ans(j);
48                      return;
49                  }
50              }
51              assert_ans(nh);
52              return;
53          }
54      }
55  }
56  int main() {
57      scanf("%d%d", &n, &k);
58      int t;
59      scanf("%d", &t);
60      if (t == 1) {
61          guess1(n);
62      } else {
63          guess2(n);
64      }
65      return 0;
66  }

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

1  #include <iostream>
2  using namespace std;
3 
4  const int maxn = 1000;
5  int n;
6  int fa[maxn], cnt[maxn];
7 
8  int getRoot(int v) {
9      if (fa[v] == v) return v;
10      return getRoot(fa[v]);
11  }
12 
13  int main() {
14      cin >> n;
15      for (int i = 0; i < n; ++i) {
16          fa[i] = i;
17          cnt[i] = 1;
18      }
19      int ans = 0;
20      for (int i = 0; i < n - 1; ++i) {
21          int a, b, x, y;
22          cin >> a >> b;
23          x = getRoot(a);
24          y = getRoot(b);
25          ans += cnt[x] * cnt[y];
26          fa[x] = y;
27          cnt[y] += cnt[x];
28      }
29      cout << ans << endl;
30      return 0;
31  }

1  #include <iostream>
2  #include <string>
3  using namespace std;
4 
5  char base[64];
6  char table[256];
7 
8  void init()
9  {
10      for (int i = 0; i < 26; i++) base[i] = 'A' + i;
11      for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;
12      for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;
13      base[62] = '+', base[63] = '/';
14 
15      for (int i = 0; i < 256; i++) table[i] = 0xff;
16      for (int i = 0; i < 64; i++) table[base[i]] = i;
17      table['='] = 0;
18  }
19 
20  string encode(string str)
21  {
22      string ret;
23      int i;
24      for (i = 0; i + 3 <= str.size(); i += 3) {
25          ret += base[str[i] >> 2];
26          ret += base[(str[i] & 0x03) << 4 | str[i + 1] >> 4];
27          ret += base[(str[i + 1] & 0x0f) << 2 | str[i + 2] >> 6];
28          ret += base[str[i + 2] & 0x3f];
29      }
30      if (i < str.size()) {
31          ret += base[str[i] >> 2];
32          if (i + 1 == str.size()) {
33              ret += base[(str[i] & 0x03) << 4];
34              ret += "==";
35          }
36          else {
37              ret += base[(str[i] & 0x03) << 4 | str[i + 1] >> 4];
38              ret += base[(str[i + 1] & 0x0f) << 2];
39              ret += "=";
40          }
41      }
42      return ret;
43  }
44 
45  string decode(string str)
46  {
47      string ret;
48      int i;
49      for (i = 0; i < str.size(); i += 4) {
50          ret += table[str[i]] << 2 | table[str[i + 1]] >> 4;
51          if (str[i + 2] != '=')
52              ret += (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;
53          if (str[i + 3] != '=')
54              ret += table[str[i + 2]] << 6 | table[str[i + 3]];
55      }
56      return ret;
57  }
58 
59  int main()
60  {
61      init();
62      cout << int(table[0]) << endl;
63 
64      int opt;
65      string str;
66      cin >> opt >> str;
67      cout << (opt ? decode(str) : encode(str)) << endl;
68      return 0;
69  }

假设输入总是合法的（一个整数和一个不含空白字符的字符串，用空格隔开），完成下面的判断题和单选题。

1  #include <algorithm>
2  #include <cstdio>
3  #include <cstring>
4  #include <vector>
5  #define ll long long
6  int n, m;
7  std::vector<int> k, p;
8  inline int mpow(int x, int k) {
9      int ans = 1;
10      for (; k; k = k >> 1, x = x * x) {
11          if (k & 1)
12          ans = ans * x;
13      }
14      return ans;
15  }
16  std::vector<int> ans1, ans2;
17  int cnt1, cnt2;
18  inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) {
19      if (l > r) {
20          ++cnt;
21          ans.push_back(v);
22          return;
23      }
24      for (int i = 1; i <= m; ++i) {
25          dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
26      }
27      return;
28  }
29  std::vector<int> cntans1;
30  int main() {
31      scanf("%d%d", &n, &m);
32      k.resize(n + 1);
33      p.resize(n + 1);
34      for (int i = 1; i <= n; ++i) {
35          scanf("%d%d", &k[i], &p[i]);
36      }
37      dfs(ans1, cnt1, 1, n >> 1, 0);
38      dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
39      std::sort(ans1.begin(), ans1.end());
40      int newcnt1 = 1;
41      cntans1.push_back(1);
42      for (int i = 1; i < cnt1; ++i) {
43          if (ans1[i] == ans1[newcnt1 - 1]) {
44              ++cntans1[newcnt1 - 1];
45          } else {
46              ans1[newcnt1++] = ans1[i];
47              cntans1.push_back(1);
48          }
49      }
50      cnt1 = newcnt1;
51      std::sort(ans2.begin(), ans2.end());
52      int las = 0;
53      ll ans = 0;
54      for (int i = cnt2 - 1; i >= 0; --i) {
55          for (; las < cnt1 && ans1[las] + ans2[i] < 0; ++las)
56          ;
57          if (las < cnt1 && ans1[las] + ans2[i] == 0)
58          ans += cntans1[las];
59      }
60      printf("%lld\n", ans);
61      return 0;
62  }