leetcode第 357/358 场周赛

2817. 限制条件下元素之间的最小绝对差

可能别人有更好的解法，我这写法是不断往线段树中插入数值，每次先插入nums[i-x]，然后搜索（1到i)中的最大值和(i到max)中的最小值去更新ans。

class Solution {
public:struct node{int mx,mn;int lson,rson;};int cnt = 1;void insert(int pos,int l,int r,int d,vector<node>&tree){tree[pos].mx = max(tree[pos].mx,d);tree[pos].mn = min(tree[pos].mn,d);if(l==r)return;int mid = (l+r)>>1;if(d<=mid){if(tree[pos].lson==0){tree[pos].lson = cnt++;tree[cnt-1].mn = (1<<30);}insert(tree[pos].lson,l,mid,d,tree);}else{if(tree[pos].rson==0){tree[pos].rson = cnt++;tree[cnt-1].mn = (1<<30);}insert(tree[pos].rson,mid+1,r,d,tree);}}int getmx(int pos,int l,int r,int L,int R,vector<node>&tree){if(L<=l && r<=R)return tree[pos].mx;int mid = (l+r)>>1;int mx = 0;if(L<=mid && tree[pos].lson)mx = getmx(tree[pos].lson,l,mid,L,R,tree);if(mid<R && tree[pos].rson)mx = max(mx,getmx(tree[pos].rson,mid+1,r,L,R,tree));return mx;}int getmn(int pos,int l,int r,int L,int R,vector<node>&tree){if(L<=l && r<=R)return tree[pos].mn;int mid = (l+r)>>1;int mx = (1<<30);if(L<=mid && tree[pos].lson)mx = getmn(tree[pos].lson,l,mid,L,R,tree);if(mid<R && tree[pos].rson)mx = min(mx,getmn(tree[pos].rson,mid+1,r,L,R,tree));return mx;}int minAbsoluteDifference(vector<int>& nums, int x) {int tnx=0;for(auto i:nums)tnx = max(tnx,i);vector<node>tree(nums.size()<<5);int ans = (1<<30);tree[0].mn = (1<<30);for(int i=0;i<nums.size();++i){if(i-x>=0)insert(0,1,tnx,nums[i-x],tree);int d = getmx(0,1,tnx,1,nums[i],tree);if(d)ans = min(ans,nums[i]-d);d = getmn(0,1,tnx,nums[i],tnx,tree);if(d!=(1<<30))ans = min(ans,d-nums[i]);}return ans;}
};

看了看别人题解，直接用set写是真的牛。自己还是见识短浅了。

2813. 子序列最大优雅度

暴力乱搞，考虑两种极端情况，一种无脑选profit大的，一种优先选不同类型的。
我们先选不同类型的，记录值，然后选profit大的没选过的， 更新一下值，然后选完后就会变成profit前k个的情况。取最大值就行。

class Solution {
public:bool flag[100010];long long findMaximumElegance(vector<vector<int>>& items, int k) {sort(items.begin(),items.end(),[](vector<int>&a,vector<int>&b){return a[0]>b[0];});map<int,int>mp;auto cmp = [](pair<int,int> a,pair<int,int> b){return a.first>b.first;};priority_queue<pair<int,int> ,vector<pair<int,int>>,  decltype(cmp)>que(cmp);long a=0,b=0;int cnt =0;long long tp = 0,dc = 0;long long ans = 0;vector<bool>flag(items.size());int num = 0;for(int i=0;i<items.size();++i){if(dc<k){if(!mp[items[i][1]]){que.push({items[i][0],items[i][1]});mp[items[i][1]] = 1;dc++;flag[i] = 1;tp+=items[i][0];ans = max(ans,tp+dc*dc);num++;}}elsebreak;}for(int i=0;i<k;++i){if(num<k  && flag[i] ==0){tp += items[i][0];num++;}else if(!que.empty() && flag[i] ==0){auto [a,b] = que.top();tp-= a-items[i][0];dc--;que.pop();}ans = max(ans,tp+dc*dc);}return ans;}
};

