洛谷100题DAY6

这篇具有很好参考价值的文章主要介绍了洛谷100题DAY6。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

26.P1628 合并序列

法一:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, cnt;
string c, s[N], a[N];
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++)
	{
		cin >> s[i];
	}
	cin >> c;
	int len = c.size();
	for(int i = 1; i <= n; i ++)
	{
		if(s[i].substr(0, len) == c)
		{
			cnt ++;
			a[cnt] = s[i];
		}
	}
	sort(a + 1, a + 1 + cnt);
	for(int i = 1; i <= cnt; i ++)
	{
		cout << a[i] << '\n';
	}
	return 0;
}

法二:

使用find函数,其是指向搜索范围内第一个元素

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, cnt;
string c, s[N], a[N];
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++)
	{
		cin >> s[i];
	}
	cin >> c;
	sort(s + 1, s + 1 + n);
	for(int i = 1; i <= n; i ++)
	{
		if(s[i].find(c) == 0)cout << s[i] << '\n';
	}
	return 0;
}

27.P1403 [AHOI2005] 约数研究

约数个数 = 将约数拆解成每个质因子乘积的形式,每次将质因子出现的个数+1后相乘得到约数个数,普通一次一次模板计算会有超时现象

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 110, mod = 1e9 + 7;
ll n, ans, primes[N];
ll solve(int x)
{
	unordered_map<int, int> primes;
	for(int i = 2; i <= x / i; i ++)
	{
		while(x % i == 0)
		{
			x /= i;
			primes[i] ++;
		}
	}
	if(x > 1)primes[x] ++;
	ll res = 1;
	for(auto i : primes)
	{
		res = res * (i.second + 1) % mod;
	}
	return res;
}
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++)
	{
		ans += solve(i);
	}
	cout << ans;
	return 0;
}

AC写法:

 每次到自己就将自己可以贡献的所有约数个数不断加起来

#include<bits/stdc++.h>
using namespace std;
int n, ans;
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++)
	{
		for(int j = i; j <= n; j += i)
		{
			ans ++;
		}
	}
	cout << ans;
	return 0;
}

28.P1644 跳马问题

法一:

#include<bits/stdc++.h>
using namespace std;
int dx[4] = {-2, -1, 1, 2};
int dy[4] = {1, 2, 2, 1};
int n, m, ans;
void dfs(int x, int y)
{
	if(x == m && y == n)
	{
		ans ++;
		return;
	}
	for(int i = 0; i < 4; i ++)
	{
		int a = x + dx[i];
		int b = y + dy[i];
		if(a >= 0 && a <= m && b >= 0 && b <= n)
		{
			dfs(a, b);
		}
	}
}
int main()
{
	cin >> m >> n;
	dfs(0, 0);
	cout << ans;
	return 0;
}

法二:

#include<bits/stdc++.h>
using namespace std;
int dy[4] = {-2, -1, 1, 2};
int dx[4] = {- 1, - 2, - 2, - 1};
const int N = 1e3 + 10;
int n, m, dp[N][N];
int main()
{
	cin >> n >> m;
	dp[0][0] = 1;
	for(int i = 0; i <= m; i ++)
	{
		for(int j = 0; j <= n; j ++)
		{
			for(int k = 0; k < 4; k ++)
			{
				int a = i + dx[k];
				int b = j + dy[k];
				if(a < 0 || a > m || b < 0 || b > n)continue;
				dp[i][j] += dp[a][b];
			}
		}
	}
	cout << dp[m][n];
}

29.P1122 最大子树和

将每朵花的两条边相连,进行dfs,传入两个参数即为当前节点与当前节点的父亲节点,dp[x]为当前节点的值,将与当前节点的值循环遍历一遍,如果现节点是当前节点的父亲则跳过,因为其是不断向下递归,只用向下的点是大于0的则一定会对答案有所贡献,现在每一个dp的值都代表了自己所能到达的最大范围,最后将每一个点遍历,找出最大的那个可以取到的和

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, u, v, w[N], dp[N];
vector<int> g[N];
void dfs(int x, int fa)
{
	dp[x] = w[x];
	for(auto y : g[x])
	{
		if(y == fa)continue;
		dfs(y, x);
		if(dp[y] > 0)dp[x] += dp[y];
	}
}
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++)cin >> w[i];
	for(int i = 1; i <= n - 1; i ++)
	{
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, 0);
	int ans = w[1];
	for(int i = 1; i <= n; i ++)
	{
		ans = max(ans, dp[i]);
	}
	cout << ans;
	return 0;
}

30.P1510 精卫填海

