[BZOJ 3625] [Codeforces 438E] 小朋友的二叉树 (DP+生成函数+多项式开根+多项式求逆) 题面 一棵二叉树的所有点的点权都是给定的集合中的一个数. 让你求出1到m中所有权值为i的二叉树的个数. 两棵树不同当且仅当树的形态不一样或者是树的某个点的点权不一样 分析 设\(c(i)\)表示数值i是否在集合中.\(f(i)\)表示权值为i的二叉树的个数.那么 \[f(n)=\sum_{i=1}^n c(i) \sum_{j=0}^{n-i} f(j)f(n-i-j)\] 其

传送门 题意:三种颜色,规定使用每种颜色次数$r,g,b$,给出一个置换群,求多少种不等价着色 $m \le 60,\ r,g,b \le 20$ 咦,规定次数? <组合数学>上不是有生成函数做法吗.... 生成函数貌似可以和背包$DP$互相转换来着 然后就做出来了 每种置换求循环,$d[i][j][k][l]$表示前$i$个循环有了$j$个红$k$个绿$l$个蓝 遇到一点小问题,一直输出$0$ 看了黄学长的代码发现他加了一个恒等置换.... 想了一会儿才明白题目给的不是置换群,因为少了一个恒

https://codeforces.com/problemset/problem/813/D dp[i][j] = 一条链以i结尾, 另一条链以j结尾的最大值 关键要保证转移时两条链不能相交 #include <iostream>#include <cstdio> #define REP(i,a,n) for(int i=a;i<=n;++i) using namespace std; , M = 1e7+; int n; int a[N], dp[N][N], x[M],

Consecutive Subsequence CodeForces - 977F 题目大意:输出一序列中的最大的连续数列的长度和与其对应的下标(连续是指 7 8 9这样的数列) 解题思路: 状态:把dp[i]定义为数列末尾为 i 的最大连续数列的长度值 状态转移方程:dp[i] = dp[i-1] + 1 再由最大连续数列最后一个值从后往前倒推出前面的所有值,到不是连续时停止 代码: #include<bits/stdc++.h> using namespace std; + ; int d

1.(467C)http://codeforces.com/problemset/problem/467/C 题意:有一个长为n的序列,选取k个长度为m的子序列(子序列中不能有位置重复),求所取的k个序列求和的最大值是多少 分析:设dp[i][j]在[j,n]范围内取了i个子序列求和所得的最大值,用sum[i]表示[1,i]的求和.转移方程为dp[i][j]=max(dp[i-1][j+m]+sum[j+m-1]-sum[j-1],dp[i][j+1]),表示要不要选择[j,j+m-1]这段为其

用生成函数套路推一推,推完老想NTT--实际上把这个多项式乘法看成dp然后前缀和优化一下即可 #include<iostream> #include<cstdio> using namespace std; const int N=1005,mod=1000000; int n,m,c[N],l,r,f[N*100],s[N],sum; int read() { int r=0,f=1; char p=getchar(); while(p>'9'||p<'0') { i

LINK:graph HDU题库里的原题 没做过自闭. 考虑dp 设\(f_{i,j}\)表示前i个点构成j个联通块是树的方案数. 对于一次询问答案即为\(\sum_{j}f_{n,j}j^k\) 考虑如何dp出来 显然每次枚举1号所在的连通块的大小 考虑这个连通块是否构成树 即可. 具体转移不再赘述 需要预处理一下i个点的树的个数 i个点的连通块个数 i个点不是树是连通块的个数. 复杂度\(n^3\) 利用分治NTT来优化可以到 \(n^2log^2\)比较繁杂且不是正解. 正解当然是考虑生成

LINK:5.15 T2 个人感觉生成函数更无脑 容斥也好推的样子. 容易想到每次放数和数字的集合无关 所以得到一个dp f[i][j]表示前i个数字 逆序对为j的方案数. 容易得到转移 使用前缀和优化即可. 进一步的可以设出其生成函数 对于第i次放数字 生成函数为\(F(x)=1+x^1+x^2+...x^{n-i}\) 那么容易得到答案的生成函数为 \(G(x)=\frac{\Pi_{i=1}^{n}(1-x^i)}{(1-x)^n}\) 化简一下 然后dp出来方案数即可 可以发现这个dp是

/* 题意:给你一个有向无环图.给一个限定t. 问从1点到n点,在不超过t的情况下,最多可以拜访几个点. 保证至少有一条路时限不超过t. 思路: 1.由无后向性我们可以知道(取决于该图是一个DAG),这题一定可以dp. 2.dp[i][j]代表,到达点i,并且拜访了j个城市的最短时间. wa点: 没有初始化数组中的0.. */ #include<bits/stdc++.h> #define N 5050 using namespace std; int inf=0x3f3f3f3f; int

题目:这里 题意:给定n个字符串,每个字符串可以进行一项操作,就是将这个字符串交换,就是该字符串的第一个和最后一个交换,第二个和倒数第二个交换,以此类推,当然可以选择对于 该字符串进行或不进行这项操作,而每个字符串都有一个相应的能量值,进行操作了就要消耗那么多能量值,最后是否能在消耗的能量值最小的情况下保证这些字符串是升序的( 字典序从小到大),不能就输出-1. 字符串用string,DP,dp[i][j]表示到第i个字符串的状态为j的时候(j为1表示这个串交换了,j为0表示这个串没有交换),注

