题解：CF1461C Random Events

a_small_penguin · 2025-04-21 14:35:47 · 题解

题目告诉我们有一个序列 a，那么这个 a 就可以分为两个部分。

第一个部分：1 ~ k，这个区间内至少有一个元素排列后位置不一样。

第二个部分：k + 1 ~ n，这个区间内所有的数字有序排列后对应的数字位置不变。

明显，只用当 k \le r_i \le n 的情况下进行排列才可以让 a 变得有序。

对于答案，考虑求出所有操作排列都不有序的概率 ans，那么答案就是 1 - ans。

特别的：对于序列本来就有序的情况，那么答案就是 1。

code：

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
int a[100009];
long double ans;

inline void sovel() {
    cin >> n >> m;
    ans = 1;
    k = n + 1;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    while(a[k - 1] == k - 1 && k - 1 >= 1) k--;
    k--;
    while(m--) {
        int r;
        long double p;
        cin >> r >> p;
        if(r >= k) {
            ans *= (1 - p);
        }
    }
    if(k == 0)
        cout << 1 << "\n"; 
    else 
        cout << 1 - ans << "\n";
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int _T = 1;
    cin >> _T;
    while(_T--) {
        sovel();
    }

    return 0;

}