蚂蚁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;
}
#蚂蚁##蚂蚁笔试##蚂蚁2024暑期实习#
大疆主管面2人在聊
