UVA12004 Bubble Sort 题解

题目链接：Bubble Sort

题意：

\(T \le 1000\) 组询问，每次给定 \(n(1 \le n \le 10^5)\) ，

问 \(1\) 到 \(n\)​ 的 \(n\) 个数的排列中逆序对个数的期望，以分数的形式输出，比如 1/2 。

这题只有入门吗？好好好，我菜就是了，我只会 dp 。

设 \(f_i\) 为 \(i\) 个数的排列的逆序对个数的期望。我们考察 \(i\) 的位置，则 \[ f_i = \frac{1}{i}\left(f_{i-1} + 0\right) + \frac{1}{i}\left(f_{i-1} + 1\right) + \cdots + \frac{1}{i}\left(f_{i-1} + i-1\right) \] 整理一下 \[ f_i = f_{i-1} + \frac{i-1}{2} \] 即（直接把每个 \(f_i\) 全部写出来就能找到规律了） \[ f_i = \frac{i(i-1)}{4} \] 时间复杂度 \(\mathcal{O}(T)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; 
    for(int c = 1; c <= qwq; c++) {
        int n; cin >> n;
        n = n * (n - 1); cout << "Case " << c << ": ";
        if(n % 4 == 0) cout << n / 4 << '\n';
        else if(n % 2 == 0) cout << n / 2 << '/' << 2 << '\n';
        else cout << n << '/' << 4 << '\n';
    }
    return 0;
}