hpu萌新训练赛（三）

集合
直接埃氏筛，边筛边合并就行。留意先 ans = b - a + 1 然后再计算。 分别是 j 和 j - i 这两个数来举行计算。
代码

1. #include <bits/stdc++.h>
2. using namespace std;
3. using i64 = long long;
4. typedef pair<int, int> PII;
6. bool st[100005];
7. int f[100005];
9. int find(int x)
10. {
11.         if (x != f[x]) f[x] = find(f[x]);
12.         return f[x];
13. }
15. int main()
16. {
17.         int a, b, p; scanf("%d%d%d", &a, &b, &p);
18.         int ans = b - a + 1;
19.         for (int i = a; i <= b; i ++) f[i] = i;
20.         for (int i = 2; i <= b; i ++)
21.         {
22.                 if (!st[i])
23.                 {
24.                         if (i >= p)
25.                         for (int j = i + i; j <= b; j += i) // j 和 j - i 是两个数，他们两个都有 i 这个质数。
26.                         {
27.                                 st[j] = true;
28.                                 if (j - i >= a && find(j) != find(j - i))
29.                                 {
30.                                         int fa = find(j), fb = find(j-i);
31.                                         f[fa] = fb;
32.                                         ans --;
33.                                 }
35.                         }
36.                         else for (int j = i + i; j <= b; j += i)
37.                         st[j] = true;
38.                 }
39.         }
40.        
41.         printf("%d", ans);
42.         return 0;
43. }

复制代码

迷宫寻路
这个是一道非常典型的 dfs 题目。
走过的记得更新为 # 即可。

1. #include <bits/stdc++.h>
2. using namespace std;
3. using i64 = long long;
4. typedef pair<int, int> PII;
5. constexpr int N = 110;
6. char g[N][N];
8. int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
9. int n, m;
10. int ans;
11. int cnt;
12. void dfs(int x, int y)
13. {
14.         if (x == n && y == m)
15.         {
16.                 ans = 1;
17.                 return;
18.         }
19.         g[x][y] = '#';
20.         // // cnt++;
21.         // if (cnt > 1e5)
22.         // {
23.         //         ans = 1e9;
24.         //         return;
25.         // }
26.         for (int i = 0; i < 4; i++)
27.         {
28.                 int ux = x + dx[i], uy = y + dy[i];
29.                 if (ux > n || ux < 1 || uy > m || uy < 1 || g[ux][uy] == '#')
30.                         continue;
31.                 dfs(ux, uy);
32.         }
33. }
35. void solve()
36. {
37.         scanf("%d%d", &n, &m);
38.         for (int i = 1; i <= n; i++)
39.                 for (int j = 1; j <= m; j++)
40.                 {
41.                         char ch;
42.                         cin >> ch;
43.                         g[i][j] = ch;
44.                 }
45.         dfs(1, 1);
46.         if (ans == 1)
47.         {
48.                 printf("Yes");
49.         }
50.         else
51.                 printf("No");
52. }
54. signed main()
55. {
56.         int _ = 1;
57.         // cin >> t;
58.         while (_--)
59.         {
60.                 solve();
61.         }
62.         return 0;
63. }

复制代码

P1464 Function
这个题目用到了影象化搜索的方法。假如我已经计算过 w(a, b, c) 了，那我就把他存下来，如许以后就不需要再举行重复计算了。

