康复训练_普及组

Posted on Edited on

康复训练_普及组

1998年

三连击

普通模拟

阶乘和

高精度

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
struct bigint
{
   int num[N], len;
}a, b, c;

inline void Read(int x, bigint &t)
{
   string s = to_string(x);
   t.len = s.length();
   for (int i = 0; i < t.len; ++ i)
      t.num[i] = s[i] - '0';
   reverse(t.num, t.num + t.len);
   return;
}

inline void Plus(bigint &a, bigint &b, big int &c)
{
   c.len = max(a.len, b.len);
   for (int i = 0; i < c.len; ++ i)
      c.num[i] = a.num[i] + b.num[i];
   for (int i = 0; i < c.len; ++ i)
      if (c.num[i] > 9)
         c.num[i + 1] += 1, c.num[i] -= 10;
   if (c.num[c.len + 1]) ++ c.len;
   return;
}

inline void Minus(bigint &a, bigint &b, big int &c)
{
   c.len = a.len;
   for (int i = 0; i < c.len; ++ i)
      c.num[i] = a.num[i] - b.num[i];
   for (int i = 0; i < c.len; ++ i)
      if (c.num[i] < 0)
         c.num[i + 1] -= 1, c.num[i] += 10;
   while (c.len > 1 && c.num[c.len - 1] == 0) -- c.len;
   return;
}

inline void Multi(bigint &a, int b, bigint &c)
{
   c.len = a.len;
   for (int i = 0; i < c.len; ++ i)
      c.num[i] = a.num[i] * b;
   for (int i = 0; i < c.len; ++ i)
   {
      c.num[i + 1] += c.num[i] / 10;
      c.num[i] %= 10;
      if (c.num[i + 1] && i + 1 == c.len) ++ c.len;
   }
   return;
}

inline void Multi(bigint &a, bigint &b, bigint &c)
{
   c.len = a.len + b.len;
   for (int i = 0; i < a.len; ++ i)
   for (int j = 0; j < b.len; ++ j)
      c.num[i + j] += a.num[i] * b.num[j];
   for (int i = 0; i < c.len; ++ i)
      if (c.num[i] > 9)
         c.num[i + 1] += (c.num[i] / 10), c.num[i] %= 10;
   while (c.num[c.len - 1] == 0 && c.len > 1) -- c.len;
   return;
}//高精度乘高精

inline int Divide(bigint &a, int b, bigint &c)
{
   c.len = a.len;
   ll t = 0;
   for (int i = c.len - 1; i >= 0; -- i)
   {
      t = t * 10 + a.num[i];
      c.num[i] = t / b;
      t %= b;
   }
   while (c.len > 1 && c.num[c.len - 1] == 0) -- c.len;
   return t;
}

t是余数，会爆int

幂次方

基本构造

观察题目发现最终结果只能是"2"或者"2(0)" 所以考虑在dfs边界设置为0和1，表示\(2^0, 2^1\) 什么时候需要带括号呢？1 = "2(0)"

联想快速幂:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ll ksm(ll a, ll b, int mod)
{
   ll res = 1ll;
   for (; b; b >>= 1)
   {
      if (b & 1) res = res * a % mod;
      a = a * a % mod;
      b >>= 1;
   }
   return res;
}

ll ksm(ll a, ll b, int mod)
{
   if (! b) return 1ll;
   if (b & 1) return ksm(a, b - 1, mod) * a % mod;
   ll res = ksm(a, b >> 1, mod);
   return res * res % mod;
}

1999

Cantor 表

找规律的一题，先找出该项在杨辉三角里面的哪一行，然后判断奇偶

奇：从左下到右上递增, 偶：从右上到左下递增

找到行首，接下来一个for就可以

回文数

这是一道高精+模拟的一个思维好题

有几个坑点，第一个是传址调用，新建局部变量数组，要清空，第二个是传值调用尽量从a开始，而不是从a+1，第三个是十六进制，d[i] = tmp - 10 + 'A'

