《算法集训传送门》

  👉引言

💖 ❄️我们的算法之路❄️💖

   众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
              ☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
   💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs)，💝宽度优先搜索（bfs），💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉

    今日主题：希冀OJ考前一刷

 👉⭐️第一题💎💎

   ✨题目

      8577. 古董搬运

   ✨思路：

经典背包问题，上暴力递归代码（没想到样例竟然是错的， 吐 ** ）打表

   ✨代码：

#include
int Max(int a, int b)
{if (a > b)return a;elsereturn 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
int Max(int a, int b)
{if (a > b)return a;elsereturn 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;
}

 👉⭐️第二题💎💎

   ✨题目

      8540. 素数

简单的数论题，判断素数，数据量比较小，不需要素数筛，直接用看sqrt(n)前能不能被整除即可

   ✨代码：

#include
#include
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;
}

 👉⭐️第三题💎

   ✨题目

      8538. 字符串

   ✨思路：

遍历s中的字符，看是否能够再不回溯的情况下在t中找到

   ✨代码：

#include
#include 
#include 
#include 
#includeint 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;
}

 👉⭐️第四题💎

   ✨题目

      8532. 数字游戏

   ✨思路：

dp问题，即将一个整数数组加和为两个最接近的整数，可以直接憋状态转移方程 dp[i][r]=max( (dp[i+1][r-num[i]]+num[i]),dp[i+1][r] )（题做多了，这种类型的还是很好憋的）,或者比如我，从暴力递归到动态规划

   ✨代码：

#include
#include 
#include 
#include 
#include
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
#include 
#include 
#include 
#include
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赛制）！

写在最后：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！