大疆笔试A卷
人生第一次AK😂虽然代码写的惨不忍睹，还是记录一下吧
1.咖啡机解bug题（单纯的解数学题，最后要记得向上取整）
#include<iostream>
#include<vector>
using namespace std;
int process(vector<float> &arr, int A, int X)
{
float totaltime = X * 60;
float yushu;
int index = arr.size();
float res = 0;
for (int i = 0; i < arr.size(); i++)
{
if (totaltime > 0&&totaltime>=(arr[i]/A))
{
totaltime -= arr[i]/A;
res += arr[i]/A;
}
else if (totaltime > 0 && totaltime < (arr[i] / A))
{
index = i + 1;
yushu = arr[i] - totaltime*A;
res += totaltime;
break;
}
else if (totaltime <= 0)
{
index = i;
break;
}
}
res += yushu;
while (index < arr.size())
{
res += arr[index++];
}
if (res > (int)res)
res = (int)res+1;
return res > 480 ? 0 : res;
}
int main()
{
int N, A, X;
cin >> N >> A >> X;
vector<float> arr;
for (int i = 0; i<N; i++)
{
float temp;
cin >> temp;
arr.push_back(temp);
}
int res = process(arr, A, X);
cout << res << endl;
}
2.零食背包问题
#include<iostream>
#include<vector>
using namespace std;
int procss(vector<int> &price, vector<int> & manyi, vector<int> & amount,int T,int N)
{
int *dp = new int[T + 1]();
for (int i = 0; i < N; i++)
{
for (int j = T; j >= 0; j--)
{
for (int jian = 0; jian <= amount[i] && jian*price[i] <= j; jian++)
{
dp[j] = dp[j] < (dp[j - jian*price[i]] + jian*manyi[i]) ? dp[j - jian*price[i]] + jian*manyi[i] : dp[j];
}
}
}
return dp[T];
}
int main()
{
int N, T;
cin >> N >> T;
vector<int> price;
vector<int> manyi;
vector<int> amount;
for (int j = 0; j<N; j++)
{
int v, i, c;
cin >> v >> i >> c;
price.push_back(v);
manyi.push_back(i);
amount.push_back(c);
}
int res = procss(price, manyi, amount, T,N);
cout << res << endl;
}
3.字符串路径匹配（用的回溯方法，为了能按首字母排序还傻傻的写了个快排😂）
#include<iostream>
#include<vector>
#include<string>
using namespace std;
void swap(vector<string> &arr, int x, int y)
{
string temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
int* Quick(vector<string> &arr, int L, int R)
{
int p1 = L - 1;
int p2 = R;
int index = L;
string p = arr[R];
while (index < p2)
{
if (arr[index][0] < p[0])
{
swap(arr, index, p1 + 1);
p1++;
index++;
}
else if (arr[index][0] > p[0])
{
swap(arr, index, p2 - 1);
p2--;
}
else
{
index++;
}
}
swap(arr, R, p2);
p2++;
return new int[2]{ p1 + 1,p2 - 1 };
}
void QuickSort(vector<string> &arr, int L, int R)
{
if (arr.size() <= 1 || L >= R)
return;
int part = rand() % (R - L + 1) + L;
swap(arr, part, R);
int *res = Quick(arr, L, R);
QuickSort(arr, L, res[0] - 1);
QuickSort(arr, res[1] + 1, R);
}
bool digui(vector<vector<char>> &arr,int i,int j,int row,string str,int index,int fangxiang)
{
if (index == str.size())
return true;
if (i < 0 || j < 0||i>=row||j>=arr[i].size())
return false;
if (arr[i][j] == str[index])
{
arr[i][j] = '1';
bool res1 = (!(fangxiang==1))&&digui(arr, i + 1, j, row,str, index + 1,3);
bool res2 = (!(fangxiang == 3)) && digui(arr, i - 1, j, row,str, index + 1,1);
bool res3 = (!(fangxiang == 2)) && digui(arr, i, j + 1, row,str, index + 1,0);
bool res4 = (!(fangxiang == 0)) && digui(arr, i, j - 1, row,str, index + 1,2);
return res1 || res2 || res3 || res4;
}
return false;
}
bool isin(vector<vector<char>> &arr,string str)
{
int row = arr.size();
int index = 0;
bool res = false;
for (int i = 0; i < row; i++)
{
int col = arr[i].size();
for (int j = 0; j < col; j++)
{
if (arr[i][j] == str[index])
{
vector<vector<char>> next = arr;
res = digui(next,i, j, row,str, index,-1);
if (res)
return res;
}
}
}
return res;
}
void process(vector<vector<char>> &arr, vector<string> &ss)
{
int row = arr.size();
int col = arr[0].size();
vector<string> res;
for (auto s : ss)
{
string str = s;
if (isin(arr, str))
{
res.push_back(str);
continue;
}
}
if (res.size() == 0)
{
cout << "" << endl;
return;
}
for (auto s : res)
{
cout << s << endl;
}
}
int main()
{
int N;
cin >> N;
vector<vector<char>> arr;
for (int i = 0; i<N; i++)
{
string s;
cin >> s;
vector<char> temp;
for (int j = 0; j<s.size(); j++)
{
temp.push_back(s[j]);
}
arr.push_back(temp);
}
int M;
cin >> M;
vector<string> ss;
for (int i = 0; i<M; i++)
{
string s;
cin >> s;
ss.push_back(s);
}
QuickSort(ss, 0, ss.size() - 1);
process(arr, ss);
}
