洛谷100题DAY6

26.P1628 合并序列

法一：

#include
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
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
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
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
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
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
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的木石所需的最小体力，输出最大体力相减即可

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