1. #include <bits/stdc++.h>
2. using namespace std;
3. using i64 = long long;
4. typedef pair<int, int> PII;
6. int dp[25][25][25];
8. i64 w(i64 a, i64 b, i64 c)
9. {
10.   if (a <= 0 || b <= 0 || c <= 0) return 1;
11.   if (a > 20 || b > 20 || c > 20)
12.   {
13.     if (dp[20][20][20]) return dp[20][20][20];
14.     dp[20][20][20] = w(20, 20, 20);  
15.     return dp[20][20][20];
16.   }
17.   if (a < b && b < c)
18.   {
19.     if (dp[a][b][c]) return dp[a][b][c];
20.     if (!dp[a][b][c - 1]) dp[a][b][c - 1] = w(a, b, c - 1);
21.     if (!dp[a][b - 1][c - 1]) dp[a][b - 1][c - 1] = w(a, b - 1, c - 1);
22.     if (!dp[a][b - 1][c]) dp[a][b - 1][c] = w(a, b - 1, c);
23.     dp[a][b][c] = dp[a][b][c - 1] + dp[a][b - 1][c - 1] - dp[a][b - 1][c];
24.     return dp[a][b][c];
26.   }
27.   if (!dp[a-1][b][c]) dp[a-1][b][c] = w(a - 1, b, c);
28.   if (!dp[a-1][b-1][c]) dp[a-1][b-1][c] = w(a-1, b-1, c);
29.   if (!dp[a-1][b][c-1]) dp[a-1][b][c-1] = w(a-1, b, c-1);
30.   if (!dp[a-1][b-1][c-1]) dp[a-1][b-1][c-1]=w(a - 1, b - 1, c - 1);
31.   return dp[a-1][b][c] + dp[a-1][b-1][c] + dp[a-1][b][c-1] - dp[a-1][b-1][c-1];
32. }
34. int main()
35. {
36.   i64 a, b, c;
37.   while (cin >> a >> b >> c)
38.   {
39.     if (a == -1 && b == -1 && c == -1)
40.     {
41.       return 0;
42.     }
43.     printf("w(%lld, %lld, %lld) = %d\n", a, b, c, w(a, b, c));
44.   }
45.   return 0;
46. }

复制代码

P1009 [NOIP 1998 普及组] 阶乘之和
这个题目用到了一个东西叫做大数，也叫高精度。可以用 c++ 代码实现，也可以用 python 来实现。python 来实现比较简单一点。

1. n = int(input())
2. x = 1
3. ans = 0
4. for i in range(1, n + 1):
5.     x *= i
6.     ans += x
7. print(ans)

复制代码

P1496 火烧赤壁
这个题目用到了离散化和差分。

1. #include <bits/stdc++.h>
2. using i64 = long long;
3. using namespace std;
4. typedef pair<int, int> PII;
6. vector<int> id;
8. int get(int x)
9. {
10.   return lower_bound(id.begin(), id.end(), x) - id.begin() + 1;
11. }
13. /*
14. 把数映射到另一个东西里面
15. */
17. void solve()
18. {
19.   int n;
20.   scanf("%d", &n);
21.   int mmax = -1, mmin = 2e9;
22.   map<i64, i64> c;
23.   vector<PII> cor;
24.   for (int i = 0; i < n; i++)
25.   {
26.     int l, r;
27.     scanf("%d%d", &l, &r);
28.     id.push_back(l);
29.     id.push_back(r);
30.     cor.push_back({l, r});
31.   }
32.   sort(id.begin(), id.end());
33.   id.erase(unique(id.begin(), id.end()), id.end());
35.   for (auto [x, y] : cor)
36.   {
37.     int xx = get(x), yy = get(y);
38.     c[xx] += 1, c[yy] -= 1;
39.     mmin = min(mmin, xx);
40.     mmax = max(mmax, yy);
41.   }
42.   for (int i = mmin; i < mmax; i++)
43.   {
44.     c[i] += c[i - 1];
45.     // cout<<c[i]<<' ';
46.   }
47.   // printf("mmin = %d mmax = %d", mmin, mmax);
48.   int ans = 0,l=0,r=0;
49.   while(r<mmax){
50.     while(l<mmax && c[l]==0)l++,r++;
51.     while(r<mmax && c[r]!=0)r++;
52.     int ln=id[l-1],rn=id[r-1];
53.     ans+=(rn-ln);
54.     // printf("l = %d r = %d\n", l, r);
55.     l = r;
56.   }
57.   cout << ans<<'\n';
58. }
60. signed main()
61. {
62.   int t = 1;
63.   // cin >> t;
64.   while (t--)
65.   {
66.     solve();
67.   }
68.   return 0;
69. }

复制代码

P1469 找筷子
这个题目用到了异或的一个性子，对一个数同时异或两次的话这个数就相当于没有异或。所以直接默认一开始为 0 ，然后不停异或就行了。

1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef pair<int, int> PII;
4. typedef long long i64;
6. void solve()
7. {
8.   int n; scanf("%d", &n);
9.   int x = 0;
10.   for (int i = 0; i < n; i++)
11.   {
12.     int u; scanf("%d", &u);
13.     x ^= u;
14.   }
15.   cout << x;
16. }
18. signed main()
19. {
20.   int t = 1;
21.   // cin >> t;
22.   while (t--)
23.   {
24.     solve();
25.   }
26.   return 0;
27. }

复制代码

P2626 斐波那契数列（升级版）
这个题目的关键在于分解质因数。求斐波那契数列的话，直接递推即可。

