https://ac.nowcoder.com/acm/contest/107965#question

D E yqw的珂学难题

Easy版本直接暴力枚举或者打表就可以通过

Hard版本正解是 $O(1)$ 的，这里放成了 $O(N)$ 可做

设 $X$ 为随机排列的价值， $E(X)$ 为随机排列价值的期望，我们发现直接求无从下手，但是根据期望的线性性，我们可以把复杂事件（或复杂随机变量）拆成若干个“子事件”，通过求子事件的期望即可求出 $X$ 的期望

设 $0-1$ 随机变量 $X_i$ 表示第 $i$ 个位置是否为峰值( 当 $i>=2\&\&i<=n-1$ 时)

X_i = \begin{cases} 1, & \text{} P[i] > P[i-1] \text{ && } P[i] > P[i+1], \\ 0, & \text{else}. \end{cases}

那么

$X = X_1+\sum_{i=2}^{n-1} X_i+X_n$

E[X] = E(X_1)+E\left[\sum_{i=2}^{n-1} X_i \right] + E(X_n) = E(X_1)+\sum_{i=2}^{n-1} E[X_i]+E(X_n).

那么第 $i$ 个位置的期望 $E(X_i)$ 怎么求呢？很简单，我们只需要考虑 $i$ 这个位置 $p[i] > p[i-1]$ 且 $p[i] > p[i+1]$ 的概率即可。

在一个 $1-n$ 的排列中，随机选 $k$ 个数，求第一个数比其他几个数小的概率

p = \frac{(k-1)!}{k!} = \frac{1}{k}.

那么对应到这题， $P(X_i)= \frac{1}{3}$ ，那么 $E(X_i)=\frac{i}{3}$ ，特别的 $E(X_1)=\frac{1}{2}$ ， $E(X_n)=\frac{n}{2}$

结果就是：

\begin{aligned} \sum_{i=1}^{n} E(X_i) &= E(X_1) + \sum_{i=2}^{n-1} \frac{i}{3} + E(X_n) \\[1mm] &= \frac{1}{2} + \frac{1}{3}\left(\sum_{i=2}^{n-1} i\right) + \frac{n}{2} \\[1mm] &= \frac{1}{2} + \frac{1}{3}\left(\frac{n(n-1)}{2} - 1\right) + \frac{n}{2} \\[1mm] &= \frac{3(n+1)}{6} + \frac{n(n-1)-2}{6} \\[1mm] &= \frac{3n + 3 + n^2 - n - 2}{6} \\[1mm] &= \frac{n^2 + 2n + 1}{6} \\[1mm] &= \frac{(n+1)^2}{6}\,. \end{aligned}

最后的结果通分一下即可代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}


void solve(){
    ll n;
    cin>>n;
    ll zi=0,mu=0;
    zi = (n+1)*(n+1);
    mu = 6;
    //约分
    ll gd = gcd(zi,mu);
    zi/=gd,mu/=gd;
    cout<<zi<<'/'<<mu<<'\n';
}



int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int _ = 1;
    while(_--)solve();
}

L 好饿好饿

思路：设选中的元素操作了 $m$ 次，总操作数为 $k$ 次，那么当前元素被翻转的 $k - m$ 次，如果 $k - m$ 为偶数则不改变，若为奇数则改变。

要使字典序最大，尽量使前面的元素为 $1$
操作次数尽量少

从前往后遍历：

若 $k$ 为奇数，则遇到前面的 $1$ 就要保护，不要让它翻转，即选中的这个 $1$ 翻转次数为 $k - 1$ ， $k - 1$ 为偶数，保护了这个 $1$ ；若遇到 $0$ ，则不保护，让它翻转。
若k为偶数，则遇到 $0$ 就保护，因为这个 $0$ 的翻转次数为 $k - 1$ ，可以翻转为 $1$ ，遇到 $1$ 则不翻转。

注意点：若从前往后遍历后有剩余的操作次数，但一定要执行完且不能对前面大数改变，即改变最小的那个数。

