美团8.15笔试部分题解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,k;
string solve()
{
	cin >> n;
	map<int,int> mp;
	for(int i=0;i<n;i++)
	{
		cin >> k;
		mp[k] = 1;
	}
	for(int i=1;i<=n;i++)
	{
		if(mp[i]==0) return "No";
	}
	return "Yes";
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T = 1;
	cin >> T;
	while(T--) cout << solve() << "\n";
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,k;
string s;
bool c(int x)
{
	for(int i=x;i<n;i++)
	{
		if(s[i]!=s[n-i+x-1]) return 0;
		if(i>=n-i+x-1) break;
	}
	return 1;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> s;
	n = s.size();
	for(int i=0;i<n;i++)
	{
		if(s[i]==s[n-1])
		{
			if(c(i)) 
			{
				cout << i << "\n";
				return 0;
			}
		}
	}
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,k;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	vector<pair<int,int>> a(n);
	for(int i=0;i<n;i++)
	{
		string st;
		cin >> k >> st;
		if(st=="L") m = 0;
		else m = 1;
		a[i] = {k,m};
	}
	stack<pair<int,int>> sou,sji;
	vector<int> o(n);
	for(int i=0;i<n;i++) o[i] = i;
	sort(o.begin(),o.end(),[&](int x,int y)
	{
		return a[x]<a[y];
	});
	vector<int> ans(n,0);
	for(int i=0;i<n;i++)
	{
		int j = o[i];
		if(a[j].second==0)
		{
			if(a[j].first%2==0)
			{
				if(sou.empty()) ans[j] = -1;
				else{
					auto x = sou.top();
					sou.pop();
					ans[x.second] = ans[j] = (a[j].first-x.first)/2;
				}
			}
			else{
				if(sji.empty()) ans[j] = -1;
				else{
					auto x = sji.top();
					sji.pop();
					ans[x.second] = ans[j] = (a[j].first-x.first)/2;
				}
			}
			
		}
		else{
			if(a[j].first%2==0)
			sou.push({a[j].first,j});
			else
			sji.push({a[j].first,j});
		}
	}
	while(!sou.empty())
	{
		auto x = sou.top();sou.pop();
		ans[x.second] = -1;
	}
	while(!sji.empty())
	{
		auto x = sji.top();sji.pop();
		ans[x.second] = -1;
	}
	for(auto& i:ans) cout << i << "\n";
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,k,x,y,p,q;
vector<pair<ll,ll>> g1[55],g2[55];
vector<ll> dis1(55,1e18),dis2(55,1e18);
void dijkstra1()
{
	priority_queue<pair<ll,ll>> q;
	vector<int> vis(55,0);
	q.push({0,y});
	dis1[y] = 0;
	while(!q.empty())
	{
		auto now = q.top();
		q.pop();
		int u = now.second;
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i=0;i<g1[u].size();i++)
		{
			ll v = g1[u][i].first,w = g1[u][i].second;
			if(dis1[v]>dis1[u]+w)
			{
				dis1[v] = dis1[u]+w;
				q.push({-dis1[v],v});
			}
		}
	}
}
void dijkstra2()
{
	priority_queue<pair<ll,ll>> q;
	vector<int> vis(55,0);
	q.push({0,x});
	dis2[x] = 0;
	while(!q.empty())
	{
		auto now = q.top();
		q.pop();
		int u = now.second;
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i=0;i<g2[u].size();i++)
		{
			ll v = g2[u][i].first,w = g2[u][i].second;
			if(dis2[v]>dis2[u]+w)
			{
				dis2[v] = dis2[u]+w;
				q.push({-dis2[v],v});
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> x >> y;
	for(int i=0;i<m;i++)
	{
		int u,v;
		cin >> u >> v >> p >> q;
		g1[u].push_back({v,p});
		g1[v].push_back({u,p});
		g2[u].push_back({v,q});
		g2[v].push_back({u,q});
	}
	dijkstra1();
	dijkstra2();
	ll ans = 1e18;
	for(int i=1;i<=n;i++)
	{
		ll z;
		cin >> z;
		ans = min(ans,max(z,dis2[i])+dis1[i]);
	}
	//for(int i=1;i<=n;i++) cout << dis1[i] << " ";cout << "\n";
	//for(int i=1;i<=n;i++) cout << dis2[i] << " ";cout << "\n";
	cout << min(ans,dis2[y]) << "\n";
}

#include<bits/stdc++.h>
using namespace std;
vector<int> dp(10009,1e9);
int main()
{
	int n,p;
	cin >> n >> p;
	string s;
	cin >> s;
	vector<int> a(p+1,0);
	for(int i=1;i<=p;i++) cin >> a[i];
	dp[1] = 0;
	for(int i=2;i<=n;i++)
	{
		if(s[i-1]=='x') continue;
		for(int j=1;j<=p&&i-j>=1;j++)
		{
			dp[i] = min(dp[i],dp[i-j]+a[j]);
		}
	}
	cout << dp[n] << "\n";
}