首页 > 其他分享 >P2612 [ZJOI2012] 波浪 题解

P2612 [ZJOI2012] 波浪 题解

时间:2024-11-13 14:21:51浏览次数:1  
标签:le cur 题解 times ZJOI2012 P2612 端点 gets dp

前置知识:连续段 dp

题目链接:P2612 [ZJOI2012] 波浪

随机一个 \(1\) 到 \(n\) 的排列 \(P_{1...n}\),问以下式子的值 \(\le m\) 的概率是多少?

\[|P_1 - P_2| + |P_2 - P_3| + |P_3 - P_4| + ... + |P_{n-1} + P_n| \]

输出一个答案表示概率。保留 \(k\) 位小数。
对于 \(40%\) 的数据,\(n \le 50,k \le 30\)。
对于 \(60%\) 的数据,\(n \le 100,k \le 8\)。
对于全部数据,\(0 \le m \le 2147483647\)。

首先不难想到按位 dp,但是由于是个排列还要状压,肯定行不通。

所以考虑依次放数字 \(1,2,...,n\)。此时不难发现,每个状态是一个连续段,所以考虑连续段 dp

设 \(dp_{i,j,k,p}\) 表示放了 \(i\) 个数字,有 \(j\) 个连续段,贡献为 \(k\),有 \(p\) 个端点被确定了的方案数。由于算的是概率,所以最后乘上 \(n!\) 即可。

但是为什么可以设贡献为状态的呢?

Trick:先把绝对值去掉,然后把每个项拆开成 \(i\) 和 \(i+1\) 的贡献。

由于我们把数字从小往大放,所以绝对值已经去掉了。然后每放一个数,就可以算出该数的贡献了。

然后就直接上连续段 dp(需要一维 \(p\) 因为 \(1\) 和 \(n\) 只有一次贡献):

连续段 dp

令 \(t = dp[i-1][j][k][p]\)。

1. 产生新的段

  • 不产生新端点(即把数放在 \(2\) 到 \(n-1\) 之间)

\[dp[i][j+1][k-2i][p] \gets t \times (j+1-p) \]

  • 产生新端点(即把数放在 \(1\) 或 \(n\))

\[dp[i][j+1][k-i][p + 1] \gets t \times (2 - p) \]

2. 接在某个已有段的两端

  • 不产生新端点(即把数放在 \(2\) 到 \(n-1\) 之间)

\[dp[i][j][k][p] \gets t \times (2j-p) \]

  • 产生新端点(即把数放在 \(1\) 或 \(n\))

\[dp[i][j][k+i][p + 1] \gets t \times (2 - p) \]

3. 作为介质,合并两个已有段

\[dp[i][j-1][k+2i][p] \gets t \times (j-1) \]

时间复杂度 \(\mathcal{O}(n^4)\),因为 \(j\) 的范围是 \(\mathcal{O}(n^2)\) 的。

精度问题

但是由于这题的精度要求比较高,所以可以 dp 到 \(i\) 时就 \(\div i\)。(不知道怎么实现可以看代码)另外,记得用 long double

然后交上去之后:

精度不够啊。

于是考虑换成 __float128

太慢了 QAQ。

难道就没有什么好的办法了吗?


你猜为什么我放了点分治的 tag?

没错!数据点分治!注意到数据范围:

对于 \(40%\) 的数据,\(n \le 50,k \le 30\)。
对于 \(60%\) 的数据,\(n \le 100,k \le 8\)。

所以如果 \(k \le 8\) 就用 long double,否则用 __float128。然后就可以通过了。

另外由于数据点分治之后要用不同的 type 存 dp,所以推荐一种比较方便的 template写法

代码

// Author: AquariusZhao
#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = 5005 << 1, Pre = 5000, Mx = 10000;
const long double eps = 1e-20;
int n, m, k;
long double dp1[2][N][M][3];
__float128 dp2[2][N][M][3];

template <class T>
void solve(T dp[2][N][M][3])
{
    int cur = 0, pre = 1;
    dp[cur][0][Pre][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        swap(cur, pre);
        memset(dp[cur], 0, sizeof(dp[cur]));
        for (int j = (i > 1); j <= i; j++)
            for (int k = 0; k <= Mx; k++)
                for (int p = 0; p <= 2; p++)
                {
                    auto from = dp[pre][j][k][p];
                    if (!from)
                        continue;
                    // new
                    if (k >= 2 * i)
                        dp[cur][j + 1][k - 2 * i][p] += from * (j + 1 - p) / i;
                    if (k >= i && p < 2)
                        dp[cur][j + 1][k - i][p + 1] += from * (2 - p) / i;
                    if (j == 0)
                        continue;
                    // end
                    dp[cur][j][k][p] += from * (2 * j - p) / i;
                    if (k + i <= Mx && p < 2)
                        dp[cur][j][k + i][p + 1] += from * (2 - p) / i;
                    if (j == 1)
                        continue;
                    // mid
                    if (k + 2 * i <= Mx)
                        dp[cur][j - 1][k + 2 * i][p] += from * (j - 1) / i;
                }
    }
    T ans = 0;
    for (int k = m; k <= Mx - Pre; k++)
        ans += dp[cur][1][Pre + k][2];
    if (ans + eps >= 1)
    {
        cout << "1." << string(k, '0');
        return;
    }
    cout << "0.";
    for (int i = 1; i <= k; i++)
    {
        ans *= 10;
        putchar(int(ans + (i == k) * 0.5) + '0');
        ans -= int(ans);
    }
}

