【希冀OJ】考前刷一刷(二)

【希冀OJ】考前刷一刷(二),第1张

算法集训传送门》   👉引言

铭记于心
🎉✨🎉我唯一知道的,便是我一无所知🎉✨🎉

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

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


    今日主题:希冀OJ考前一刷
 👉⭐️第一题💎💎    ✨题目

      8577. 古董搬运

   ✨思路

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

   ✨代码
#include
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
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;
}
 👉⭐️第二题💎💎    ✨题目

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

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


 👉⭐️第四题💎    ✨题目

      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赛制)!

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

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/langs/1498084.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-25
下一篇 2022-06-25

发表评论

登录后才能评论

评论列表(0条)

保存