1. #include <bits/stdc++.h>
2. using namespace std;
3. using i64 = long long;
4. typedef pair<int, int> PII;
5. constexpr int N = 50 + 10;
6. i64 f[N];
7. const int M = 2147483648;
9. void init()
10. {
11.         f[1] = 1;
12.         f[2] = 1;
13.         for (int i = 3; i <= 48; i++)
14.                 f[i] = f[i - 1] + f[i - 2];
15.         for (int i = 1; i <= 48; i++)
16.         {
17.                 f[i] %= M;
18.         }
19. }
21. void solve()
22. {
23.         init();
24.         // for (int i = 1; i <= 48; i ++)
25.         // {
26.         //         cout << f[i] << "\n";
27.         // }
28.         int n;
29.         cin >> n;
30.         i64 x = f[n];
31.         map<int, int> mp;
32.         int mmin = 2e9;
33.         for (int i = 2; i * i <= x; i++)
34.         {
35.                 if (x % i == 0)
36.                 {
37.                         mmin = min(mmin, i);
38.                         while (x % i == 0)
39.                         {
40.                                 mp[i]++;
41.                                 x /= i;
42.                         }
43.                 }
44.         }
45.         if (x > 1)
46.         {
47.                 mmin = min(mmin, int(x));
48.                 mp[x]++;
49.         }
50.         printf("%lld=", f[n]);
51.         for (auto m : mp)
52.         {
53.                 if (m.first == mmin)
54.                 {
55.                         printf("%d", m.first);
56.                         for (int i = 2; i <= m.second; i++)
57.                                 printf("*%d", m.first);
58.                 }
59.                 else
60.                         for (int i = 1; i <= m.second; i++)
61.                                 printf("*%d", m.first);
62.         }
63. }
65. signed main()
66. {
67.         int _ = 1;
68.         // cin >> t;
69.         while (_--)
70.         {
71.                 solve();
72.         }
73.         return 0;
74. }

复制代码

P3879 [TJOI2010] 阅读明白
这个题目用到了 map<string, vector> 这个 stl 容器。会用这个容器的话然后举行一下去重就能做出来了。

1. #include <bits/stdc++.h>
2. using namespace std;
3. using i64 = long long;
4. typedef pair<int, int> PII;
6. int main()
7. {
8.   int n; scanf("%d", &n);
9.   map<string, vector<int>> mp;
10.   for (int i = 1; i <= n; i ++)
11.   {
12.     int x; scanf("%d", &x);
13.     for (int j = 1; j <= x; j ++)
14.     {
15.       string u; cin >> u;
16.       mp[u].push_back(i);
17.     }
18.   }
19.   int m; scanf("%d", &m);
20.   while (m --)
21.   {
22.     string s; cin >> s;
23.     sort(mp[s].begin(), mp[s].end());
24.     mp[s].erase(unique(mp[s].begin(), mp[s].end()), mp[s].end());
25.     for (int i = 0; i < mp[s].size(); i ++)
26.     {
27.       printf("%d ", mp[s][i]);
28.     }
29.     printf("\n");
30.   }
31.   return 0;
32. }

复制代码

P1024 [NOIP 2001 提高组] 一元三次方程求解
这个题目直接暴力就行了，不外是浮点数暴力，每次加上 0.01 然后判定这个答案行不可。

1. #include <bits/stdc++.h>
2. using namespace std;
3. using i64 = long long;
4. typedef pair<int, int> PII;
6. double a, b, c, d;
8. double ck(double x)
9. {
10.         double l = x - 0.001, r = x + 0.001;
11.         if ((a * pow(r, 3) + b * pow(r, 2) + r*c + d < 0) && (a * pow(l, 3) + b * pow(l, 2) + c * l + d > 0) ||(a * pow(r, 3) + b * pow(r, 2) + r*c + d > 0) && (a * pow(l, 3) + b * pow(l, 2) + c * l + d < 0))
12.                 return true;
13.         return false;
14. }
16. void solve()
17. {
18.         cin >> a >> b >> c >> d;
19.         for (double i = -100.0; i <= 100.0; i += 0.01)
20.         {
21.                 if (ck(i))
22.                 printf("%.2lf ", i);
23.         }
24. }
26. signed main()
27. {
28.         int _ = 1;
29.         // cin >> t;
30.         while (_--)
31.         {
32.                 solve();
33.         }
34.         return 0;
35. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。