【自動車演算法崗】差了5秒鐘，終究還是沒能AK呀，第三題一開始只對了18%的資料，在還有20分鐘的時候，發現題目看錯了，碼到 cout<<ans<<endl; 的時候發現還剩5秒了，趕緊從ide復制到代碼框內，游標剛剛放到保存代碼上，發現按不動了，好家伙，時間截止了！！！
筆試題分為兩大部分：4道演算法題+3道人工智能相關知識的多選題，限時兩個小時，每個子部分提交后可以再回傳修改，這點還是很人性化的，不像有的筆試，子部分提交后就無法回傳修改了，就不是那么的友好了，
題目大概都是力扣 [mid~hard] 的難度，下面切入正題吧！由于晚上還有一場筆試，具體的思路證明之類的以后再補了哈，先貼一下Code
第一題_四川麻將
題意
玩法是摸完牌之后選擇3張花色一樣的牌按某種順序換給其他人，為了盡可能破壞對手的游戲體驗，每次都會選擇不連續的3張牌換出去，比如手上有 {1 4 5 6 8} 這5張條子，則可能會選擇 {1 5 8} 這三張條子換出去，
把這個問題進行了簡化，現在給你一個可重集合，并希望你從中選出一個盡可能大的子集使得其中沒有兩個數是 “連續” 的，
輸入輸出描述
輸入
第一行一個整數n(1<=n<=100000)，代表可重集大小
第二行n個空格隔開的整數(范圍在1到200000之間)，代表可重集
輸出
輸出滿足條件的最大子集的大小
樣例資料
輸入
6
1 2 3 5 6 7
輸出
4
AC_Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10, M = 2e5+10;
int n, a[N], dp[M];
int main() {
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++) dp[a[i]] = 1 ;
for(int i=1; i<M; i++) {
if(dp[i]) dp[i] = max(dp[i],dp[i-2]+1);
dp[i] = max(dp[i],dp[i-1]);
}
cout << dp[M-1] << endl;
return 0;
}
第二題_翻轉最大子段和
題意
最大子段和是力扣上比較經典問題，這里對它進行了改編，允許在求解該問題之前翻轉這個陣列的連續一段，如翻轉 (1,2,3.45.6) 的第3個到第5個元素組成的子陣列得到的是 (1,2,5,4,3,6)，求翻轉后該陣列的最大子段和最大能達到多少，
輸入輸出描述
輸入
第一行—個正整數n，(1<=n<=100000)，代表陣列長度
第二行n個空格隔開的整數 (-1000<=ai< =1000)，代表陣列元素大小
輸出
求翻轉后所得陣列的最大子段和
樣例資料
輸入
6
-1 3 -5 2 -1 3
輸出
7
AC_Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10, inf = 1e9+10;
int n, a[N], p[N], s[N];
void solve() {
p[0] = -inf;
int sum=0;
for(int i=1; i<=n; i++) {
sum = max(0, sum) + a[i];
p[i] = max(p[i-1], sum);
}
s[n+1]=-inf; sum=0;
for(int i=n; i>=1; i--) {
sum = max(0, sum) + a[i];
s[i] = max(s[i+1], sum);
}
}
int main() {
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
solve();
int ma = *max_element(p+1, p+n+1);
for(int i=1; i<n; i++)
ma = max(ma, p[i]+s[i+1]);
cout << ma << endl;
return 0;
}第三題_切豆腐
題意
為了切出更均勻的豆腐，想知道每一次下刀之后切出來的豆腐塊中體積最大的那塊有多大，
輸入輸出描述
第一行兩個整數n,m (1<=n,m<=1000)，代表最開始長寬高均為n厘米，總共切了m刀，
第二行m個小寫字母，每個字母都是 x,y,z 中的一個，第i個代表刀垂直于哪個坐標軸，
第三行m個大于0且小于n的正整數，第i個代表第i刀所在平面到豆腐的右上角 (或者任選一個角并固定，無論選哪個角答案均相同) 的距離，
保證切的時候豆腐不會產生形變且不會產生位移，每次下刀都會把整塊豆腐切開，不存在切到一半收刀，切出來的每塊小豆腐都是邊長為正整數的長方體，
樣例資料
輸入
2 3
x y z
1 1 1
輸出
4
2
1
AC_Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10, M = 2e5+10;
int n, m;
int main()
{
cin >> n >> m;
vector<string> op(m+1);
for(int i=1; i<=m; i++) cin>>op[i];
vector<int> v(m+1);
for(int i=1; i<=m; i++) cin>>v[i];
multiset<int> x,y,z;
x.insert(0), x.insert(n);
y.insert(0), y.insert(n);
z.insert(0), z.insert(n);
for(int i=1; i<=m; i++)
{
if(op[i][0]=='x') x.insert(v[i]);
else if(op[i][0]=='y') y.insert(v[i]);
else if(op[i][0]=='z') z.insert(v[i]);
}
int mx=0, my=0, mz=0, pre=0;
for(auto it:x) mx = max(mx,it-pre), pre=it;
pre=0;
for(auto it:y) my = max(mx,it-pre), pre=it;
pre=0;
for(auto it:z) mz = max(mx,it-pre), pre=it;
vector<int> ans(m+1);
for(int i=m; i>=1; i--)
{
ans[i] = mx*my*mz;
if(op[i][0]=='x')
{
auto it = x.find(v[i]);
int suf = *(++it);
it--;
int pre = *(--it);
mx = max(mx, suf-pre);
x.erase(v[i]);
}
if(op[i][0]=='y')
{
auto it = y.find(v[i]);
int suf = *(++it);
it--;
int pre = *(--it);
my = max(my, suf-pre);
y.erase(v[i]);
}
if(op[i][0]=='z')
{
auto it = z.find(v[i]);
int suf = *(++it);
it--;
int pre = *(--it);
mz = max(mz, suf-pre);
z.erase(v[i]);
}
}
for(int i=1; i<=m; i++)
cout << ans[i] << endl;
return 0;
}第四題_區間操作求和
題意
給出一個長度為n的陣列，進行m次陣列上的區間操作，操作包含將區間內所有數加上一個值和查詢一個區間內所有數的和，如果允許重新排列初始陣列中的元素并依次進行操作，則操作中所有查詢區間和的答案之和能夠達到多大?
輸入輸出描述
輸入
第一行有兩個數 n,m(1<=n=<5000,1<=m<=500)，代表陣列長度和操作次數，第二行有n個數，代表初始陣列中的元素，接下來m行每行 1 l r 或 2 l r k，分別代表查詢下標屬于 [l,r] 的元素之和這一揭作和將下標屬于 [l,r] 的元素全部加上定值k，l r k 滿足1<=l<=r<=n，1<=k<=5000
輸出
輸出若允許重新排列初始陣列，進行m次操作后產生的所有輸出之和最大值
樣例資料
輸入
5 5
3 4 2 1 5
1 1 3
2 3 4 2
1 2 4
2 2 3 2
1 3 5
輸出
42
AC_Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10, M = 2e5+10;
int n, m;
int main() {
cin>>n>>m;
vector<ll> a(n+1);
for(int i=1; i<=n; i++) cin>>a[i];
ll ans_sum=0;
vector<ll> cnt(n+1),add(n+1);
for(int i=1; i<=m; i++) {
int op; cin>>op;
if(op==1) {
int l,r;
cin>>l>>r;
for(int i=l; i<=r; i++) cnt[i]++, ans_sum += add[i];
}
else{
int l,r,k;
cin>>l>>r>>k;
for(int i=l; i<=r; i++) add[i] += k;
}
}
sort(a.begin()+1,a.end());
sort(cnt.begin()+1,cnt.end());
for(int i=1; i<=n; i++)
ans_sum += 1LL * cnt[i] * a[i];
cout << ans_sum << endl;
return 0;
}
OVER~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/438074.html
標籤：AI