【逐日一题 | 2025年5.5 ~ 5.11】搜索相干题

   个人主页：Guiat
归属专栏：逐日一题
  

正文
1. 【5.5】P3717 [AHOI2017初中组] cover

   题目链接：https://www.luogu.com.cn/problem/P3717
  【分析】
暴力搜索 + 两点间隔公式，时间复杂度：O(m * n ^ 2)。
【AC_Code】

1. #include <iostream>
2. #include <cmath>
3. #define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
5. using namespace std;
7. bool vis[105][105]; int ans;
9. void solve()
10. {
11.         int n, m, r; cin >> n >> m >> r;
12.         while (m --)
13.         {
14.                 int x, y; cin >> x >> y;
15.                 for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++)
16.                 {
17.                         double dis = sqrt(pow((i - x), 2) + pow((j - y), 2));
18.                         if (dis <= r) vis[i][j] = true;
19.                 }
20.         }
21.         for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) if (vis[i][j]) ans ++;
22.         cout << ans << '\n';
23. }
25. int main()
26. {
27.         IOS int _ = 1;   // cin >> _;
28.         while (_ --) solve();
29.        
30.         return 0;
31. }

复制代码

2. 【5.6】P1897 电梯里的尴尬

   题目链接：https://www.luogu.com.cn/problem/P1897
  【分析】
先读懂题目样例，之后按题意模拟即可，具体看代码。

【AC_Code】

1. #include <iostream>
2. #include <algorithm>
3. #define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
5. using namespace std;
7. const int N = 1e5 + 10; int a[N], now, ans;
9. void solve()
10. {
11.         int n; cin >> n; for (int i = 0; i < n; i ++) cin >> a[i];
12.         sort(a, a + n);
13.         for (int i = 0; i < n; )
14.         {
15.                 int tar = a[i];
16.                 if (tar > now) ans += (tar - now) * 6;
17.                 else if (tar < now) ans += (now - tar) * 4;
18.                 int cnt = 0;
19.                 while (i < n && a[i] == tar) cnt ++, i ++;
20.                 ans += 5; ans += cnt; now = tar;
21.         } ans += now * 4;
22.         cout << ans << '\n';
23. }
25. int main()
26. {
27.         IOS int _ = 1;   // cin >> _;
28.         while (_ --) solve();
29.        
30.         return 0;
31. }

复制代码

3. 【5.7】P2689 东南西北

   题目链接：https://www.luogu.com.cn/problem/P2689
  【分析】
按题意模拟即可，注意逻辑，属于简单题。
【AC_Code】

1. #include <iostream>
2. #define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
4. using namespace std;
6. int ans;
8. void solve()
9. {
10.         int x1, y1, x2, y2, T; cin >> x1 >> y1 >> x2 >> y2 >> T;
11.         while (T --)
12.         {
13.                 char c; cin >> c;
14.                 if (c == 'N' && y1 < y2) y1 ++, ans ++;
15.                 else if (c == 'S' && y1 > y2) y1 --, ans ++;
16.                 else if (c == 'W' && x1 > x2) x1 --, ans ++;
17.                 else if (c == 'E' && x1 < x2) x1 ++, ans ++;
18.                 if (x1 == x2 && y1 == y2) { cout << ans << '\n'; return ; }
19.         }
20.         cout << -1 << '\n';
21. }
23. int main()
24. {
25.         IOS int _ = 1;   // cin >> _;
26.         while (_ --) solve();
27.        
28.         return 0;
29. }

复制代码

4. 【5.8】P1145 约瑟夫

   题目链接：https://www.luogu.com.cn/problem/P1145
  【分析】

pos（删除位置）
4 = (0 + 4) % (2 * 3 - 0)
3 = (4 + 4) % (2 * 3 - 1)
3 = (3 + 4) % (2 * 3 - 2)
=> pos = (pos + m - 1) % (2 * k - i)
【AC_Code】

