[非官方题解]排位赛#4题解（1-5）
2024-01-16 20:19:37
发布于：浙江
本次比赛，题目较为简单，第二题、第三题的难度明显下降，基本上同学都AC了。
接下来是本人撰写的非官方题解！
注：4-6题请在[非官方题解]ACGO排位赛#4题解.2中观看
T1 夺宝升级
本题我的第一反应就是一个个判断是否通过，通过就加等级。
但是其实还有一个重要点：可以选择顺序来闯关。
所以我们只要把关卡按照等级下限从小到大排序一个个闯就行了。
这里不推荐使用sort函数，较为复杂。
本代码使用冒泡排序：
:
#include<bits/stdc++.h>
using namespace std;
int a[1001],b[1001];
int main(){
int t;
cin>>t;
for(int i=1;i<=t;i++){
int n,k;
cin>>n>>k;
for(int j=1;j<=n;j++) cin>>a[j];
for(int j=1;j<=n;j++) cin>>b[j];
for(int j=1;j<=n;j++){
for(int l=1;l<=n-1;l++){
if(a[l]>a[l+1]){
swap(a[l],a[l+1]);
swap(b[l],b[l+1]);
}
}
}
for(int j=1;j<=n;j++) if(k>=a[j]) k+=b[j];
cout<<k<<endl;
}
return 0;
}
T2 公约数序列
此题我们来分析一下：
首先，[l,r]区间有三种情况：
① l、r中有一个偶数，一个奇数，那么一共就有偶数个数字，一半奇、一半偶。
② l、r都是奇数，那么一共有奇数个数，奇数的个数比偶数的个数多1
③ l、r都是偶数，那么一共有偶数个数，偶数的个数比奇数的个数多1
先看第一种情况，如果k大于奇数的个数（总个数一半），就可以把奇数全消掉（可以一个奇一个偶相乘或者多个奇与多个偶相乘）
第二种，也是如果k大于奇数的个数（总个数+1除以2），就可以把奇数全消掉（同上），
第三种，也一样，如果k大于奇数的个数（总个数-1除以2，就可以把奇数全消掉（同上），
所以，写出完整代码：
#include<bits/stdc++.h>
using namespace std;
int t;
int main(){
cin>>t;
for(int i=1;i<=t;i++){
int l,r,k;
cin>>r>>l>>k;
if(k==0){
if(l==r){
if(l==1) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
else cout<<"NO"<<endl;
}
else if(k>=l-r) cout<<"YES"<<endl;
else{
if(l%2==1&&r%2==0||l%2==0&&r%2==1){
if(2*k>=l-r+1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
else if(l%2==0&&r%2==0){
if(k>=(l-r-2)/2) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
else{
if(k>=(l-r)/2) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
}
return 0;
}
T3 树枝
这里我给出我的代码(2个），具体可以看官方题解官方题解Q1-4
#include<bits/stdc++.h>
using namespace std;
long long cT(vector<int>& s) {
sort(s.begin(), s.end());
int n=s.size();
long long count=0;
int maxSum=s[n-1]+s[n-2];
vector<int> f;
for(int i=0;i<n;i++) if(s[i]<maxSum) f.push_back(s[i]);
int m=f.size();
for(int l=0;l<m-2;l++) {
int r=l+2;
int max_i=r;
for(int i=l+1;i<m-1;i++) {
while(r<m&&f[l]+f[i]>f[r]) r++;
count+=r-i-1;
max_i=r;
}
if(l+1==max_i) break;
else r = max_i;
}
return count;
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int> s(n);
for(int i=0;i<n;i++) cin>>s[i];
long long res=cT(s);
cout<<res<<endl;
}
return 0;
}
(奇怪的代码）
还有一极其简单的代码（通俗易懂，不用解释）
:
#include<bits/stdc++.h>
using namespace std;
int a[5010];
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
long long ans=0;
for(int i=0;i<n-2;i++){
for(int j=i+1,k=i+2;j<n-1;j++){
int tmp=a[i]+a[j];
while(k<n&&tmp>a[k]) k++;
ans+=k-j-1;
}
}
cout<<ans<<endl;
}
return 0;
}
T4 画板
此题最简单的做法就是判断是否存在一组平行线和另一组斜率不同的平行线即可（后面还有一种）
(具体看官方题解官方题解T1-4）
当然，还有一种比较复杂但易懂的方法（考试时这么写的然后90分了，有个点没注意到，但可以AC）：
首先，我们输入每组样例后，先判断n（线段数）是否大于等于3，如果小于3就直接输出No
如果上述条件符合，那么先遍历每条一次函数，如果k，b都和前面的某一条一次函数相同，就把这个函数删除，把后面的函数前移一位，然后把n减1（就是这我没注意到，第二个测试点中100个测试组错了一个）
然后遍历每条函数，如果有一个数字在k中出现了n-1及以上次（也就是只有1条不与他们平行），就输出No;
如果上述通过，从-100到100遍历x，如果所有函数在x这个点的y值都想同（交于同一点），输出No；
如果上述通过，遍历每条函数，如果每条函数的b值都相同（当x=0时，他们的y值都是b，交于同一点，此步可以省去,只是为了帮助整理每种情况）,输出No；
如果上述通过，遍历每条函数的b/k的值，如果都相同（交于同一点，同样可以舍去），输出No；
如果上述全部通过，输出Yes;
#include<bits/stdc++.h>
using namespace std;
int k[1010],b[1010];
double z[1010];
int main(){
int t;
cin>>t;
for(int jjbb=1;jjbb<=t;jjbb++){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>k[i]>>b[i];
}
if(n==1||n==2) cout<<"No"<<endl;
else{
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
if(k[i]==k[j]&&b[i]==b[j]){
for(int l=i;l<=n;l++){
k[l]=k[l+1],b[l]=b[l+1];
}
n--;
}
}
}
bool flag1=false;
for(int j=-100;j<=100;j++){
int s=0;
for(int i=1;i<=n;i++){
if(k[i]==j) s+=1;
}
if(s>=n-1)flag1=true;
}
if(flag1==true){
cout<<"No"<<endl;
}
else{
bool flag2=true;
for(int jj=-100;jj<=100;jj++){
bool flagshit=true;
int s=k[1]*jj+b[1];
for(int i=1;i<=n;i++){
if(k[i]*jj+b[i]!=s) flagshit=false;
}
if(flagshit==true){
flag2=false;
}
}
if(flag2==false) cout<<"No"<<endl;
else{
bool flag3=false;
for(int i=1;i<=n-1;i++){
if(b[i]!=b[i+1]) flag3=true;
}
if(flag3==false){
cout<<"No"<<endl;
}
else{
bool flag4=false;
for(int i=1;i<=n;i++){
z[i]=b[i]/k[i];
}
for(int i=1;i<=n-1;i++){
if(z[i]!=z[i+1]) flag4=true;
}
if(flag4==false){
cout<<"No"<<endl;
}
else{
if(n==1||n==2) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
}
}
}
}
}
}
return 0;
}
T5:排列
这里首先给出一种70分的做法：
遍历k次数组，找出第一个数字与编号不匹配且整齐度最大的位置，然后再找出与那个位置编号匹配的数的位置，使用swap交换即可。
最后遍历数组算出最大整齐度。
#include<bits/stdc++.h>
using namespace std;
int n,k,a[100010];
long long v[100010];
long long ans=0;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>v[i];
bool flag=true;
for(int i=1;i<=n;i++){
if(v[i]!=1) flag=false;
}
for(int i=1;i<=k;i++){
int max1=-1,p;
for(int j=1;j<=n;j++){
if(a[j]!=j&&v[j]>max1){
max1=v[j];
p=j;
}
}
for(int j=1;j<=n;j++){
if(a[j]==p) swap(a[j],a[p]);
}
}
for(int i=1;i<=n;i++){
if(a[i]==i) ans+=v[i];
}
if(flag==true)cout<<ans+1;
else cout<<ans;
return 0;
}
然后是AC的做法（转自官方题解）：
如果不考虑整齐度，交换元素让所有元素归位，我们可以考虑让每个元素直接回到他的位置试试看。以样例[2, 1, 4, 5, 3]为例，为了方便我们令t为待交换元素（搁置元素）。
令 t = 2，放回到它的位置 i = 2，此时 a[2] = 1，把 1 设为搁置元素。
此时 t = 1，数组为 [2, 2, 4, 5, 3]；
然后我们再将搁置元素 t = 1 放到 i = 1，此时数组为 [1, 2, 4, 5, 3]，下标为 1, 2 的元素已归位。
同理我们可以使用以上方法使剩余元素归位。
不难发现，每一轮交换总是从一个位置开始，然后回到 结束，形成一个环。
每个元素只会与其所在环内的元素交换，且让一个有个元素的环的所有元素归位，只需要次交换。
接着我们考虑交换次数受限制的情况。比如对于一个大小为 的环，我们可以交换元素的次数只有次，那么对于这个大小为的环，我们最多只能使个元素归位。
由于题目中我们让每个元素归位获得的整齐度是不一样的，所以对于一个环我们如果只能归位有限个元素，显然应该选择优先归位权重（ *整齐度 *）更大的元素。所以归位一个环内的元素时，可以将环内元素按照权重从大到小排序，优先归位权重更大的元素。
接下来问题便可以转化成：数组中不在自己位置上的元素形成个环，对于每个环可以选择归位若干个元素，限制为
那么由于每个元素归位的权重不同，对于每个大小为 的环，实际上我们只需要关注在环中选择归位元素的数量即可，不需要枚举环中具体归位哪些元素。即选择 环中归位的元素数量 即可。
那么这里问题便转化为了一个 分组背包 问题：
有个环，最多操作 次。
每个环可以选择归位元素的数量。
环选择归位 个元素的操作次数为
获得的 整齐度 为即环 中权重最大的 个元素的 整齐度 之和。
求解每个环选择归位多少个元素，操作次数总和不超过 ，且获得的 整齐度 最大。
对于本题的答案就是分组背包处理完后的答案加上已经在位置上的元素的 整齐度 之和
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, k;
cin >> n >> k;
vector<int> a(n), v(n);
for (auto &x : a) cin >> x, --x;
for (auto &x : v) cin >> x;
vector<i64> dp(k+1);
i64 res = 0;
vector<int> st(n);
for (int i = 0; i < n; ++i) {
// 位置正确直接累加整齐度
if (a[i] == i) {
res += v[i];
continue;
}
// 已处理过的环内元素跳过
if (st[i] == 1) continue;
// 处理环内元素
vector<i64> sum;
int j = i;
do {
sum.push_back(v[j]);
st[j] = 1;
j = a[j];
} while (j != i);
// 从大到小排序并求前缀和
sort(sum.rbegin(), sum.rend());
partial_sum(begin(sum), end(sum), begin(sum));
// 分组背包
int m = sum.size();
for (int i = k; i > 0; --i) {
for (int j = min(m - 1, i); j > 0; --j)
if (j == m - 1)
dp[i] = max(dp[i], dp[i-j] + sum[j]);
else
dp[i] = max(dp[i], dp[i-j] + sum[j-1]);
}
}
cout << res + dp[k] << '\n';
return 0;
}
由于字数到限制，第六题会分另一个题解
有帮助，赞一个