蚂蚁0420开发笔试代码分享

T1水前缀后缀minmax

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

const int maxl=1e6+10;

int n;
int a[maxl];
int premx[maxl],sufmx[maxl];
int premi[maxl],sufmi[maxl];

inline int getmx(int i)
{
	int ret=a[i]+a[i+1];
	if(i+2<=n)
		ret=max(ret,sufmx[i+2]);
	if(i-1>=1)
		ret=max(ret,premx[i-1]);
	return ret;
}

inline int getmi(int i)
{
	int ret=a[i]+a[i+1];
	if(i+2<=n)
		ret=min(ret,sufmi[i+2]);
	if(i-1>=1)
		ret=min(ret,premi[i-1]);
	return ret;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	premx[1]=premi[1]=a[1];
	for(int i=2;i<=n;i++)
		premx[i]=max(premx[i-1],a[i]),
		premi[i]=min(premi[i-1],a[i]);
	sufmx[n]=sufmi[n]=a[n];
	for(int i=n-1;i>=1;i--)
		sufmx[i]=max(sufmx[i+1],a[i]),
		sufmi[i]=min(sufmi[i+1],a[i]);
	int ans=2e9,mx,mi;
	for(int i=1;i<n;i++)
	{
		mx=getmx(i);
		mi=getmi(i);
		ans=min(ans,mx-mi);
	}
	printf("%d",ans);
	return 0;
}

T2打表代码

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

const int maxl=1e6+10;

int n;
int a[maxl],b[maxl],p[maxl];
int ans;
vector<vector<int> > ansa;
set<vector<int> >s;
inline int calc()
{
	int ret=0;
		for(int i=1;i<=n;i++)
		{
			int cnt2=1,cnt3=1;
			for(int j=i;j<=n;j++)
			{
				if(a[j]==2)
					cnt2++;
				else
					cnt3++;
				ret+=cnt2*cnt3;
			}
		}
	return ret;
}

int main()
{
	scanf("%d",&n);
	int cnt2,cnt3;
	scanf("%d %d",&cnt2,&cnt3);
	for(int i=1;i<=cnt2;i++)
		b[i]=2;
	for(int i=cnt2+1;i<=n;i++)
		b[i]=3;
	for(int i=1;i<=n;i++)
		p[i]=i;
	ans=2e9;
	do
	{
		for(int i=1;i<=n;i++)
			a[i]=b[p[i]];
		int tmp=calc();
		if(tmp<ans)
		{
			ansa.clear();s.clear();
			vector<int> d;
			for(int i=1;i<=n;i++)
				d.push_back(a[i]);
			ansa.push_back(d);
			ans=tmp;
			s.insert(d);
		}
		else if(tmp==ans)
		{
			vector<int> d;
			for(int i=1;i<=n;i++)
				d.push_back(a[i]);
			if(s.find(d)==s.end())
			{
				ansa.push_back(d);
				s.insert(d);
			}
		}
	}while(next_permutation(p+1,p+1+n));
	printf("%d\n",ans);
	for(auto &d:ansa)
	{
		for(auto &x:d)
			printf("%d ",x);
		puts("");
	}
	return 0;
}

T2AC 代码，但是并不是最小的

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxl=1e6+10;

int n;ll ans=0;
int a[maxl],b[maxl],p[maxl];
ll sum2[maxl];
ll suml[maxl],sumr[maxl];
ll sum3[maxl];

int main()
{
	ll cnt2=0,cnt3=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]==2)
			cnt2++;
		else
			cnt3++;
	}
	
	//scanf("%lld %lld",&cnt2,&cnt3);

		for(int i=1;i<=cnt2;i++)
		{
			sum2[i]=sum2[i-1]+i+1;
			ans+=sum2[i];
		}	
		for(int i=1;i<=cnt3;i++)
		{
			sum3[i]=sum3[i-1]+i+1;
			ans+=sum3[i];
			ans+=(i+1)*sum2[cnt2];	
		}
	/*
	else
	{
		
		if(cnt2>cnt3)
			swap(cnt2,cnt3);
		int le=cnt2/2,ri=cnt2-le;
		for(int i=1;i<=le;i++)
		{
			suml[i]=suml[i-1]+i+1;
			ans+=suml[i];
		}
		for(int i=1;i<=cnt3;i++)
		{
			sum3[i]=sum3[i-1]+i+1;
			ans+=sum3[i];
			ans+=(i+1)*suml[le];	
		}
		for(int i=1;i<=ri;i++)
		{
			sumr[i]=sumr[i-1]+i+1;
			ans+=sumr[i];
			ans+=(i+1)*sum3[cnt3];
			ans+=(i+2+i+1+le)*le/2*(cnt3+1);
		}
		
	}
	*/
	cout << ans;
	return 0;
}

要写成22233333这样求才对，但实际不是这样最小啊，打表找出规律，cnt2=cnt3时，全2全3最小，假设cnt2<cnt3, {222}cnt2/2  {33333}cnt3 {222}cnt2/2。

9个数3个2, 6个3，最小应该是2 2 3 3 3 3 3 3 2，这样答案是324，而直接2 2 2 3 3 3 3 3是336，上面注释代码是当cnt2<cnt3是的正解代码，标程数据是错的

T3简单数位DP，好像直接顺着DP也行？但是数位dp的dfs写法很无脑

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

int n;
char s[maxl];
int dp[maxl][2];
int ans[maxl][2];

inline void add(int &a,int b)
{
	a+=b;
	if(a>=mod) a-=mod;
}

inline int dfs(int k,int f1)
{
	if(k>n)
		return 1;
	int &x=dp[k][f1];
	if(x>0)
		return x;
	if(!f1 || s[k]=='B') //a[k]='B'
		add(x,dfs(k+1,f1 && s[k]=='B'));
	add(x,dfs(k+1,f1 && s[k]=='R'));
	return x;	
}

inline int calc(int k,int f1)
{
	if(k>n)
		return 0;
	int &x=ans[k][f1];
	if(x>0)
		return x;
	if(!f1 || s[k]=='B') //a[k]='B'
		add(x,calc(k+1,f1 && s[k]=='B'));
	add(x,calc(k+1,f1 && s[k]=='R'));
	add(x,dfs(k+1,f1 && s[k]=='R'));
	return x;	
}

int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	dfs(1,1);
	calc(1,1);
	printf("%d",ans[1][1]);
	return 0;
}