阿里31号游戏开发笔试最后一题求助
题是这样的:给一个数n(n>=1),再给一个数组[1,2,3,...,k]。问,用数组中的数,有多少种方法能让n变成0。
从记忆化就能20%了,但是超内存,翻译成dp还是超内存(毕竟都O(nk))。
之后写了个队列O(k)的方法,用例都对,一提交0%,麻了,不知道错哪了。
```
if(n<k)
{
std::cout<<(1<<(n-1))<<std::endl;return;
}
queue<unsigned long long> q;
q.push(1);
unsigned long long now_sum = 1;
for (unsigned long long hp = 1; hp < n; hp++)
{
unsigned long long sum = now_sum % 998244353;
q.push(sum);
now_sum += sum;
now_sum = now_sum % 998244353;
if (q.size() > k)
{
unsigned long long pop_num = q.front(); q.pop();
now_sum = now_sum - pop_num;
}
}
std::cout << now_sum << std::endl;
```
从记忆化就能20%了,但是超内存,翻译成dp还是超内存(毕竟都O(nk))。
之后写了个队列O(k)的方法,用例都对,一提交0%,麻了,不知道错哪了。
```
if(n<k)
{
std::cout<<(1<<(n-1))<<std::endl;return;
}
queue<unsigned long long> q;
q.push(1);
unsigned long long now_sum = 1;
for (unsigned long long hp = 1; hp < n; hp++)
{
unsigned long long sum = now_sum % 998244353;
q.push(sum);
now_sum += sum;
now_sum = now_sum % 998244353;
if (q.size() > k)
{
unsigned long long pop_num = q.front(); q.pop();
now_sum = now_sum - pop_num;
}
}
std::cout << now_sum << std::endl;
```
全部评论
我也遇到过提交了0%的情况,可能是代码有问题
阿里招聘还没结束啊
相关推荐
国家一级产品交付工程...:这个世界也太颠了 想起来第一次实习面试 一家小公司 刚到就要填各种各样的表 然后老板来面试 一直问数学怎么样 最后还说给我开50一天 够我一天的吃饭和路费了 希望我第二天就可以来 还说给我这么好的一个学习机会 应该珍惜感谢他

点赞 评论 收藏
分享
点赞 评论 收藏
分享