Codeforces Round #728 (Div. 2)

比赛链接：Here

1541A. Pretty Permutations

给定 序列，让每一个数字都不处于原来的位置，但总的移动距离要最小

• 为偶数的情况
• 为奇数的情况

【AC Code】

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int a[110];
    for (int i = 1; i <= 101; ++i)a[i] = i;
    for (int i = 1; i <= 101; i += 2) swap(a[i], a[i + 1]);
    int _; for (cin >> _; _--;) {
        int n; cin >> n;
        if (n & 1) {
            for (int i = 1; i <= n - 2; ++i)
                cout << a[i] << " ";
            cout << n << " " << a[n - 1];
        } else {
            for (int i = 1; i <= n; ++i)
                cout << a[i] << " ";
        }
        cout << '\n';
    }
}

1541B. Pleasant Pairs

问有多少对数 #card=math&code=%28i%2Cj%29) 满足以下条件：

相同题型：ABC206 C - Swappable

枚举所有 的倍数加以判断

注意点：

时间复杂度：)#card=math&code=%5Cmathcal%7BO%7D%28n%C2%B7log%28n%29%29)

【AC Code】

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        ll n; cin >> n;
        vector<ll>a(n + 1);
        for (int i = 1; i <= n; ++i)cin >> a[i];
        ll cnt = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = a[i] - i; j <= n; j += a[i]) {
                if (j <= i) continue;
                else if (a[i] * a[j] == i + j)cnt++;
            }
        cout << cnt << "\n";
    }
}

1541C. Great Graphs

个点和 数组，表示第 个点到第一个点的最短距离。

现在需要进行加边，然后使得所有边权和最小（可加负边）

思路转自码尔泰

很明显其实， 其实可以排个序，对于最后结果并没有影响，之后我们可以考虑对于每个点，只建一条正向道路，使得满足题目条件，然后在满足题目条件的情况下尽可能多地建反向道路，这样可以减小总的边权和。

【AC Code】

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        int n; cin >> n;
        vector<ll>d(n + 1), sum(n + 1);
        for (int i = 1; i <= n; ++i)cin >> d[i];
        ll b = 1e9 + 7;
        sort(d.begin() + 1, d.end());
        for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + d[i];
        ll ans = 0;
        for (int i = 3; i <= n; ++i)
            ans -= d[i] * (i - 2) - sum[i - 2];
        cout << ans << "\n";
    }
}