1. #include <iostream>
2. #define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
4. using namespace std;
6. void solve()
7. {
8.         int k; cin >> k; int m = k + 1;
9.         while (1)
10.         {
11.                 int pos = 0; bool flag = true;
12.                 for (int i = 0; i < k; i ++)
13.                 {
14.                         pos = (pos + m - 1) % (2 * k - i);
15.                         if (pos < k) { flag = false; break; }
16.                 }
17.                 if (flag) { cout << m << '\n'; return ; }
18.                 m ++;
19.         }
20. }
22. int main()
23. {
24.         IOS int _ = 1;   // cin >> _;
25.         while (_ --) solve();
26.        
27.         return 0;
28. }

复制代码

5. 【5.9】P1088 [NOIP 2004 普及组] 火星人

   题目链接：https://www.luogu.com.cn/problem/P1088
  【分析】
相称于一个全排列模版：求输入的整数序列举行 m 次字典序下一个排列的变动。
【AC_Code】

1. #include <iostream>
2. #include <algorithm>
3. #define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
5. using namespace std;
7. const int N = 1e4 + 10; int a[N];
9. void solve()
10. {
11.         int n, m; cin >> n >> m;
12.         for (int i = 0; i < n; i ++) cin >> a[i];
13.         for (int i = 0; i < m; i ++) next_permutation(a, a + n);
14.         for (int i = 0; i < n; i ++) cout << a[i] << ' '; cout << '\n';
15. }
17. int main()
18. {
19.         IOS int _ = 1;   // cin >> _;
20.         while (_ --) solve();
21.        
22.         return 0;
23. }

复制代码

6. 【5.10】P1164 小A点菜

   题目链接：https://www.luogu.com.cn/problem/P1164
  【分析】
01背包的变种，构建二维dp矩阵，f[j]表示前i个菜品恰恰花费j元的方案数，二维可以优化到一维，这里采用二维解法。
【AC_Code】

1. #include <iostream>
2. #define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
4. using namespace std;
6. int a[110], f[110][10010];
8. void solve()
9. {
10.         int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++) cin >> a[i];
11.         for (int i = 0; i <= n; i ++) f[i][0] = 1;
12.         for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++)
13.         {
14.                 f[i][j] += f[i - 1][j];
15.                 if (j >= a[i]) f[i][j] += f[i - 1][j - a[i]];
16.         }
17.         cout << f[n][m] << '\n';
18. }
20. int main()
21. {
22.         IOS int _ = 1;   // cin >> _;
23.         while (_ --) solve();
24.        
25.         return 0;
26. }

复制代码

7. 【5.11】P1019 [NOIP 2000 提高组] 单词接龙

   题目链接：https://www.luogu.com.cn/problem/P1019
  【分析】
考察搜索＋字符串处理。
【AC_Code】

1. #include <iostream>
2. #include <string>
3. #define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
5. using namespace std;
7. string s[25]; int n, vis[25], ans;
9. string check(string s1, string s2)
10. {
11.         for (int i = 1; i < s1.length() && i < s2.length(); i ++)
12.         {
13.                 if (s1.substr(s1.length() - i, i) == s2.substr(0, i))
14.                         return (s1.substr(0, s1.length() - i) + s2);
15.         }
16.         return "0";
17. }
19. void dfs(string drag)
20. {
21.         if (drag.size() > ans) ans = drag.size();
22.         for (int i = 0; i < n; i ++)
23.         {
24.                 if (vis[i] == 2) continue;
25.                 if (check(drag, s[i]) != "0") { vis[i] ++; dfs(check(drag, s[i])); vis[i] --; }
26.         }
27. }
29. void solve()
30. {
31.         cin >> n; for (int i = 0; i < n; i ++) cin >> s[i];
32.         char c; cin >> c;
33.         for (int i = 0; i < n; i ++)
34.         {
35.                 if (s[i][0] == c) { vis[i] ++; dfs(s[i]); vis[i] --; }
36.         }
37.         cout << ans << '\n';
38. }
40. int main()
41. {
42.         IOS int _ = 1;   // cin >> _;
43.         while (_ --) solve();
44.        
45.         return 0;
46. }

复制代码

结语
感谢您的阅读！等候您的一键三连！接待指正！

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

继续阅读请点击广告