百度2021校招C++/PHP研发工程师笔试卷（9月3日）

// 暴力
#include <bits/stdc++.h>
using namespace std;

int main() {
	int T, L, n;
	cin >> T;
	while (T--) {
		cin >> L >> n;
		vector<int> left(n);
		vector<int> right(n);
		for (int i = 0; i < n; ++i) {
			cin >> left[i];
			cin >> right[i];
		}
		vector<int> res(L + 1, 0);
		for (int i = 0; i < n; ++i) {
			for (int j = left[i]; j <= right[i]; ++j) {
				++res[j];
			}
		}
		for (int i = 1; i <= L; ++i) {
			cout << res[i] << " ";
		}
		cout << endl;
	}	
}

// 双指针
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PAIR;

bool cmp(const PAIR& p1, const PAIR& p2) {
	return p1.first < p2.first;
}

int main() {
	int T, n, m;
	cin >> T;
	while (T--) {
		cin >> n >> m;
		vector<PAIR> a(n);
		vector<PAIR> b(m);
		int t;
		for (int i = 0; i < n; ++i) {
			cin >> t;
			a[i] = {t, i};
		}
		for (int i = 0; i < m; ++i) {
			cin >> t;
			b[i] = {t, i};
		}
		sort(a.begin(), a.end(), cmp);
		sort(b.begin(), b.end(), cmp);

		vector<int> res(n, -1);
		int i = 0, j = 0;
		while (i < n && j < m) {
			while (j < m && a[i].first > b[j].first)
				++j;
			if (j == m)
				break;
			res[a[i].second] = ++b[j].second;
			++i;
			++j;
		}
		for (int i = 0; i < n; ++i) {
			cout << res[i] << " ";
		}
		cout << endl;
	}	
}

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;

// n: 台阶总数
// m: 单步跨越最多m级台阶
int n, m;
int dfs(int pre2, int pre1, int r, vector<vector<vector<int>>>& dp) {
	if (r == 0)
		return 1;
	if (r < 0)
		return 0;
	if (dp[pre2][pre1][r] != -1)
		return dp[pre2][pre1][r]; 
	int res = 0;
	for (int i = 1; i <= min(m, r); ++i) {
		if (i != pre1 && i != pre2) {
			res = (res + dfs(pre1, i, r - i, dp)) % mod;
		}
	}
	return dp[pre2][pre1][r] = res;
}

int main() {
	cin >> n >> m;
	vector<vector<vector<int>>> dp(m + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, -1)));
	cout << dfs(0, 0, n, dp) << endl;
    return 0;
}