记录下美团9.3笔试

第三题：字母数

反向建图拓扑排序，压缩状态统计1的个数

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
	int n;
	cin >> n;
	vector<vector<int>> v(n + 1);
	vector<int> in(n + 1, 0), dp(n + 1, 0);
	for(int i = 2, x; i <= n; i++){
		cin >> x;
		v[i].push_back(x);
		in[x] ++;
	}
	queue<int> q;
	string s;
	cin >> s;
	vector<int> ans(n + 1);
	for(int i = 0; i < n; i++){
		dp[i + 1] |= (1 << ((int)(s[i] - 'A')));
		if(in[i + 1] == 0) q.push(i + 1);
	}
	while(!q.empty()){
		int x = q.front(); q.pop();
		ans[x] = __builtin_popcount(dp[x]);
		for(auto y : v[x]){
			if(in[y] == 0) continue;
			dp[y] |= dp[x];
			in[y]--;
			if(in[y] == 0) q.push(y);
		}
	}
	for(int i = 1; i <= n; i++)
		i == 1 ? cout << ans[i] : cout << " " << ans[i];
	cout << endl;
	return 0;
}

第四题：城市

dp只过了90%，求改正

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
	int n, m, k;
	cin >> n >> m >> k;
	vector<vector<int>> v(3, vector<int>(m + 1));
	for(int i = 0; i < 3; i++)
		for(int j = 1; j <= m; j++)
			cin >> v[i][j];
	vector<vector<vector<ll>>> dp(m + 1, vector<vector<ll>>(2, vector<ll>(2, 0)));
	// dp[i][j][k]
	dp[0][0][1] = dp[0][1][1] = k;
	for(int i = 1; i <= m; i++){
		// 不取;
		//cout << "*** " << endl;
		if(dp[i - 1][0][0] >= dp[i - 1][1][0]){
			dp[i][0][0] = dp[i - 1][0][0];
			dp[i][0][1] = dp[i - 1][0][1];
		}else{
			dp[i][0][0] = dp[i - 1][1][0];
			dp[i][0][1] = dp[i - 1][1][1];
		}
		// 取 不取相等;
		if(v[0][i] == dp[i - 1][0][1] && dp[i][1][0] < dp[i - 1][0][0] + v[1][i])
			dp[i][1][0] = dp[i - 1][0][0] + v[1][i];
		else if(v[0][i] != dp[i - 1][0][1] && dp[i][1][0] < dp[i - 1][0][0] + v[2][i])
			dp[i][1][0] = dp[i - 1][0][0] + v[2][i];
		// 取 取 相等 不等
		if(v[0][i] == dp[i - 1][1][1] && dp[i][1][0] < dp[i - 1][1][0] + v[1][i])
			dp[i][1][0] = dp[i - 1][1][0] + v[1][i];
		else if(v[0][i] != dp[i - 1][1][1] && dp[i][1][0] < dp[i - 1][1][0] + v[2][i])
			dp[i][1][0] = dp[i - 1][1][0] + v[2][i];
		dp[i][1][1] = v[0][i];
		//cout << dp[i][0][0] << " " << dp[i][1][0] << endl;
	}
	cout << max(dp[m][0][0], dp[m][1][0]);
	return 0;
}

第五题：组题

滑动窗口

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
	ll n;
	cin >> n;
	vector<int> a(n), b(n), c(n);
	for(int i = 0; i < n; i++)
		cin >> a[i];
	for(int i = 0; i < n; i++)
		cin >> b[i];
	for(int i = 0; i < n; i++)
		cin >> c[i];
	vector<int> vis(n, 0);
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	sort(c.begin(), c.end());
	int j = 1, cnt = 0, k = 1;
	for(int i = 0; i < n; i++){
		while(j < n && c[j] <= b[i] * 2){
			cnt++; j++;
		}
		while(k < n && c[k] <= b[i]) {
			cnt--; k++;
		}
		vis[i] = cnt;
	}
	ll ans = 0;
	j = 1, cnt = 0, k = 1;
	for(int i = 0; i < n; i++){
		while(j < n && b[j] <= a[i] * 2){
			cnt += vis[j]; j++;
		}
		while(k < n && b[k] <= a[i]){
			cnt -= vis[k]; k++;
		}
		ans += cnt;
	}
	cout << ans << endl;
	return 0;
}