Codeforces Round #728 (Div. 2)题解(A-C)

被B卡了大半场,结果C一下就看出来了。
最近期末考试+D通过人数才两位,大概率不去补。

A. Pretty Permutations

题意

有n只猫,编号为1,2,3,4,……,n排成一排。现在给这些猫重新排序,让每只猫尽可能移动最短的距离,输出排序后的编号顺序。

题解

签到题,如果n是偶数直接1,2互换、3,4互换……。如果是奇数,前面的和偶数一样,后三个顺序为n,n-2,n-1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        ll n;
        cin>>n;
        if(n%2==0){
            for(int i=1;i<=n;i++){
                if(i%2==1) cout<<i+1<<" ";
                else cout<<i-1<<" ";
            }
        }
        else{
            for(int i=1;i<=n-3;i++){
                if(i%2==1) cout<<i+1<<" ";
                else cout<<i-1<<" ";
            }
            cout<<n<<" "<<n-2<<" "<<n-1<<" ";
        }
        cout<<endl;
    }
    return 0;
}

B. Pleasant Pairs

题意

给出n个不同数的数组a,求在j>i的条件下,满足a[i]* a[j]=i+j的(i,j)数量。

题解

假设我们已知i和a[i],只有当i+j是a[i]的倍数时,条件才可能成立。所以,我们从num[i]-(i%num[i])开始遍历,遍历步长为num[i]。这样可以保证i+j一定是a[i]的倍数。可以推断出a[i]越大,遍历的次数越少。遍历次数为n+\frac{n}{2}+\frac{n}{3}+\frac{n}{4}……+1,最坏情况下是1166750次。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        set<pair<int,int>> re;
        ll n;
        cin>>n;
        ll num[n+1];
        for(int i=1;i<=n;i++){
            cin>>num[i];
        }
        for(ll i=1;i<=n;i++){
            ll j;
            if(i<num[i]) j=num[i]-i;
            else j=(num[i]-(i%num[i]));
            if(j==0)j=num[i];
            //cout<<num[i]<<" "<<i<<" "<<j<<endl;
            for(;j<=n;j+=num[i]){
                if(i==j) continue;
                if(i+j==num[i]*num[j]) {
                    if(re.count({num[j],num[i]})==0&&re.count({num[i],num[j]})==0) {
                        re.insert({num[i],num[j]});
                        //cout<<i<<" "<<j<<endl;
                    }
                }
            }
        }
        cout<<re.size()<<endl;
    }
    return 0;
}

C. Great Graphs

题意

给出一张有向图从1号结点分别到1-n号节点消耗的最短边权(边权可以有负)。构造一张有向图,在满足每个方向只有一条边的情况下,使得边权总和最小。

题解

首先排序,然后前缀和。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        ll n,s;
        cin>>n;
        vector<ll> num;
        for(int i=0;i<n;i++){
            cin>>s;
            num.push_back(s);
        }
        if(n<=2){
            cout<<0<<endl;
            continue;
        }
        ll re=0;
        sort(num.begin(),num.end());
        ll q=num[0],j=1;
        for(int i=2;i<num.size();i++){
            re+=num[i]*j-q;
            j++;
            q+=num[i-1];
        }
        cout<<-re<<endl;
    }
    return 0;
}

题目来源于https://codeforces.com/contest/1541

知识共享许可协议
Text is available under CC BY-NC-SA 4.0 unless otherwise stated.

除非特殊声明,本站所有内容均以 CC BY-NC-SA 4.0协议授权。
上一篇
下一篇