bzoj5123 [Lydsy12月赛]线段树的匹配-白红宇

bzoj5123 [Lydsy12月赛]线段树的匹配

阅读量：4580 次

发布时间：2019-06-09

本文共 990 字，大约阅读时间需要 3 分钟。

题意:

线段树是这样一种数据结构：根节点表示区间 [1, n]；对于任意一个表示区间 [l, r] 的节点，若 l < r，

则取 mid = ⌊l+r/2⌋，该节点的左儿子为 [l, mid]，右儿子为 [mid + 1, r]；若 l = r，则它为叶子。

一棵树的匹配是指一个树边集合，满足任意两条边没有公共端点。一棵树的最大匹配是指所有合法

匹配方案中，所选树边最多的匹配方案。

给定一棵表示 [1, n] 的线段树，请求出它的最大匹配中有多少条边，并求出有多少种最大匹配的方

案。因为答案很大，请对 998244353 取模输出。

Input

第一行包含一个正整数 n(1 ≤ n ≤ 1018)。

Output

输出一行两个整数，第一个表示最大匹配中的边数，第二个表示方案数对 998244353 取模的结果。

f[n]表示大小为n的线段树的最大匹配数,g[n]表示方案数.

结论:线段树每一层的节点大小最多有两种.

如果上一层有2k,2k-1,那下一层就有k,k-1.如果上一层有2k,2k+1,那么下一层就有k,k+1.反正最多两种.

层数logn,那么有用状态2logn个,200不到,map开dp数组+记忆化搜索,完事.

#include
    
     #include
     using namespace std;typedef long long ll;const ll mod=998244353;map
      
        f0,f1;map
       
         g0,g1;ll f(ll n){  if(n==1)return 0;  if(f1[n])return 0;  ll l=n/2,r=n-n/2;  f(l);f(r);  f0[n]=max(f0[l],f1[l])+max(f0[r],f1[r]);  f1[n]=1+max(f0[l]+max(f0[r],f1[r]),f0[r]+max(f0[l],f1[l]));  ll ans0=0,ans1=0;  if(f0[l]==f1[l])ans0=g0[l]+g1[l];  else if(f0[l]

转载于:https://www.cnblogs.com/liu-runda/p/8426442.html

你可能感兴趣的文章

Android 演示 DownloadManager——Android 下载 apk 包并安装

查看>>

采用oracle存储过程读取excel文件更新表

查看>>

固定虚拟机中windows系统的ip地址

查看>>

【转】正则应用实例，如将多个空格改为1个空格

查看>>

移动端自动打包平台

查看>>