Codeforces Round 1022 (Div. 2)

Problem - A - Codeforces

看这数据量，算出每个排列来，是不现实的，需要找找规律

来看找规律代码

#include <bits/stdc++.h>
using namespace std;int main() 
{int t;cin >> t;while (t--){int n;cin >> n;vector<int>arr(n);map<int, int>ans;for (int i = 0; i < n; i++){arr[i] = i + 1;}ans[0] = 1;while (next_permutation(arr.begin(), arr.end())){int now = 0;for (int i = 0; i < n; i++){now += abs(arr[i] - i - 1);}ans[now] = 1;}for (auto it : ans){cout << it.first << endl;}}
}

每次ans的值是+2的，我们多测测

通过数学推导，可以发现这些不同值的数量可以通过公式 :

直接计算得出，无需生成所有排列。

#include <iostream>
using namespace std;int main() {int t;cin >> t;while (t--) {int n;cin >> n;cout << (n * n) / 4 + 1 << endl;}return 0;
}