美团3.18笔试

T1: 暴力

#include<bits/stdc++.h>

using namespace std;

int main(){
	int n, a, b;
	cin >> n >> a >> b;
	vector<pair<int, int>> co(n);
	for(int i = 0; i < n; i++){
		cin >> co[i].first >> co[i].second;
	}

	sort(co.begin(), co.end());

	int ans = 0;
	for(int i = 0; i < n; i++){
		int nxt = i;
		for(int j = i; j < n; j++){
			if(co[j].first - co[i].first > a){
				break;
			}
			nxt = j;
		}

		vector<int> y;
		for(int j = i; j <= nxt; j++){
			y.push_back(co[j].second);
		}
		sort(y.begin(), y.end());

		int siz = (int)y.size();
		for(int j = 0; j < siz; j++){
			int idx = upper_bound(y.begin(), y.end(), y[j] + b) - y.begin();
			ans = max(ans, idx - j);
		}
	}
	cout << ans << endl;
}

T2. 双指针+map

#include <bits/stdc++.h>

using namespace std;
int main(){
	int n, k;
	cin >> n >> k;
	vector<int> a(n + 1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];	
	}
	map<int, int> cnt;
	int ans = 0;
	int curr = 0;
	int l = 1;
	for(int r = 1; r <= n; r++){
		if(!cnt[a[r]]){
			++curr;
		}
		++cnt[a[r]];

		while(curr > k && l <= r){
			--cnt[a[l]];
			if(cnt[a[l]] == 0) --curr;
			++l;
		}
		ans = max(ans, r - l + 1);
	}
	cout << ans << endl;
}

T3. 贪心，讨论

#include <bits/stdc++.h>

using namespace std;


int main(){
	string s;
	cin >> s;
	int n = (int)s.size();
	int tot_dif = 0;
	int idx = -1;
	for(int i = 0; i < n / 2; i++){
		if(s[i] != s[n - 1 - i]){
			++tot_dif;
			idx = i;
		}
	}
	assert(tot_dif <= 2);
	if(tot_dif == 0){
		bool found = 0;
		for(int i = 0; i < n / 2; i++){
			if(s[i] != 'a'){
				s[i] = s[n - 1  - i] = 'a';
				found = 1;
				break;
			}
		}
		if(!found && (n & 1)){
			s[n / 2] = 'a';
		}
	}else if(tot_dif == 1){
		if(n & 1){
			bool has_a = (min(s[idx], s[n - 1 - idx]) == 'a');
			if(has_a){
				s[idx] = s[n - 1 - idx] = 'a';
				s[n / 2] = 'a';
			}else{
				s[idx] = s[n - 1 - idx] = 'a';
			}
		}else{
			s[idx] = s[n - 1 - idx] = 'a';
		}
	}else{
		for(int i = 0; i < n / 2; i++){
			if(s[i] != s[n - 1 - i]){
				char minn = min(s[i], s[n - 1 - i]);
				s[i] = s[n - 1 - i] = minn;
			}
		}
	}

	cout << s << endl;
}

T4 背包

#include <bits/stdc++.h>

using namespace std;

int main(){
	int n, x, y;
	cin >> n >> x >> y;
	vector<int> a(n), b(n);

	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
	} 

	vector<vector<int> > dp(x + 1, vector<int>(y + 1, 0));

	for(int i = 0; i < n; i++){
		for(int j = x; j >= 0; j--){
			for(int k = 0; k <= y; ++k){
				if(j >= a[i]) dp[j][k] = max(dp[j][k], dp[j - a[i]][k] + 1);
				if(k && j >= b[i]) dp[j][k] = max(dp[j][k], dp[j - b[i]][k - 1] + 1);
			}
		}
	}

	int maxx = dp[x][y];
	for(int xx = 0; xx <= x; xx++){
		for(int yy = 0; yy <= y; yy++){
			if(dp[xx][yy] == maxx){
				cout << maxx << ' ' << xx << endl;
				return 0;
			}
		}
	}
}

T5. 暴力DFS

#include <bits/stdc++.h>

using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	vector<vector<int> > g(n + 1);
	vector<int> sum(n + 1, 0);
	int u, v;
	for(int i = 1; i <= n - 1; i++){
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	function<void(int, int, int, int)> dfs = [&](int rt, int u, int fa, int d){
		if(d > a[rt]){
			return ;
		}
		sum[u]++;
		for(int v: g[u]){
			if(v == fa) continue;
			dfs(rt, v, u, d + 1);
		}
	};

	for(int i = 1; i <= n; i++){
		dfs(i, i, 0, 0);
	}

	for(int i = 1; i <= n; i++){
		cout << sum[i] << ' ';
	}
	cout << endl;
}