不可以写d[i] = tmp - 10 + '0' + 'A'从ascil的角度来看，多了48

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
inline void dfs(int t, char *a)
{
   char b[N]; strcpy(b, a);
   reverse(b, b + strlen(b));
   // printf("\nthis is %d times:\n", t);
   // printf("a:%s\tb:%s\n", a, b);
   if (strcmp(a, b) == 0) return (void)(flag2 = t - 1);
   if (t > LIM) return (void)(flag1 = 1);
   if (flag1 || flag2) return;
   int c[N], len = strlen(a);
   memset(c, 0, sizeof c);
   for (int i = 0; i < len; ++ i)
   {
      int tmp1, tmp2;
      if (a[i] <= '9' && a[i] >= '0') tmp1 = a[i] - '0';
      else tmp1 = a[i] - 'A' + 10;
      if (b[i] <= '9' && b[i] >= '0') tmp2 = b[i] - '0';
      else tmp2 = b[i] - 'A' + 10;
      c[i] = tmp1 + tmp2;
   }
   for (int i = 0; i < len; ++ i) if (c[i] >= n) c[i + 1] += c[i] / n, c[i] %= n;
   if (c[len]) ++ len;
   // printf ("c:");
   // for (int i = len - 1; i >= 0; -- i) cout << c[i];
   char d[N]; int len2 = len;
   for (int i = 0; i < len; ++ i)
   {
      int tmp = c[-- len2];
      if (tmp <= 9) d[i] = tmp + '0';
      else d[i] = tmp - 10 + 'A';
   }
   return (void)(dfs(t + 1, d));
}

旅行家的预算

贪心加模拟

由于数据量很小，我的做法是，开一个结构体，除了n个油站放进去，起点和终点也塞进去，以距起点的距离为第一关键字排个序

递归边界是，到达终点，

递归过程是，针对于每一个油站可去的范围内，如果下一个比当前油价便宜，那么只需要恰好到达下一站即可，如果下一个比当前贵，那么最优选项就是当前加满再去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline void dfs(int t, double money, double h)
{
   // printf("t = %d, money = %.2lf, h = %.2lf\n", t, money, h);
   if (t == n) return (void)(flag = 1, res = min(res, money));
   for (int i = t + 1; i <= n; ++ i)
   {
      double s = (a[i].d - a[t].d) / d_2;
      if (s > c) break;
      if (h >= s) dfs(i, money, h - s);
      else
      {
         if (a[i].p >= a[t].p)
            dfs(i, money + (c - h) * a[t].p, c - s);
         else dfs(i, money + (s - h) * a[t].p, 0.0);
      }
   }
   return;
}

2000

计算器的改良

普通模拟，有点类似栈但不是栈,因为没有括号，没有乘除

我的思路是根据'='分成两段，分别处理,最后整合

考虑针对每一段，每遇到一个特殊符号就处理，减号flag=1，加号不管，也就是flag=0,遇到数字就把上次的符号弹出，处理，然后复原

细节有点多，考虑以下几种情况

3-a=3//-0.000?

a+2a=6//3a=6

5a=5//a=inf?

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
for (int i = 0; i <= pos; ++ i)
{
   if ((s[i] >= 'A' && s[i] <= 'Z') || (s[i] >= 'a' && s[i] <= 'z'))
   {
      x1 = s[i];
      int now = tmp;
      if (now == 0)//系数为1
      {
         if (flag) now = -1, flag = 0;
         else now = 1;
      }
      else
      {
         if (flag) now = -now, flag = 0;
         else now = now;
      }
      l += now;
      tmp = 0;
      continue;
   }
   if (s[i] == '+' || s[i] == '=')
   {
      if (flag == 1) sum1 -= tmp;
      else sum1 += tmp;
      flag = 0;
      tmp = 0;
      continue;
   }
   else if (s[i] == '-')
   {
      if (flag == 1) sum1 -= tmp;
      else sum1 += tmp;
      flag = 1;
      tmp = 0;
      continue;
   }
   else tmp = tmp * 10 + s[i] - '0';
}

乘积最大

一眼区间dp，dfs也可以做，需要高精

由于需要区间操作，所以按照惯例我们都需要预处理一下，把区间转换为字符串就好了

