爱奇艺 秋招 测试开发工程师 笔试 1题AC+2题思路
第一题：
切割块，大意是x y z的立方体，切k刀，只能整点坐标切割
思路：平均切，一面一刀，开longlong
写的很繁琐 233333
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
int x,y,z;
int k;
int xx,yy,zz;
long long ans;
scanf("%d%d%d%d",&x,&y,&z,&k);
xx=1;yy=1;zz=1;
int step;
step=1;
for (int t=1;t<=k;t++)
{
if (xx==x && yy==y && zz==z) break;
if (step==1)
{
if (xx<x)
{
xx++;
step=2;
}
else if (yy<y)
{
yy++;
step=3;
}
else if (zz<z)
{
zz++;
step=1;
}
}
else if (step==2)
{
if (yy<y)
{
yy++;
step=3;
}
else if (zz<z)
{
zz++;
step=1;
}
else if (xx<x)
{
xx++;
step=2;
}
}
else if (step==3)
{
if (zz<z)
{
zz++;
step=1;
}
else if (xx<x)
{
xx++;
step=2;
}
else if (yy<y)
{
yy++;
step=3;
}
}
}
ans=xx*yy;
ans=ans*zz;
printf("%lld\n",ans);
return 0;
}
第二题不会
给定长度为N-1的01序列A，P为1~N的数列
求满足：A[i]=0时P[i]<P[i+1]，A[i]=1时P[i]>P[i+1] 的P的排列的方案数
暴搜剪不剪枝都18%...直接输样例也18%，写到自闭，是我配不上爱奇艺！
然后我去问巨佬第二题思路了
f[i][j]表示我们处理到了第i位，第i位的数字，在接下来的m=(n-i+1)个数（包括第i个位置）中排第j的方案数
a[i]==0：此时有m-j个数可以放在下一个位置，可以更新的是f[i+1] [j ~ m-j] ，就是在j~m中找比当前j大的数来更新，这一段的数，要+=f[i][j]
a[i]==1：此时有j-1个数可以放在下一个位置,可以更新f[i+1][1 ~ j]
a[i]==0：此时有m-j个数可以放在下一个位置，可以更新的是f[i+1] [j ~ m-j] ，就是在j~m中找比当前j大的数来更新，这一段的数，要+=f[i][j]
a[i]==1：此时有j-1个数可以放在下一个位置,可以更新f[i+1][1 ~ j]
查看16道真题和解析
