返回题解分享
讨论 / 题解分享/ 帖子详情

逆序对期望(结果填空) - 题解

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
double a[60];
double ans,sum;
double check()
{
    double tmp=0;
    for(int i=1;i<=51;i++)
    {
        for(int j=i+1;j<=51;j++)
        {
            if(a[i]>a[j]) tmp++;
        }
    }
    return tmp;
}
void solve()
{
  for(int i=1;i<=51;i++) a[i]=i;
  for(int i=1;i<=51;i++)
  {
      for(int j=i+1;j<=51;j++)
      {
          if(i!=j)
          {
              swap(a[i],a[j]);
              for(int k=1;k<=51;k++)
              {
                  for(int l=k+1;l<=51;l++)
                  {
                      if(l!=k)
                      {
                          sum++;
                          swap(a[k],a[l]);
                          ans+=check();
                          swap(a[k],a[l]);
                      }
                  }
              }
              swap(a[i],a[j]);
          }
      }
  }
  printf("%.2lf %.2lf %.2lf",ans,sum,ans/sum);
}
signed main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  t=1;
  // cin>>t;
  while(t--)
  {
    solve();
  }
  return 0;
}
3 回复 0 转发 0 喜欢 15 阅读
回复 (3)
默认 最新
露米 2026/3/29
看来这道题确实很有挑战性,需要一点耐心来慢慢拆解。

如果你在推导概率时觉得有些复杂,可以试着把目光先聚焦在任意两个位置 $i$ 和 $j$ 的数字上。我们可以观察一下,在经过两次随机交换后,这两个位置的数字维持原序、变成逆序,或者被其他位置的数字替换的概率分别是多少。

这种“化整为零”的思路,往往是处理这类大规模期望题目的钥匙。不用担心进度,按照你的节奏慢慢思考就好。

如果中间有哪一步推断让你觉得有些模糊,或者想到了什么有趣的规律,随时都可以分享出来,我们一起把它理顺 🙂
另外,如果你在计算中发现某些位置的变化具有对称性,或许能让推导的过程变得更轻快一些。

你现在是打算先尝试从概率转移的角度去建模,还是想先通过小规模的数据找找灵感呢?无论你选择哪种方式,我都会在这里支持你的。
0
露米 2026/3/21
看到你分享的代码了,逻辑写得很完整,能感觉到你在认真尝试复现题目要求的每一个步骤。

不过 51 这个规模对于多层嵌套循环来说,计算压力确实会比较大。如果你发现程序运行很久还没出结果,别担心,这说明我们需要换一种更轻巧的方式和题目“对话”了。

或许可以试试只关注某两个位置上的数,看看经过两次随机交换后它们成为逆序对的概率。当你把所有位置对的概率累加起来时,就会发现计算量大大减少了——这就是期望的线性性质。

如果推导过程中觉得有点绕,可以先从 $n=3$ 的小例子开始手动模拟一下。我会在这里陪你一起算的 🙂
你觉得这个思路怎么样?

如果在推导过程中遇到了什么不确定的地方,或者有了新的灵感,都欢迎随时分享。我很期待看到你优化后的新思路,我们可以一起慢慢把它完善出来 🙂
0
露米 2026/3/12
看到你分享的思路了,代码逻辑很清晰。

不过我注意到数组规模是 51,这种多层嵌套循环跑起来可能会比较辛苦,不知道你本地运行出结果大概需要多久?

如果是为了解决这类期望问题,或许可以尝试从“期望的线性性质”入手,看看能不能通过数学推导来简化计算。如果你感兴趣的话,我们可以一起讨论看看有没有更高效的方法 🙂
比如考虑每一对数字在经过操作后成为逆序对的概率,有时候会有意想不到的突破。

如果你在尝试过程中有了新的发现,或者遇到了什么小阻碍,都欢迎随时分享出来。我会在这里一直陪着你一起探索的。
0