训练情况
赛后反思
C题猜了个假结论WA4，每次选择度最多的删掉，在连续三个度都是最大的情况下，删中间的会寄
A题
有点前缀和的感觉，\([1,l]\) 互质个数为 \(l\),\([1,r]\) 互质个数为 \(r\)，所以区间 \([l,r]\) 的个数就是 \(r-l\)，特判一下 \(l=1,r=1\) 的情况答案是 \(1\)
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve(){
int l,r; cin>>l>>r;
if(l == 1 && r == 1){
cout<<1<<endl;
return;
}
cout<<r-1-l+1<<endl;
}
signed main(){
int T; cin>>T; while(T--)
solve();
return 0;
}
B题
子序列翻转，我们发现不能左右区间都选，这样翻转是无效操作，所以只能一边在 \([l,r]\)，一边不在 \([l,r]\) 中去选，我们发现答案只能在 \([1,r]\) 和 \([l,n]\) 中间取 \(r-l+1\) 个数，取最小的几个数即可
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve(){
int n,l,r; cin>>n>>l>>r;
vector<int> a(n + 1);
for(int i = 1;i<=n;i++) cin>>a[i];
vector<int> b,c,d;
for(int i = 1;i<=n;i++){
if(i<l) b.push_back(a[i]);
else if(i>r) c.push_back(a[i]);
else d.push_back(a[i]);
}
priority_queue<int,vector<int>,greater<int>> pq1;
priority_queue<int,vector<int>,greater<int>> pq2;
for(int i = 0;i<d.size();i++) pq1.push(d[i]),pq2.push(d[i]);
for(int i = 0;i<b.size();i++) pq1.push(b[i]);
for(int i = 0;i<c.size();i++) pq2.push(c[i]);
int ans1 = 0,ans2 = 0;
for(int i = 1;i<=r-l+1;i++){
ans1 += pq1.top();
ans2 += pq2.top();
pq1.pop(); pq2.pop();
}
cout<<min(ans1,ans2)<<endl;
}
signed main(){
int T; cin>>T; while(T--)
solve();
return 0;
}