目錄

• 3660. 最短時間 【難度: 簡單 / 知識點: 思維】
• 3661. 重置數列 【難度: 簡單 / 知識點: 暴力】
• 3662. 最大上升子序列和 【難度: 難 / 知識點: DP 樹狀數組 離散化】

3660. 最短時間 【難度: 簡單 / 知識點: 思維】

看四個角到這個點的最遠距離

#include<bits/stdc++.h> using namespace std; int main(void) {int t; cin>>t;while(t--){int n,m,r,c; cin>>n>>m>>r>>c;cout<<max(abs(1-r),abs(n-r))+max(abs(m-c),abs(1-c))<<endl;}return 0; }

3661. 重置數列 【難度: 簡單 / 知識點: 暴力】

總的數據范圍很小

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],n,k; int main(void) {int t; cin>>t;while(t--){cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];int ans=1e9;for(int i=1;i<=100;i++){int cnt=0;for(int j=1;j<=n;j++) if(a[j]!=i) cnt++,j=j+k-1;ans=min(ans,cnt);}cout<<ans<<endl;}return 0; }

3662. 最大上升子序列和 【難度: 難 / 知識點: DP 樹狀數組 離散化】

#include<bits/stdc++.h> using namespace std; typedef long long int LL; const int N=1e5+10; int n; int w[N]; LL tr[N]; vector<int>xs; LL f[N]; int get(int x) {return lower_bound(xs.begin(),xs.end(),x)-xs.begin()+1; } int lowbit(int x) {return x&-x; } void add(int x,LL v) {for(int i=x;i<=n;i+=lowbit(i)) tr[i]=max(tr[i],v); } LL query(int x) {LL res=0;for(int i=x;i;i-=lowbit(i)) res=max(res,tr[i]);return res; } int main(void) {cin>>n;for(int i=0;i<n;i++){cin>>w[i];xs.push_back(w[i]);}sort(xs.begin(),xs.end());xs.erase(unique(xs.begin(),xs.end()),xs.end());LL res=0;for(int i=0;i<n;i++){int k=get(w[i]);f[i]=query(k-1)+w[i];//以w[i]結尾的上升子序列的最大和res=max(res,f[i]);add(k,f[i]);}printf("%lld",res);return 0; }

總結

以上是生活随笔為你收集整理的Acwing第 3 场周赛【完结】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。