我们设\(f_{i,t}\)表示在前i个数中插入t个乘号可以表示的最大值，由于正常递推无法确定上一次在哪里分割，所以我们改变思路，枚举一个j，即枚举分割点，然后结束了

calc模拟了高精乘过程，maxx是针对两个字符串取最大值，比的时候记得从高位开始比

局部变量里面的数组（结构体)一定要初始化

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
inline void func(int l, int r)
{
   string w = "";
   for (int i = l; i <= r; ++ i)
      w += s[i];
   return w;
}

for (int i = 1; i <= n; ++ i)
for (int j = i; j <= n; ++ j)
   b[i][j] = func(i, j);
inline string calc(string x, string y)
{
   bigint a, b, c;
   memset(a.num, 0, sizeof a.num);
   memset(b.num, 0, sizeof b.num);
   memset(c.num, 0, sizeof c.num);
   a.len = x.size(), b.len = y.size();
   c.len = a.len + b.len;
   for (int i = 0; i < a.len; ++ i) a.num[i] = x[a.len - 1 - i] - '0';
   for (int i = 0; i < b.len; ++ i) b.num[i] = y[b.len - 1 - i] - '0';
   for (int i = 0; i < a.len; ++ i)
   for (int j = 0; j < b.len; ++ j)
      c.num[i + j] += a.num[i] * b.num[j];
   for (int i = 0; i < c.len; ++ i)
      if (c.num[i] > 9)
         c.num[i + 1] += c.num[i] / 10, c.num[i] %= 10;
   while (c.len > 1 && c.num[c.len - 1] == 0) -- c.len;
   string w = "";
   for (int i = c.len - 1; i >= 0; -- i) w += c.num[i] + '0';
   return w;
}

for (int t = 1; t <= k; ++ t)
{
   for (int i = 1; i <= n; ++ i)
   {
      f[i][0] = b[1][i];
      for (int j = 1; j <= i; ++ j)
      {
         string tmp = calc(f[j - 1][t - 1], b[j][i]);
         f[i][t] = maxx(f[i][t], tmp);
      }
      // printf("i: %d, t: %d, f[%d][%d]: %s\n", i, t, i, t, f[i][t].c_str());
   }
}

单词接龙

很工整的dfs,与字符串结合细节较多

题意有几处不清楚的地方：

  1. 单词接龙，单词可以重复使用

  2. 匹配的时候，重合部分不可以和尾巴长度相等，但是重合部分可以和龙头长度相等

a.substr(start, len) 从字符串a的start位置开始，选出len个字符

a.find(str, start)从字符串a的start位置开始，查找str,没有start，默认从头找，找不到返回a.npos(一般都是-1)

普通的find函数无法满足该题需要，考虑如下情况： 

1
2
t: atoucheat, s[i]: tact
w: t, pos: 1
t出现了两次，但我们只需要在后半段，也就是子段可能出现的地方查找就可以了

故int pos = t.find(w, len - 1 - k)

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
inline void dfs(string t, int len)
{
   // printf("this time, t: %s, len: %d\n", t.c_str(), len);
   for (int i = 1; i <= n; ++ i)
   {
      // printf ("t: %s, s[i]: %s\n", t.c_str(), s[i].c_str());
      if (v[i] == 2) continue;
      int slen = s[i].length();
      for (int k = 0; k < slen; ++ k)
      {
         string w = s[i].substr(0, k + 1);
         int pos = t.find(w, len - 1 - k);
         // printf("w: %s, pos: %d\n", w.c_str(), pos);
         if (pos != string::npos && pos + k + 1 == len && w != s[i])
         {
            string p = t.substr(0, len - 1 - k);
            // printf ("i: %d, p: %s, s[i]: %s, pos: %d, k: %d\n", i, p.c_str(), s[i].c_str(), pos, k);
            ++ v[i];
            dfs(p + s[i], len - k - 1 + slen);
            -- v[i];
         }
      }
   }
   return (void)(res = max(res, len));
}
for (int i = 1; i <= n; ++ i)
{
   if (s[i][0] == ch[0])
   {
      ++ v[i];
      dfs(s[i], s[i].length());
      -- v[i];
   }
}

搜索