👉引言
| 铭记于心 | ||
| 🎉✨🎉我唯一知道的，便是我一无所知🎉✨🎉 |
💖 ❄️我们的算法之路❄️💖
众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs) ，💝宽度优先搜索（bfs） ，💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉
今日主题：希冀OJ考前一刷
👉⭐️第一题💎💎
✨题目
✨思路：
经典背包问题，上暴力递归代码（没想到样例竟然是错的， 吐 ** ）打表
✨代码：
#include<stdio.h> int Max(int a, int b) { if (a > b) return a; else return b; } int n; int proc(int num[], int i, int W) { if (W <= 0 || i == n)return 0; int p1 = proc(num, i + 1, W); if (W >= num[i])return Max(proc(num, i + 1, W - num[i]) + 1, p1); else return p1; } int main() { int num[110] = { 0 }; int W; scanf("%d %d", &W, &n); for (int i = 0; i < n; i++) { scanf("%d", &num[i]); } printf("%d", proc(num, 0, W)); return 0; }
- 打表代码
#include<stdio.h> int Max(int a, int b) { if (a > b) return a; else return b; } int main() { int dp[110][110] = { {0} }; int num[110] = { 0 }; int W, n; scanf("%d %d", &W, &n); for (int i = 0; i < n; i++) { scanf("%d", &num[i]); } for (int i = n - 1; i >= 0; i--) { for (int j = 0; j <= W; j++) { if (j - num[i] >= 0) dp[i][j] = Max(dp[i + 1][j - num[i]] + 1, dp[i + 1][j]); else dp[i][j] = dp[i + 1][j]; } } printf("%d", dp[0][W]); return 0; }
👉⭐️第二题💎💎
✨题目
简单的数论题，判断素数，数据量比较小，不需要素数筛，直接用看sqrt(n)前能不能被整除即可
✨代码：
#include<stdio.h> #include<math.h> char names[11][15]; int n; int Mon[11]; int isZ(int n) { //判断质数 int i; for (i = 2; i <= sqrt(n); i++) { if (n % i == 0) { return 0; } } return 1; } int main() { int n; scanf("%d", &n); int sum = 0; for (int i = 2; i <= n; i++) { if (isZ(i)) sum++; } printf("%d", sum); return 0; }
👉⭐️第三题💎
✨题目
✨思路：
遍历s中的字符，看是否能够再不回溯的情况下在t中找到
✨代码：
#include<stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include<math.h> int main() { char str1[1024], str2[1024]; scanf("%s", str1); scanf("%s", str2); int j = 0, i = 0; while (i < strlen(str1)) { while (j < strlen(str2)) { if (str1[i] == str2[j])break; j++; } if (j == strlen(str2))break; i++; j++; } if (i == strlen(str1))printf("yes"); else printf("no"); return 0; }
👉⭐️第四题💎
✨题目
✨思路：
dp问题，即将一个整数数组加和为两个最接近的整数，可以直接憋状态转移方程 dp[i][r]=max( (dp[i+1][r-num[i]]+num[i]),dp[i+1][r] )（题做多了，这种类型的还是很好憋的）,或者比如我，从暴力递归到动态规划
✨代码：
#include<stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include<math.h> int n; int Max(int a, int b) { return a > b ? a : b; } int process(int num[], int i, int r) { if (r <= 0)return 0; if (i == n)return 0; int p1 = 0; if (r >= num[i]) p1 = process(num, i + 1, r - num[i]) + num[i]; return Max(p1, process(num, i + 1, r)); } int main() { int num[1000] = { 0 }; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &num[i]); } int ans = process(num, 0, 180); int res = abs((360 - ans) - ans); printf("%d", res); return 0; }
- 上述暴力递归有部分数据超时，所以这里改成记忆化搜索
#include<stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include<math.h> int n; int Max(int a, int b) { return a > b ? a : b; } int dp[1000][1000]; int process(int num[], int i, int r) { if (dp[i][r]) return dp[i][r]; if (i == n || r <= 0) { dp[i][r] = 0; return dp[i][r]; } int p1 = 0; if (r >= num[i]) p1 = process(num, i + 1, r - num[i]) + num[i]; dp[i][r] = Max(p1, process(num, i + 1, r)); return dp[i][r]; } int main() { int num[1000] = { 0 }; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &num[i]); } int ans = process(num, 0, 180); int res = abs((360 - ans) - ans); printf("%d", res); return 0; }
⭐️总结⭐️
下午考c语言程序设计，现在先练练手，找了几道简单的，但是也比较有意思，希望下午能满分🙏🙏🙏，莫要出意外，我保证多测各种边界数据（这****的OI赛制）！
写在最后：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！
