首页 > 其他分享 >Luogu P6834 梦原 题解

Luogu P6834 梦原 题解

时间:2024-03-29 16:35:41浏览次数:20  
标签:int 题解 ll long P6834 Luogu sum dp define

原题传送门

首先考虑如果树的形态确定了之后的情况:如果当前点比爸爸的值大,那么显然爸爸变成 \(0\) 之后,这个点需要自己被额外操作删除,贡献就是 \(a[v] - a[u]\)。
类似,如果比爸爸的值小,那么这个点肯定会跟爸爸一起被删除,所以贡献就是 \(0\)。
综上所述,一个点的贡献是 \(max{a[v] - a[u], 0}\)。

接下来考虑树的形态,以求得答案。
首先,最终期望值可以拆分成每个点的贡献的期望值之和,那么显然有动态规划:

\(dp[i] = \frac{1}{i - max(1, i - k) } * \sum_{v \in [max(1, i - k), i - 1]}{max(a[v] - a[u], 0)}\)

其中 \(dp[1] = a[1]\)

答案就是 \(\sum_{i \in [1, n]}{dp[i]}\)

注意优化:使用权值树状数组快速求得\(a_u\)总和,然后再用一权值树状数组快速求具体数量,乘上 \(a_v\) 即可。注意划窗时,要删去左侧的部分。

#include <bits/stdc++.h>
using namespace std;
#define N 2000010
#define ll long long
#define int long long

template <class T>
inline T read(T& a){
    T x = 0, s = 1;
    char c = getchar(); 
    while(!isdigit(c)){ if(c == '-')  s = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
    a = x * s;
    return a; 
}

int n, k; 
ll a[N]; 
const int mod = 998244353; 
ll dp[N]; 

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

unordered_map <int, int> g; 
int b[N]; 

struct Segment_tree{
    int tree[N]; 

    #define lowbit(x) (x&-x)

    void update(int x, int k){
        for(int i = x; i <= n; i += lowbit(i))
            tree[i] = ((tree[i] + k) % mod + mod) % mod;
        return ;  
    }

    int ask(int x){
        int sum = 0; 
        for(int i = x; i; i -= lowbit(i)){
            sum = (sum + tree[i]) % mod; 
        }
        return sum; 
    }

    int query(int l, int r){
        return (ask(r) - ask(l - 1) + mod) % mod; 
    }
 
} tree, tree2; 

signed main(){
    read(n), read(k); 
    for(int i = 1; i <= n; i++)
        b[i] = read(a[i]);
    int id = 0; 
    sort(b + 1, b + n + 1); 
    for(int i = 1; i <= n; i++){
        if(!g[b[i]]) g[b[i]] = ++id; 
    }
    for(int i = 1; i <= n; i++){
        b[i] = g[a[i]]; 
    }
    // cout << qpow(2, mod - 2) << endl; 
    dp[1] = a[1]; 
    tree.update(b[1], a[1]); 
    tree2.update(b[1], 1); 
    int now = 1; 
    for(int i = 2; i <= n; i++){
        while(now < max(1ll, i - k)) tree.update(b[now], -a[now]), tree2.update(b[now], -1), now++; 
        // cout << "------" << -tree.query(1, 1, n, 1, g[a[i]] - 1) + a[i] * tree2.query(1, 1, n, 1, g[a[i]] - 1) << " " << qpow(i - max(1, i - k), mod - 2) << endl; 
        dp[i] = (qpow(i - max(1ll, i - k), mod - 2) % mod * ((-tree.query(1, b[i] - 1) + (a[i] * tree2.query(1, b[i] - 1)) % mod) % mod)) % mod; 
        tree.update(b[i], a[i] % mod); 
        tree2.update(b[i], 1); 
    }
    // for(int i = 1; i <= n; i++)
        // cout << dp[i] << endl; 
    ll ans = 0; 
    for(int i = 1; i <= n; i++){
        ans = (ans + dp[i]) % mod; 
    }

    cout << (ans + mod) % mod << endl; 
    return 0; 
}

标签:int,题解,ll,long,P6834,Luogu,sum,dp,define
From: https://www.cnblogs.com/wondering-world/p/18104052

相关文章

  • ICPC2023 杭州 题解
    M-V-DiagramSolution很显然,连续的子序列的一段肯定是包括最左边或最右边的其中一个点Code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constllinf=1ll<<60;intmain(){intt;cin>>t;while(t--){ intn;cin>>n;......
  • [正常题解]Acwing.5308 公路
    ​首先需要理解一个证明:​ 假设我们有三个点,前两个点价格为\(a_1,\a_2\),距离为\(v_1,\v_2\)那么就有式子:\(\frac{a_1\timesv_1}{d}+\frac{a_2\timesv_2}{d}\式①\),和式子\(\frac{a_1\timesv_1}{d}+\frac{a_1\timesv_2}{d}\式子②\)$\rightarrow\frac{1}{d}(......
  • CF1184E1题解
    CF11841E1&blog尽然想让第一条边最大且这条边在最小生成树中,那么这条边就需要尽量晚。但是假如加上一条边\(i\)可以使\(u_1\)和\(v_1\)联通并且第\(w_i\lew_1\)那么我们就会舍弃原本第一条边,使用第\(i\)条边。所以第一条边的比安全一定小于等于所有么满足上述条......
  • 2023年全国青少年信息素养大赛 第9届Python编程挑战赛北京赛区(小学组)复赛试题解析
    2023年全国青少年信息素养大赛第9届Python编程挑战赛北京赛区(小学组)复赛试题解析T1.求余数题目描述:输入一个正整数,输出这个整数除以5的余数。输入描述:输入一行一个正整数输出描述:输出这个整数除以5的余数样例1:输入:12输出:2#示例代码n=int(input())print(n%5)......
  • 【洛谷 P8738】[蓝桥杯 2020 国 C] 天干地支 题解(字符串+数学+模运算)
    [蓝桥杯2020国C]天干地支题目描述古代中国使用天干地支来记录当前的年份。天干一共有十个,分别为:甲(jiǎ)、乙(yǐ)、丙(bǐng)、丁(dīng)、戊(wù)、己(jǐ)、庚(gēng)、辛(xīn)、壬(rén)、癸(guǐ)。地支一共有十二个,分别为:子(zǐ)、丑(chǒu)、寅(yín)、卯(mǎo)、辰(chén)、巳(sì)、午(wǔ......
  • 【洛谷 P8654】[蓝桥杯 2017 国 C] 合根植物 题解(并查集)
    [蓝桥杯2017国C]合根植物题目描述w星球的一个种植园,被分成m×nm\timesnm×n个小格子(东西方向......
  • 启动应用程序出现FirewallAPI.dll找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个FirewallAPI.dll文件(挑选合适的版本文件)把......
  • 启动应用程序出现fthsvc.dll找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个fthsvc.dll文件(挑选合适的版本文件)把它放......
  • 启动应用程序出现fontext.dll找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个fontext.dll文件(挑选合适的版本文件)把它放......
  • Leetcode 第 126 场双周赛题解
    Leetcode第126场双周赛题解Leetcode第126场双周赛题解题目1:3079.求出加密整数的和思路代码复杂度分析题目2:3080.执行操作标记数组中的元素思路代码复杂度分析题目3:3081.替换字符串中的问号使分数最小思路代码复杂度分析题目4:3082.求出所有子序列的能量和思......