洛谷100题DAY6

超、凢脫俗 2024-03-02 09:09 41阅读 0赞

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

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