/* 题意:给一个长度不超过5000的字符串,每个字符都是0到9的数字. 要求将整个字符串划分成严格递增的几个数字,并且不允许前导零. 思路: 1.很开心得发现,当我在前i个区间以后再加一个区间的时候,转移 的条件只跟最后一个区间的数字大小有关,这决定这道题可以dp... 2.dp[i][j]代表前j个字符,最后划分的区间的第一个字符是第i个的答案数. 3.可知对于所有的dp[i][i...n]他们的答案都取决与dp[1...i-1][i-1]. 4.很容易想到对于同一个i,累加求得dp[i][

/* 我是一个习惯后悔,但是没办法忍受内疚感的二货== 这题是个无脑dp,但是比赛大概20min没出...其实最后5min我好好想想简单化边界条件,可以出的. 题意: 给你一个长度为1e6的由?*01四种字符组成的字符串,类似扫雷,?代表当前不确定,0代表当前无雷,并且 两边无雷,1代表当前五雷且两边有一个雷,2同样的,问当所有格子已知以后一共有多少种可能的局面. 思路: 首先想到的是,这个问题无后效性,而当前位置的合法方式只与它之前的两位有关. 所以dp的思路也是显而易见的,即dp[i][j]

题意: 有n天,m门课和常数k; 每天上一门课,每门课程有两个属性,最少作业量a,最多作业量b,和难度c. 1<=a<=b<=1e16 c<=100 1<=n<=m<=50 1<=k<=100 要求所有课程的作业量总和最多. 要求除第一天外,其他情况下作业量是前一天加k或者前一天乘k. 输出每天课程的序号,以及该课程应该布置的作业量. 思路: dp[i][j][k]代表第i门课,第j作业量,第k天的总和. 注意j是相对最少作业量的位移量. #inclu

题目链接 题意: 对于长度为$n$的排列,在已知一些位的前提下求逆序对的期望 思路: 将答案分为$3$部分 $1.$$-1$与$-1$之间对答案的贡献.由于逆序对考虑的是数字之间的大小关系,故假设$-1$的数量为$cnt$,可以等效成求长度为$cnt$的排列的逆序对期望.设$dp[i]$为长度为$i$的全排列的逆序对期望,有$dp[i]=dp[i-1]+$$\frac{i-1}{2}$,可以理解成在原$dp[i-1]$的基础上,数值$i$对每个长度为$i-1$的排列产生$\sum_{t=1}^{

Game with Strings 题意并不是在图上走,看了好久才看出来.. dp[ i ][ mask ]表示从 i 层开始走,起点有mask个, a的个数-b的个数的  最大值或者最小值. #include<bits/stdc++.h> #define LL long long #define LD long double #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL&g

大意: 给定序列, 每次操作可以任选一个数+1/-1, 求最少操作数使序列严格递增. 序列全-i后转化为求最少操作数使序列非降, 那么贪心可以知道最后$a_i$一定是修改为某一个$a_j$了, 暴力dp即可. #include <iostream> #include <cstdio> #define REP(i,a,n) for(int i=a;i<=n;++i) using namespace std; typedef long long ll; const int N =

大意: 给定序列$a,b$, 每次可以任取两个相同大小的$a_i,b_j$删除$a_i,b_j$左侧所有元素, 花费为e, 得分1, 最后结束时必须再花费之前删除元素的个数, 不得分. 初始能量$s$, 求最大得分方案. 这题关键是注意到$\frac{s}{e}$的范围比较小, 直接暴力dp即可.. #include <iostream> #include <algorithm> #include <cstdio> #include <math.h> #in

传送门 生成函数基础题. 题意:给出nnn个数以及它们的数量,求从所有数中选出i∣i∈[L,R]i|i\in[L,R]i∣i∈[L,R]个数来可能组成的集合的数量. 直接构造生成函数然后乘起来f(x)=∏i=1n(1+x+x2+...+xtimei)f(x)=\prod_{i=1}^n(1+x+x^2+...+x^{time_i})f(x)=∏i=1n​(1+x+x2+...+xtimei​)然后求出系数即可. 由于模数是1e61e61e6无法nttnttntt,考虑到数据很小可以直接用dpdp

大意: 总共$n$的时间, $k$个红包, 红包$i$只能在时间$[s_i,t_i]$范围内拿, 并且拿完后时间跳到$d_i+1$,Bob采用贪心策略,每个时间点若有红包能取则取钱数$w_i$最大的, $w_i$相同则取$d_i$最大的, Alice有$m$次机会让Bob跳过一个时间, 求Alice如何操作能使Bob得到钱数最少. 比较简单的DP, 记$dp[i][j]$为$i$时刻还能干扰$j$次的最小收益 $dp[i][j]=min(dp[d_i][j]+w_i,dp[i+1][j-1])$

大意: 给定一个m个bool变量的方程, 求方程解的个数 给定方程的形式类似于这样 每个括号是一个子式, 每个子式里变量数不超过2, 每个变量出现次数不超过2, 方程右侧一直是1 对每个变量出现的式子连边, 建好图后, 求出每个连通块内值为0或1的个数, 最后dp一下就能求出答案 考虑如何求每个连通块的答案, 因为每个点度数最多为2, 也就是说每个连通块只能为链或者简单环, 所以均可以dp求出 这题想法还是比较简单, 但具体实现还是不会了....以后还是要多练DP了

题意: 房间着火了,里面有n件物品,每件物品有营救需要的时间t,被烧坏的最晚时间d,他的价值p,问能得到的最大价值,并且输出营救出来的物品编号 代码: //必然是先救存活时间短的即d小的,所以先排个序,dp[i][j]表示枚举到第i件物品时救出他的时间是j时的最大价值,然后就 //是取还是不取这件物品的问题了他的状态是由dp[i-1][~]转移来的.另外这题需要记录取了哪些物品,用g[i][j]表示第i件 //物品在j时间取没取,用pre数组记录前驱.输出还要按照取得顺序输出. #include