- 2024-05-22P2606 [ZJOI2010] 排列计数
P2606[ZJOI2010]排列计数树形dp序列中每个位置的限制只有另外一个位置,那么我们将这样的限制连线,就可以得到一棵树。在这题中,这棵树刚好是小根堆,一棵完全二叉树。题目就转化为一共有多少种小根堆。那么显然的\(a_1=1\),然后左子树和右子树分剩下的\([2,n]\),并且左右子树不互
- 2024-02-29P2606 [ZJOI2010] 排列计数 题解
题意:求有多少个排列满足:对于每一个\(2\lei\len\),\(a_i>a_{\frac{i}{2}}\)。首先我们会发现这些数之间的大小关系形成了一个完全二叉树,因为每一个\(a_i\)都必须小于\(a_{2\timesi}\)和\(a_{2\timesi+1}\)。会发现本题的方案和每个位置具体的值并没有关系,而只
- 2023-11-16[ZJOI2010] 基站选址
我感觉我缺了一个dp优化的思路我不知道我是不是能够对状态继续优化dp写少了。。。确诊了题目描述有NN个村庄坐落在一条直线上,第i(i>1)i(i>1)个村庄距离第11个村庄的距离为DiDi。需要在这些村庄中建立不超过KK个通讯基站,在第ii个村庄建立基站的费用为CiCi。如
- 2023-09-28P2602 [ZJOI2010] 数字计数&HDU 2089 (数位dp)
luoguHDU最近在复习数位dp数位dp,就是在一些计数问题的时候按照一位一位的顺序依次计算,通常可以采用记忆化搜索的方式这两道题就是很典型的数位dp数位dp通常要记录是不是顶着上限,有没有前导零,到了哪一位以及一些特殊的条件要求。数位dp通常要把某个区间的问题转变成两个区间
- 2023-02-21P2602 [ZJOI2010] 数字计数:数位DP
https://www.luogu.com.cn/problem/P2602//#include<iostream>//#include<iomanip>//#include<unistd.h>//#include<climits>//#include<string>//#inclu
- 2023-01-24P2602 [ZJOI2010] 数字计数
P2602[ZJOI2010]数字计数-洛谷|计算机科学教育新生态(luogu.com.cn)数位DP模板题由于是对0~9进行统计,所以我们只需对每一个数进行数位DP即可不过对于0和1~9还是
- 2022-12-14[ZJOI2010]排列计数
$[ZJOI2010]$排列计数链接:https://www.luogu.com.cn/problem/P2606题面:求满足$p_{i}>p_{i/2}(∀i∈[2,n])$的排列个数。题解:考虑将限制转化成一棵树,如果我们将$i
- 2022-11-22 P2602 [ZJOI2010] 数字计数
Idea可以模仿我们人类分类讨论的时候做的事情,并且加以记忆化,这样就可以完成.Code#include<bits/stdc++.h>usingnamespacestd;#defineMAXN16#defineF(i,a,
- 2022-11-06洛谷 P2606 [ZJOI2010]排列计数 题解
LuoguP2606[ZJOI2010]排列计数题解题目描述称一个\(1\simn\)的排列\(p_1,p_2,\dots,p_n\)是Magic的,当且仅当\[\foralli\in[2,n],p_i>p_{\lfloori/2
- 2022-10-25BZOJ 2111([ZJOI2010]Perm 排列计数-乘法逆元+完全二叉树模型+数列分数表示法)
2111:[ZJOI2010]Perm排列计数TimeLimit: 10Sec MemoryLimit: 259MBSubmit: 478 Solved: 283[Submit][Status][Discuss]
- 2022-10-21 P2604 [ZJOI2010]网络扩容 | 建平行边
本来的思路是纯纯地打一个大暴力在残余网络上跑spfa,每跑出一条增广路就是当前能扩容的最小花费然后k<=10,只需要跑最多十次:)正解是建平行边啦,容量为inf,费用为扩容费用,
- 2022-08-16题解 [ZJOI2010]排列计数
好题。%你赛考到了不会摆烂,后来发现原来有向下取整,题面没有。。。(就算有我也做不出来啦qAq首先我们会发现这个长得就是小根堆,答案就变成了小根堆的计数。首先最小的