目录
2023.6.11日模拟赛
T1
求\(n\)个碳原子的烷基的同分异构体个数,答案对 \(n\)取模,不考虑空间异构,能否稳定存在等.即求\(n\)个点，每个点度数小于等于\(3\)，且根节点度数小于等于\(4\) 的无标号有根树个数
比赛的时候手模到了\(n=6\)，由于太有自信，没看\(n=7\)
考虑常规做法\(dp[i]\)表示i个节点构成的树的种类，然后枚举子树的大小按照递增排序来去重
不难推出
\(dp[1]=1;dp[2]=1;dp[3]=2;\)
\(dp[4]=3;dp[5]=5;dp[6]=17;\)
当\(n=7\)时
枚举子树到\(3 3 0\)时，三的两种方案会算重，不能直接用乘法原理
那不如枚举一下重复的个数，由于还要保证子树方案单调不减，所以我们有了一个新的\(dp\)状态
\(dp[i][j][k]\)表示有\(i\)个节点,最大子树为\(j\),子树个数为\(k\)的方案数
回想设出状态的目的：第二维为了去掉子树全排列的重复情况，转移的时候第三维是为了方便转移
关于计算时的去重 分类讨论即可
\(k=3\)时，每个方案有op种，相当于在op个里面可重复的选3个
\(\dbinom{op+3-1}{3}\)
这里给出代码:
点击查看代码
dp[1][0]=1;
for(int j=1;j<n;j++){
int yg=(dp[j][0]+dp[j][1]+dp[j][2]+dp[j][3])%mod;
for(int i=n;i>j;i--){
for(int k=1;k<=3&&k<i;k++){
for(int l=1;l<=k&&l*j+k-l<i&&i-j*l<=j;l++){//
dp[i][k]=(dp[i][k]+lmy(yg,l)*dp[i-j*l][k-l])%mod;
}
}
}
}
T2
一个一维的扫雷游戏，每个格子用\(*\)表示有雷，用数字\(0,1,2\)表示无雷并且相邻格子中有\(0,1,2\)个雷，求方案数
直接dp
T3
已知两个数\(x,y\),求有多少个正整数不能被 \(a*x+b*y\)\((a>=0,b>=0)\)表示
当\(ax+by\equiv1\)有解时，数量有限，剩下的建议抽象理解
T4
在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字
二分枚举答案，将比答案大的变成1，比答案小的变成0，每次询问区间查询，修改即可
2023.6.12日模拟赛
T1
有 n类不同的武器，起义军想购买到所有的武器。去军火商购买时，每次只能买一把，并且买到的武器究竟是n 类武器中的哪一类是等概率的，概率均为1/n 。第 i次购买武器时需要支付 i 元钱。现在起义军手中没有武器，他们想知道自己得到所有种类的武器需要花费的钱数目的期望。
第一眼和OSU巨像，维护两个数组，两次dp，但是太久没做期望了看到就头疼所以跳了（基本忘干净）
设f[i]为当前有i个武器，买到第i个武器的期望次数
\(p=(n-i)/n;\)
\(f[i]=(1-p)*(f[i]+1)+p*(f[i+1]+1);\)
g[i]为当前有i个武器，买到第n个武器的期望花费
\(g[i]=(1-p)*(g[i]+f[i]+1)+p*(g[i+1]+f[i+1]+1);\)
T2
根据部队的归属的关系，可以看作一棵树，树根为 号部队，每个非叶子部队都有一个操作类型 max或 min
操作 max 表示：这个部队的战力等于与其相邻的子部队中所有战力的最大值。
操作 min 表示：这个部队的战力等于与其相邻的子部队中所有战力的最小值。
设树上有 k个叶子部队，你可以给每个叶子部队填上 [1,k] 的战力，并且每个数字只能使用一次，求根部队的最大战力。
对于所有max，关注子树中最大的数即可，所有的min,关注所有子树
设f[i]为i节点所需的最小数字个数
对于max f[i]=min(f[v])
对于min f[i]=f[i]+f[v];
对于叶子节点 f[i]=1;
树形dp即可
T3
起义军们会给定你一个矩形，你需要正确的回答出这个矩形中能给起义军们做的最大衣服的面积
懒得复制完整题目了
暴力就能过，vector存一下每一行的矩形的端点（我存的左下角）
坐标dp预处理矩形
可能我比别人快是因为类似写了一个hash，O(1)判断是否可行？
所以我找矩形的时间O(nm)
hash最初设的太小被卡了，后面发现n,m巨小，hasn值拉差增大就行了
T4
有一个大小为n 的包，有n种物品，其中第i种物品的大小为i，数量为 i个 ，装满这个背包的方案数是多少
分开处理,设tmp=sqrt(n)
i<=tmp 多重背包 f[2][100005];// 选择到的物体种类 容积 滚动了一下数组
转移很神：
f[i][j]=f[i-1][j]+f[i][j-i];
那么对于f[i][j-i]从f[i][j-2i]转移过来，转移到f[i][j-ii]个数限制，但f[i][j-i*i]还是被算了，所以要减掉
而对于j小一点的时候，是没有必要减的
i>tmp 完全背包
转移神
考虑如何构造出所有的由tmp+1~n组成的的序列
维护一个单调不减的序列
支持：队首加入tmp+1
所有元素+1
g[i][j]表示有i个物品，当前容量为j的方案数
所以转移方程:g[i][j]=g[i][j-i]+g[i-1][j-tmp-1];
这个也可以滚动数组
最后乘法原理计算答案就好
2023.6.12日模拟赛
T1
考试的时候发现a,b相差很小了，但是没发现a,b在n^(a-b)附近（裂开）
考虑枚举d=a-b,d<=20,每次在n^(d)周围计算，暴力check
对于一个d,最多只有d个a
T2
构造数列题
不合法情况直接判掉
剩下的如果n/k为偶数直接蛇形填就好
如果为奇数，考虑分成3+偶数，对于3
第一列顺着填下来，第二列从中间位置开始填，填完在转上去
第三列直接算就行
学到了一个新东西
\(vector<int>().swap(v);\)
这玩意能清空数组并回收内存……
T3
依旧很神
将所有操作离线下来，将更改操作分成两部分,在\(l\)处\(+val\),\(r+1\)处\(-val\),按照坐标排序
这样扫描到x可以保证所有对x有影响的一定处理过了，对x没有影响的已经撤销了操作
相当于处理了一次区间操作
在考虑第二个限制，时间（或者说是答案）
用一个树状数组存每个时间所带来的贡献，因为上面说了，所以实际上count(当前操作的时间)就是沙子的高度
然后就可以二分查询
排序和差分起到了一个数据结构的作用，很神，虽然以前见过，但考试的时候还是没想出来
T4
很神，式子并不是很难推，这里不写了，我在电脑上写公式巨慢……
但是有几个思想：
先算出f[i]表示没坏的流量，用f[i]去计算每种坏了的情况所造成的影响来初始化g[i]
由于每次只能坏一个管道，所以管道坏时，对u流量没有影响，对于u的儿子们有影响，因为只有一个管道，所以所有的情况都是独立存在的，但是转移都一样
如果每次修改，时间太大，所以我们将造成的影响压缩到u里，在第二次DFS时下放影响，但是坏了的地方会多加，所以坏了的地方提前减掉就行了
推出来u加上的刚好为v减少的，初始化g就行了
总结：确实受益匪浅，比学知识点的印象要深……
我数学是真拉