dp[i]表示到目前为止,得到总体积为i的木石所需的最小体力,输出最大体力相减即可文章来源地址https://www.toymoban.com/news/detail-730500.html

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int v, n, c, k[N], m[N], dp[N];
//dp[i]表示到目前为止,得到总体积为i的木石所需的最小体力 
int main()
{
	cin >> v >> n >> c;
	for(int i = 1; i <= n; i ++)
	{
		cin >> k[i] >> m[i];
	}
	memset(dp, 0x3f, sizeof dp);
	dp[0] = 0;
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1e4 + 10; j >= k[i]; j --)
		{
			dp[j] = min(dp[j], dp[j - k[i]] + m[i]);
		}
	}
	int ans = dp[v];
	for(int i = v; i <= 2e4; i ++)
	{
		ans = min(ans, dp[i]);
	}
	if(c >= ans)cout << c - ans;
	else cout << "Impossible" << '\n';
	return 0;
}

到了这里,关于洛谷100题DAY6的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构day08(树、算法)

    今日任务: 二叉树: 今日思维导图 链接: 快排:快速排序法(详解)_李小白~的博客-CSDN博客图画挺好啊 常见款:https://www.runoob.com/w3cnote/quick-sort.html  

    2024年02月10日
    浏览(42)
  • 数据结构与算法学习(day1)

    (1)我是一个大三的学生(准确来说应该是准大三,因为明天才报名哈哈哈)。 (2)最近就想每天闲着没事也刷些C语言习题来锻炼下编程水平,也一直在思考企业对应届大学生能力的要求,所以经常会想到关于面试的事情。由于我也没实习过,所以我对面试没有一个具象化

    2024年02月10日
    浏览(53)
  • 数据结构与算法学习(day4)——解决实际问题

    在本章的学习此前,需要复习前三章的内容,每个算法都动手敲一遍解题。宁愿学慢一点,也要对每个算法掌握基本的理解! 前面我们学习了简化版桶排序、冒泡排序和快速排序三种算法,今天我们来实践一下前面的三种算法。 本章的学习目标: (1)回顾三个算法的基本原

    2024年02月09日
    浏览(57)
  • 数据结构与算法学习(day1)——简化版桶排序

    (1)我是一个大三的学生(准确来说应该是准大三,因为明天才报名哈哈哈)。 (2)最近就想每天闲着没事也刷些C语言习题来锻炼下编程水平,也一直在思考企业对应届大学生能力的要求,所以经常会想到关于面试的事情。由于我也没实习过,所以我对面试没有一个具象化

    2024年02月09日
    浏览(43)
  • 【Java数据结构与算法】Day2-高级排序(希尔、归并、快速、计数)

    ✅作者简介:热爱Java后端开发的一名学习者,大家可以跟我一起讨论各种问题喔。 🍎个人主页:Hhzzy99 🍊个人信条:坚持就是胜利! 💞当前专栏:【Java数据结构与算法】 🥭本文内容:Java数据结构与算法中的比较高级的排序,希尔排序、归并排序、快速排序、计数排序

    2024年02月02日
    浏览(64)
  • 二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”

    各位CSDN的uu们你们好呀,今天继续数据结构与算法专栏中的二叉树,下面,让我们进入二叉树的世界吧!!! 二叉树(上)——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客 二叉树链式结构的实现 二叉树链式结构的实现 求二叉树的高度 但是这种写法有很大的问题

    2024年02月17日
    浏览(41)
  • 【优选算法题练习】day6

    76. 最小覆盖子串 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意:对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串

    2024年02月16日
    浏览(41)
  • 【算法训练(day6)】双指针模板

    通常情况下我们可能会遇到在某些可遍历的集合中寻找满足某种性质的字串或元素。这时候我们采取暴力的思路就会面临多重循环。我们可以利用题目中所给的集合并利用其性质将多重循环降成一重循环。光用语言描述可能不太好理解。接下来看几个双指针典型案例 请从字符

    2024年02月06日
    浏览(36)
  • 数据结构 day1

    1x.mind  2间接定义结构体数组,进行4种方式的定义和初始化  3定义结构体存储10辆车(车的信息:品牌、单价、颜色)         1.定义函数,实现循环输入         2.定义函数,实现排序         3.定义函数,计算红色车的个数  

    2024年02月11日
    浏览(42)
  • 数据结构day1

    1.思维导图 2.定义一个简单宏或宏函数,实现两个数交换。 3.定义字符类型指针,指针指向n个连续堆区内存,输入,计算字符串长度 定义函数,实现内存申请 定义函数,解释字符串长度 定义函数,释放内存

    2024年01月20日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包