2812. 找出最安全路径

先通过一遍bfs计算出每一个点的安全系数
然后从（0，0）开始跑bfs，每次选择安全系数最大的点，并记录每条路径中最小的安全系数。

class Solution {
public:struct node{int x,y,val;bool operator<(const node &a)const{return val<a.val;}};int maximumSafenessFactor(vector<vector<int>>& grid) {int n = grid.size();int m = grid[0].size();vector dis(n,vector<int>(m,(1<<30)));queue<pair<int,int>>q;for(int i=0;i<n;++i)for(int j=0;j<m;++j)if(grid[i][j]){dis[i][j] = 0;q.push({i,j});}int f[] = {0,-1,0,1,1,0,-1,0};while(!q.empty()){auto [x,y] = q.front();q.pop();for(int i=0;i<4;++i){int nx = x+f[i<<1];int ny = y+f[i<<1|1];if(nx>=0 && nx<n && ny>=0 &&ny<m){if(dis[nx][ny]>dis[x][y]+1){dis[nx][ny] = dis[x][y]+1;q.push({nx,ny});}}}}vector cost(n,vector<int>(m,0));vector flag(n,vector<bool>(m,0));priority_queue<node>que;que.push({0,0,dis[0][0]});cost[0][0] = dis[0][0];while(!que.empty()){auto u = que.top();que.pop();if(flag[u.x][u.y])continue;flag[u.x][u.y] = 1;for(int i=0;i<4;++i){int nx = u.x+f[i<<1];int ny = u.y+f[i<<1|1];if(nx>=0 && nx<n && ny>=0 &&ny<m){if(cost[nx][ny]<cost[u.x][u.y] && !flag[nx][ny]){cost[nx][ny] = min(cost[u.x][u.y],dis[nx][ny]);que.push({nx,ny,dis[nx][ny]});}}}}return cost[n-1][n-1];}
};

2818. 操作使得分最大

统计每一个数字的最大区间$[L,R]$，满足当$L<=l<=i且i<=r<=R$时，该区间的分数为$nums[i]$,这个区间使用单调栈统计，然后每个$num[i]$可以被使用次数就为$(i-L+1)\ast (R-i+1)$。最后把数字从大到小排序，然后选择k个即可。

class Solution {
public:const int mod = 1e9+7;int maximumScore(vector<int>& nums, int k) {vector<int> score(nums.size());auto calscore = [](int a){int ret = 0;for(int i=2;i*i<=a;++i){if(a%i==0){ret++;while(a%i==0)a/=i;}}if(a!=1)ret++;return ret;} ;for(int i=0;i<nums.size();++i)score[i] = calscore(nums[i]);vector<int>pre(nums.size());vector<int>sa(nums.size(),nums.size());stack<int>ddz;for(int i=0;i<nums.size();++i){while(!ddz.empty() && score[i]>score[ddz.top()]){sa[ddz.top()] = i;ddz.pop();}if(ddz.empty())pre[i] = -1;else pre[i] = ddz.top();ddz.push(i);}auto cmp = [](pair<int,long long>a,pair<int,long long>b){if(a.first==b.first)return a.second<b.second;return a.first<b.first;};priority_queue< pair<int,long long>, vector<pair<int,long long> > , decltype(cmp) > que(cmp);for(int i=0;i<nums.size();++i){que.push({nums[i],(sa[i]-i)*(i-pre[i])});}long long ans = 1;auto qpow = [=](long long a,long long b)->long long{long long ret = 1;while(b){if(b&1) ret = (a*ret)%mod;a = a*a%mod;b>>=1;}return ret;};while(k){auto [x,y] = que.top();que.pop();ans = ans*qpow(x,min(y,1ll*k))%mod;k -= min(y,1ll*k);}return ans;}
};