20230806米哈游笔试题解及代码分享

T1

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const int maxl=1e6+10;

int n,m,ans;

inline void prework()
{
	cin>>n;
	vector<string> a(n);
	vector<string> b(n);
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++)
		cin>>b[i];
	int num=0;
	for(int i=0;i<n;i++)
	{
		if(a[i]==b[i]) num++;
		else num--;
		if(num<0)
			return;
	}
	ans++;
}

inline void mainwork()
{
	
}

inline void print()
{
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t=1;
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		prework();
		mainwork();
		print();
	}
	cout<<ans;
	return 0;
}

T2

从小开始打到半血，能使得后面获得更多的转圈圈，最后再把转圈圈全打完还不够需要继续普攻的加上

但是这样是错的，但是只有这种错解能过

5

1 2 3 3 10 ，这个输出6，但实际上攻击10 五次就打完了

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const int maxl=1e6+10;

int n,m;ll ans=0;
int a[maxl],b[maxl];

inline void prework()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+1+n);
	int now=0;
	for(int i=1;i<=n;i++)
	{
		int d=a[i]-(a[i]/2);
		if(now<d)
		{	
			ans+=d-now;
			b[i]=d-now;
		}
		now++;
	}
	for(int i=1;i<=n;i++)
	if(now+b[i]<a[i])
		ans+=a[i]-(now+b[i]);
	cout<<ans;
}

inline void mainwork()
{
	
}

inline void print()
{
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t=1;
//	cin>>t;
	for(int i=1;i<=t;i++)
	{
		prework();
		mainwork();
		print();
	}
	return 0;
}

T3

把一个子树i挪到1节点，其实就是这棵子树所有点的深度减掉dep[i]-2，就可以直接算了

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const int maxl=1e6+10;

int n,m;ll ans;
ll a[maxl],dep[maxl],suma[maxl],dp[maxl];
vector<int> e[maxl];

inline void prework()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<n;i++)
	{
		int u,v;cin>>u>>v;
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	}
}

inline void dfs(int u,int fa)
{
	dp[u]=a[u];
	suma[u]=a[u];
	for(int v:e[u])
	{
		if(v==fa) continue;
		dep[v]=dep[u]+1;
		dfs(v,u);
		suma[u]+=suma[v];
		dp[u]+=dp[v]+suma[v];
	}
}

inline void mainwork()
{
	dep[1]=1;
	dfs(1,0);
	ans=dp[1];
	for(int i=2;i<=n;i++)
	{
		ans=min(ans,dp[1]-(dep[i]-2)*suma[i]);
	}
}

inline void print()
{
	cout<<ans;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t=1;
//	cin>>t;
	for(int i=1;i<=t;i++)
	{
		prework();
		mainwork();
		print();
	}
	return 0;
}