int main()
{
#ifdef aquazhao
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    cin >> n >> m >> k;
    if (k <= 8)
        solve(dp1);
    else
        solve(dp2);
    return 0;
}

标签:le,cur,题解,times,ZJOI2012,P2612,端点,gets,dp
From: https://www.cnblogs.com/avalaunch/p/18543732

相关文章

  • P11071 「QMSOI R1」 Distorted Fate题解
    题意:给定一个序列,给定两种操作:将一个区间异或上一个给定的值。给定\(l,r\)求\[{\large(\sum_{i=l}^r\bigcup_{j=l}^iA_j)\bmod2^{30}}\]\(0\lea_i,x<2^{30}\),\(1\lel\ler\len\)思路由于操作数以及区间过大,一位一位地去模拟肯定是不行的。因此考虑去离线......
  • [题解]CF1407D Discrete Centrifugal Jumps
    思路注意到第二个条件和第三个条件本质相似,可以用相同的维护方式处理,因此这个只讨论第二个条件的维护方式。定义\(dp_i\)表示走到\(i\)的最少步数。第一个条件的转移显然为\(dp_i\leftarrowdp_{i-1}\)。对于第二个条件,\(i\)能向\(j\)转移,当且仅当\(h_{i+1\sim......
  • Codeforces Round 985 div1+2 个人题解(A~E)
    CodeforcesRound985div1+2个人题解(A~E)Dashboard-Refact.aiMatch1(CodeforcesRound985)-Codeforces火车头#include<bits/stdc++.h>usingnamespacestd;#defineftfirst#definesdsecond#defineyescout<<"yes\n"#definenoc......
  • [CF1935E] Distance Learning Courses in MAC 题解
    [CF1935E]DistanceLearningCoursesinMAC难度正常的一道题。首先我们发现“挑选若干个区间”就是一句废话,因为按位或只会贡献答案而不会减小答案。所以我们需要在\([L,R]\)的每个区间都挑一个数,使得最终的按位或最大。想办法让尽可能多的二进制位都变成\(1\),且越是高......
  • [USACO06NOV] Corn Fields G 题解
    题目链接[USACO06NOV]CornFieldsG题解这是一道典型的状压dp,对于\(M\)行\(N\)列的图,由于每个点只有\(1\)和\(0\)两种状态,我们将其压缩为一个长度为\(M\)的数组,数组(\(g\))的每一项\(g_{i}\)表示状态的二进制表示法表示的数(如\(101\)表示为\(5\)),我们预先处......
  • [CEOI2023] A Light Inconvenience 题解
    Description今年CEOI的开幕式上有一场精彩的火炬表演。表演者们站成一排,从\(1\)开始从左往右编号。每个表演者举着一根火炬,初始只有一个举着点燃的火炬的表演者。表演分为\(Q\)幕。在第\(a\)幕开始之前,要么\(p_a>0\)个表演者从右侧加入表演,他们的火炬是熄灭的;要么最......
  • gym103102H AND = OR 题解
    非常巧妙的一个题。我们首先考虑单组询问该怎么做。首先需要注意到一个结论,即设答案为\(x\),那么对于\(\forally<x\),\(y\)都应该放在与组;同样的,对于\(\forally>x\),\(y\)都应该放在与组。进一步的,我们观察在\(\text{popcount}\)上也有同样的性质,即对于\(\forally,......
  • 好题记录 [集训队互测 2023] 优惠购物 题解
    首先发现这个过程的限制比较多,那么考虑重新描述这个过程。令\(x_i\)表示在第\(i\)个物品上使用了\(x_i\)张券,那么一组\(x_{1\simn}\)就描述了一个方案。方便起见,令\(s_i\)为前i个物品买完后剩了几张券,那么有:\(s_0=m\)\(s_i=s_{i-1}+\lfloor\frac{a_i-......
  • 【题解】洛谷P7287: 「EZEC-5」魔法
    P7287「EZEC-5」魔法感觉好题有思维,但是我没认真读题,看到样例就我以为了,他让任意一个区间满足大于\(S\)即可不是全部。我们手搓一下样例就可以发现,对于加法我们不加白不加的话肯定全部的数都加上,乘法肯定要等到加完后才开始,这些都是贪心思路。然后就是开始搭配操作了,我遇到......
  • 题解:「2017 山东一轮集训 Day7」逆序对
    LibreOJ6077前置知识:生成函数、组合数先考虑平方怎么做。\(f_{i,j}\)表示处理了前\(i\)个值,逆序对有\(j\)个。显然可以转移到\(f_{i+1,j},f_{i+1,j+1},f_{i+1,j+2},...,f_{i+1,j+i}\)。然后发现这个东西是个很简单的递推,而且长得很生成函数,于是可以很自然的写成\[1\t......