被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