9-5 搜狗笔试 AK

9-5搜狗题目,3题AK第一题第二题第三题

第一题

题意:

给你三种道具A,B,C.分别有a个,b个,c个.
可以把其中的任意两个道具(包括两个同一种的)换成任意指定道具.
三种不同的道具各来一个可以换一个奖品.求有多少种奖品

思路:

通过排序,弄成a < b < c
设答案为ans = 0
先合成a个奖品

ans += a
a = 0
b -= a
c -= a

然后再判断 c-2*b > b

如果是的话
我们可以先拿2b个合成A,然后合成b个奖品,然后只有c可能大于0.然后5个c可以合成一个奖品

ans += b
c -= 3*b//先花2*b个合成b个A,然后合成b个奖品,合计3b个
b = 0
ans += c / 5

不然的的话,先把B,C的数量弄的相等,然后2个b两个c可以合成一个奖品

temp = (c-b)/2;//先合成temp个奖品
ans += temp;
c = c - temp * 3;
b -= temp;
ans += (b+c) / 4;

全部代码

int numberofprize(int a,int b,int c)
{
if(a > b)
swap(a,b);
if(b > c)
{
swap(b,c);
}
if(a > b)
{
swap(a,b);
}
int ans = 0;
ans = a;
b -= a;
c -= a;
if(c - 2*b >= b)//修改
{
c -= 3*b;
ans += b;
ans += (c/5);
}
else{
long long temp = (c-b)/2;
ans += temp;
c = c - temp * 3;//修改
b -= temp;//修改
ans += (b+c) / 4;
}
return ans;

}

第二题

题意:告诉你有n个房子并且告诉了房子的中心和长度,是按序排列的。问我们建造一栋长度为t的且挨着其他房子的方案有多少种。
思路:我们可以知道房子是有序排列的,不难发现,方案至少是2种,即第一个房子的西边和最后一个房子的东边,
那么我们只需要判断一下房子与房子之间能否建房子,如果房子之间的长度比t长那么就有2种方案,如果和t一样
长就有一种方案,否则就没有。我们遍历每个房子之间的距离,特别的两个房子有奇数的情况下特殊考虑一下就可以了。

int getHouse(int t,int *a,int xalen)
{
int ans=2;
for (int i = 2; i <xalen ; i+=2) {
int r=a[i-2]+a[i-1]/2;
int l=a[i]-a[i+1]/2;
int k;
if(a[i-1]%2!=0&&a[i+1]%2!=0)
{
k=l-r-1;
if(k==t)
ans++;
if(k>t)
ans+=2;
}
else if(a[i-1]%2==0&&a[i+1]%2==0)
{
k=l-r;
if(k==t)
ans++;
if(k>t)
ans+=2;
} else{
if(l-r>=t)
ans+=2;
}
}
return ans;
}

第三题

思路:不难想到枚举所有情况,枚举所有情况不难想到搜索,搜索不难想到用DP来优化。 我们讲细一点,怎么从搜索联系到DP。
如果用搜索,那么怎么来表示呢。可以用DFS(pos,val)来表示到了第pos个位置,然后最后一位是val。
那么

   void dfs(int pos,int val)
{
if(pos==L+1) ans++;
for(int i=0;i<=9;i++){
dfs(pos+1,(i+val)/2);
if((i+val)&1) dfs(pos+1,(i+val)/2+1);
}
}

我们来分析,(1)他那些地方重复了,(2)怎么修改为DP。
(1) pos+1不变,但是val却有很多个可以变为同一个,他们可以合并,然后再去DFS。
(2) 所以可以变为DP,DP就是一种解决重复问题的算法,很明显我们的DFS满足DP的条件:由于pos单调,无后效性。当然还有其他性质,可以自己检验。 DFS转为DP,首先我们得观察DFS,DFS有二维,DP也可以用二维,用dp[pos][val]表示已经表示了pos位,最后一位是val的方案。
不难得到:

            for(j=0到9)
int x=j+c[i]-'0';
dp[i][x/2]+=dp[i-1][j];
...x为奇数再+

到了现在,还剩下最后一个问题,和原来的数字重复,我们直选要判定是否可以满足题意造一个出来即可,如果可以,答案-1即可。
判定方法:如果从前往后,如果都满足:前一个数字+(0-9)的一半可以变为后一个数字,则满足。

class Solution{
public:
long long getPassWordCount(string password){
int L=password.length(),F=1;
long long dp[110][10];
memset(dp,0,sizeof(dp));
for(int i=0;i<=9;i++) dp[0][i]=1;
for(int i=1;i<L;i++){
int w=password[i-1]-'0';
int v=password[i]-'0';
if(!(w/2<=v&&((w+9)/2>=v))) F=0;
for(int j=0;j<=9;j++){
int x=j+password[i]-'0';
if(x&1){
dp[i][x/2]+=dp[i-1][j];
dp[i][x/2+1]+=dp[i-1][j];
}
else {
dp[i][x/2]+=dp[i-1][j];
}
}
}
long long ans=0;
for(int i=0;i<=9;i++) ans+=dp[L-1][i];
if(F) ans--;
return ans;
}
};

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

9-5 搜狗笔试 AK

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 9-5 搜狗笔试 AK
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