CTime_Pup_314

不能再颓废了

0%

20809102 NOIP模拟题

发表于 更新于 分类于 阅读次数： Valine：

card

给定 \(n\) 张值为 \(i\) 的卡牌，每次随机选择一个整数 \(m\)，将每 \(m\) 张合成 \(1\) 张卡牌值加 \(1\)，剩下的卡牌丢掉，直到最后只剩下一张牌，求值的期望

题意有些不清楚，首先 \(m\) 张牌合并的意思是将 \(n\) 张牌依次排列，依次把相邻的 \(m\) 张牌只合并 \(1\) 次，新的牌的值就是原来 \(m\) 张牌的值的任意一张加 \(1\) 剩下的丢掉，注意可以自己和自己合并

明确了意思就不难做出来了，显然任何局面下的每张牌面的牌面都一样，所以设 \(E(n)\) 为有 \(n\) 张牌时，每张牌值得期望，则有

\[ E(n)\ =\ \frac{\sum_{i=1}^n[E(\lfloor\frac{n}{i}\rfloor)+1]}{n} \] 化简得

\[ E(n)\ =\ \frac{n+\sum_{i=2}^nE(\lfloor\frac{n}{i}\rfloor)}{n-1} \]

除法分块即可

记忆化搜索时用数组记录状态会快一点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int P = 998244353;
const int N = 3e7+5;
int h[N];
int64 qpow(int64 a, int b)
{
    int64 ret = 1;
    for( ; b; b >>= 1, a = a*a%P) if(b&1) ret = a*ret%P;
    return ret;
}
int64 E(int n)
{   
    if(n == 1) return 1;
    if(n < N&&h[n]) return h[n];
    int64 ret = n;
    for(int l = 2, r; l <= n; l = r+1)
        r = n/(n/l), ret = (ret+E(n/l)*(r-l+1)%P)%P;
    if(n < N) return h[n] = ret*qpow(n-1, P-2)%P;
    return ret*qpow(n-1, P-2)%P;
}
int n;
int main()
{
    freopen("card.in", "r", stdin);
    freopen("card.out", "w", stdout);
    printf("%lld\n", E(read()));
    return 0;
}

gift

最初 \(Kirin\) 手里拿着一张值为 \(0\) 的卡牌，然后他从第 \(1\) 张卡牌走到第 \(n\) 张卡牌，每次他遇到一张比手里的卡牌等级大的卡牌，他就会交换手中的卡牌与这张卡牌，多次询问 \(x\) 次操作后第 \(y\) 张卡牌的值

当第 \(k\) 次操作时，位于位置 \(i\) 的卡牌若比 \([1,\ i]\) 的第 \(k\) 大卡牌大的情况下位置 \(i\) 的卡牌变为第 \(k\) 大的卡牌，并且在之后操作下依次减小，否则，位置 \(i\) 的卡牌不变，因此，\((x,\ y)\) 的答案为 \(min(xthmax_{1\le k\le y}\lbrace a_k\rbrace,\ a_y)\)

还有一个疑问是，一开始审错题看成冒泡排序了，但是，如何求第 \(k\) 次冒泡排序的第 \(i\) 个位置的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 1e6+5;
int n, q, a[N], _[N];
vector<pair<int, int> > s[N];
int val[N<<2], ans[N];
void add(int x, int l, int r, int p)
{   
    ++val[x]; if(l == r) return;
    int mid = (l+r)>>1;
    if(p <= mid) return add(x<<1, l, mid, p);
    else return add(x<<1|1, mid+1, r, p);
}
int query(int x, int l, int r, int k)
{
    if(l == r) return l;
    int mid = (l+r)>>1;
    if(val[x<<1|1] >= k) return query(x<<1|1, mid+1, r, k);
    else return query(x<<1, l, mid, k-val[x<<1|1]);
}
int main()
{
    freopen("gift.in", "r", stdin);
    freopen("gift.out", "w", stdout);
    n = read(), q = read();
    for(int i = 1; i <= n; ++i) _[i] = a[i] = read();
    sort(_+1, _+1+n);
    for(int i = 1; i <= q; ++i)
    {
        int x = read(), y = read();
        s[y].push_back(make_pair(x, i));
    }
    for(int i = 1, p; i <= n; ++i)
    {
        add(1, 1, n, p = lower_bound(_+1, _+1+n, a[i])-_);
        for(int k = 0; k < s[i].size(); ++k)
        {
            int x = s[i][k].first, d = s[i][k].second;
            ans[d] = min(x <= i?_[query(1, 1, n, x)]:0, a[i]);
        }
    }
    for(int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
    return 0;
}