// 学而不思则罔，不思不学则爽
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10, mod = 1;
int n, m, k, x, y;
string s;
void solve()
{

    cin >> n >> k;
    m = k;
    cin >> s;
    vector<int> ans(n);
    if (k % 2 != 0)
    {
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '1' && k != 0)
            {
                ans[i]++;
                k--;
            }
            if (k == 0)
                break;
        }
        if (k)
            ans[n - 1] += k;
    }
    else
    {
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '0' && k != 0)
            {
                ans[i]++;
                k--;
            }
            if (k == 0)
                break;
        }
        if (k)
            ans[n - 1] += k;
    }
    for (int i = 0; i < n; i++)
    {
        if ((m - ans[i]) % 2 == 0)
            cout << s[i];
        else if (s[i] == '1')
            cout << '0';
        else
            cout << '1';
    }
    cout << endl;

    return;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

M 珂朵莉树的魔法序列

直接暴力模拟即可

这里给出一种优美的暴力解法，在随机数据下，珂朵莉树可以在 $O(nlognlogn)$ 的时间复杂度下维护题目所需操作

有兴趣的可以自行从网上学习

#include<bits/stdc++.h>

using namespace std;
using i64 =long long; 
using ll = long long;

ll qpow(ll a, ll b, ll y)
{
    ll res = 1;
    a%=y;
    while (b)
    {
        if (b & 1)res = res * a % y;
        b >>= 1;
        a = a * a % y;
    }
    return res;
}

struct node
{
    ll l, r;
    mutable ll v; 
    node(ll l, ll r, ll v) : l(l), r(r), v(v) {} 
    bool operator<(const node &o) const { return l < o.l; }
};

set<node> tree;
//tree.insert(node(1,n,1))

//区间分割 
set<node>::iterator split(ll pos)
{
    auto it = tree.lower_bound(node(pos, 0, 0)); // 寻找左端点大于等于pos的第一个节点
    if (it != tree.end() && it->l == pos) // 如果已经存在以pos为左端点的节点，直接返回
        return it;
    it--; // 否则往前数一个节点
    ll l = it->l, r = it->r, v = it->v;
    tree.erase(it); // 删除该节点
    tree.insert(node(l, pos - 1, v)); // 插入<l,pos-1,v>和<pos,r,v>
    return tree.insert(node(pos, r, v)).first; // 返回以pos开头的那个节点的迭代器
    // insert默认返回值是一个pair，第一个成员是我们要的迭代器 {it,bool} 
}

//区间赋值
void assign(ll l, ll r, ll v)
{
    auto end = split(r + 1), begin = split(l); // 顺序不能颠倒，否则可能RE
    tree.erase(begin, end); // 清除一系列节点
    tree.insert(node(l, r, v)); // 插入新的节点
}

//区间加 
void add(ll l, ll r, ll v)
{
    auto end = split(r + 1);
    for (auto it = split(l); it != end; it++)
        it->v += v;
}

//求区间k大值 
ll kth(ll l, ll r, ll k)
{
    auto end = split(r + 1);
    vector<pair<ll, ll>> v; // pair里存节点的值和区间长度
    for (auto it = split(l); it != end; it++)
        v.push_back(make_pair(it->v, it->r - it->l + 1));
    sort(v.begin(), v.end()); // 直接按节点的值的大小排下序
    for (int i = 0; i < v.size(); i++) // 然后挨个丢出来，直到丢出k个元素为止
    {
        k -= v[i].second;
        if (k <= 0)
            return v[i].first;
    }
    //不存在
    return -1;
}

//区间n次方和 
ll sum_of_pow(ll l, ll r, ll x, ll y)
{
    ll tot = 0;
    auto end = split(r + 1);
    for (auto it = split(l); it != end; it++)
        tot = (tot + qpow(it->v, x, y) * (it->r - it->l + 1)) % y; // qpow自己写一下
    return tot;
}

void solve(){

    int n,m;
    cin>>n>>m;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        tree.insert(node(i,i,a[i]));
    }
    int op,l,r,x,k,mod,p;
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            cin>>l>>r>>x;
            add(l,r,x);
        }
        else if(op==2){
            cin>>l>>r>>x;
            assign(l,r,x);
        }
        else if(op==3){
            cin>>l>>r>>k;
            cout<<kth(l,r,k)<<'\n';
        }
        else{
            cin>>l>>r>>p>>mod;
            cout<<sum_of_pow(l,r,p,mod)<<'\n';
        }
    }
}



int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    solve();
    return 0;
}

题解 | D E L N(第20届中北大学程序设计大赛)

D E yqw的珂学难题

L 好饿好饿

M 珂朵莉树的魔法序列