JZTXT

洛谷100题计划(30/100)

发布时间 2023-09-24 00:10:31作者: Ke_scholar

洛谷100题计划(30/100)

P1628 合并序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

把符合条件的字符串都放进multiset里(可以包含重复的元素,且自动排序),然后输出即可

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<string> s(N);
    for (auto &i : s)
        cin >> i;

    string T;
    cin >> T;

    multiset<string> ans;
    for(auto &i : s){        
        if(i.size() < T.size()) continue;
        if(i.substr(0,T.size()) == T)
            ans.insert(i);
    }

    for(auto i : ans)
        cout << i << '\n';

    return 0;
}

P1403 [AHOI2005] 约数研究 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

先给出公式\(ans += \lfloor\frac{N}{i}\rfloor\),这里的\(\lfloor\frac{N}{i}\rfloor\)意思是\(1\sim N\)中有多少个数的约数包含\(i\),以题干中举例:

1 2 3 4 5 6
1 1 1 1 1 1
2 2 2
3 3
4
5
6 
#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    i64 ans = 0;
    for(int i = 1;i <= N;i ++){
        ans += N / i;
    }

    cout << ans << '\n';

    return 0;
}

P1644 跳马问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

看数据范围比较小,直接dfs暴搜了,dp应该也能做,不过感觉没直接dfs好写(

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

typedef pair<i64, i64> PII;

int main() {

	int n,m;
	cin >> n >> m;

	int u[] = {-2,-1,1,2},v[] = {1,2,2,1};
	
	i64 ans = 0;
	auto dfs = [&](auto self, int x,int y){
		if(x > n || y > m || x < 0 || y < 0)
			return ;

		if(x == n && y == m){
			ans ++;
			return ;
		}

		for(int i = 0;i < 4;i ++){
			self(self,x + u[i], y + v[i]);
		}
	};

	dfs(dfs,0,0);
	cout << ans << '\n';

	return 0;
}

P1510 精卫填海 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

此题就是一个背包题,但是有个很坑的点,就是不一定刚好满足体积\(v\)的就是体力最小的,大于\(v\)的也可以填满,所以得开大一点,这里是直接开到了\(2v\)

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

typedef pair<i64, i64> PII;

int main() {

	int v,n,c;
	cin >> v >> n >> c;
	vector<i64> k(n),m(n);
	for(int i = 0;i < n;i ++)
		cin >> k[i] >> m[i];

	vector<i64> dp(2 * v + 1,INT_MAX);
	dp[0] = 0;
	i64 resv = INT_MAX;
	for(int i = 0;i < n;i ++){
		for(int j = 2 * v;j >= k[i];j --){
			dp[j] = min(dp[j], dp[j - k[i]] + m[i]);
		}		
	}

	for(int i = v;i <= 2 * v;i ++)
		resv = min(resv, dp[i]);

	if(resv <= c) cout << c - resv << '\n';
	else cout << "Impossible\n";

	return 0;
}