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的值都代表了自己所能到达的最大范围,最后将每一个点遍历,找出最大的那个可以取到的和文章来源:https://www.toymoban.com/news/detail-730500.html
#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模板网!