阿里秋招 7月24日 笔试题 回顾 (吃烧饼 开关灯)
程序员文章站
2022-06-27 17:13:46
阿里秋招 7月24日 笔试题 回顾题目一 吃烧饼题目一 开关灯题目一 吃烧饼解题思路:dp问题,当前的饼数不能大于之前最小的,最后求和即可陷阱:int大小不够#include #include #include using namespace std;int main(){vector cakes;size_t plateNums{};std::...
题目一 吃烧饼
假设有 n 个盘子,第 I 个盘子上有 个烧饼,参赛者每次选择 1 ~ n 的整数 x ,将1 ~x 每个盘子都吃掉一个烧饼。如果其中某个盘子为空,则这个 x 不可选。
如果可以一直吃,请问一共能够吃掉多少个烧饼?
输入
3
2 1 3
输出
4
解题思路:dp问题,当前的饼数不能大于之前最小的,最后求和即可
陷阱:int大小不够
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<long long> cakes;
size_t plateNums{};
std::cin >> plateNums;
for (size_t i = 0; i < plateNums; ++i)
{
long long tmp;
cin >> tmp;
cakes.push_back(tmp);
}
for (size_t i = 1; i < cakes.size(); i++)
{
cakes[i] = std::min(cakes[i - 1], cakes[i]);
}
long long sum{};
for (auto &num : cakes)
sum += num;
cout << sum;
return 0;
}
题目一 开关灯
N 行 L 列的长方形灯阵, L 个开关,按下第 i 个开关可以改变第 i 列所有灯的状态(亮→灭,灭→亮),而且不同行可以随意交换。
给出初始状态即最终状态。计算能否通过改变开关完成转换,如果可以,输出最少次数,否则输出Impossible。一共有m组(例子中m=3)
输入
3
3 2
01 11 10
11 00 10
2 3
101 111
010 001
2 2
01 10
10 01
输出
1
impossible
0
解题思路:异或问题,且为完全匹配。
#include<iostream>
#include <vector>
long long toBinary(long long num)
{
if (num) return num % 10 + 2 * toBinary(num / 10);
else return 0;
}
long long toCnt(long long num)
{
long long sum{};
while (num)
{
sum += num % 2;
num /= 2;
}
return sum;
}
int main()
{
int group{};
std::cin >> group;
for (int i = 0; i < group; i++)
{
std::vector<long long> start, end;
long long minSwitchMode = LLONG_MAX;
int n{}, L{};
std::cin >> n >> L;
long long num{};
for (size_t j = 0; j < n; j++)
{
std::cin >> num;
start.push_back(toBinary(num));
}
for (size_t j = 0; j < n; j++)
{
std::cin >> num;
end.push_back(toBinary(num));
}
for (size_t j = 0; j < start.size(); j++)
{
bool noMatch = true;
std::vector<bool>visited(n, false);
long long switchMode = start[j] ^ end[0];
visited[j] = true;
for (size_t k = 1; k < end.size(); k++)
{
noMatch = true;
for (size_t l = 0; l < start.size(); l++)
{
if (!visited[l] && switchMode == (start[l] ^ end[k]))
{
noMatch = false;
visited[l] = true;
break;
}
}
if (noMatch) break;
}
if (noMatch) continue;
minSwitchMode = toCnt(switchMode) < minSwitchMode ? toCnt(switchMode) : minSwitchMode;
}
if (minSwitchMode == LLONG_MAX)
std::cout << "Impossible\n";
else
std::cout << minSwitchMode << std::endl;
}
return 0;
}
本文地址:https://blog.csdn.net/weixin_43290523/article/details/107592136